Deadlock detection and recovery: Question bank — Hinglish deep dive

4.2.22 · D5 · Coding › Operating Systems › Deadlock detection and recovery

Definition Notation — is page par use kiya gaya har symbol, simple shabdon mein

Taaki ye page self-contained rahe, test se pehle poora vocabulary yahan diya ja raha hai:

$n$ ::: system mein processes ki sankhya (jobs). Socho "room mein kitne bachche hain." Is poore page par $n$ = number of processes.
$m$ ::: resource types ki sankhya (printer, tape drive, memory block, …). Har type ke kai identical copies ho sakte hain = instances. Kyunki $m$ types hain, isliye neeche ke zyaadatar quantities $m$ numbers ki lists hain, ek har type ke liye.
$A l l oc a t i o n_{i}$ ::: length $m$ ki ek list — abhi is waqt process $i$ ke paas har type ke kitne instances hain.
$R e q u es t_{i}$ ::: length $m$ ki ek list — process $i$ abhi is waqt kya maang raha hai (uski current maang, lifetime maximum nahi).
$M a x_{i}$ aur $N ee d_{i} = M a x_{i} - A l l oc a t i o n_{i}$ ::: ye Banker's Algorithm se belong karte hain. $M a x_{i}$ = $i$ ko kabhi bhi zyaada se zyaada kitna chahiye ho sakta hai; $N ee d_{i}$ = us worst case mein se kya bacha hai. Detection inhe use nahi karta — yahi poora trap hai.
$A v ai l ab l e$ ::: length $m$ ki ek list — har type ke free instances jo pool mein unused pade hain.
$W or k$ ::: $A v ai l ab l e$ ki ek scratch copy jo badhti hai jab khatam hone wale processes apne resources wapas dete hain. Ye "simulation mein ab tak kitna free hai" counter hai.
$F ini s h [i]$ ::: ek true/false flag — kya simulation mein process $i$ ko finish karne layak dikhaya ja chuka hai?
$W F G$ (Wait-For Graph) ::: ek picture jahan har node ek process hai aur ek arrow $P_{i} \to P_{j}$ ka matlab hai " $P_{i}$ ek aisi resource ka wait kar raha hai jo $P_{j}$ ke paas hai." Resource Allocation Graph ko collapse karke banaya jaata hai (resource nodes hata do).

Figure — Deadlock detection and recovery

Bucket lagbhag khali shuru hoti hai ( $W or k = A v ai l ab l e$ ). Jab bhi koi process $R e q u es t_{i} \leq W or k$ pass karta hai, woh finish hota hai aur apna $A l l oc a t i o n_{i}$ bucket mein daal deta hai, toh level upar uthta hai. Jaise level badhta hai, requests jo "bahut badi" thi ek pal pehle ab fit ho jaati hain — yahi snowball hai. Agar kisi point par koi bhi remaining process ki request current level pe fit nahi hoti aur level badhna band ho jaaye, toh woh leftover processes kabhi bhi satisfy nahi ho saktieen → woh deadlocked set hain (figure mein coral color mein neeche dikhaye gaye hain).

True or false — justify

Wait-For Graph mein cycle hona hamesha deadlock ka matlab hai.

Sirf single-instance system mein. Ek type ke multiple instances hone par koi doosra holder ek instance release kar sakta hai jo kisi waiter ko free kar de, isliye cycle simulation confirm kiye bina dissolve ho sakti hai (dekho finish-snowball figure s02).

Agar detection loop mein har

F ini s h [i] = t r u e

ho jaaye, toh system abhi deadlock-free hai.

True — ek valid finish order exist karta hai, isliye har process apna current

R e q u es t_{i}

obtain kar sakta hai, run kar sakta hai, aur release kar sakta hai; koi permanently stuck nahi hai.

Deadlock detection guarantee karta hai ki koi process future mein kabhi deadlock nahi hoga.

False. Detection current state ka ek snapshot hai; baad mein aane wale requests ke baare mein kuch nahi bolti. Dekho Deadlock Prevention vs Avoidance — sirf avoidance/prevention aage dekhta hai.

Jo process zero resources hold kar raha hai woh bhi deadlock mein part ho sakti hai.

False.

A l l oc a t i o n_{i} = 0

hone par woh

F ini s h = t r u e

se shuru hota hai: woh kuch nahi hold karta jiska koi wait kare, isliye woh circular-wait chain mein nahi ho sakta.

Detection zyaada baar chalana strictly better hai kyunki deadlocks jaldi pakad mein aate hain.

False. Detection ka cost

O (m \cdot n^{2})

hai (Why section mein justified hai); har ungrantable request par chalana bahut bada overhead hai. Deadlock ka rare hona hi wahi reason hai kyun hum delay tolerate karte hain.

Saare deadlocked processes ko abort karna sabse safe recovery hai kyunki yeh definitely kaam karta hai.

Yeh deadlock toh definitely tod deta hai, lekin "safest" galat hai — yeh sabse zyaada kaam waste karta hai. Ek-ek karke abort karna kam waste karta hai lekin detector ko baar baar chalana padta hai.

