Beautiful Code [266]
24.1.2. Locks Are Bad
To make a long story short, today's dominant technology for concurrent programming—locks and condition variables—is fundamentally flawed. Here are some standard difficulties, some of which we have just seen:
Taking too few locks
It is easy to forget to take a lock and thereby end up with two threads that modify the same variable simultaneously.
Taking too many locks
It is easy to take too many locks and thereby inhibit concurrency (at best) or cause deadlock (at worst).
Taking the wrong locks
In lock-based programming, the connection between a lock and the data it protects often exists only in the mind of the programmer and is not explicit in the program. As a result, it is all too easy to take or hold the wrong locks.
Taking locks in the wrong order
In lock-based programming, one must be careful to take locks in the "right" order. Avoiding the deadlock that can otherwise occur is always tiresome and error-prone, and sometimes extremely difficult.
Error recovery
Error recovery can be very hard because the programmer must guarantee that no error can leave the system in a state that is inconsistent, or in which locks are held indefinitely.
Lost wakeups and erroneous retries
It is easy to forget to signal a condition variable on which a thread is waiting, or to retest a condition after a wakeup.
But the fundamental shortcoming of lock-based programming is that locks and condition variables do not support modular programming. By "modular programming," I mean the process of building large programs by gluing together smaller programs. Locks make this impossible. For example, we could not use our (correct) implementations of withdraw and deposit unchanged to implement transfer; instead, we had to expose the locking protocol. Blocking and choice are even less modular. For example, suppose we had a version of withdraw that blocked if the source account had insufficient funds. Then we would not be able to use withdraw directly to withdraw money from A or B (depending on which had sufficient funds), without exposing the blocking condition—and even then it wouldn't be easy. This critique is elaborated elsewhere.[§]
[§] Edward A. Lee, "The problem with threads,"IEEE Computer, Vol. 39, No. 5, pp. 33–42, May 2006; J. K. Ousterhout, "Why threads are a bad idea (for most purposes)," Invited Talk, USENIX Technical Conference, January 1996; Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy, "Composable memory transactions," ACM Symposium on Principles and Practice of Parallel Programming (PPoPP '05), June 2005.
Beautiful Concurrency > Software Transactional Memory
24.2. Software Transactional Memory
Software Transactional Memory is a promising new approach to the challenge of concurrency, as I will explain in this section. I shall explain STM using Haskell, the most beautiful programming language I know, because STM fits into Haskell particularly elegantly. If you don't know any Haskell, don't worry; we'll learn it as we go.
24.2.1. Side Effects and Input/Output in Haskell
Here is the beginning of the code for transfer in Haskell:
transfer :: Account -> Account -> Int -> IO ( )
-- Transfer 'amount' from account 'from' to account 'to'
transfer from to amount = ...
The second line of this definition, starting with --, is a comment. The first line gives the type signature for transfer.[||] This signature says that transfer takes as its arguments two values of type Account (the source and destination accounts) and an Int (the amount to transfer), and returns a value of type IO ( ). This result type says, "transfer returns an action that, when performed, may have some side effects, and then returns a value of type ( )." The type ( ), pronounced "unit," has just one value, which is also written ( ); it is akin to void in C. So, transfer's result type IO ( ) announces that its side effects constitute the only reason for calling it. Before we go further, we must explain how side effects