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 work⁸ 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 transactions¹⁷ 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 databases⁷ 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 architecture^{12, 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. ¹⁴

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 designs^{5, 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, ³ 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. ¹⁰

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.