Last Tech Tuesday, we learned about atomic actions as a way of dealing with the problems arising from concurrency. I ended that post by pointing to the limits of atomic actions – most notably that the operating system and/or database system cannot provide arbitrarily complex atomic actions as it cannot possibly anticipate all the needs of different programs. At the time I also raised the question as to how atomic actions can be provided in the first place!

Let’s start with the second question. One answer is that this is very easy to do if the hardware is able to guarantee that a set of instructions or potentially a single instruction can complete without any interference from other concurrently executing programs. As it turns out, very little is needed from the hardware in order to build more complex ways of managing concurrency in software. For instance, the ability to check and change the value of a memory location in one go would be enough. As it turns out with some fancy footwork such as Dekker’s algorithm it is also possible to achieve a similar result using software only without any explicit hardware support. 

Once we have a primitive atomic action or mutual exclusion capability we can use that to build up more complicated ways of managing concurrency. For instance, a so-called counting semaphore can be used to let a pre-defined number of programs (but no more) access a resource concurrently. Or we can use it to acquire a write lock on a row in a database, which we can then update without interference from any concurrently executing programs. The idea behind all of these mechanism is essentially the same: limit access to prevent conflict. Unlike an atomic action that means that arbitrarily complex sequences of activity can be carried out before another program is given access.

So let’s go back to our ATM problem from before and see how we can now solve it. Here is some example pseudo code

The call to lock() will block program execution until it has acquired the lock on the account. It guarantees that only on program can acquire a lock at any one time. There goes our chance of getting rich by lining up thousands of simultaneous withdrawals at different ATM machines!

Does that mean all is fine? And if so, why would anybody want to just use atomic actions instead? As it turns out having more powerful capabilities for managing concurrency gives us opportunities to mess things up in other ways (as in “with great power comes great responsibility”). Here is just one quick example – the potential for two programs to deadlock. Consider the following naive implementation for transferring money between two accounts:

Imagine now that I try to send money to Susan at the same time as she is trying to send money to me. Two transfer programs start to execute concurrently and for one of them account1 is my account and for the other account1 is Susan’s account. So each program manages to acquire the first lock. Let’s assume each of us has enough money in the account to make the transfer so that we get inside the conditional. Well, now the program trying to execute my transfer wants a lock for account2 which is Susan’s account but that’s already held by the program trying to execute Susan’s transfer to me. And vice versa. Since locks block, neither program can continue to execute. That also means that neither of the initial locks will ever be released and the two programs will remain suspended forever. Any subsequent programs that need access to our accounts would also be stuck. In fact until the processes are forced to terminate both accounts would be inaccessible.

As so often in software, by solving one problem (the limited capabilities of atomic actions) we have introduced another (deadlock) that is potentially much more severe! Next Tuesday I will wrap up this little mini series about concurrency with a brief look at asynchronous programming with non-blocking algorithms.