Deadlocks

Coffman’s 1971 conditions are necessary and jointly sufficient. Mutual exclusion: the resource cannot be shared — a mutex, a row lock, a pipe buffer with one reader. Hold and wait: a thread holds one resource while waiting for another. No preemption: the resource cannot be taken away; the holder must release it voluntarily. Circular wait: a chain of threads where each waits for a resource the next one holds, closing back on the first. Remove any one and deadlock is impossible; every prevention technique is a choice of which one to remove.

Mutual exclusion is usually the point (you took the lock because the section needs it), and no preemption is a property of locks (you cannot yank a mutex from a thread mid-update without corrupting what it guards). That leaves hold-and-wait — acquire everything at once, or nothing — and circular wait — impose an order so cycles cannot form — as the two practical levers. Databases pick a third route: allow all four, detect the cycle, and preempt after all by aborting a transaction.

Draw a waits-for graph: a directed graph with one node per thread and an edge from T1 to T2 when T1 is blocked on a resource T2 holds. A deadlock exists if and only if the graph has a cycle. Detection is therefore a solved problem from the DSA domain — depth-first search with a visited/on-stack colouring (Cycle Detection on a Directed Graph) — run over the lock manager’s bookkeeping. With resources that have multiple instances (a semaphore with N permits) the graph gains resource nodes and the condition becomes "no reduction sequence clears it", but the two-lock mutex case is a plain cycle.

In practice you rarely run the detector yourself; you read its output. The Linux kernel’s lockdep records every lock-acquisition order it has ever seen and reports a *potential* cycle the first time an inconsistent order appears — before the deadlock actually occurs. The JVM’s jstack walks monitor ownership and prints "Found one Java-level deadlock" with both stacks. Go’s runtime panics with "all goroutines are asleep - deadlock!" when nothing can ever run. For a native process the manual version is gdb -p PID, thread apply all bt, find every thread in __lll_lock_wait, read which mutex address each wants, and read from the stack frames who holds it: the cycle is usually two threads long and takes ten minutes to see.

The production signature is a hang at 0% CPU with health checks still passing if they do not touch the locked subsystem (A Taxonomy of Concurrency Bugs). Because nothing errors, the first alert is often a queue backing up or a latency graph going vertical. A watchdog that dumps all thread stacks when a request exceeds a deadline is the cheapest deadlock detector a service can have.

Lock ordering removes circular wait: assign every lock a rank (by address, by a documented hierarchy, by object id) and always acquire in ascending rank. If every thread obeys, the waits-for graph is acyclic by construction. This is the discipline in the Linux kernel, in every database engine’s internal latches, and in any codebase that has survived a deadlock. Its weakness is that the order must be global and known — a callback or a library that takes its own lock while you hold yours breaks it silently — and that some code genuinely needs to lock two objects whose relative order is only known at runtime (transfer between two accounts).

For the runtime-order case, remove hold-and-wait with try-lock and back off: lock the first, try_lock the second, and if that fails release the first, pause, and retry. std::lock(m1, m2) and std::scoped_lock(m1, m2) implement exactly this deadlock-free acquisition; Java has no built-in equivalent, so it is written by hand with tryLock. Randomised backoff prevents two threads from retrying in lockstep and livelocking (A Taxonomy of Concurrency Bugs). For the transfer example, ordering by account id is simpler and is what most code does.

Timeouts do not prevent deadlock; they convert it into an error. pthread_mutex_timedlock, try_lock_for, acquire(timeout=): after N seconds the waiter gives up, releases what it holds, logs, and either retries or fails the request. That is a legitimate strategy for coarse operations (a request handler, a batch job) and a poor one inside hot paths, where a timeout either fires spuriously under load or is too long to matter. Whatever the strategy, keep the number of locks any one path holds simultaneously small — two is manageable, five is a research project.

Any resource with the four properties will do. Two processes each writing a large message to the other over a pair of pipes deadlock when both pipe buffers (64 KiB by default on Linux) fill before either starts reading — the classic subprocess.communicate bug when you read stdout to completion before stderr. A thread pool deadlocks when every worker blocks waiting for a task that needs a worker to run: with 8 workers, 8 tasks each submitting a subtask and waiting on it exhausts the pool with nothing runnable. fork() in a multithreaded process copies a heap lock held by another thread into the child, where the holder does not exist; the child’s first malloc waits forever — the reason fork without an immediate exec is unsafe with threads.

The same shape appears across machines: two services each calling the other synchronously with a bounded connection pool, each holding a connection while waiting for the other, is a distributed deadlock that no local detector sees. Timeouts are the only defence there, which is one reason every network call needs one.

Transactions take row locks and hold them until commit; two transactions updating the same two rows in opposite orders deadlock exactly like two threads. The engine cannot impose an order — the application chose it — so it detects and recovers. PostgreSQL waits deadlock_timeout (1 s by default) on any lock, then runs the waits-for-graph cycle check over all waiting backends; if it finds a cycle it aborts one participant with ERROR: deadlock detected (SQLSTATE 40P01) and releases its locks so the rest proceed. InnoDB checks the graph eagerly at each wait and rolls back the transaction that has done the least work. The aborted client is expected to retry — the database has, in effect, preempted a resource, which mutex-based code cannot do.

Everything transfers. The application-side fix is the same lock ordering: update rows in a consistent order (by primary key) and keep transactions short so hold-and-wait windows are small. The diagnostic is the same graph: pg_locks joined to pg_stat_activity shows who waits on whom, and the deadlock error message prints the cycle. Locks and Deadlocks covers the database side; the point of this lesson is that it is not a different phenomenon, only a different lock manager with a retry contract built in.