Deadlock prevention — break each condition

4.2.20 · Coding › Operating Systems

KYA break kar rahe hain hum?

Deadlock Prevention = system ko aisa design karo ki IN MEIN SE EK BHI kabhi true na ho sake.

Figure — Deadlock prevention — break each condition

KAISE todein har condition ko

2. Hold and Wait todo

Worked example Technique: wait karte hue kabhi hold mat karo

Do designs hain:

All-or-nothing (sab kuch pehle hi maango): ek process ko start hone se pehle saare zaroorat wale resources request karne padte hain; ya toh atomically sab milenge, ya kuch nahi.
Release-before-request: ek process ko nayi resources maangne se pehle apne saare held resources release karne padte hain.

Kyun kaam karta hai: agar aap kabhi X hold karte hue Y ka wait nahi karte, toh condition 2 destroy ho jaati hai. Yeh step (all-or-nothing) kyun? Kyunki agar aapke paas sab kuch pehle se hai, toh aap hold karte hue kabhi wait nahi karte — wait karne ke liye kuch bacha hi nahi. Cost: low resource utilization (aap resources pehle hi grab kar lete ho aur unpe baithe rehte ho) aur starvation (bahut saare popular resources ki zaroorat wala process forever wait kar sakta hai).

3. No Preemption todo

4. Circular Wait todo ⭐ (the 80/20 winner)

Formula Resource types ki total ordering

Har resource type $R$ ko ek unique integer $f (R)$ assign karo. Rule: ek process resource $R_{j}$ tabhi request kar sakti hai jab $f (R_{j}) > f (R_{k})$ ho, har us $R_{k}$ ke liye jo woh currently hold kar rahi hai. $request allowed ⟺ f (R_{new}) > max_{R \in held} f (R)$

Derivation ki yeh cycles kyun khatam karta hai (proof by contradiction): Maan lo ek circular wait exist karta hai: $P_{0} \to P_{1} \to \dots \to P_{n - 1} \to P_{0}$ , jahan $P_{i}$ $R_{i}$ hold karta hai aur $R_{i + 1}$ ka wait karta hai (indices mod $n$ ). Rule ke mutabiq, kyunki $P_{i}$ $R_{i}$ hold karta hai aur $R_{i + 1}$ request kar raha hai: $f (R_{i}) < f (R_{i + 1}) for each i$ Cycle ke around chain karte hue: $f (R_{0}) < f (R_{1}) < \dots < f (R_{n - 1}) < f (R_{0})$ Isse milta hai $f (R_{0}) < f (R_{0})$ — ek contradiction. Isliye koi cycle exist nahi kar sakta. $■$

Yeh 80/20 technique kyun hai: yeh sasta hai (bas ek ordering impose karo), run-time pe future needs ki koi prediction nahi chahiye, aur real systems (jaise Linux kernel lock ordering) actually yahi use karte hain.

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho 4 bacche crayons share kar rahe hain. Jam tabhi hoga jab sab kuch ek saath galat ho jaaye: har crayon sirf ek baccha use kar sakta ho (1), har baccha ek crayon pakde hue doosra maang ke rota ho (2), kisi ko crayons chheenne ki ijazat na ho (3), aur woh waiting ke ek circle mein phans gaye hon (4). Ensure karne ke liye ki woh KABHI jam nahi honge, teacher bas ek rule hataa deti hai — sabse aasaan: "crayons order mein lene hain: pehle red, phir blue, phir green." Ab circle ho hi nahi sakta, kyunki uska matlab hoga red, red se pehle aata hai — jo bakwaas hai. Ek simple rule, zero jams forever.

Active Recall

Flashcards

Deadlock ke liye 4 Coffman conditions kya hain?

Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait — charon ek saath hold karni chahiye.

EK Coffman condition todne se deadlock prevent kyun hota hai?

Deadlock ke liye charon ka logical AND chahiye; agar koi bhi false hai, toh conjunction false hai, isliye deadlock impossible hai.

Mutual Exclusion kaise todein?

Resources ko shareable banao (spooling, read-only/lock-free access). Limited hai kyunki kuch resources intrinsically non-shareable hote hain.

Hold and Wait kaise todein?

Ya toh saare resources atomically pehle request karo, YA nayi request karne se pehle saare held resources release kar do.

Hold and Wait todne ki cost kya hai?

Low resource utilization (pehle reserve kiye resources idle baithe rehte hain) aur possible starvation.

No Preemption kaise todein?

Kisi process se resources forcibly le lo (preempt karo) jab usse kuch nahi mil raha; CPU/memory ke liye aasaan, printers/mutexes ke liye mushkil.

Circular Wait todne wala resource-ordering rule batao.

Har resource type ko ek unique number f(R) do; ek process R_new tabhi request kar sakti hai jab f(R_new) > f(R) ho har us R ke liye jo woh currently hold karti hai.

Resource ordering circular wait ko kyun khatam karta hai, prove karo.

Ek cycle se milega f(R0)<f(R1)<...<f(R0), yaani f(R0)<f(R0), jo ek contradiction hai; isliye koi cycle exist nahi kar sakti.

Kaun si Coffman condition todna usually impossible hota hai, aur kyun?

Mutual Exclusion — kuch resources (printer mid-job, write-lock) inherently non-shareable hote hain.

Prevention vs Avoidance?

Prevention structurally ek condition ko impossible banata hai (static, koi future info nahi chahiye). Avoidance sab conditions allow karta hai lekin har request ko run-time pe check karta hai safe state mein rehne ke liye (Banker's algorithm, max claims chahiye).

Practical 80/20 prevention technique kaun si hai aur kyun?

Circular Wait todna, resources ki total ordering se — sasta, static, koi future prediction nahi; real kernels mein use hota hai.

Connections

Deadlock — Coffman conditions
Deadlock avoidance — Banker's algorithm
Deadlock detection and recovery
Resource Allocation Graph
Mutex and Locks
Starvation vs Deadlock
Spooling and the printer