Deadlock — four necessary conditions (Coffman)

4.2.19 · Coding › Operating Systems

KIYA hai deadlock?

Key word hai circular waiting on each other. Agar unme se ek bhi process ko set ke bahar se eventually apna resource mil sakta, toh woh true deadlock nahi hai — woh sirf ek delay hai.

KYUN chahiye chaar conditions?

1971 mein Edward Coffman ne pucha: kin circumstances mein deadlock possible bhi hota hai? Unhone four necessary conditions dhundhe. "Necessary" ka matlab hai:

$Deadlock ⟹ (C_{1} \land C_{2} \land C_{3} \land C_{4})$

Toh agar koi ek bhi condition false ho, deadlock ho hi nahi sakta. Yahi WHY hai har deadlock-prevention strategy ke peeche: ek condition todo aur deadlock impossible ho jaata hai.

Chaar Coffman Conditions

HOW har condition contribute karti hai (gridlock scratch se derive karo)

Deadlock ko step by step build karo aur dekho har condition kahan use hoti hai:

Process $P_{0}$ resource $R_{0}$ grab karta hai. Yeh possible kyun hai? Kyunki $R_{0}$ non-sharable hai — Mutual Exclusion ek owner ko baaki sab ko lock out karne deta hai.
$P_{0}$ ab $R_{1}$ chahta hai lekin $R_{0}$ hold kiye rakhta hai. Woh $R_{0}$ kyun rakhta hai? Hold and Wait — woh jo hold kar raha hai use release nahi karta jabki aur maangta hai.
Meanwhile $P_{1}$ $R_{1}$ hold kiye baitha hai aur $R_{0}$ chahta hai. Koi doosre ki resource grab nahi kar sakta. OS $P_{1}$ se $R_{1}$ kyun nahi cheen sakta? No Preemption — resources sirf voluntarily release hote hain.
Ab $P_{0} \to P_{1} \to P_{0}$ : wait ka ek closed loop. Yeh fatal kyun hai? Circular Wait — dependency graph mein ek cycle hai, isliye "main unke khatam hone ka wait karunga" wali reasoning apni hi tail ko chase karti rehti hai forever.

Koi ek bhi link hatao aur chain toot jaati hai:

No mutual exclusion → dono $R_{0}, R_{1}$ share karein → koi wait nahi.
No hold-and-wait → $P_{0}$ ko $R_{1}$ maangne se pehle $R_{0}$ drop karna hoga → hold-while-waiting nahi.
Preemption allowed → OS $P_{1}$ se $R_{1}$ le leta hai, $P_{0}$ ko de deta hai → loop khatam.
No circular wait (e.g. resources order karo, increasing order mein request karo) → koi cycle ban hi nahi sakti.

Figure — Deadlock — four necessary conditions (Coffman)

Worked Examples

Worked example Example 1 — Do mutexes, classic deadlock

Threads A aur 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? Haan — mutexes non-sharable hote hain. Yeh step kyun? Ek lock by definition doosron ko exclude karta hai.
Hold & wait? Haan — A, L1 hold kiye baitha hai jabki L2 ka wait kar raha hai. Kyun? Usne L1 kabhi release nahi kiya.
No preemption? Haan — tum doosre thread ke mutex ko jabardasti unlock nahi kar sakte. Kyun? OS mutexes nahi yanks karta.
Circular wait? $A \to B \to A$ . Kyun? A, L2 (jo B hold kiye hai) ka wait kar raha hai, B, L1 (jo A hold kiye hai) ka wait kar raha hai. Charon → deadlock. Fix: ek global lock order laago — hamesha L1 pehle lock karo L2 se. Yeh circular wait khatam kar deta hai.

Recall Feynman: 12-saal ke bachche ko samjhao

Socho ek square hallway mein 4 bacche hain. Har bachcha apne saamne wale darwaze ka knob pakad leta hai aur chodega nahi jab tak woh agla darwaza bhi nahi khol sakta — lekin us agle darwaze ka knob already aage wale bachche ne pakad rakha hai. Ab sab ek knob pakde baitha hai, aage wale ka wait kar raha hai, ek circle mein. Koi nahi chodega (no preemption), koi knob share nahi kar sakta (mutual exclusion), aur sab ek ring mein wait kar rahe hain (circular wait) jabki pakde bhi hain (hold-and-wait). Unke phansne ke liye charon silly rules ek saath true honi chahiye. Sirf ek rule badlo — jaise "agar dono darwaze ek saath nahi khul sakte toh chod do" — aur jam clear ho jaata hai.

Forecast-then-Verify checkpoint

Aage padhne se pehle predict karo: Agar hum saare resources preemptible bana dein, tab bhi kya deadlock ho sakta hai? → Verify karo: Nahi. No Preemption hatane se condition 3 false ho jaati hai, isliye necessary set incomplete hai ⇒ deadlock impossible (haalaanki livelock aa sakta hai).

Flashcards

"Deadlock ke liye necessary condition" ka formal matlab kya hota hai?

Deadlock ⇒ (charon conditions hold hoti hain); equivalently, agar koi ek condition false ho, toh deadlock ho hi nahi sakta.

Chaar Coffman conditions list karo.

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

"Charon conditions present hain" deadlock guarantee kyun nahi karta?

Yeh necessary hain lekin sufficient nahi; deadlock ke liye bura interleaving / resource-allocation graph mein actual cycle bhi chahiye (single-instance case).

Global lock ordering enforce karna kaun si condition todata hai?

Circular wait.

"Saare resources ek saath request karo" kaun si condition todata hai, aur iska downside kya hai?

Hold and wait; downside yeh hai ki poor utilization aur possible starvation/livelock.

Circular wait precisely define karo.

Ek set {P0..Pn-1} jahan har Pi ek aisi resource ka wait karta hai jo P(i+1 mod n) hold kiye hai, ek closed cycle banate hue.

Deadlock context mein mutual exclusion kya hota hai?

Kam se kam ek resource non-sharable hai — sirf ek process ek baar mein use hold kar sakti hai.

Deadlock aur livelock mein kya farq hai?

Deadlock = processes freeze hain, koi state change nahi; livelock = processes state change karte rehte hain (e.g. retry karte hain) lekin koi progress nahi hoti.

Dining philosophers problem mein ek philosopher ko right-fork-first uthwana kaise help karta hai?

Yeh circular wait asymmetry introduce karke todta hai, taaki koi uniform directed cycle ban hi na sake.

Agar resources OS dwara preemptible hon, toh kaun si Coffman condition fail hoti hai?

No Preemption fail hoti hai (condition 3).

Connections

Resource-Allocation Graph — cycle detection circular wait ko visible banata hai.
Deadlock Prevention — har strategy ek Coffman condition negate karti hai.
Deadlock Avoidance — Banker's Algorithm — conditions forbid karne ki jagah system ko safe states mein rakhta hai.
Deadlock Detection and Recovery — deadlock hone do, phir usse todo (aksar preemption ke zariye).
Mutual Exclusion aur Semaphores and Mutexes — jahan condition 1 aati hai.
Dining Philosophers Problem — canonical illustration.
Starvation and Livelock — failure modes jin mein tum deadlock prevent karte waqt trade ho jaate ho.