Deadlock, Livelock and Starvation

Locks fix the lost update and introduce a new failure: a system in which every thread is waiting and nothing will ever happen. Deadlock needs four conditions at once, and breaking any one of them prevents it. The usual choice is a single global order in which every lock is taken.

Deadlock has two cousins. In livelock everyone is busy and nobody makes progress. In starvation the system makes progress and one thread never does. The three look different from outside, need different signals to catch and share a root: threads waiting on each other in a pattern nobody drew.

The Deadly Embrace

Thread A holds lock 1 and waits for lock 2. Thread B holds lock 2 and waits for lock 1. Neither can proceed, neither will let go, and nothing else will intervene. The processor is idle and nothing logs an error.

The classic example is a money transfer that locks the source account and then the destination, so that the two balances change together. It works for months. It deadlocks the first time two transfers between the same two accounts run in opposite directions at the same moment: one locks account 17 and waits for account 42, the other locks account 42 and waits for account 17.

The Four Conditions

Coffman, Elphick and Shoshani set out the conditions in 1971, and deadlock needs all four at once. Mutual exclusion: a resource is held by one thread at a time. Hold and wait: a thread holding one resource may request another. No preemption: nothing can take a lock away from the thread that holds it. Circular wait: there is a cycle in who waits for whom.

Because all four are required, every prevention strategy removes one of them. Sharing a resource removes the first, taking every lock at once removes the second, allowing a lock to be taken away removes the third, and a lock order removes the fourth. In practice the fourth is the one engineers can remove cheaply.

Lock Ordering

Give every lock a rank and always acquire locks in increasing rank. A cycle then cannot form, because closing it would require some thread to acquire a lower-ranked lock while holding a higher one, which the rule forbids. The rank is a topological order over the locks, the idea Chapter 8 develops for dependency graphs.

The transfer is fixed in one line: always lock the account with the lower id first, whichever direction the money moves. Both transfers between accounts 17 and 42 now try account 17's lock first, one of them waits there holding nothing, and the cycle never closes.

Detection and the Timeout

A deadlock is a cycle in the wait-for graph, the graph with an edge from each waiting thread to the thread it waits for, and finding a cycle is the graph search of Chapter 8. Databases build this graph, find cycles and abort one of the transactions in the cycle, which the application must then retry.

Code without a detector puts a timeout on acquiring a lock. A timeout breaks hold-and-wait by giving up. It is honest, because it admits that a deadlock can happen and turns it into an error. It is also dangerous: if the retry repeats the same order at once, the same collision happens again.

Livelock and Starvation

Two threads that detect a conflict, both back off and both retry at the same instant can repeat that forever, busy the whole time and getting nowhere, like two people stepping aside in a corridor in step with each other. Randomized backoff breaks the symmetry, the way the random pivot of Chapter 9 keeps any one input from being bad every time. Backend Deep Dive covers the practice in its topic Retries, Backoff and Jitter.

Starvation is a thread that never gets the lock because others always win it: an unfair lock under load, or a writer waiting behind an endless stream of readers. Its sharpest form is priority inversion. A low-priority task holds a lock that a high-priority task needs, while medium-priority work keeps the low-priority holder off the processor, so the high-priority task waits on the least important work in the system. This reset the Mars Pathfinder lander repeatedly in 1997, until engineers switched on priority inheritance, which lends the holder the waiter's priority, with a patch uploaded from Earth.

How Each Failure Looks in Production

A deadlocked service shows near-zero processor use and a full thread pool, which a dashboard reads as a quiet afternoon. A database deadlock surfaces as an aborted transaction the code must retry. Livelock shows as high processor use and no throughput. Starvation shows as one client, one queue or one kind of request that is always slow while the averages look fine.

Each needs a different signal, and a service with no timeouts anywhere cannot recover from any of them without a restart. The timeout is what turns silence into an error somebody can see.

Processor idle, thread pool full, requests time out→Deadlock: a cycle of waiters

Processor busy, throughput near zero, retries climbing→Livelock: symmetric retries

System healthy, one client or task always stuck→Starvation: it never wins