What are the four Coffman conditions for deadlock, and why must all four hold simultaneously?

middlemust knowfreq 62%

answer

MUTEX, HOLD-and-wait, NO-preemption, CIRCULAR wait
All four necessary; break one to prevent
Circular wait = cycle in the wait-for graph
Circular wait is the easiest to break (lock ordering)
Necessary, not strictly sufficient (needs the right interleaving)

basics

~10 s

The four Coffman conditions are: mutual exclusion, hold-and-wait, no preemption, and circular wait. A deadlock can only happen when all four are true at once, so breaking any one of them prevents deadlock.

solid answer

~50 s

Deadlock requires four conditions to hold together (the Coffman conditions): (1) Mutual exclusion — a resource can be held by only one thread at a time. (2) Hold-and-wait — a thread holds at least one resource while waiting to acquire others. (3) No preemption — a resource can't be forcibly taken from a thread; it must release it voluntarily. (4) Circular wait — there's a cycle of threads where each waits for a resource held by the next. They're necessary conditions: all four must be present simultaneously for deadlock, so prevention works by ensuring at least one can never hold. In practice the most tractable to break is circular wait, via a consistent global lock-ordering: if every thread always acquires locks in the same total order, no cycle can form. tryLock-with-timeout attacks no-preemption/hold-and-wait by letting a thread give up and release. They're necessary but the conjunction isn't strictly sufficient on its own without a specific resource-allocation state.

go deeper

for a junior

Can name the four conditions and state that breaking one prevents deadlock.

for a middle

Explains each condition with a concrete lock example and maps each to a prevention technique.

for a senior

Articulates necessary-vs-sufficient, the wait-for graph cycle, and why lock-ordering is the cheapest lever.

for a principal

Reasons about which condition is realistic to break at system scale (e.g. immutable data vs. ordering vs. timeout/rollback) and the trade-offs of each.

Background

In 1971 Coffman, Elphick, and Shoshani identified four conditions that must all be true at the same time for a deadlock to be possible. They are necessary conditions: if even one is absent, deadlock cannot occur. This is powerful because it turns deadlock prevention into a checklist — guarantee that at least one condition can never hold, and you've designed deadlock out.

The four conditions

Mutual exclusion. At least one resource is held in a non-shareable mode — only one thread can use it at a time. A synchronized block or a ReentrantLock is exactly this: one holder. If resources were freely shareable (e.g. immutable data, read-only access), there'd be nothing to wait for.
Hold-and-wait. A thread that already holds one resource requests another while keeping the first. In the bank example, a thread holds acct1's lock and then asks for acct2's. If threads had to grab all resources at once (or none), they'd never be holding one while waiting for another.
No preemption. A resource cannot be forcibly taken away from the thread holding it; the holder must release it voluntarily. Java monitors and ReentrantLock.lock() are non-preemptive — nobody can yank the lock from you. (Note tryLock(timeout) introduces a form of voluntary preemption: the waiter gives up.)
Circular wait. There exists a set of threads T1, T2, …, Tn such that T1 waits for a resource held by T2, T2 for one held by T3, …, and Tn for one held by T1 — a closed cycle in the wait-for graph (a directed graph where an edge A→B means 'A is waiting for a lock B holds'). A cycle in that graph is the signature of deadlock.

Why all four must hold together

Each condition alone is harmless. Mutual exclusion is everywhere and causes no deadlock by itself. Circular wait can't even form unless threads can hold-and-wait. Remove any single condition and the cycle becomes impossible:

No mutual exclusion -> nothing is exclusively held -> no waiting.
No hold-and-wait -> a thread never holds X while wanting Y -> no chain.
Preemption allowed -> a stuck cycle can be broken by reclaiming a resource.
No circular wait -> by definition no cycle -> no deadlock.

Necessary vs. sufficient

The four conditions are necessary for deadlock. They are not automatically sufficient: even with all four 'possible', deadlock only actually occurs in a specific resource-allocation state (a particular interleaving that closes the cycle). That's why deadlock is timing-dependent — the conditions enable it, the schedule triggers it.

Mapping conditions to prevention

Break mutual exclusion: use immutable/shareable data, lock-free structures, or copy-on-write — often impractical for genuinely exclusive resources.
Break hold-and-wait: acquire all locks atomically up front, or release-and-retry; don't request new locks while holding others.
Break no preemption: use tryLock with a timeout so a thread can abandon what it holds and back off.
Break circular wait (most practical): impose a global total order on locks and always acquire in that order, so the wait-for graph can never contain a cycle.

