Deadlock: when a lock stops being a fix

A lock fixed the race in the previous lesson, so the obvious move is to add another one. Here is a bank transfer between two accounts, each with its own lock. This is the bug that has taken down more production systems than any other single mistake in concurrency.

/* transfer.c */
void transfer(account *from, account *to, long cents) {
  mutex_lock(&from->lock);
  mutex_lock(&to->lock);
  from->balance -= cents;
  to->balance += cents;
  mutex_unlock(&to->lock);
  mutex_unlock(&from->lock);
}

transfer(&alice, &bob, 500);    /* thread 1 */
transfer(&bob, &alice, 700);    /* thread 2 */Each account has its own lock. The two calls below run in two different threads at the same time.

Look at who owns what. Thread 1 acquired the lock on alice and now wants the lock on bob. Thread 2 acquired the lock on bob and now wants the lock on alice. Neither will ever let go, because neither has finished. Both sleep forever. Four conditions had to hold at the same time for this to happen, and all four were named in 1971; they are still the checklist.

mutual exclusion      request()
hold and wait         hold(A); request(B)
no preemption         request(B); loop
circular wait         T1 -> B, T2 -> A

all four hold   ->   deadlock
break any one   ->   no deadlockThe four Coffman conditions. Break any one of them and a deadlock becomes impossible, no matter how the locks are used.

The condition that is cheapest to break here is the circular wait, and the cure is one line: give every lockable object a global order and always acquire locks in that order. The classic trick is to compare addresses - the one that is lower in memory is always taken first. Then it is impossible for two threads to hold locks the other one needs, because both of them reach for the same one first.

mutex_lock(&from->lock);   /* wrong: order depends on arguments */
mutex_lock(&to->lock);

mutex_lock(&lo->lock);     /* right: one global order, by address */
mutex_lock(&hi->lock);Both calls now take the lower address first, so one of them simply waits for the other instead of fighting it.

The other condition you can break is hold and wait. Make every acquisition all-or-nothing: if the second lock is not free right now, release the first and start over. Nothing waits while holding anything, so no cycle of holders can form. This only works if the state is not left half-changed: the function must either do everything or do nothing. That is a real constraint, and it is exactly why banking code uses transactions.

while (!mutex_trylock(&from->lock)) { /* backoff */ }
if (!mutex_trylock(&to->lock)) {
  mutex_unlock(&from->lock);
  return RETRY;                /* held nothing while waiting */
}

/* $ timeout 30 ./bank && echo ok || echo 'still stuck' */

A deadlock is not the only way for work to stop. Two threads can also keep running and keep undoing each other: each one notices a conflict, politely releases its lock and retries - and both retry at the same moment, forever. This is livelock. The CPU is at 100%, the logs are full of activity, and no transaction ever completes. It is arguably worse than a deadlock, because a deadlocked process sits at zero CPU and shows up in a stack dump, while a livelocked one looks busy and healthy. The cure is to introduce randomness: exponential backoff with a random component, so the two threads stop retrying in lockstep.

deadlock    blocked,  cpu 0%
livelock    running,  cpu 100%
starvation  running,  cpu 100%

F1 holds B forever
F2 and F3 retry
F1 is frozenThree ways for work to stop, distinguished only by what the processor is doing and who is stuck.

Starvation is the third failure and the mildest-looking. Nothing is cyclic and nothing is blocked: the system as a whole is making progress, but one particular thread never gets its turn. A reader-writer lock that always prefers arriving readers is the usual cause - under a steady stream of readers, a writer waits forever. A thread of the lowest priority on a busy machine is another. Starvation is a fairness bug rather than a structural one, and it can take days to notice because the throughput graphs look perfect.

Now the reason the obvious advice is wrong. Adding a lock does not add safety, it adds a resource, and every new resource is a new waiting edge in the graph. Two locks create one possible cycle; ten locks create 45 ordered pairs and every one of them can be the wrong order somewhere in the codebase. A function that takes three separate locks and calls into code that takes two more has made a deadlock possible in a place nobody will think to look. Locks also do not compose: two independent modules that are each correct can deadlock the moment one calls the other while holding its own lock.

In practice, locks are not the only resource that can deadlock. A thread holding a database connection while waiting for a connection from the same pool starves the pool; two services each waiting for a synchronous call from the other is a distributed deadlock that no single stack dump can show you. Detecting these in production is usually done with timeouts and watchdog threads: if a transaction has not progressed in N seconds, dump the stack of every thread and look for the cycle. In a running process you can see it directly - the stacks of the deadlocked threads name the lock each one is waiting for and the lock each one owns.