Deadlock

The problem it solves

Two threads. Two locks. Each thread takes both, in the order that made sense where it was written. One takes A then B; the other takes B then A.

Read either thread on its own and it is unremarkable: take the locks you need, do the work, release them. The bug exists only in the relationship between the two orderings, which is why code review misses it — the reviewer is looking at one function, and the fault is in a pair.

Most of the time it works. Most interleavings have one thread finish its critical section before the other starts, and everything completes. Then, occasionally, thread 1 takes A and thread 2 takes B before either can take its second lock, and now each is waiting for a lock the other holds. Neither will ever release, because releasing comes after acquiring, and acquiring is what they are waiting for.

That “most of the time it works” is the whole reason deadlock reaches production. A bug that failed reliably would be caught in development.

The mechanism

Deadlock requires four conditions to hold at once, and Coffman’s list is worth knowing because each entry is a place you could intervene:

1. Mutual exclusion — the resources cannot be shared.
2. Hold and wait — a thread holding one resource waits for another.
3. No preemption — a resource cannot be taken back by force.
4. Circular wait — a cycle of threads each waiting for the next.

Break any one and deadlock is impossible. In practice, the fourth is the one you break, because the first three are usually inherent to what you are doing. Breaking the fourth means imposing a total order over every lock and requiring every thread to acquire in that order. A cycle needs somebody to take them backwards; if nobody does, no cycle can form.

Notice this engine needs no deadlock detector. Deadlock is not a special condition it looks for — it is a terminal state with threads still alive and no action available, which falls straight out of how “runnable” is defined. That is also exactly what deadlock is in reality: not an error, but the absence of anything that can happen next.

What the enumeration shows

The default program deadlocks in 2 of its 6 interleavings. The other four complete perfectly. Read those numbers next to each other, because they are the reason this bug survives testing: a third of orderings fail and two thirds pass, so a test that runs it a handful of times has a decent chance of seeing nothing wrong.

Drive it to the deadlocked state and the wait-for graph appears: T1 → T2 labelled B, T2 → T1 labelled A, both nodes in the signal colour because they are on a cycle. Every thread’s badge says what it is blocked on and who holds it. That picture — who is waiting for whom — discards everything about what the threads were trying to do, and it is sufficient: a cycle here is a deadlock and no cycle here is not one.

Then switch to lock-ordering, where both threads take A before B. Zero interleavings deadlock, out of the whole enumerated space. Not fewer; none.

The third variant is the one worth the most. deadlock-ring has three threads: A→B, B→C, C→A. Every pair is consistent — look at any two threads and you will find no disagreement about ordering — and the ring still closes, in 6 of 234 interleavings. This is why “we always take the account lock before the ledger lock” is not a policy until it covers every lock in the system.

The numbers worth carrying

• Two threads, opposite order: 2 of 6 interleavings deadlock. Consistent order: 0 of 2.
• Three threads in a ring: 6 of 234 — rarer, and invisible to pairwise reasoning.
• The failure probability per execution scales with how long each lock is held. Deadlock needs both threads inside the window simultaneously, so halving the time between the two acquisitions roughly quarters the rate — which is why it appears when a system gets busier or a critical section grows.

Where it breaks down

Lock ordering requires knowing every lock. That is easy in one module and hard across a codebase, and impossible when a lock is inside a library you call. Any callback invoked while holding a lock can acquire something you have never heard of, which is the practical origin of “never call unknown code inside a critical section”.

Not all deadlocks involve locks. Two threads waiting on each other’s queues, a pool whose tasks wait on the same pool, a thread awaiting a future that only it could complete — all the same cycle with different resources. Thread pool deadlock is the version that involves no locks whatsoever and is probably the most common in modern service code.

Timeouts are not a fix. tryLock with a timeout converts a hang into a failure and a retry, which is better operationally and leaves the cycle intact. Worse, symmetric retries can produce livelock, where both threads back off and retry in step forever.

Databases deadlock too, and they do preempt: they detect the cycle and abort one transaction. That is condition 3 broken deliberately, and it is why your application must be prepared to retry a transaction that failed for a reason it did not cause.

What people get wrong

“Deadlock needs two threads.” One thread and one non-reentrant lock is enough — see reentrancy.

“We take locks in a consistent order.” Across every path, including the ones inside libraries and callbacks? The three-thread ring is the counterexample where every pair looks consistent.

“It only happens under load.” Load widens the window. The cycle exists at any load.

“We will detect and recover.” Detection at runtime means finding a cycle in the wait-for graph, which is possible — jstack prints it, and databases do it as a matter of course — but recovery means killing something. For a database transaction that is fine; for two application threads mid-update it usually is not.

In production

jstack on a Java process prints “Found one Java-level deadlock” with both threads and both monitors, which is a genuinely good diagnostic — after the fact. Go’s runtime detects only total deadlock (every goroutine asleep) and says nothing when two goroutines are stuck while others run, which is the common case. pstack or a debugger will show you the same thing anywhere else: threads parked in a lock acquisition, and the ownership tells you the cycle.

The preventive practices that actually work:

Order your locks and write the order down. A comment naming the global order, next to the lock declarations, is worth more than any amount of care.

Reduce to one lock where you can. Two locks that are always taken together should be one lock.

Never hold a lock across a call you do not control — I/O, a callback, a virtual method, an event dispatch. This single rule prevents most real deadlocks, because it prevents the unknown second acquisition.

Use tryLock with a timeout at the boundary, so that a cycle you did not prevent becomes an alert instead of a hang, and make sure the retry is jittered so it does not become livelock.

The follow-up questions

“What are the conditions for deadlock?” — The four Coffman conditions, and which one you break in practice, and why it is the fourth.

“How do you prevent it?” — A total order over locks. The follow-up is always “over which locks”, and the answer is all of them, including the ones inside your dependencies.

“Three threads, three locks, every pair consistent. Safe?” — No. The ring. This is the question that finds out whether the ordering rule is understood or recited.

“You cannot change the acquisition order. What else?” — One lock instead of two, tryLock with jittered backoff, or restructure so the second lock is not needed while holding the first.