## Background In 1971 Coffman, Elphick, and Shoshani identified four conditions that **must all be true at the same time** for a deadlock to be possible. They are **necessary conditions**: if even one is absent, deadlock cannot occur. This is powerful because it turns deadlock *prevention* into a checklist — guarantee that at least one condition can never hold, and you've designed deadlock out. ## The four conditions 1. **Mutual exclusion.** At least one resource is held in a non-shareable mode — only one thread can use it at a time. A `synchronized` block or a `ReentrantLock` is exactly this: one holder. If resources were freely shareable (e.g. immutable data, read-only access), there'd be nothing to wait for. 2. **Hold-and-wait.** A thread that already holds one resource requests *another* while keeping the first. In the bank example, a thread holds `acct1`'s lock and *then* asks for `acct2`'s. If threads had to grab *all* resources at once (or none), they'd never be holding one while waiting for another. 3. **No preemption.** A resource cannot be forcibly taken away from the thread holding it; the holder must release it voluntarily. Java monitors and `ReentrantLock.lock()` are non-preemptive — nobody can yank the lock from you. (Note `tryLock(timeout)` *introduces* a form of voluntary preemption: the waiter gives up.) 4. **Circular wait.** There exists a set of threads T1, T2, …, Tn such that T1 waits for a resource held by T2, T2 for one held by T3, …, and Tn for one held by T1 — a closed cycle in the **wait-for graph** (a directed graph where an edge A→B means 'A is waiting for a lock B holds'). A cycle in that graph is the signature of deadlock. ## Why all four must hold *together* Each condition alone is harmless. Mutual exclusion is everywhere and causes no deadlock by itself. Circular wait can't even form unless threads can hold-and-wait. Remove **any** single condition and the cycle becomes impossible: - No mutual exclusion -> nothing is exclusively held -> no waiting. - No hold-and-wait -> a thread never holds X while wanting Y -> no chain. - Preemption allowed -> a stuck cycle can be broken by reclaiming a resource. - No circular wait -> by definition no cycle -> no deadlock. ## Necessary vs. sufficient The four conditions are **necessary** for deadlock. They are *not* automatically **sufficient**: even with all four 'possible', deadlock only actually occurs in a specific resource-allocation state (a particular interleaving that closes the cycle). That's why deadlock is timing-dependent — the conditions enable it, the schedule triggers it. ## Mapping conditions to prevention - Break **mutual exclusion**: use immutable/shareable data, lock-free structures, or copy-on-write — often impractical for genuinely exclusive resources. - Break **hold-and-wait**: acquire all locks atomically up front, or release-and-retry; don't request new locks while holding others. - Break **no preemption**: use `tryLock` with a timeout so a thread can abandon what it holds and back off. - Break **circular wait** (most practical): impose a **global total order** on locks and always acquire in that order, so the wait-for graph can never contain a cycle.

Which Coffman condition does a consistent global lock-ordering eliminate, and why is it the usual choice?
It eliminates circular wait. If every thread acquires locks in the same total order, the wait-for graph is a DAG and no cycle can form. It's the usual choice because it requires no runtime mechanism (no timeouts/rollback) — just a discipline on acquisition order.
How does tryLock(timeout) relate to the Coffman conditions?
It introduces voluntary preemption / breaks hold-and-wait: a thread waiting too long abandons the attempt, releases the locks it already holds, and retries, so a forming cycle is broken instead of becoming permanent.

saying these in an interview costs you the question

Listing only some conditions or inventing extra ones
Saying the four conditions are sufficient (they're necessary; a triggering interleaving is still needed)
Claiming you must break all four — breaking just one prevents deadlock
Confusing 'no preemption' (can't take the lock away) with 'no priority'

context

Background

The four conditions

Mutual exclusion. At least one resource is held in a non-shareable mode — only one thread can use it at a time. A synchronized block or a ReentrantLock is exactly this: one holder. If resources were freely shareable (e.g. immutable data, read-only access), there'd be nothing to wait for.

Hold-and-wait. A thread that already holds one resource requests another while keeping the first. In the bank example, a thread holds acct1's lock and then asks for acct2's. If threads had to grab all resources at once (or none), they'd never be holding one while waiting for another.

No preemption. A resource cannot be forcibly taken away from the thread holding it; the holder must release it voluntarily. Java monitors and ReentrantLock.lock() are non-preemptive — nobody can yank the lock from you. (Note tryLock(timeout) introduces a form of voluntary preemption: the waiter gives up.)

Circular wait. There exists a set of threads T1, T2, …, Tn such that T1 waits for a resource held by T2, T2 for one held by T3, …, and Tn for one held by T1 — a closed cycle in the wait-for graph (a directed graph where an edge A→B means 'A is waiting for a lock B holds'). A cycle in that graph is the signature of deadlock.

Why all four must hold together

No mutual exclusion -> nothing is exclusively held -> no waiting.

No hold-and-wait -> a thread never holds X while wanting Y -> no chain.

Preemption allowed -> a stuck cycle can be broken by reclaiming a resource.

No circular wait -> by definition no cycle -> no deadlock.

Necessary vs. sufficient

Mapping conditions to prevention

Break mutual exclusion: use immutable/shareable data, lock-free structures, or copy-on-write — often impractical for genuinely exclusive resources.

Break hold-and-wait: acquire all locks atomically up front, or release-and-retry; don't request new locks while holding others.

Break no preemption: use tryLock with a timeout so a thread can abandon what it holds and back off.

Break circular wait (most practical): impose a global total order on locks and always acquire in that order, so the wait-for graph can never contain a cycle.

What are the four Coffman conditions for deadlock, and why must all four hold simultaneously?

§ answer

basics

solid answer

§ go deeper

▾level notes4 levels

▾deep dive~3 min

Background

The four conditions

Why all four must hold together

Necessary vs. sufficient

Mapping conditions to prevention

▾common follow-ups2 questions

▾red flags4 flags

§ context

▾related questions3 questions

▾related topics2 topics

Background

The four conditions

Why all four must hold together

Necessary vs. sufficient

Mapping conditions to prevention

answer

go deeper

context