skip to content

What is a deadlock, and which four conditions must all hold at the same time for one to be possible?

level: juniorimportance: must knowfreq 72%

answer

  1. Coffman 1971: mutex, hold-and-wait, no preempt, circular wait
  2. all four at once; break one and it is impossible
  3. necessary always; sufficient only for single-instance resources
  4. hang with near-zero CPU, not a crash
  5. not just locks: pools, permits, queue slots, row locks

basics

~10 s

Deadlock is a set of threads permanently blocked, each waiting for a resource another one in the set holds. It requires four conditions at once: mutual exclusion, hold-and-wait, no preemption, circular wait.

solid answer

~50 s

A deadlock is a state where a group of participants (threads, transactions, services) can never progress, because each waits for a resource held by another member of the same group. It is permanent: no scheduling decision resolves it. Coffman's four necessary conditions: 1. **Mutual exclusion** - at least one resource is exclusive, one holder at a time. 2. **Hold and wait** - a participant holds one resource while requesting another. 3. **No preemption** - a resource is released only voluntarily by its holder. 4. **Circular wait** - a cycle of waiters exists: T1 waits on T2, T2 on T3, ... Tn on T1. They are *necessary*, so eliminating any one makes deadlock impossible - which is exactly what prevention techniques do. With single-instance resources a cycle in the wait-for graph is also sufficient, so detecting deadlock reduces to finding a cycle.

code

text · 7 lines
text
T1                      T2
acquire(A)   ok
                        acquire(B)   ok
acquire(B)   blocks (held by T2)
                        acquire(A)   blocks (held by T1)

wait-for graph:  T1 -> T2 -> T1   (cycle => deadlock)

go deeper

for a junior

Name all four conditions and give the two-thread, two-lock example with the opposite acquisition order. Knowing that breaking one condition is enough is the expected extra.

for a middle

Add the necessary-versus-sufficient distinction and map the conditions onto the wait-for graph, plus how deadlock differs from livelock and starvation.

for a senior

Frame the conditions as a diagnostic checklist over real resources - pool permits, queue slots, row locks - and explain why conditions 1 to 3 are usually fixed by the platform so the design lever is circular wait.

for a principal

Discuss where each condition is negotiable at architecture level (immutability removes mutual exclusion, abortable transactions remove no-preemption) and what the system must give up in exchange.

## What deadlock means A deadlock is a state in which a set of participants is **permanently** blocked because each member waits for something another member of the same set holds and will never release. Permanence is the point: no retry inside the blocked threads, no scheduler decision, and no passage of time fixes it. Only outside intervention (killing a thread, aborting a transaction, restarting the process) breaks it. The symptom is a hang, not a crash. The process is alive, CPU is near zero, and the resources the deadlocked set holds are never released, so everything else that needs them piles up behind. A two-thread deadlock on a shared lock can freeze an entire service. ## The four Coffman conditions Coffman, Elphick and Shoshani (1971) identified four conditions that must all hold simultaneously: 1. **Mutual exclusion.** At least one resource is held in a non-shareable mode. If everything could be shared freely (immutable data, read-only access), nobody would ever have to wait. 2. **Hold and wait.** A participant that already holds at least one resource requests another instead of releasing what it has first. If every participant grabbed its whole set atomically or held nothing while asking, waits could not nest. 3. **No preemption.** A held resource cannot be taken away by force; it is released only when the holder chooses to. If the system could revoke a lock and roll the holder back, any impasse could be broken. 4. **Circular wait.** There exists a set T1..Tn such that T1 waits for a resource held by T2, T2 for one held by T3, and Tn for one held by T1. The two-participant case (T1 waits on T2, T2 waits on T1) is the common one. A useful way to hold these in your head: the first three are properties of the **resource and its protocol** (is it exclusive, can you hold while asking, can it be revoked), while the fourth is a property of a particular **execution order**. ## Necessary versus sufficient The four conditions are *necessary*: remove any single one and deadlock cannot occur. That is why prevention is always described as "attack one condition". Sufficiency is subtler. When every resource type has exactly one instance, a circular wait (a cycle among waiters) plus the other three conditions means the system *is* deadlocked. When a resource type has several interchangeable instances - a pool of 10 connections, a semaphore with N permits - a cycle is necessary but not sufficient: some third participant not in the cycle may release an instance and unblock everyone. Detection there needs a reduction or safety analysis rather than a plain cycle test. ## A minimal example Two exclusive resources A and B, two threads that take them in opposite order. Interleaving decides everything: if T1 finishes before T2 starts, nothing happens; if they interleave as below, the system is stuck forever. That intermittency is why deadlocks slip through testing and appear under production load. ## Lookalikes worth distinguishing - **Livelock**: participants keep changing state and consuming CPU but make no progress (two people stepping aside in a corridor). States change; in a deadlock they do not. - **Starvation**: progress is possible, but one unlucky participant never gets its turn. The system as a whole is fine. - **Plain blocking hang**: everyone waits on an external event - a socket read with no timeout, a message that never arrives. Stacks look frozen, but there is no cycle, so it is not a deadlock; the fix is a timeout, not lock discipline. ## Beyond mutexes Nothing in the four conditions mentions locks. Database row locks, connection-pool permits, semaphores, bounded queue slots, worker threads in a bounded pool, file locks and distributed leases all satisfy conditions 1 to 3, so all of them can deadlock. Anything finite, exclusive and non-preemptible is a candidate.

  • If the four conditions are necessary, why do deadlocks still surprise teams in production?
    The first three conditions are almost always true by construction - exclusive resources that cannot be revoked are how most systems are built. Only circular wait depends on the interleaving, so a deadlock-capable design can run correctly for months until timing, load, or a new call path realizes the cycle. Testing rarely reproduces the exact interleaving, so the design flaw ships.
  • How do you tell a deadlock from a livelock without a debugger?
    Look at CPU and at whether state changes. A deadlocked set is blocked, so CPU attributable to it is roughly zero and repeated stack snapshots are byte-identical. A livelocked set is running - CPU is high, stacks move between snapshots, retry or backoff counters climb - yet no unit of work completes. Throughput is zero in both cases; only the resource profile differs.

Four-way stop where every driver has entered the intersection and each is blocked by the car on their right. Nobody can reverse (no preemption), nobody gives up the space they occupy (hold and wait), only one car fits per spot (mutual exclusion), and the blocking relation forms a ring (circular wait).

saying these in an interview costs you the question

  • Saying deadlock is 'when a thread waits too long' - slow is not deadlocked; deadlock is permanent and cyclic.
  • Claiming any one of the four conditions alone causes deadlock; all four must hold together.
  • Believing only mutexes deadlock, ignoring connection pools, semaphores, bounded queues and database locks.
  • Assuming a cycle always proves deadlock, even when resources have multiple interchangeable instances.
  • Confusing deadlock with starvation or livelock, where progress is still structurally possible or state still changes.

context

resolving links…