have been no conflicting updates to the locations read, and
then writing-back the updates to the TVars that have been
modified.
However, the retry and orElse abstractions led us to
think more carefully about how to integrate blocking operations with this general approach. Following Harris and
Fraser’s work8 we built retry by using a transaction’s log
to identify the TVars that it has read and then adding “trip
wires” to those TVars before blocking: subsequent updates
to any of those TVars will unblock the thread.
The orElse and catch constructs are both implemented
using closed nested transactions17 so that the updates made
by the enclosed work can be rolled back without discarding
the outer transaction. There is one subtlety that we did not
appreciate in our original paper: if the enclosed transaction
is rolled back then the log of locations it has read must be retained by the parent. In retrospect the reason is clear—the
decision of whether or not to roll back must be validated at
the same atomic point as the outer transaction.
5. 1. Progress
The STM implementation guarantees that one transaction
can force another to abort only when the first one commits.
As a result, the STM implementation is lock-free in the sense
that it guarantees at any time that some running transaction can successfully commit. For example, no deadlock
will occur if one transaction reads and writes to TVar x
and then TVar y, while a second reads and writes to those
TVars in the opposite order. Each transaction will observe
the original value of those TVars; the first to validate will
commit, and the second will abort and restart. Similarly,
synchronization conflicts over TVars cannot cause cyclic
restart, where two or more transactions repeatedly abort
one another.
Starvation is possible, however. For example, a transaction
that runs for a very long time may repeatedly be aborted by
shorter transactions that conflict with it. We think that starvation is unlikely to occur in practice, but we cannot tell without further experience. A transaction may also never commit
if it is waiting for a condition that never becomes true.
6. ReLateD WoRK
Transactions have long been used for fault tolerance in
databases7 and distributed systems. These transactions
rely on stable storage and distributed commit protocols
to protect system integrity against crashes and communication failures. Transactional memory of the kind we
are studying provides access to memory within a single
process; it is not intended to survive crashes, so there is
no need for distributed commit protocols or stable storage. It follows that many design and implementation
issues are quite different from those arising in distributed
or persistence-only transaction systems. TM was originally proposed as a hardware architecture12, 24 to support
nonblocking synchronization, and architectural support
for this model remains the subject of ongoing research,
as does the construction of efficient implementations
in software. Larus and Rajwar provide a recent survey of
implementation techniques. 14
Transactional composition requires the ability to run
transactions of arbitrary size and duration, presenting a
challenge to hardware-based transactional memory designs,
which are inherently resource-limited. One way for hardware to support large transactions is by virtualization, 4, 22
providing transparent overflow mechanisms. Another way is
by hybrid STM designs5, 13 that combine both hardware and
software mechanisms.
After our original paper, Carlstrom et al. examined a form
of retry that watches for updates to a specified set of locations, 3 arguing that this is easier to support in hardware and
may be more efficient than our form of retry. However,
unless the watch set is defined carefully, this sacrifices the
composability that retry provides because updates to non-watched locations may change the control flow within the
transaction.
Our original paper also discusses related programming
abstractions for concurrency, notably Concurrent ML’s
composable events and Scheme48’s proposals.
7. concLusion
In this paper we have introduced the ideas from STM-Haskell for composable memory transactions, providing
a substrate for concurrent programming that offers far
richer composition than has been available to date: two
atomic actions can be glued together in sequence with
the guarantee that the result will run atomically, and two
atomic actions can be glued together as alternatives with
the guarantee that exactly one of them will run. In subsequent work we have further enhanced the STM interface
with invariants. 10
We have used Haskell as a particularly suitable laboratory
to explore these ideas and their implementation. An obvious question is this: to what extent can our results be carried back into the mainstream world of imperative programming? This is a question that we and many others have been
investigating since our original paper. The ideas of composable blocking through retry and orElse seem straightforward to apply in other settings—subject, of course, to support for blocking and wake-up within the lower levels of the
systems.
A more subtle question is the way in which our separation between transacted state and nontransacted state can
be applied, or our separation between transacted code and
nontransacted code. In Haskell, mutable state and impure
code are expected to be the exception rather than the norm,
and so it seems reasonable to distinguish the small amount
of impure transacted code from the small amount of impure
nontransacted code; both, in any case, can call into pure
functions.
In contrast, in mainstream languages, most code is written in an impure style using mutable state. This creates a tension: statically separating transacted code and data retains
the strong guarantees of STM-Haskell (no irrevocable calls
to “launchMissiles” within a transaction, and no direct
access to transacted state without going through the STM
interface), but it requires source code duplication to create transacted variants of library functions and marshaling
between transacted data formats and normal data formats.