Deadlock — four necessary conditions (Coffman)

WHAT is a deadlock?

The key word is circular waiting on each other. If even one of them could eventually get its resource from outside the set, it isn't a true deadlock — that's just a delay.

WHY do we need four conditions?

In 1971 Edward Coffman asked: under what circumstances is deadlock even possible? He found four necessary conditions. "Necessary" means:

$\text{Deadlock} \implies (C_1 \wedge C_2 \wedge C_3 \wedge C_4)$

So if any one condition is false, deadlock cannot happen. This is the WHY behind every deadlock-prevention strategy: break one condition and you make deadlock impossible.

The Four Coffman Conditions

HOW each condition contributes (derive the gridlock from scratch)

Build the deadlock step by step and watch where each condition is used:

Process $P_0$ grabs resource $R_0$ . Why possible? Because $R_0$ is non-sharable — Mutual Exclusion lets one owner lock everyone else out.
$P_0$ now wants $R_1$ but keeps holding $R_0$ . Why does it keep $R_0$ ? Hold and Wait — it doesn't release what it has while requesting more.
Meanwhile $P_1$ holds $R_1$ and wants $R_0$ . Neither can grab the other's resource. Why can't the OS just snatch $R_1$ from $P_1$ ? No Preemption — resources are released only voluntarily.
Now $P_0 \to P_1 \to P_0$ : a closed loop of waiting. Why fatal? Circular Wait — the dependency graph has a cycle, so the "I'll wait for them to finish" reasoning chases its own tail forever.

Remove any one link and the chain breaks:

No mutual exclusion → both share $R_0,R_1$ → no waiting.
No hold-and-wait → $P_0$ must drop $R_0$ before asking for $R_1$ → no held-while-waiting.
Preemption allowed → OS takes $R_1$ from $P_1$ , gives to $P_0$ → loop dissolves.
No circular wait (e.g. order resources, request in increasing order) → no cycle can form.

Figure — Deadlock — four necessary conditions (Coffman)

Worked Examples

Worked example Example 1 — Two mutexes, classic deadlock

Threads A and B, locks L1, L2.

A: lock(L1); ... lock(L2)
B: lock(L2); ... lock(L1)

Interleaving: A locks L1, B locks L2, A waits for L2, B waits for L1.

Mutual exclusion? Yes — mutexes are non-sharable. Why this step? A lock by definition excludes others.
Hold & wait? Yes — A holds L1 while waiting L2. Why? It never released L1.
No preemption? Yes — you cannot forcibly unlock another thread's mutex. Why? OS doesn't yank mutexes.
Circular wait? $A\to B\to A$ . Why? A waits on L2 (held by B), B waits on L1 (held by A). All four → deadlock. Fix: impose a global lock order — always lock L1 before L2. This kills circular wait.

Recall Feynman: explain to a 12-year-old

Imagine 4 kids in a square hallway. Each kid grabs the doorknob of the door in front of them and won't let go until they can open the next door too — but that next door's knob is already held by the kid ahead. Now everybody is stuck holding a knob, waiting for the kid in front, in a circle. Nobody will let go (no preemption), nobody can share a knob (mutual exclusion), and they wait in a ring (circular wait) while still gripping (hold-and-wait). For them to get stuck, all four silly rules must be true at once. Change just one rule — like "let go if you can't open both doors" — and the jam clears.

Forecast-then-Verify checkpoint

Before reading on, predict: If we make all resources preemptible, can deadlock still occur? → Verify: No. Removing No Preemption falsifies condition 3, so the necessary set is incomplete ⇒ deadlock impossible (though we may get livelock instead).

Flashcards

What does "necessary condition for deadlock" formally mean?

Deadlock ⇒ (all four conditions hold); equivalently, if any condition is false, deadlock cannot occur.

List the four Coffman conditions.

Mutual exclusion, Hold and wait, No preemption, Circular wait.

Why is "all four conditions present" NOT enough to guarantee deadlock?

They are necessary but not sufficient; deadlock also needs the unlucky interleaving / an actual cycle in the resource-allocation graph (single-instance case).

Which condition does enforcing a global lock ordering break?

Circular wait.

Which condition does "request all resources at once" break, and its downside?

Hold and wait; downside is poor utilization and possible starvation/livelock.

Define circular wait precisely.

A set {P0..Pn-1} where each Pi waits for a resource held by P(i+1 mod n), forming a closed cycle.

What is mutual exclusion in deadlock context?

At least one resource is non-sharable — only one process may hold it at a time.

What is the difference between deadlock and livelock?

Deadlock = processes frozen, no state change; livelock = processes keep changing state (e.g. retrying) but make no progress.

In the dining philosophers problem, how does making one philosopher pick right-fork-first help?

It breaks circular wait by introducing asymmetry, so no uniform directed cycle can form.

If resources were preemptible by the OS, which Coffman condition fails?

No Preemption fails (condition 3).

Connections

Resource-Allocation Graph — cycle detection makes circular wait visible.
Deadlock Prevention — each strategy negates one Coffman condition.
Deadlock Avoidance — Banker's Algorithm — keeps system in safe states instead of forbidding conditions.
Deadlock Detection and Recovery — allow deadlock, then break it (often via preemption).
Mutual Exclusion and Semaphores and Mutexes — where condition 1 comes from.
Dining Philosophers Problem — canonical illustration.
Starvation and Livelock — failure modes you trade into when preventing deadlock.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, deadlock ka matlab hai ki kuch processes hamesha ke liye atak gaye — har ek dusre ka resource pakde baitha hai aur dusre ka chhodne ka wait kar raha hai, par koi bhi chhodega nahi. Imagine karo 4 gaadiyan chauraha pe ghus gayi, sab apni lane block kar rahi hain, ab na koi aage ja sakta na peeche — yahi gridlock deadlock hai.

Edward Coffman ne 1971 me bola ki deadlock tabhi possible hai jab ye chaaron conditions ek saath sach hon: (1) Mutual Exclusion — resource share nahi ho sakta, ek time pe ek hi banda; (2) Hold and Wait — process ek resource pakde hue dusre ka wait kar raha hai; (3) No Preemption — OS zabardasti resource cheen nahi sakta, banda khud chhodega tabhi; (4) Circular Wait — ek ring ban jaati hai jahan P0 wait kare P1 ka, P1 wait kare P2 ka... aur last wala wait kare P0 ka.

Important baat: ye chaaron necessary hain, sufficient nahi. Matlab agar deadlock hua hai to chaaron zaroor honge — par chaaron hone ka matlab ye nahi ki deadlock pakka hoga. Arrow ek hi direction me chalta hai: deadlock ⇒ chaaron conditions. Isi liye deadlock prevention ka pura funda yahi hai — kisi ek condition ko tod do, deadlock impossible ho jaayega. Jaise global lock ordering lagao to circular wait toot jaata hai, ya "saare resource ek saath maango" karo to hold-and-wait khatam ho jaata hai (par phir starvation ka risk aata hai). Yaad rakho: ek link toda, chain tooti, gridlock khatam.

Test yourself — Operating Systems

Connections