Deadlock

Locks solve races, but they create a new danger. Suppose thread T1 holds lock A and waits for lock B, while thread T2 holds lock B and waits for lock A. Neither can proceed, neither will release what it holds, and the two threads wait forever. This is deadlock. It can freeze a web server, a database or an operating system kernel, and like races it may appear only under rare timing, long after testing is finished. This lesson defines deadlock precisely, presents the four conditions it requires, and studies the four strategies for dealing with it: prevention, avoidance, detection and recovery, and ignoring it.

Lessons 5 and 6 introduced locks, semaphores and condition variables. CMPUT-274 showed a small deadlock between two Python threads. Here we treat the problem systematically, as operating system designers and database engineers do.

The four Coffman conditions

In 1971 Edward Coffman and colleagues showed that a deadlock can happen only if four conditions all hold at once. Mutual exclusion: at least one resource is held in a non-shareable mode, so other threads must wait for it. Hold and wait: a thread holds at least one resource while waiting to acquire more. No preemption: resources cannot be forcibly taken away; a thread releases them only voluntarily. Circular wait: there is a cycle of threads, each waiting for a resource held by the next. Break any one condition and deadlock becomes impossible, which is the basis of prevention.

A resource-allocation graph shows the situation. Circles are threads, squares are resources, an arrow from a thread to a resource is a request, and an arrow from a resource to a thread is an assignment. If every resource has a single instance, a cycle in the graph means deadlock. If resources have several instances, such as three identical printers, a cycle means deadlock is possible but not certain. Collapsing the resources gives a wait-for graph between threads only, which is what detection algorithms search.

Dining philosophers

Dijkstra's dining philosophers problem dramatizes deadlock. Five philosophers sit at a round table with one fork between each pair. To eat, a philosopher needs both the fork on the left and the fork on the right. If every philosopher picks up the left fork at the same moment, each waits forever for the right fork, which a neighbour holds. All four Coffman conditions hold: forks are exclusive, each philosopher holds one while waiting for another, nobody grabs a fork from a neighbour, and the waiting forms a circle.

# Dining philosophers, stepped deterministically: each philosopher picks up left fork, then right fork
def run(n, ordered, steps=12):
    forks = [None] * n                       # who holds each fork
    holding = {p: [] for p in range(n)}
    eaten = [0] * n
    for t in range(steps):
        for p in range(n):
            left, right = p, (p + 1) % n
            first, second = (min(left, right), max(left, right)) if ordered else (left, right)
            want = first if not holding[p] else second
            if len(holding[p]) < 2 and forks[want] is None:
                forks[want] = p; holding[p].append(want)
            if len(holding[p]) == 2:         # eat, then put both forks down
                eaten[p] += 1
                for f in holding[p]: forks[f] = None
                holding[p] = []
        if all(len(holding[p]) == 1 for p in range(n)) and all(f is not None for f in forks):
            return f"deadlock at step {t}: every philosopher holds one fork and waits for the other"
    return f"no deadlock after {steps} steps; meals eaten per philosopher: {eaten}"
print("left-then-right :", run(5, ordered=False))
print("lowest-numbered first:", run(5, ordered=True))

left-then-right : deadlock at step 0: every philosopher holds one fork and waits for the other
lowest-numbered first: no deadlock after 12 steps; meals eaten per philosopher: [2, 5, 5, 6, 2]

The simplest fix breaks circular wait by imposing an order on resources: number the forks and always pick up the lower-numbered fork first. Philosopher 4, whose forks are 4 and 0, picks up fork 0 first, which breaks the symmetry. Other fixes allow at most four philosophers at the table (a counting semaphore of four, breaking the cycle), or require picking up both forks atomically (breaking hold and wait).

Strategy 1: prevention

Lock ordering is the technique real systems rely on. The Linux kernel documents the order in which its locks must be taken, and a run-time checker called lockdep records every order it observes and warns the first time any code path takes two locks in an order that contradicts another path, even if no deadlock happened. Databases and file systems often order locks by address or by identifier, for example always locking the account with the smaller number first when transferring money between two accounts. ThreadSanitizer offers the same check for user programs.

#include <pthread.h>
#include <stdio.h>

static pthread_mutex_t accounts = PTHREAD_MUTEX_INITIALIZER;   /* lock A */
static pthread_mutex_t audit_log = PTHREAD_MUTEX_INITIALIZER;  /* lock B */

