Solving deadlocks with globally-defined lock orderings

There are different ways to either minimize the likelihood of deadlocking or else just avoid it altogether. One best practice is to minimize the scope of your critical sections so as to decrease the time that threads hang onto locks, and hence to decrease the likelihood of a deadlock. That however doesn't solve the issue; deadlocks can still occur.

Another technique is to avoid the sort of nested locking that we saw in the example in the previous page. Instead of locking each account individually, we might define a single lock that any thread must acquire before doing a transfer. While this does indeed eliminate deadlocks, it does so at a very steep cost: acquiring the single lock becomes a bottleneck, and limits the parallelism we're trying to achieve in the first place. It does not scale.

A third technique is to use timeouts. Under this approach, if any thread is blocked for a sufficiently lengthy period of time, it just gives up.

Those are all legitimate techniques, but in this section we'll discuss global lock orders.

What is a globally-defined lock order?

Recall in our discussion of deadlocks that they arise from circular dependencies between the threads. Any given thread depends on a resource (a lock) that the previous thread in the ring holds. So one way to stamp out deadlocks is to define a global ordering on the locks so that such cycles can never arise. In other words, you define and publish rules around which locks to acquire before which other locks. This approach requires significant discipline from developers since there isn't any automatic way to enforce it. It is however extremely useful since it makes deadlocks impossible.

Let's see how we might apply a global lock order to the funds transfer example.

The funds transfer example reconsidered

At first glance you might think, "Wait a minute. The source account's lock is always grabbed before the destination account's lock, so how is it possible for a deadlock to occur?" But upon closer examination it's clear that that's not a correct analysis. Whatever global lock order we define needs to translate ultimately down to instances, not roles in a transaction. Sometimes account 4 will be the source account, and sometimes it will be the destination account. Similarly for account 14. Whatever global lock order we define needs to handle that.

One straightforward way to define a lock order for our current example would be to say that we always grab the lock for the account with the lower ID first. Listing 4 shows the new code:

public void transferFunds(Account from, Account to, Money amount) {
	long fromId = from.getId();
	long toId = to.getId();
	long lowId = (fromId < toId ? fromId : toId);
	long highId = (fromId < toId ? toId : fromId);
	synchronized (lowId) {
		synchronized (highId) {
			from.decreaseBy(amount);
			to.increaseBy(amount);
		}
	}
}

The code above is deadlock-free, because cyclic dependencies are impossible. Say thread T₁ wants to transfer funds from account 4 to account 14, and thread T₂ wants to transfer funds from account 14 to account 4. Both threads will try to grab the lock for account 4 before trying to grab the lock for account 14. Thus it's impossible to wait for the lock on account 4 while holding the lock for account 14, at least as long as all code observes the same globally-defined lock ordering that we've observed here. (Hence "global".)

Conclusion and recommended readings

In this article we looked at several key areas of concurrent programming that (in my opinion, anyway) all practicing software developers should understand. In my observation, when it comes to concurrency, there is a huge gap between what typical developers should know and what they actually know, and that causes real-world production issues on a regular basis. I wrote this article to try to narrow that gap.

There are of course lots of good resources for concurrent programming. Here are some of my favorites:

• Concurrency: Past and Present, by Brian Goetz: An entertaining presentation on concurrency. Goetz is a well-known authority on concurrent programming.
• Java Concurrency in Practice, by Brian Goetz. A really great and approachable book.
• Concurrent Programming in Java(TM): Design Principles and Pattern (2nd Edition), by Doug Lea. Another great book on concurrency; probably the standard. More academic than the Goetz book but still quite approachable.
• The Therac-25 Accidents: A classic software engineering paper on how race conditions actually injured and killed people. The basic idea is that the Therac-25 machine, which was designed to administer radiation to cancer patients, was vulnerable to race conditions that occurred as the human operator became more experienced with operating the machine (and thus keyboarded commands more quickly). The race conditions led to massive radiation overdoses. Long but well worth the read.

Post a comment