Deadlock and How to Avoid It

The polite stand-off

Across this rung you have collected a toolbox: the mutex for a critical section, the condition variable for waiting on a predicate, the semaphore for counting resources, and you have put them together in producer-consumer. Each tool makes one thread wait so another can make progress. A deadlock is what happens when that waiting forms a closed loop: every thread is waiting, none can proceed, and the program simply stops — no crash, no error, just silence.

Picture two threads and two mutexes, call them A and B. Thread 1 locks A, then reaches for B. Thread 2, at the very same instant, locks B, then reaches for A. Now thread 1 is holding A and waiting for B; thread 2 is holding B and waiting for A. Neither will ever let go of what it holds, because each is blocked before it can finish. They will wait for each other until you kill the process. This is the smallest, purest deadlock there is, and it needs nothing exotic — just two locks taken in opposite orders.

The four conditions

In 1971 Edward Coffman and colleagues wrote down four conditions that must ALL hold at once for a deadlock to be possible. Knowing them is the whole game, because to prevent deadlock you only need to break any single one. They are worth memorizing, because they turn a mysterious hang into a checklist you can actually reason about.

1. Mutual exclusion — a resource is held by at most one thread at a time. This is the whole point of a lock, so you rarely give it up; it is just the precondition that makes the other three matter.
2. Hold and wait — a thread keeps the locks it already has while blocking to acquire another one. Thread 1 holding A while waiting for B is exactly this.
3. No preemption — a lock cannot be forcibly taken away; the holder must release it voluntarily. The system cannot reach in and confiscate B from a stuck thread.
4. Circular wait — there is a cycle of threads, each waiting for a resource the next one in the cycle holds. With two threads the cycle is just A-waits-for-B-waits-for-A.

The fourth condition, circular wait, is the one you can attack most cleanly in everyday code. Break the cycle and a deadlock becomes impossible no matter how the threads interleave. That single idea — impose a global order on your locks — is the most practical defense most programmers will ever use, and the next section is entirely about it.

Lock ordering: break the cycle

Here is the discipline, and it is gloriously simple: pick a fixed, global order for all your locks, and make every thread acquire them in that order, always. If A always comes before B, then nobody ever holds B while reaching for A — so the cycle that needs A-before-B and B-before-A can never close. The order can be anything consistent: lock addresses, an id you assign, alphabetical names. What matters is that every code path agrees.

/* deadlock-prone: order depends on which way you call it */
void transfer(Account *from, Account *to, long amt) {
    pthread_mutex_lock(&from->lock);
    pthread_mutex_lock(&to->lock);     /* <- can invert vs another thread */
    from->balance -= amt;
    to->balance   += amt;
    pthread_mutex_unlock(&to->lock);
    pthread_mutex_unlock(&from->lock);
}

/* fixed: always lock the lower address first */
void transfer(Account *from, Account *to, long amt) {
    Account *first  = from < to ? from : to;
    Account *second = from < to ? to   : from;
    pthread_mutex_lock(&first->lock);
    pthread_mutex_lock(&second->lock);
    from->balance -= amt;
    to->balance   += amt;
    pthread_mutex_unlock(&second->lock);
    pthread_mutex_unlock(&first->lock);
}

Notice what the fixed version protects: it does not change WHICH locks are held, only the order they are taken. The lock invariant — the rule about what each lock guards — is untouched. This is why lock ordering is so beloved: it is a pure discipline, costs nothing at run time, and you can check it by reading the code. The hard part is keeping the order consistent as the codebase grows, which is why people document the hierarchy and some debuggers and the thread sanitizer can flag a lock taken out of order.

Other ways out, and a couple of cousins

Lock ordering attacks circular wait; trylock-with-backoff attacks hold-and-wait. You can also attack hold-and-wait head-on by acquiring ALL the locks you will need in one atomic step at the start, and refusing to start until you have them all — no partial holding, no waiting mid-stream. And you can sidestep mutual exclusion entirely for simple shared counters by using an atomic operation such as compare-and-swap: an atomic add takes no lock, so there is no lock to deadlock on. These lock-free techniques are powerful but subtle, and they are a topic for later rungs, not a free lunch.

Two close cousins are worth naming so you do not mistake them for deadlock. Starvation is when a thread is technically able to run but keeps losing the race for a lock and never gets in; the system as a whole makes progress, but that one thread is stuck. Priority inversion is nastier: a low-priority thread holds a lock that a high-priority thread needs, and a medium-priority thread (which needs neither) hogs the CPU and keeps the low-priority holder from ever releasing — so the high-priority thread waits on a low-priority one. The fix, priority inheritance, temporarily lifts the holder's priority. You will meet priority inversion and starvation again in real schedulers.

Finding and admitting deadlocks

Be honest about how deadlocks show up in practice: usually as a bug report that says "it just froze." Because nothing crashes, there is no core dump and no error code to grep for. The single most useful move is to attach a debugger to the hung process and print the backtrace of every thread. You will typically see two threads parked inside pthread_mutex_lock(), each one line away from finishing, each waiting on the lock the other holds — the cycle made visible. That picture, once you have seen it, is unmistakable.

Two cautions to keep you humble. First, a deadlock can be a heisenbug: it depends on a precise interleaving, so it may appear once a week in production and never under your debugger. That is not the deadlock being clever — it is the timing being rare. Second, do not confuse a deadlock with a slow operation or a thread legitimately blocked on input; check the backtraces before you conclude anything. The honest summary of this whole rung: locks are necessary and they are sharp. The four conditions tell you exactly where the sharp edge is, and lock ordering is the habit that keeps you from cutting yourself.