static void *transfer(void *x) {          /* takes A then B */
    (void)x;
    pthread_mutex_lock(&accounts); pthread_mutex_lock(&audit_log);
    pthread_mutex_unlock(&audit_log); pthread_mutex_unlock(&accounts);
    return NULL;
}
static void *report(void *x) {            /* takes B then A: inconsistent order */
    (void)x;
    pthread_mutex_lock(&audit_log); pthread_mutex_lock(&accounts);
    pthread_mutex_unlock(&accounts); pthread_mutex_unlock(&audit_log);
    return NULL;
}
int main(void) {
    pthread_t x, y;
    pthread_create(&x, NULL, transfer, NULL); pthread_join(x, NULL);
    pthread_create(&y, NULL, report, NULL);   pthread_join(y, NULL);
    puts("this run finished, but the two threads take the locks in opposite orders");
    return 0;
}

$ gcc -O1 -g -pthread -fsanitize=thread toy.c -o toy
$ ./toy
this run finished, but the two threads take the locks in opposite orders
==================
WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock)
  Cycle in lock order graph: M0 => M1 => M0
  Mutex M1 acquired here while holding mutex M0 in thread T1:
    #0 pthread_mutex_lock tsan_interceptors_posix.cpp
    #1 transfer toy.c:9
  Mutex M0 acquired here while holding mutex M1 in thread T2:
    #0 pthread_mutex_lock tsan_interceptors_posix.cpp
    #1 report toy.c:15
  Thread T1 created by main thread at:
    #0 pthread_create tsan_interceptors_posix.cpp
    #1 main toy.c:21
  Thread T2 created by main thread at:
    #0 pthread_create tsan_interceptors_posix.cpp
    #1 main toy.c:22
SUMMARY: ThreadSanitizer: lock-order-inversion (potential deadlock) toy.c:9 in transfer
==================
ThreadSanitizer: reported 1 warnings

This run completed, because the two threads did not overlap in time. Under load, one thread could hold the accounts lock while the other holds the audit log lock, and both would hang. The report names the cycle in the lock-order graph and both code locations, which is exactly the information needed to fix it: decide one order (accounts, then audit log) and follow it everywhere.

Strategy 2: avoidance

Avoidance lets the system grant a request only if doing so keeps the system in a safe state, one from which there is some order in which every thread can obtain its maximum demand and finish. Dijkstra's banker's algorithm implements this. Each thread declares in advance the maximum number of each resource type it may need. When it requests resources, the system pretends to grant them and runs a safety check: can the threads finish one by one, each using the currently free resources plus those released by threads that finished before it? If yes, the request is granted; if not, the thread waits, even though the resources are free.

# Banker's algorithm: is the state safe, and can a request be granted?
import copy
avail = [3, 3, 2]                                    # free instances of resources A, B, C
maxd  = {"P0": [7, 5, 3], "P1": [3, 2, 2], "P2": [9, 0, 2], "P3": [2, 2, 2], "P4": [4, 3, 3]}
alloc = {"P0": [0, 1, 0], "P1": [2, 0, 0], "P2": [3, 0, 2], "P3": [2, 1, 1], "P4": [0, 0, 2]}
def need(p, al): return [m - a for m, a in zip(maxd[p], al[p])]
def safe(avail, al):
    work, done, order = avail[:], set(), []
    while len(done) < len(al):
        for p in sorted(al):
            if p not in done and all(n <= w for n, w in zip(need(p, al), work)):
                work = [w + a for w, a in zip(work, al[p])]; done.add(p); order.append(p); break
        else:
            return None
    return order
print("current state safe sequence:", safe(avail, alloc))
def request(p, req):
    if any(r > n for r, n in zip(req, need(p, alloc))): return "error: exceeds declared maximum"
    if any(r > a for r, a in zip(req, avail)): return "must wait: not enough free resources"
    al = copy.deepcopy(alloc); al[p] = [a + r for a, r in zip(al[p], req)]
    av = [a - r for a, r in zip(avail, req)]
    seq = safe(av, al)
    return f"grant (safe sequence {seq})" if seq else "deny for now: granting would make the state unsafe"
print("P1 requests [1, 0, 2]:", request("P1", [1, 0, 2]))
print("P4 requests [3, 3, 0]:", request("P4", [3, 3, 0]))
print("P0 requests [0, 2, 0]:", request("P0", [0, 2, 0]))