Detection algorithm aur Banker's safety check ek hi algorithm hain.

False. Loop ka shape match karta hai, lekin detection actual current

R e q u es t_{i}

test karta hai (backward-looking) jabki Banker's

N ee d_{i} = M a x_{i} - A l l oc a t i o n_{i}

test karta hai (worst-case, forward-looking).

Resource ko preempt karne ke liye hamesha rollback zaroori hai.

Essentially true: victim ne resource R ko use karte huye beech mein kho diya, isliye woh consistent rehne ke liye ek safe checkpoint tak rollback karna padega (ya restart karna padega) — tum sirf continue nahi kar sakte jaise kuch hua hi nahi.

Agar deadlock detection "no deadlock" report kare, toh CPU utilization high hogi.

False. Utilization kai reasons se low ho sakti hai (I/O waits, idle jobs). Low utilization sirf detection chalane ka trigger hai, deadlock ka synonym nahi.

Spot the error

"Multiple instances ke saath, hum Wait-For Graph mein cycle dhundh kar deadlock detect karte hain."

Error: WFG cycles sirf single-instance systems decide karte hain. Multiple instances ke liye finish-simulation chahiye, kyunki wahan cycle necessary hai par sufficient nahi.

"Detection mein hum

N ee d_{i} = M a x_{i} - A l l oc a t i o n_{i}

use karte hain dekhhne ke liye ki kaun finish kar sakta hai."

Error: yeh Banker's hai, jo worst-case leftover need use karta hai. Detection actual current

R e q u es t_{i}

use karta hai, koi maximum nahi.

R e q u es t_{i} \leq W or k

ka matlab hai process

i

finish ho gaya, isliye

W or k

A l l oc a t i o n_{i}

mein add karo."

Do errors hain: iska matlab hai

i

finish kar sakta hai (kiya nahi), aur hum

A l l oc a t i o n_{i}

W or k

mein add karte hain (jo woh hold karta hai usse reclaim karo), ulta nahi.

"Kyunki saare char Coffman conditions hold karni chahiye, mutual exclusion todna standard recovery hai."

Error: char conditions hain mutual exclusion (ek resource share nahi ho sakta), hold-and-wait, no-preemption, aur circular-wait — aur mutual exclusion usually intrinsic hoti hai (ek printer share nahi ho sakta), isliye recovery normally no-preemption (preempt) ya circular-wait (abort) todti hai. Dekho Coffman Conditions.

"Victim selection sirf woh process choose karti hai jiske paas sabse kam resources hain taaki cleanup fast ho."

Oversimplified/wrong. Cost mein priority, ab tak run kiya time, held resources, affected processes, aur — bahut zaroori — pehle ke rollbacks ki sankhya shaamil hoti hai taaki starvation na ho.

"Detector hume exactly batata hai ki kis request ki wajah se deadlock hua."

Error: agar detection har request par nahi balki periodically chale, toh deadlock banne ke baad se kaafi requests aa chuki hain, isliye generally culprit request pinpoint nahi ki ja sakti.

"Safe state aur deadlock-free snapshot ek hi cheez hain."

Error: safe (Banker's) ka matlab hai ki saari future worst-case demands (

N ee d_{i}

) ke liye safe sequence exist karta hai; deadlock-free detection ka matlab sirf yeh hai ki current

R e q u es t_{i}

sab satisfy ho sakti hain. Safe ⊂ deadlock-free.

Why questions

Zero request hamesha

R e q u es t_{i} \leq W or k

test kyun pass karta hai?

Kyunki

\leq

component-wise hai (upar define kiya gaya hai):

(0, 0, \dots) \leq W or k

kisi bhi non-negative

W or k

ke liye hold karta hai kyunki har entry

0 \leq W or k [k]

hoti hai. Jo process kuch nahi maang raha usse kuch grant nahi karna padta, isliye woh immediately finish ho jaata hai aur apni holdings release kar deta hai. Example with

m = 3

: P0 with

R e q u es t = (0, 0, 0)

tab bhi pass karta hai jab

W or k = (0, 0, 0)

ho.

Hum directly deadlock prove karne ki jagah jo bhi run kar sake usse optimistically grant kyun karte hain?

Ek toy example with

m = 3

types: pool khali shuru hoti hai

(0, 0, 0)

, lekin P0 ke paas

(0, 1, 0)

hai aur woh kuch nahi maang raha. P0 ko grant karo → woh finish hota hai →

W or k

badhkar

(0, 1, 0)

ho jaata hai. Ab jo process doosre type ki ek unit chahti thi woh run kar sakti hai, apna saman wapas karti hai, aur pool snowball karta hai. Jo bhi process pool ke badhna band hone ke baad bhi unsatisfiable hai woh genuinely, permanently stuck hai — yahi tumhara deadlocked set hai. (Dekho figure s02.)

Victim ki cost function mein rollbacks ki sankhya kyun include karte hain?

