Deadlocks

Why it matters

A deadlock is a silent outage: no crash, no error, just threads that never return while requests pile up behind them. It happens with mutexes in one process, with row locks in a database (which detects it and kills one transaction), and with services that wait on each other through bounded pools. The prevention techniques are simple and must be designed in, because a deadlock that happens once a month in production is very hard to reproduce.

The idea

A deadlock is a set of threads each waiting for a resource held by another thread in the set, so none can proceed. The classic example: thread 1 locks A then wants B; thread 2 locks B then wants A.

The four conditions

Deadlock can occur only if all four Coffman conditions hold at once. Break any one and deadlock becomes impossible.

Prevention in practice

1. 1

   Lock ordering

   Give every lock a rank (by address, by account ID, by a documented hierarchy) and always acquire in ascending order. A transfer between accounts 7 and 3 always locks 3 first, whichever direction the money moves. This removes circular wait and is the most widely used technique.
2. 2

   Hold fewer locks

   Restructure so a thread never needs two locks at once: copy what you need under one lock, release, then take the other.
3. 3

   Timeouts and try-lock

   Acquire with a deadline; on failure, release everything held and retry after a randomised backoff. It turns a deadlock into a slower path, at the cost of possible livelock.
4. 4

   Never call out while holding a lock

   Calling an unknown callback, a plugin, a logger or a remote service under a lock invites it to take another lock in an unknown order.

Prevention, avoidance or detection

Every system takes one of three stances towards deadlock, and most real ones mix two.

Avoidance: the banker's algorithm, worked

Avoidance grants a request only if the system stays in a safe state: some order exists in which every thread can still finish even if each asks for its declared maximum. The banker's algorithm keeps, per resource type, an Allocation table (held now), a Max table (the declared ceiling) and Need (Max minus Allocation), plus an Available vector. Five threads, three resource types A, B and C, with 3, 3 and 2 units free:

      Allocation   Max       Need
P0    0 1 0        7 5 3     7 4 3
P1    2 0 0        3 2 2     1 2 2
P2    3 0 2        9 0 2     6 0 0
P3    2 1 1        2 2 2     0 1 1
P4    0 0 2        4 3 3     4 3 1
Available: 3 3 2

The safety check pretends to finish any thread whose Need fits in Available, then adds back what it held. P1 fits (1 2 2 within 3 3 2) and returns 2 0 0, making 5 3 2; P3 fits and makes 7 4 3; then P4, P2 and P0 in turn. The sequence P1, P3, P4, P2, P0 exists, so the state is safe. Now P1 requests 1 0 2. It is within P1's Need and within Available, and the pretended grant leaves 2 3 0 with the safe sequence P1, P3, P4, P0, P2, so it is granted. Next P0 asks for 0 2 0. The units are free, but after the grant Available would be 2 1 0 and nobody's remaining Need fits, not even P3's 0 1 1. No safe sequence exists, so the request is refused and P0 waits while the resources sit idle. That refusal is the whole idea, and the reason avoidance is rare outside textbooks: it needs every thread's maximum demand in advance, a fixed set of threads, and it keeps resources unused to hold the guarantee.

Detection and recovery

Instead of preventing deadlock, a system can let it happen and find it. With one instance of each resource, build the wait-for graph of who waits on whom and search for a cycle; with several instances, run the banker's safety check against current requests instead of maximum needs, and any thread that can never be marked finished is deadlocked. Detection can run on every blocked request, on a timer, or when many threads are blocked and CPU use has fallen. Recovery means choosing a victim and taking something from it: abort the transaction that holds the fewest locks or has done the least work, roll it back, and let the others proceed; the victim retries. Databases do exactly this. Postgres waits deadlock_timeout (one second by default) before it searches the graph, then aborts one transaction with error 40P01; InnoDB checks on every lock wait and picks the transaction with the fewest undo records. The application must catch the error and retry the whole transaction, because the database has thrown its work away. For diagnosis rather than recovery, jstack prints Java monitor deadlocks, Go reports "all goroutines are asleep", and the Linux kernel's lockdep validator records the order in which lock classes are taken and reports a possible deadlock the first time two are taken in opposite orders, long before any hang.

Inversion: deadlock's cousin

A lock can also let a less urgent thread block a more urgent one for an unbounded time with no cycle at all: the urgent thread waits on a lock, and the holder cannot run because a medium thread keeps the CPU. This is priority inversion, told in full with the Mars Pathfinder story in the Real-time scheduling lesson. The fix lives in the lock: on Linux a mutex created with PTHREAD_PRIO_INHERIT lends the waiter's urgency to the holder until it releases, and the kernel's rt_mutex does the same inside the scheduler.

Relatives

Livelock: threads keep reacting to each other and changing state without progress, like two people stepping aside in a corridor in the same direction forever; randomised backoff breaks the symmetry. Starvation: a thread can in principle proceed but never gets the resource because others always win; fair locks and aging prevent it.

Deadlock beyond one process

The same structure appears at larger scale. Two services each with a pool of 10 threads, each handling requests by calling the other synchronously: under load all 20 threads wait on the other pool and nothing completes. A job that holds a database connection while waiting for a lock held by a job waiting for a connection. The fixes are the same: consistent ordering, timeouts, not holding one scarce resource while waiting for another, and bulkheads that keep pools separate.

Trade-offs

Lock ordering is cheap and reliable but requires discipline across a codebase. Timeouts and retry handle what ordering cannot and add latency and possible livelock. Avoidance gives a guarantee and pays for it with idle resources and a declared maximum that most programs cannot state. Detection and abort, the database approach, keep code simple and make callers responsible for retrying, and the victim's work is lost. Coarser locking reduces deadlock risk at the cost of parallelism.

In an interview

Show the ordering rule and the retry: "Transfers lock both account rows in ascending ID order inside one transaction, so two transfers in opposite directions cannot deadlock. The database can still report deadlocks from other access paths, so the service retries a transaction on a deadlock error up to three times with jitter." If asked for the banker's algorithm, name the three tables and the safety check, and say why a request can be refused while resources are free: "Granting it would leave no order in which everyone can still finish."