current state safe sequence: ['P1', 'P3', 'P0', 'P2', 'P4']
P1 requests [1, 0, 2]: grant (safe sequence ['P1', 'P3', 'P0', 'P2', 'P4'])
P4 requests [3, 3, 0]: deny for now: granting would make the state unsafe
P0 requests [0, 2, 0]: grant (safe sequence ['P3', 'P1', 'P0', 'P2', 'P4'])

An unsafe state is not yet a deadlock, but it is one from which deadlock might be unavoidable. The banker's algorithm is elegant and widely taught, yet it is rarely used in general-purpose operating systems: threads seldom know their maximum needs in advance, the number of threads changes constantly, and running the safety check on every request is expensive. Its ideas appear in more specialized places, such as admission control for real-time tasks (SCHED_DEADLINE refuses tasks that would make the system unschedulable) and in some resource managers for clusters.

Strategy 3: detection and recovery

Detection lets deadlocks happen, finds them and then recovers. For single-instance resources, the system periodically builds a wait-for graph and searches it for cycles with depth-first search, which takes time proportional to the number of threads plus edges. For multi-instance resources, a variant of the banker's safety check run on current requests rather than declared maxima identifies the deadlocked set. How often to run detection is a trade-off: running it on every blocked request finds deadlocks immediately but costs time; running it every few seconds or when processor utilization drops is cheaper.

# Detect deadlock by finding a cycle in a wait-for graph (single-instance resources)
waits_for = {                       # thread -> threads it is waiting for
    "T1": ["T2"],                   # T1 wants the lock T2 holds
    "T2": ["T3"],
    "T3": ["T1"],                   # ... and T3 wants T1's lock: a cycle
    "T4": ["T1"],
    "T5": [],
}
def find_cycle(g):
    UNSEEN, ON_PATH, DONE = 0, 1, 2
    mark = {v: UNSEEN for v in g}; stack = []
    def dfs(v):
        mark[v] = ON_PATH; stack.append(v)
        for w in g[v]:
            if mark[w] == ON_PATH:
                return stack[stack.index(w):] + [w]
            if mark[w] == UNSEEN:
                c = dfs(w)
                if c: return c
        mark[v] = DONE; stack.pop(); return None
    for v in g:
        if mark[v] == UNSEEN:
            c = dfs(v)
            if c: return c
c = find_cycle(waits_for)
print("cycle:", " -> ".join(c) if c else "none")
blocked = {v for v in waits_for if v in c} if c else set()
print("deadlocked:", sorted(blocked), "| blocked behind them: ['T4'] | free: ['T5']")

cycle: T1 -> T2 -> T3 -> T1
deadlocked: ['T1', 'T2', 'T3'] | blocked behind them: ['T4'] | free: ['T5']

Recovery means breaking the cycle. The system can abort one or more threads in the cycle, choosing victims by cost (how much work would be lost, how many resources they hold, their priority), or preempt resources by rolling a thread back to an earlier checkpoint. Databases do exactly this: PostgreSQL, MySQL's InnoDB and SQL Server detect deadlocks between transactions and abort one, which the application then retries. To avoid starving the same victim forever, the selection should account for how many times a transaction has already been rolled back.

Strategy 4: ignore it

Most general-purpose operating systems, including Linux and Windows, take what textbooks call the ostrich approach for user programs: they do not prevent, avoid or detect deadlocks among application threads. Deadlocks are rare relative to the cost of the machinery, and the application is better placed to fix them, for example by consistent lock ordering. If an application deadlocks, the user or a watchdog restarts it. The kernel, by contrast, takes great care with its own locks, because a kernel deadlock freezes the whole machine. Watchdog timers in embedded systems and health checks in container orchestrators are, in effect, coarse deadlock recovery: if a component stops responding, restart it.

Related problems: livelock and starvation

Livelock is deadlock's cousin: threads are not blocked, but they keep changing state in response to each other without making progress, like two people in a corridor who keep stepping aside in the same direction. Trylock-and-retry schemes can livelock if every thread backs off and retries in lockstep; adding random back-off delays, as Ethernet does after collisions, fixes it. Starvation is a thread that could make progress but is repeatedly passed over, for example a writer starved by readers in Lesson 6 or a transaction chosen as the deadlock victim every time. Correct concurrent programs need freedom from all three.

Worked examples