Starvation rokne ke liye. Socho cost hamesha sabse saste victim ko choose karti hai; agar process X hamesha sabse sasta hai, toh woh preempt hoti hai, rollback hoti hai, preempt hoti hai, rollback hoti hai… forever aur kabhi finish nahi karti. "X ko kitni baar pehle rollback kiya ja chuka hai?" add karne se X expensive ho jaata hai, isliye eventually koi aur choose hota hai aur X complete kar paata hai.

Single-instance case

O (n^{2})

kyun cost karta hai jabki multiple instances

O (m \cdot n^{2})

kyun?

Single instance = Wait-For Graph par plain cycle detection, jiske nodes

n

processes hain; DFS har node aur edge visit karta hai, aur

n

nodes aur

n^{2}

possible edges tak ke saath woh

O (n^{2})

hai (yahan

n

= number of processes, wohi

n

jo is poore page par use kiya gaya hai). Multiple instances: finish-loop ka har pass saare

n

processes scan karta hai, aur har ek ke liye

R e q u es t_{i} \leq W or k

mein $m$ resource components compare karta hai — yeh har pass mein

m \cdot n

kaam hai. Worst case mein har pass mein sirf ek naya process finish hota hai, isliye

n

passes tak lagte hain →

m \cdot n \times n = O (m \cdot n^{2})

Jab deadlocks rare hain toh prevention ki jagah "detect and recover" kyun choose karte hain?

Prevention/avoidance har ek resource request par ek check chalata hai — ek permanent tax jo ek second mein lakhon baar pay hota hai. Detect-and-recover har request par kuch nahi pay karta aur expensive detector sirf occasionally chalata hai (e.g. jab CPU utilization girta hai). Agar deadlocks almost kabhi nahi hote, toh kabhi kabhi bada bill constant chhote bill se kaafi sasta hai.

Preemption recovery rollback skip karke baad mein victim ko resume kyun nahi kar sakta?

Isko step by step dekho: process X resource R use karte huye beech mein file likhne mein tha jab R chheen liya gaya. X ki internal state (variables, adha likha data) assume karti hai ki woh abhi bhi R hold kar raha hai aur uska kaam intact hai. Agar tum sirf R wapas do aur resume karo, toh X corrupt state se continue karta hai. Iske bajaye usse ek consistent checkpoint par wapas jaana hoga jo R ke use hone se pehle liya gaya tha, aur wahan se redo karna hoga.

Edge cases

Agar

A v ai l ab l e

shuru mein sab zeros ho toh kya hoga?

Detection phir bhi kaam karta hai:

W or k

(0, 0, \dots)

se shuru hota hai, isliye sirf woh processes jo zero

R e q u es t

rakhti hain (ya jinhe kisi finisher ke reclaimed resources se satisfy kiya ja sake) start kar sakti hain. Poora snowball free instances se nahi balki reclaimed

A l l oc a t i o n

se bootstrap hota hai.

Agar har process resources hold kare lekin har

R e q u es t_{i}

zero ho toh kya?

Koi deadlock nahi — har process ko aur kuch nahi chahiye, isliye sab immediately test pass kar lete hain aur finish ho jaate hain; unhe trap karne ke liye koi circular wait nahi hai.

Kya WFG cycle appear ho sakta hai phir bhi snapshot deadlock-free ho?

Haan — lekin sirf multiple instances ke saath. Snowball kisi teesre holder ko finish karne de sakta hai aur ek aisa instance release ho sakta hai jo loop mein kisi ek process ko satisfy kare, cycle todo. Yahi reason hai kyun single-instance WFG cycles sufficient hain par multi-instance wale nahi: graph spare copies ki information kho deta hai.

Ek process kisi resource ke itne instances maange jo system mein kabhi nahi honge — deadlock hai?

Nahi, yeh deadlock nahi hai (mutually-waiting processes ka koi set nahi hai); yeh ek unsatisfiable request / error hai. Deadlock ke liye do ya zyaada processes ke beech circular waiting chahiye.

Detection chalti hai, koi finish nahi kar pa raha, lekin ek process voluntarily release karne wali thi — kya yeh sach mein deadlocked hai?

Snapshot ke hisaab se yeh deadlocked hai. Detection frozen state judge karta hai; ek release jo abhi hua nahi hai woh visible nahi hai, jo snapshot-based detection ki ek limitation hai, rule ka false positive nahi.

Char mein se sirf teen Coffman conditions hold karein — kya deadlock ho sakta hai?

Nahi. Saari char (mutual exclusion, hold-and-wait, no-preemption, circular-wait) necessary hain; koi ek bhi todo aur deadlock impossible hai — yahi exactly recovery ka kaam karne ka tarika hai.

Recall Ek-line self-test

Do verdict rules ::: Single instance: WFG mein cycle necessary AND sufficient hai. Multiple instances: finish-simulation chalao; baaki $F ini s h [i] = f a l se$ processes deadlocked hain. Do recovery families ::: Process termination (sab abort karo / ek-ek abort karo, detector dobara chalate huye) aur resource preemption (victim choose karo → checkpoint par rollback karo → starvation rokne ke liye rollbacks count karo).