Deadlock avoidance — Banker's algorithm — Hinglish notes

4.2.21 · Coding › Operating Systems

YEH algorithm exist kyun karti hai?

"Safe" kyun matter karta hai: Ek state safe hoti hai agar processes ka kam se kam ek ordering (ek safe sequence) exist kare jisme har process apni remaining needs le sake, completion tak run kare, aur sab kuch release kare. Unsafe ≠ deadlocked — iska bas matlab hai ki deadlock ho sakta hai. Banker kabhi unsafe state mein jaane se mana karta hai, isliye deadlock kabhi nahi ho sakta.

DATA STRUCTURES kya hain?

$n$ processes aur $m$ resource types ke liye:

KAISE: Safety Algorithm (scratch se derive kiya)

Hum jaanna chahte hain: "Current allocation ke hisaab se, kya sab log finish ho sakte hain?"

Step 0 — bookkeeping set up karo.

$W or k = A v ai l ab l e$ (free pool jo hum simulate karte waqt de sakte hain).
$F ini s h [i] = f a l se$ sab $i$ ke liye (abhi tak kisi ne finish nahi kiya).

$W or k$ ko $A v ai l ab l e$ se kyun shuru karein: jab tak koi finish nahi karta, sirf woh resources lend kar sakte hain jo abhi free hain.

Step 1 — ek aisi process dhundho jo abhi finish ho sake. $i$ dhundho jiske liye $F ini s h [i] = f a l se$ ho aur $N ee d [i] \leq W or k$ ho (componentwise).

Kyun: agar ek process ki remaining need free pool mein fit ho, toh hum imagine kar sakte hain ki use sab kuch de diya, use run hone diya, aur sab wapas le liya.

Step 2 — natak karo ki woh finish ho gayi aur resources wapas kar diye. $W or k = W or k + A l l oc a t i o n [i], F ini s h [i] = t r u e$

$A l l oc a t i o n [i]$ add kyun karein, $M a x [i]$ nahi: jab woh finish hoti hai toh woh sab kuch release karti hai jo usne hold kiya tha, jo $A l l oc a t i o n$ hai. Uski $N ee d$ step 1 mein $W or k$ se already cover ho gayi thi.

Step 3 — repeat karo jab tak koi aisi process na mile.

Step 4 — decide karo. Agar sab $i$ ke liye $F ini s h [i] = t r u e$ → state safe hai; jo order humne pick kiya woh ek safe sequence hai. Warna unsafe.

KAISE: Resource-Request Algorithm

Process $P_{i}$ request $R e q u es t_{i}$ karta hai.

Natak-phir-check kyun: grant safe hai ya nahi yeh jaanne ka ek hi tarika hai — resulting state ko dekho aur verify karo ki safe sequence abhi bhi exist karti hai.

Figure — Deadlock avoidance — Banker's algorithm

Worked Example 1 — Kya state safe hai?

3 resource types $A, B, C$ jinka total $= (10, 5, 7)$ hai.

Process	Allocation (A B C)	Max (A B C)
P0	0 1 0	7 5 3
P1	2 0 0	3 2 2
P2	3 0 2	9 0 2
P3	2 1 1	2 2 2
P4	0 0 2	4 3 3

Available $= T o t a l - \sum A l l oc a t i o n = (10, 5, 7) - (7, 2, 5) = (3, 3, 2)$ . Yeh step kyun? Free = total minus sab kuch jo held hai.

Need = Max − Allocation: P0 (7 4 3), P1 (1 2 2), P2 (6 0 0), P3 (0 1 1), P4 (4 3 1).

Ab Safety run karo $W or k = (3, 3, 2)$ ke saath:

$N ee d_{P 1} = (1, 2, 2) \leq (3, 3, 2)$ ✓ → P1 finish, $W or k = (3, 3, 2) + (2, 0, 0) = (5, 3, 2)$ . Alloc P1 kyun add kiya? Woh apne held resources release karta hai.
$N ee d_{P 3} = (0, 1, 1) \leq (5, 3, 2)$ ✓ → $W or k = (5, 3, 2) + (2, 1, 1) = (7, 4, 3)$ .
$N ee d_{P 0} = (7, 4, 3) \leq (7, 4, 3)$ ✓ → $W or k = (7, 4, 3) + (0, 1, 0) = (7, 5, 3)$ .
$N ee d_{P 2} = (6, 0, 0) \leq (7, 5, 3)$ ✓ → $W or k = (7, 5, 3) + (3, 0, 2) = (10, 5, 5)$ .
$N ee d_{P 4} = (4, 3, 1) \leq (10, 5, 5)$ ✓ → $W or k = (10, 5, 7)$ . Sab finish ho gaye.

Safe sequence: $⟨ P 1, P 3, P 0, P 2, P 4 ⟩$ . State SAFE hai. ✅

