Deadlock detection and recovery — Hinglish notes

4.2.22 · Coding › Operating Systems

1. Deadlock kya hai (recap)

Char Coffman conditions sabhi hold karni chahiye: mutual exclusion, hold-and-wait, no preemption, aur circular wait. Detection assume karta hai ki hum inhe hone dete hain aur phir consequence dhundh te hain.

2. Detection — single instance per resource type

Hum ek Wait-For Graph (WFG) banate hain: Resource-Allocation Graph se resource nodes hatakar use collapse karte hain.

KYA: node = process. Edge $P_{i} \to P_{j}$ ka matlab hai $P_{i}$ uss resource ka intezaar kar raha hai jo currently $P_{j}$ ne hold kiya hua hai.
KAISE derive karein: RAG mein, agar $P_{i} \to R_{k}$ (request) aur $R_{k} \to P_{j}$ (allocation) hai, toh WFG mein $P_{i} \to P_{j}$ draw karo.

Figure — Deadlock detection and recovery

3. Detection — multiple instances per resource type

Data structures

$Available [1.. m]$ : $m$ resource types mein se har ek ke free instances.
$Allocation [n] [m]$ : process $i$ abhi kitna hold kar raha hai.
$Request [n] [m]$ : process $i$ abhi kya request kar raha hai (note: yeh request hai, Banker's ka "max need" nahi).

YEH KYU KAAM KARTA HAI: agar $R e q u es t_{i} \leq W or k$ hai, toh process $i$ jo maang raha hai woh mil sakta hai, woh run kar sakta hai, aur jo hold kar raha hai sab release kar dega — $A l l oc a t i o n_{i}$ pool mein wapas aayega. Hum optimistically resources unhe dete hain jo run kar sakte hain, free pool badhta jaata hai. Jis bhi process ko hum is tarah kabhi satisfy nahi kar sakte, woh genuinely stuck hai.

4. Detection kab run karein?

5. Recovery

Detect hone ke baad, kam se kam ek Coffman condition todo. Teen families:

Worked example Worked detection — multiple instances

3 types $A, B, C$ with totals; current state:

P	Allocation (A B C)	Request (A B C)
P0	0 1 0	0 0 0
P1	2 0 0	2 0 2
P2	3 0 3	0 0 0
P3	2 1 1	1 0 0

$A v ai l ab l e = (0, 0, 0)$ .

Step 1. $W or k = (0, 0, 0)$ . P0 ko $(0, 0, 0) \leq W or k$ chahiye? Haan. Kyun? Zero request hamesha pass hoti hai. P0 finish, $W or k + = (0, 1, 0) = (0, 1, 0)$ . Step 2. P2 ko $(0, 0, 0) \leq (0, 1, 0)$ chahiye? Haan. $W or k + = (3, 0, 3) = (3, 1, 3)$ . Step 3. P1 ko $(2, 0, 2) \leq (3, 1, 3)$ chahiye? Haan. $W or k + = (2, 0, 0) = (5, 1, 3)$ . Step 4. P3 ko $(1, 0, 0) \leq (5, 1, 3)$ chahiye? Haan. $W or k + = (2, 1, 1) = (7, 2, 4)$ . Sab finish → koi deadlock nahi. Sequence $⟨ P 0, P 2, P 1, P 3 ⟩$ .

Ab $R e q u es t_{P 2} = (0, 0, 1)$ change karo. Dobara: P0 finish → $W or k = (0, 1, 0)$ . P2 ko $(0, 0, 1) \leq (0, 1, 0)$ chahiye? Nahi (C: 1 ≤ 0 fail). P1 ko $(2, 0, 2)$ chahiye? Nahi. P3 ko $(1, 0, 0)$ chahiye? Nahi. Aur koi nahi chal sakta → P1, P2, P3 deadlocked hain. Yeh step kyun matter karta hai: C ki ek extra unit of demand jo kabhi free nahi hoti, poori chain jam kar deti hai.

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho char bachche hain, har ek ke paas do khilaunon ke ek-ek aadhe hisse hain jo woh swap karna chahte hain, aur har ek doosre ka intezaar kar raha hai ki pehle woh apna aadha de. Koi nahi chhodta, toh sab freeze ho jaate hain — yahi deadlock hai. Teacher (OS) ek checklist lekar ghoomti hai: "Kya koi bhi abhi jo khilaune khule pade hain unse finish kar sakta hai?" Agar haan, woh bachcha kheelta hai, phir apne khilaune box mein wapas daal deta hai taaki doosre le sakein — aur teacher chalti rehti hai. Agar woh ek aisi jagah pahunch jaaye jahan koi bachcha kabhi nahi khel sakta, woh stuck hain. Theek karne ke liye woh ya toh ek bachche ko quit karwa deti hai aur khilaune le leti hai (termination) ya ek khilauna chhin leti hai aur de deti hai (preemption) — woh bachcha choose karti hai jis ka kam se kam progress zaaya ho.

Flashcards

Single-instance system mein, deadlock ke liye kaun si graph condition necessary AND sufficient hai?

Wait-For Graph (WFG) mein ek cycle hona.

Multiple resource instances ke saath cycle deadlock ke liye sufficient kyun nahi hai?

Koi doosra holder ek aisa instance release kar sakta hai jo waiting process ko satisfy kar de, toh cycle sab ko stuck kiye bina resolve ho sakti hai. Tumhe finishing simulate karni padegi.

Deadlock detection algorithm aur Banker's algorithm mein key difference kya hai?

Detection actual current Request use karta hai (baad mein, optimistic); Banker's Need = Max − Allocation use karta hai (worst-case, pehle se, unsafe states prevent karne ke liye).

Detection mein, Allocation = 0 wale processes Finish = true se kyun shuru karte hain?

Woh koi resources hold nahi karte, isliye woh kisi circular-wait deadlock ka hissa nahi ho sakte aur kisi ko block nahi kar sakte.

Detection algorithm decide karta hai ki ek process finish kar sakti hai?

Agar uski current Request ≤ Work (componentwise) ho; phir woh run karti hai aur release karti hai, toh Work += Allocation_i.

Detection loop khatam hone ke baad, kaun deadlocked hai?

Har woh process i jiske liye Finish[i] = false hai.

Deadlocks allow karke phir detect karna, prevention se behtar kyun ho sakta hai?

Prevention/avoidance har request pe tax lagaata hai; agar deadlocks rare hain, toh occasional detection+recovery overall sasta padta hai.

Do main recovery strategies bataao.

Process termination (sab abort / ek-ek karke abort) aur resource preemption (checkpoint par rollback ke saath).

Preemption se recovery mein kaun se teen issues complicated karte hain?

Victim selection (cost minimize karo), rollback (ek safe checkpoint par), aur starvation (hamesha same victim mat chunna).

Jab ek hi process ko bar-bar victim choose kiya jaaye toh starvation kaise rokein?

Victim-cost function mein pehle se ki gayi rollbacks ki count include karo taaki ek chronic victim eventually protected ho jaaye.

V processes wale WFG mein cycle detection ki cost kya hai?

O(V²).

Connections

Resource Allocation Graph — WFG uska sirf-processes-wala projection hai.
Banker's Algorithm — same loop, lekin avoidance (Need) vs detection (Request).
Coffman Conditions — recovery inme se ek ko todkar kaam karta hai.
Checkpointing and Rollback — woh mechanism jo preemption recovery enable karta hai.
CPU Scheduling — victim selection mein priority/aging ideas reuse hoti hain.
Deadlock Prevention vs Avoidance — alternative philosophies.