transactions. In other words, although
the code in a transaction may modify
individual variables through a series
of assignments, another computation
can only observe the program state
immediately before or immediately after the transaction executes. Isolation
ensures that concurrently executing
tasks cannot affect the result of a transaction, so a transaction produces the
same answer as when no other task was
executing. Transactions provide a basis to construct parallel abstractions,
which are building blocks that can be
combined without knowledge of their
internal details, much as procedures
and objects provide composable abstractions for sequential code.
TM Programming Model. A programming model provides a rationale
for the design of programming language constructs and guidance on how
to construct programs. Like many aspects of TM, its programming model is
still the subject of active investigation.
Most TM systems provide simple
atomic statements that execute a block
of code (and the routines it invokes) as
a transaction. An atomic block isolates
the code from concurrently executed
threads, but a block is not a replacement for general synchronization
such as semaphores or condition variables. 2 In particular, atomic blocks by
themselves do not provide a means to
coordinate code running on parallel
threads.
Automatic mutual exclusion (AME),
by contrast, turns the transactional
model “inside-out” by executing most
of a program in transactions. 15 AME
supports asynchronous programming, in which a function starts one
or more asynchronous computations
and later rendezvouses to retrieve
their results. This programming model is a common way to deal with unpredictable latency in user-directed
and distributed systems. The atomicity provided by transactions ensures
that an asynchronous computation,
which executes at an unpredictable
rate, does not interfere with other, simultaneously active computations.
Advantages of Transactional Memory. Parallel programming poses many
difficulties, but one of the most serious
challenges in writing correct code is
coordinating access to data shared by
several threads. Data races, deadlocks,
and poor scalability are consequences
of trying to ensure mutual exclusion
with too little or too much synchronization. TM offers a simpler alternative
to mutual exclusion by shifting the burden of correct synchronization from
a programmer to the TM system. 9 In
theory, a program’s author only needs
to identify a sequence of operations on
shared data that should appear to execute atomically to other, concurrent
threads. Through the many mechanisms discussed here, the TM system
then ensures this outcome.
Harris and Peyton-Jones11 argued
that, beyond providing a better programming abstraction, transactions
also make synchronization composable, which enables the construction
of concurrency programming abstractions. A programming abstraction is
composable if it can be correctly combined with other abstractions without
needing to understand how the abstractions operate.
Simple locking is not composable.
Consider, as an example, a class that
implements a collection of bank accounts. The class provides thread-safe
Deposit and Withdraw operations
to add and remove money from a bank
account. Suppose that we want to compose these operations into a thread-safe Transfer operation, which
moves money from one account to another. The intermediate state, in which
money was debited but not credited,
should not be visible to other threads
(that is, the transfer should be atomic).
Since Deposit and Withdraw lock an
account only during their operation,
properly implementing Transfer requires understanding and modifying
the class’s locking discipline by adding
a method to either lock all accounts
or lock a single account. The latter approach allows non-overlapping transfers to execute concurrently, but introduces the possibility of deadlock if a
transfer from account A to B overlaps
with a transfer from B to A.
TM allows the operations to be composed directly. The Deposit and Withdraw operations each execute in a transaction, to protect their manipulations
of the underlying data. The Transfer
operation also executes in a transaction,
which subsumes the underlying operations into a single atomic action.
Limitations of Transactional Memory. Transactions by themselves cannot
replace all synchronization in a parallel
program. 2 Beyond mutual exclusion,
synchronization is often used to coordinate independent tasks, for example,
by ensuring that one task waits for another to finish or by limiting the number of threads performing a task.
Transactions by themselves provide
little assistance in coordinating independent tasks. For example, consider
a producer-consumer programming
relationship, in which one task writes
a value that another task reads. Transactions can ensure the tasks’ shared
accesses do not interfere. However,
this pattern is expensive to implement with transactions, whose goal is
to shield a task from interactions with
other tasks. If the consumer transaction finds the value is not available, it
can only abort and check for the value
later. Busy waiting by aborting is inefficient since an aborted transaction
rolls back its entire computation. A
better solution is for the producer to
signal the consumer when the value
is ready. However, since a signal is
not visible in a transaction, many TM
systems provide a guard that prevents
a transaction from starting execution
until a predicate becomes true.
Haskell TM introduced the retry
and orElse constructs as a way for a
transaction to wait until an event occurs and to sequence the execution of
two transactions. 11 Executing a retry statement causes the surrounding transaction to abort. It does not
reexecute until a location it previously