How synchronization gives rise to deadlocks

We saw in the previous section how a thread will grab a lock just before entering a critical section, thereby forcing other threads to "block" (concurrency lingo for "wait for another thread to release a lock") until they can acquire the lock. Normally this blocking behavior is unremarkable. It is a standard part of concurrent programming since we're trying to protect data from data races.

If there's too much contention for locks, that can of course have a negative effect on performance since threads are sitting around waiting instead of doing work. But usually this just means subpar performance rather than hanging.

The pathological case of contention for locks is deadlocking. This is characterized by two or more threads becoming permanently hung. They are notoriously difficult to predict, avoid and handle, but it's not impossible. The secret to understanding deadlocks is to understand that they arise when threads wait for each other to release a lock in a cyclic fashion. The simplest case would be thread T₁ waiting for T₂ to release a lock, and T₂ waiting for T₁ to release a lock. Neither one can make forward progress. The next simplest case is T₁ waiting for T₂, T₂ waiting for T₃, and T₃ waiting for T₁. Now we have three deadlocked threads. Obviously the cycle can be of arbitrary length; all threads involved will be deadlocked.

Here's a diagram that shows how it works:

Figure 1. Deadlocks arise from circular dependencies between threads.

In figure 1, you can see that each thread holds the lock needed by the preceding thread. As the dependencies are circular, there is no way for any of the threads to make forward progress once something like the above happens. All five threads are hung—that is, deadlocked.

Photo credit: gladius

A furry aside

By now you might understand what I meant at the beginning of the article when I said that concurrent programming is kind of like an arms race. We start with single threads, but sometimes that's too slow, so we introduce multithreading. That causes a problem though, which is that the threads can interfere with one another when working with shared data. So we introduce turn-taking through mutexes (and through the synchronized keyword in particular). But that has the effect of limiting parallelism, and if we take that too far, we can end up sacrificing the parallelism (and performance) that we sought in the first place. In the most extreme case, we can inadvertently cause threads to deadlock.

(Maybe Whac-A-Mole is a better metaphor. That's OK. I'm going to stick with arms race just because I really like the mech/cyber photo. Think of it as an arms race between software engineers and small furry rodents.)

Now let's consider an example of code vulnerable to deadlocks.

Some deadlocky code

For this one we're going to use the standard bank account funds transfer example. Yes, it's a clichéd example, but it's such a good example and originality is overrated anyway. Here's listing 3:

public void transferFunds(Account from, Account to, Money amount) {
	synchronized (from) {
		synchronized (to) {
			from.decreaseBy(amount);
			to.increaseBy(amount);
		}
	}
}

(We'll ignore exceptional conditions such as insufficient funds. Or, if you like, assume that decreaseBy() throws an unchecked InsufficientFundsException.)

If it isn't obvious, the method is a service method that transfers funds from one account to another account. Before going further, take a look at the code and see if you can figure out how the deadlock can occur. Keep in mind what we said about cyclic dependencies.

Here's how a deadlock can occur

Recall from the discussion above that deadlocks involve multiple threads. Each one grabs a lock that one of the other threads needs, and needs a lock that one of the other threads has. Here, we have two synchronized blocks, and each entry point corresponds to a place where a thread will try to grab a lock, maybe successfully and maybe not.

With that information it's straightforward to construct the sequence of events that leads to the deadlock:

1. Thread T₁ enters the method, with the source account being account 4 and the destination account being account 14. T₁ is able to acquire the lock for account 4, but then there's a context switch before it can enter the second synchronized block.
2. Thread T₂ also enters the method, with the source account being account 14 and the destination account being account 4. T₂ is able to acquire the lock for account 14, but then gets blocked when trying to acquire the lock for account 4. That stands to reason, since T₁ has it. Context switch.
3. T₁ tries to grab the lock for account 14, but of course it can't since T₂ has it. Threads T₁ and T₂ are now deadlocked.

That's a fairly intricate bit of logic, and developers new to concurrent programming may wonder how in the heck they are supposed to anticipate problems like that. They may also wonder whether this series of events is so implausible that is just isn't worth worrying about. To answer the second concern first, deadlocks most certainly do occur in real code. Keep in mind that although the situations that produce them may be implausible, the problem is that CPU clock speeds are pretty incredible, and so things that seem implausible suddenly become just a matter of time.

As to how to defend against deadlocks, we'll look at that right now.

Post a comment