§32.3–32.4Deadlock Bugs … Summary

Non-deadlock bugs were the majority; deadlock deadlock A situation where a set of threads are each holding a resource and waiting for one held by another, forming a cycle in which none can proceed — e.g. every dining philosopher holding their left fork and waiting for their right, or a consumer holding a mutex while blocked on 'full' while the producer that would post 'full' is blocked on that mutex. Studied in depth in ch32. defined in ch. 31 — open in glossary is the classic minority — old, hard, and worth understanding deeply.

32.3 Deadlock Bugs

Deadlock is a cycle of threads each holding a lock the next one wants. The minimal case (Fig 32.6):

// Thread 1            // Thread 2
lock(L1);              lock(L2);
lock(L2);              lock(L1);

If Thread 1 grabs L1, then a switch lets Thread 2 grab L2, each now waits for the other forever. The dependency graph makes the cycle visible:

Why do deadlocks happen?

“Just grab locks in the same order” sounds easy — so why do deadlocks occur? Two reasons: complex dependencies (the VM system calls the file system to page in a block; the FS calls the VM system for a page — a natural circular dependency), and encapsulation. Hiding implementation makes modular software, but hides locking. Java’s Vector.AddAll(v2) internally locks v1 then v2; a concurrent v2.AddAll(v1) locks v2 then v1 — deadlock, invisible to the caller.

The four conditions — and how to break each

Deadlock needs all four Coffman conditions to hold at once — mutual exclusion, hold-and-wait hold-and-wait One of the four Coffman conditions for deadlock: threads hold resources (locks) they've already acquired while waiting to acquire more. Prevented by acquiring ALL needed locks at once, atomically, under a global prevention lock (at the cost of modularity and concurrency). defined in ch. 32 — open in glossary , no preemption no preemption One of the four Coffman conditions for deadlock: resources (locks) cannot be forcibly taken from the threads holding them. Worked around with pthread_mutex_trylock — a thread that fails to get a second lock releases the ones it holds and retries, gracefully backing out of its own ownership. defined in ch. 32 — open in glossary , and circular wait circular wait The key Coffman condition for deadlock: a circular chain of threads exists, each holding a resource (lock) that the next thread in the chain is waiting for. Prevented — most practically — by imposing a total (or partial) ordering on lock acquisition so no cycle can ever form. defined in ch. 32 — open in glossary . Break any one and it can’t happen — giving four families of prevention:

Circular wait prevention (lock ordering) is the most practical. When a function takes two locks, enforce order by lock address:

// grab in a consistent order regardless of argument order
if (m1 > m2) { lock(m1); lock(m2); } // high-to-low
else         { lock(m2); lock(m1); }
// assumes m1 != m2

No preemption via trylock avoids holding-while-waiting — but risks livelock livelock A failure where threads are not blocked (not deadlocked) yet make no progress — e.g. two threads each grab lock 1, fail to trylock lock 2, release lock 1, and retry in lockstep forever. Unlike deadlock the threads keep running; fixed by adding a random back-off delay before retrying. defined in ch. 32 — open in glossary :

top:
    lock(L1);
    if (trylock(L2) != 0) {
        unlock(L1);
        goto top;   // two threads can loop here in lockstep forever
    }

Two threads can repeat this in sync, never progressing (not blocked — just spinning fruitlessly). The fix: a random back-off before retrying, breaking the symmetry.

Beyond locks: lock-free structures

To break mutual exclusion itself, use lock-free lock-free A synchronization approach that coordinates threads using atomic hardware instructions (e.g. compare-and-swap) instead of locks, so no lock is held and no deadlock can arise (livelock still can). It sidesteps the mutual-exclusion deadlock condition; e.g. a list insert via while(CAS(&head, n->next, n)==0). Pioneered by Herlihy. defined in ch. 32 — open in glossary structures built on atomic compare-and-swap instead of locks. A list insert:

void insert(int value) {
    node_t *n = malloc(sizeof(node_t));
    n->value = value;
    do {
        n->next = head;
    } while (CompareAndSwap(&head, n->next, n) == 0);
}

Step through two threads racing to insert — the loser just retries:

No lock is held, so no deadlock (livelock is still possible). A wait-free wait-free A stronger form of lock-free synchronization guaranteeing that EVERY operation completes in a finite number of steps (no unbounded retry loops). Harder to build than lock-free; a few wait-free structures have made their way into real systems, including Linux. defined in ch. 32 — open in glossary structure goes further — guaranteeing every operation finishes in a finite number of steps — but is harder to build; a few now ship in real systems, including Linux.

Avoidance and detection

Deadlock avoidance deadlock avoidance A strategy that uses global knowledge of which locks each thread may acquire to schedule threads so deadlock can never occur — e.g. never co-scheduling two threads that both grab L1 and L2. Dijkstra's Banker's Algorithm is the classic example; it needs full advance knowledge and can limit concurrency, so it's rarely general-purpose. defined in ch. 32 — open in glossary uses global knowledge of which locks threads need to schedule around trouble — never co-running two threads that could form a cycle:

Since only T1 and T2 grab both locks, keeping them off the same CPU (or never concurrent) guarantees safety; T3 (one lock) and T4 (none) can overlap freely. Dijkstra’s Banker’s Algorithm is the classic version — but it needs full advance knowledge and limits concurrency, so it’s rarely general-purpose.

The last resort: detect and recover. Let deadlock happen rarely, run a detector that builds the resource graph and looks for cycles, and restart when one is found (many databases do exactly this).

32.4 Summary

Non-deadlock bugs — atomicity and order violations — are common but often easy to fix. Deadlock is old and hard; the best practice is careful lock ordering to prevent it. Lock-free and wait-free approaches, and lock-free programming models like MapReduce, point beyond locks — because locks are problematic by nature, and perhaps best avoided unless truly necessary.