Doi: 10.1145/1378704.1378725
Composable Memory Transactions
By Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy
abstract
Writing concurrent programs is notoriously difficult and
is of increasing practical importance. A particular source
of concern is that even correctly implemented concurrency
abstractions cannot be composed together to form larger
abstractions. In this paper we present a concurrency model,
based on transactional memory, that offers far richer composition. All the usual benefits of transactional memory are
present (e.g., freedom from low-level deadlock), but in addition we describe modular forms of blocking and choice that
were inaccessible in earlier work.
1. intRoDuction
The free lunch is over. 25 We have been used to the idea that
our programs will go faster when we buy a next-generation
processor, but that time has passed. While that next-generation chip will have more CPUs, each individual CPU
will be no faster than the previous year’s model. If we want
our programs to run faster, we must learn to write parallel
programs.
Writing parallel programs is notoriously tricky. Mainstream lock-based abstractions are difficult to use and they
make it hard to design computer systems that are reliable
and scalable. Furthermore, systems built using locks are difficult to compose without knowing about their internals.
To address some of these difficulties, several researchers (including ourselves) have proposed building programming language features over software transactional memory
(STM), which can perform groups of memory operations
atomically. 23 Using transactional memory instead of locks
brings well-known advantages: freedom from deadlock and
priority inversion, automatic roll-back on exceptions or tim-eouts, and freedom from the tension between lock granularity and concurrency.
Early work on software transactional memory suffered
several shortcomings. Firstly, it did not prevent transactional
code from bypassing the STM interface and accessing data
directly at the same time as it is being accessed within a transaction. Such conflicts can go undetected and prevent transactions executing atomically. Furthermore, early STM systems
did not provide a convincing story for building operations
that may block—for example, a shared work-queue supporting operations that wait if the queue becomes empty.
Our work on STM-Haskell set out to address these problems. In particular, our original paper makes the following
contributions:
• We re-express the ideas of transactional memory in the
setting of the purely functional language Haskell
(Section 3). As we show, STM can be expressed particularly elegantly in a declarative language, and we are able
to use Haskell’s type system to give far stronger guaran-
tees than are conventionally possible. In particular, we
guarantee “strong atomicity” 15 in which transactions
always appear to execute atomically, no matter what
the rest of the program is doing. Furthermore transactions are compositional: small transactions can be
glued together to form larger transactions.
• We present a modular form of blocking (Section 3. 2).
The idea is simple: a transaction calls a retry operation to signal that it is not yet ready to run (e.g., it is trying to take data from an empty queue). The programmer
does not have to identify the condition which will
enable it; this is detected automatically by the STM.
• Theretry function allows possibly blocking transactions to be composed in sequence. Beyond this, we also
provide orElse, which allows them to be composed as
alternatives, so that the second is run if the first retries
(see Section 3. 4). This ability allows threads to wait for
many things at once, like the Unix select system
call—except that orElse composes, whereas select
does not.
Everything we describe is fully implemented in the Glasgow Haskell Compiler (GHC), a fully fledged optimizing
compiler for Concurrent Haskell; the STM enhancements
were incorporated in the GHC 6. 4 release in 2005. Further
examples and a programmer-oriented tutorial are also
available. 19
Our main war cry is compositionality: a programmer can
control atomicity and blocking behavior in a modular way
that respects abstraction barriers. In contrast, lock-based
approaches lead to a direct conflict between abstraction and
concurrency (see Section 2). Taken together, these ideas offer
a qualitative improvement in language support for modular
concurrency, similar to the improvement in moving from assembly code to a high-level language. Just as with assembly
code, a programmer with sufficient time and skills may obtain better performance programming directly with low-level
concurrency control mechanisms rather than transactions—
but for all but the most demanding applications, our higher-level STM abstractions perform quite well enough.
This paper is an abbreviated and polished version of an
earlier paper with the same title. 9 Since then there has been
a tremendous amount of activity on various aspects of transactional memory, but almost all of it deals with the question
of atomic memory update, while much less attention is paid
to our central concerns of blocking and synchronization between threads, exemplified by retry and orElse. In our
view this is a serious omission: locks without condition variables would be of limited use.
Transactional memory has tricky semantics, and the
original paper gives a precise, formal semantics for transactions, as well as a description of our implementation. Both
are omitted here due to space limitations.