Worked Example 2 — Kya request grant karni chahiye?

Example 1 ki state se, $P 1$ request $R e q u es t_{1} = (1, 0, 2)$ karta hai.

$(1, 0, 2) \leq N ee d_{P 1} (1, 2, 2)$ ? ✓
$(1, 0, 2) \leq A v ai l ab l e (3, 3, 2)$ ? ✓
Pretend-grant:
- $A v ai l ab l e = (3, 3, 2) - (1, 0, 2) = (2, 3, 0)$
- $A l l o c_{P 1} = (2, 0, 0) + (1, 0, 2) = (3, 0, 2)$
- $N ee d_{P 1} = (1, 2, 2) - (1, 0, 2) = (0, 2, 0)$

Safety run karo $W or k = (2, 3, 0)$ ke saath:

P1 $N ee d (0, 2, 0) \leq (2, 3, 0)$ ✓ → $W or k = (2, 3, 0) + (3, 0, 2) = (5, 3, 2)$
P3 $(0, 1, 1) \leq (5, 3, 2)$ ✓ → $W or k = (7, 4, 3)$
P0 $(7, 4, 3) \leq (7, 4, 3)$ ✓ → $W or k = (7, 5, 3)$ ... P2, P4 follow karte hain.

Safe sequence $⟨ P 1, P 3, P 0, P 2, P 4 ⟩$ exist karti hai → GRANT. ✅ Natak karne ke baad bhi verify kyun karte hain? Kyunki availability kam ho gayi; hume confirm karna hai ki sab abhi bhi finish ho sakte hain.

Worked Example 3 — Ek request jo refuse ho jaati hai

Example 1 se, maan lo $P 4$ $(3, 3, 0)$ request karta hai.

$\leq N ee d_{P 4} (4, 3, 1)$ ? ✓
$\leq A v ai l ab l e (3, 3, 2)$ ? ✓ → natak karo: $A v ai l ab l e = (0, 0, 2)$ .

Safety run karo $W or k = (0, 0, 2)$ ke saath: scan karo needs P0(7 4 3)✗, P1(1 2 2)✗, P2(6 0 0)✗, P3(0 1 1)✗ (B short hai), P4(1 0 1)✗. Koi bhi process proceed nahi kar sakti → UNSAFE → rollback, P4 wait karta hai. ❌ Ek aisi request refuse kyun karein jo "fit" hoti hai? $A v ai l ab l e$ mein fit hona kaafi nahi — resulting state mein koi safe sequence nahi hai.

Common mistakes

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho ek toy-lending library hai. Har bachcha librarian ko batata hai ki use ek saath zyada se zyada kitne toys chahiye honge. Zyada toys dene se pehle, librarian sochti hai: "Agar main yeh abhi deti hoon, toh kya main phir bhi sure kar sakti hoon ki koi ek bachcha apne saare toys le le, khel le, aur wapas kar de, phir agla bachcha, aur aise sab khush ho jayein?" Agar haan, toh woh deti hai. Agar ek bhi arrangement impossible ho, toh woh kehti hai "ruko." Kyunki woh hamesha ek escape plan rakhti hai, koi bhi bachcha kabhi hamesha ke liye stuck nahi hota.

Flashcards

Safe state kya hota hai?

Woh state jisme kam se kam ek ordering (safe sequence) exist kare jisme har process apni remaining needs le sake, finish kare, aur resources release kare.

Need ka formula?

Need[i][j] = Max[i][j] − Allocation[i][j].

Safety Algorithm mein Work ko kya initialize kiya jaata hai?

Work = Available (abhi free resources).

Simulation mein jab ek process "finish" hoti hai, toh Work mein Max add hota hai ya Allocation?

Allocation (jo usne actually hold kiya tha); uski Need Work se already cover ho gayi thi.

Kya unsafe matlab deadlock hai?

Nahi — unsafe matlab deadlock possible hai, yeh nahi ki woh ho chuka hai.

Resource request ke liye teen checks kya hain?

(1) Request ≤ Need, warna error; (2) Request ≤ Available, warna wait; (3) pretend-allocate karke Safety run karo; grant tabhi karo jab safe ho.

Banker's algorithm ko detection ke comparison mein kya extra knowledge chahiye?

Har process ki maximum resource demand (Max) pehle se declared honi chahiye.

Table se Available kaise compute karte hain?

Available = Total resources − sab Allocation rows ka sum.

Jab P4 (3,3,0) request karta hai aur state unsafe ho jaati hai, toh kya hota hai?

Pretend-allocation rollback karo aur P4 ko wait karwao.

Connections

Deadlock — Coffman conditions
Deadlock detection and recovery
Deadlock prevention
Resource Allocation Graph
Process scheduling
Semaphores and mutual exclusion