Beautiful Code [30]
[] This turn of phrase is due to Tony Hoare.
In this chapter, I'll describe Software Transactional Memory (STM), a promising new approach to programming shared-memory parallel processors that seems to support modular programs in a way that current technology does not. By the time we are done, I hope you will be as enthusiastic as I am about STM. It is not a solution to every problem, but it is a beautiful and inspiring attack on the daunting ramparts of concurrency.
24.1. A Simple Example: Bank Accounts
Here is a simple programming task.
Write a procedure to transfer money from one bank account to another. To keep things simple, both accounts are held in memory: no interaction with databases is required. The procedure must operate correctly in a concurrent program, in which many threads may call transfer simultaneously. No thread should be able to observe a state in which the money has left one account, but not arrived in the other (or vice versa).
This example is somewhat unrealistic, but its simplicity allows us to focus in this chapter on what is new about the solution: the language Haskell and transactional memory. But first let us briefly look at the conventional approach.
24.1.1. Bank Accounts Using Locks
The dominant technologies used for coordinating concurrent programs today are locks and condition variables. In an object-oriented language, every object has an implicit lock, and the locking is done by synchronized methods, but the idea is the same. So, one might define a class for bank accounts something like this:
class Account {
Int balance;
synchronized void withdraw( Int n ) {
balance = balance - n; }
void deposit( Int n ) {
withdraw( -n ); }
}
We must be careful to use a synchronized method for withdraw, so that we do not get any missed decrements if two threads call withdraw at the same time. The effect of synchronized is to take a lock on the account, run withdraw, and then release the lock.
Now, here is how we might write the code for transfer:
void transfer( Account from, Account to, Int amount ) {
from.withdraw( amount );
to.deposit( amount ); }
This code is fine for a sequential program, but in a concurrent program, another thread could observe an intermediate state in which the money has left account from but has not arrived in to. The fact that both methods are synchronized does not help us at all. Account from is first locked and then unlocked by the call to method withdraw, and then to is locked and unlocked by deposit. In between the two calls, the money is (visibly) absent from both accounts.
In a finance program, that might be unacceptable. How do we fix it? The usual solution would be to add explicit locking code like so:
void transfer( Account from, Account to, Int amount ) {
from.lock(); to.lock();
from.withdraw( amount );
to.deposit( amount );
from.unlock(); to.unlock() }
But this program is fatally prone to deadlock. In particular, consider the (unlikely) situation in which another thread is transferring money in the opposite direction between the same two accounts. Then each thread might get one lock and then block indefinitely waiting for the other.
Once recognized—and the problem is not always so obvious—the standard fix is to put an arbitrary global order on the locks, and to acquire them in increasing order. The locking code would then become:
if from < to
then { from.lock(); to.lock(); }
else { to.lock(); from.lock(); }
That works fine when the full set of required locks can be predicted in advance, but that is not always the case. For example, suppose from.withdraw is implemented by transferring money out of the from2 account if from does not have enough funds. We don't know whether to acquire from2's lock until we have read from, and by then it is too late to acquire the locks in the "right" order. Furthermore, the very existence of from2 may be a private matter that should be known by from, but not by transfer. And even if transfer did know about from2, the locking