T first opened it. DSTM also validates
the read set every time it opens an object, to avoid allowing a transaction to
continue executing in an erroneous
program state in which some objects
changed after the transaction started
execution.
The second condition is that transaction T is not modifying an object
that another transaction is also modifying. DSTM prevents this type of conflict by only allowing one transaction
to open an object for modification.
When a write-write conflict occurs,
DSTM aborts one of the two conflicting
transactions and allows the other to
proceed. DSTM rolls the aborted transaction back to its initial state and then
allow it to reexecute. The policy used to
select which transaction to abort can
affect system performance, including
liveness, but it should have no effect on
the semantics of the STM system. 28
The performance of DSTM, like
other STM systems, depends on the
details of the workload. In general,
the large overheads of STM systems
are more expensive than locking on a
small number of processors. However,
as the number of processors increases,
so does the contention for a lock and
the cost of locking. When this occurs
and conflicts are rare, STMs have been
shown to outperform locks on small
benchmarks.
Deferred-Update Systems. Other
deferred-update STM systems investigated alternative implementation
a transacted object in the DStm system.
Locator
TMobject
techniques. Harris and Fraser’s WSTM
system detects conflicts at word, not
object, granularity. This approach
can avoid unnecessary conflicts if two
transactions access different fields in
an object, but it complicates the implementation sufficiently that few STM
systems adopted the idea (although,
HTM systems generally detect conflicts at word or cache line granularity).
WSTM also was the first STM system integrated into a programming language.
Harris and Fraser extended Java with
an atomic statement that executed its
block in a transaction, for example:
atomic {
int x = lst.head;
lst = lst.tail;
…
}
The construct also provided an optional guard that prevents a transaction from executing until the condition
becomes true.
Considerable research has investigated the policies that select which
transaction to abort at a conflict. 10, 28
No one policy performs best in all situations, though a policy called “Polka”
performed well overall. Under this policy, each transaction tracks the number of objects it has open and uses
this count as its priority. A transaction
attempting to acquire access to an object immediately aborts a conflicting,
lower-priority transaction. If the ac-
status
quiring transaction’s priority is lower,
it backs off N times, where N is the difference in priority, with an exponentially increasing interval between the
retries. The transaction aborts and reexecutes if it cannot acquire an object
within N attempts.
Direct Update Systems. In a direct-update STM system, transactions directly modify an object, rather than a
copy. 1, 12, 27 Eliminating the copy potentially is more efficient, since it does
not require a clone of each modified
object. However, direct-update systems must record the original value
of each modified memory location,
so the system can restore the location
if the transaction aborts. In addition,
a direct update STM must prevent a
transaction from reading the locations modified by other, uncommitted
transactions, thereby reducing the potential for concurrent execution.
Direct update STM systems also require a lock to prevent multiple transactions from updating an object concurrently. Because of the high cost of
fair multiple reader-single writer locks,
the systems do not lock a read-only object and instead rely on read-set validation to detect concurrent modification
of read-only objects. These lock sets incur the same high overhead cost as in
deferred-update systems.
The locks used to prevent multiple
writes to a location, however, raise the
possibility of stalling many transactions when a transaction is suspended
or descheduled while holding locks.
Deferred-update STM systems typically use non-blocking data structures,
which prevented a failed thread from
obstructing other threads. Direct-update STM systems provide similar forward progress guarantees to an application by detecting and aborting failed
or blocked threads.
Transaction
new Data
old Data
object — new version
object — old version
tmobject is a handle for the object. it points to a Locator, which in turn points to
the transaction that opened the object, the original (“old) version of the object, and
the transaction’s private (“new”) clone of the object.
hardware Support for
transactional memory
The programming effort necessary to
exploit parallelism is justified if the
new code performs better or is more
responsive than sequential code. Even
though the performance of recent
STM systems scales with the number
of processors in a Multicore chip, the
overhead of the software systems is
significant. Even with compiler optimizations, a STM thread may run two