Beautiful Code [270]
good :: Account -> IO ( )
good acc = do { hPutStr stdout "Withdrawing..."
; atomically (withdraw acc 10) }
24.2.3. Implementing Transactional Memory
The guarantees of atomicity and isolation that I described earlier should be all that a programmer needs in order to use STM. Even so, I often find it helpful to have a reasonable implementation model to guide my intuitions, and I will sketch one such implementation in this section. But remember that this is just one possible implementation. One of the beauties of the STM abstraction is that it presents a small, clean interface that can be implemented in a variety of ways, some simple and some sophisticated.
One particularly attractive implementation is well established in the database world, namely optimistic execution. When atomically act is performed, a thread-local transaction log is allocated, initially empty. Then the action act is performed, without taking any locks at all. While performing act, each call to writeTVar writes the address of the TVar and its new value into the log; it does not write to the TVar itself. Each call to readTVar first searches the log (in case the TVar was written by an earlier call to writeTVar); if no such record is found, the value is read from the TVar itself, and the TVar and value read are recorded in the log. In the meantime, other threads might be running their own atomic blocks, reading and writing TVars like crazy.
When the action act is finished, the implementation first validates the log and, if validation is successful, commits the log. The validation step examines each readTVar recorded in the log and checks that the value in the log matches the value currently in the real TVar. If so, validation succeeds, and the commit step takes all the writes recorded in the log and writes them into the real TVars.
These steps are performed truly indivisibly: the implementation disables interrupts, or uses locks or compare-and-swap instructions—whatever is necessary to ensure that validation and commit are perceived by other threads as completely indivisible. All of this is handled by the implementation, however, and the programmer does not need to know or care how it is done.
What if validation fails? Then the transaction has had an inconsistent view of memory. So, we abort the transaction, reinitialize the log, and run act all over again. This process is called re-execution. Because none of act's writes have been committed to memory, it is perfectly safe to run it again. However, notice that it is crucial that act contains no effects other than reads and writes on TVars. For example, consider:
atomically (do { x <- readTVar xv
; y <- readTVar yv
; if x>y then launchMissiles
else return () })
where launchMissiles::IO ( ) causes serious international side effects. Because the atomic block is executed without taking locks, it might have an inconsistent view of memory if other threads are concurrently modifying xv and yv. If that happens, it would be a mistake to launch the missiles, and only then discover that validation fails so the transaction should be rerun. Fortunately, the type system prevents us from running IO actions inside STM actions, so the above fragment would be rejected by the type checker. This is another big advantage of distinguishing the types of IO and STM actions.
24.2.4. Blocking and Choice
Atomic blocks as we have introduced them so far are utterly inadequate to coordinate concurrent programs. They lack two key facilities: blocking and choice. In this section, I'll describe how the basic STM interface is elaborated to include them in a fully modular way.
Suppose that a thread should block if it attempts to overdraw an account (i.e., withdraw more than the current balance). Situations like this are common in concurrent programs: for example, a thread should block if it reads from an empty buffer,