read changes value, which avoids
the crudest form of busy waiting in
which a transaction repeatedly reads
an unchanging value and aborts. The
orElse construct composes two
transactions by starting the second
one only if the first transaction fails to
commit. This pattern—which arises
in situations as simple as checking for
a value in a cache and recomputing
it if necessary—is difficult to express
otherwise, since a transaction’s failure and reexecution is transparent to
other computation.
We still do not understand the
trade-offs and programming pragmatics of the TM programming model.
For example, the semantics of nested
transactions is an area of active debate.
Suppose that code in a transaction O
invokes a library routine, which starts
its own transaction I. Should the two
transactions interact in any way, and
if so, what are the implications for the
TM implementation and for programmers building modular software and
libraries? Consider when transaction
I commits. Should its results be visible
only to code in transaction O (closed
nesting) or also to other threads (open
nesting)? If the latter, what happens
if transaction O aborts? Similarly, if
transaction I aborts, should it terminate transaction O as well, or should
the inner transaction be rolled back
and restarted independently?
ILLUS TRATION BY STUDIO TONNE / ZEEGENRUSH.COM
Finally, the performance of TM is
not yet good enough for widespread
use. Software TM systems (STM) impose considerable overhead costs on
code running in a transaction, which
saps the performance advantages of
parallel computers. Hardware TM systems (HTM) can lower the overhead,
but they are only starting to become
commercially available, and most
HTM systems fall back on software for
large transactions. Better implementation techniques are likely to improve
both types of systems and are an area
of active research.
transactional memory
implementation
TM can be implemented entirely in
software (STM) or with specialized
hardware support (HTM). Many different implementation techniques have
been proposed, and this paper, rather
than surveying the literature, focuses
review articles
on a few key techniques. A more complete overview is available elsewhere. 18
Most TM systems of both types implement optimistic concurrency control in which a transaction executes
under the assumption that it will not
conflict with another transaction. If
two transactions conflict, because one
modifies a location read or modified
by the other, the TM system aborts
one of the transactions by reversing
(rolling back) its side effects. The alternative pessimistic concurrency
control requires a transaction to establish exclusive access to a location
(for example, by acquiring a lock) before modifying it. This approach also
may abort and roll back a transaction,
in case of deadlock.
Software Transactional Memory.
The initial paper on STM by Shavit and
Touitou29 showed it was possible to
implement lock-free, atomic, multi-lo-cation operations entirely in software,
but it required a program to declare in
advance the memory locations to be accessed by a transaction.
Herlihy et al.’s Dynamic STM
(DSTM) 14 was the first STM system that
did not require a program to declare
the memory locations accessed by a
transaction. DSTM is an object-gran-ularity, deferred-update STM system,
which means that a transaction modifies a private copy of an object and
only makes its changes visible to other
transactions when it commits. The
transaction exclusively accesses the
copy without synchronization. However, another transaction can access the
original, underlying object while the
first transaction is still running, which
causes a logical conflict that the STM
system detects and resolves by aborting one of the two transactions.
An STM system can detect a conflict when a transaction first accesses
an object (early detection) or when the
transaction attempts to commit (late
detection). Both approaches yield the
same results, but may perform differently and, unfortunately, neither is
consistently superior. Early detection
prevents a transaction from performing unnecessary computation that a
subsequent abort will discard. Late detection can avoid unnecessary aborts,
as when the conflicting transaction itself aborts because of a conflict with a
third transaction.
Another complication is a conflict
between a transaction that only reads
an object and another that modifies
the object. Since reads are more common than writes, STM systems only
clone objects that are modified. To
reduce overhead, a transaction tracks
the objects it reads and, before it commits, ensures that no other transaction
modified them.
DSTM is a library. An object manipulated in a transaction is first registered with the DSTM system, which
returns a TMObject wrapper for the
object (as illustrated in the accompanying figure). Subsequently, the code
executing the transaction can open
the TMObject for read-only or read-write access, which returns a pointer
to the original or cloned object, respectively. Either way, the transaction
manipulates the object directly, without further synchronization.
A transaction ends when the program attempts to commit the transaction’s changes. If the transaction successfully commits, the DSTM system
atomically replaces, for all modified
objects, the old object in a Locator
structure with its modified version.
A transaction T can commit successfully if it meets two conditions. The
first is that no concurrently executing
transaction modified an object read by
T. DSTM tracks the objects a transaction opened for reading and validates
the entries in this read set when the
transaction attempts to commit. An
object in the read set is valid if its version is unchanged since transaction