Deadlock avoidance — Banker's algorithm: Question bank

4.2.21 · D5 · Coding › Operating Systems › Deadlock avoidance — Banker's algorithm

Shuru karne se pehle, in traps ki foundation mein jo vocabulary hai use refresh karo: Deadlock — Coffman conditions, Deadlock prevention, Deadlock detection and recovery, Resource Allocation Graph, aur Process scheduling.

True or false — justify karo

Unsafe state aur deadlocked state ek hi cheez hai.

False — unsafe state ka sirf matlab hai ki koi safe sequence abhi guaranteed nahi hai, isliye deadlock ho sakta hai avoid karna impossible; processes abhi bhi sab chal rahi ho sakti hain aur lucky order mein requests aane par khatam bhi ho sakti hain.

Har safe state abhi deadlock avoid karta hai.

True — "safe" ka matlab hai ki kam se kam ek aisa ordering exist karta hai jisme har process finish ho jaye, toh by definition is waqt koi permanently stuck nahi hai.

Ek deadlocked state hamesha unsafe hota hai.

True — agar processes already deadlocked hain, toh koi bhi ordering unhe sab finish nahi karne deti, jo ki exactly unsafe ki definition hai (unsafe broader set hai; deadlocked uska ek subset hai).

Banker's algorithm bina har process ki maximum demand jaane run kiya ja sakta hai.

False — poora method

N ee d = M a x - A l l oc a t i o n

par tikka hai;

M a x

ke bina tum

N ee d

compute nahi kar sakte aur check nahi kar sakte ki koi process abhi finish ho sakti hai ya nahi, isliye avoidance possible hi nahi hai.

Agar ek state safe hai, toh koi bhi request grant karna use safe rakhta hai.

False — grant

A v ai l ab l e

ko reduce karta hai aur ek hi safe sequence ko destroy kar sakta hai; isliye precisely yahi reason hai ki har request ke baad pretend state par Safety Algorithm dobara run karna zaroori hai.

Ek single safe sequence state ko safe declare karne ke liye kaafi hai.

True — safety ke liye sirf itna chahiye ki kam se kam ek ordering kaam kare; algorithm ek poori sequence complete hote hi ruk jaata hai aur sabko dhundhna zaroori nahi.

Do alag safe sequences do alag states describe karte hain.

False — ek hi state kai valid safe sequences admit kar sakti hai; yeh simply identical allocation ke liye alternative escape plans hain, alag systems nahi.

Banker's algorithm ek Coffman condition todne se deadlock prevent karta hai.

False — yeh prevention hai; Banker's avoidance hai: yeh Deadlock — Coffman conditions charon ko intact rakhta hai aur instead koi bhi aisi request refuse karta hai jo unsafe state ki taraf le jaaye.

Agar $A v ai l ab l e$ zero vector hai, toh state zaroor unsafe hogi.

False — agar kisi process ka

N ee d

bhi zero hai (use apna

M a x

already mil chuka hai), toh woh finish ho sakti hai aur resources release kar sakti hai, pool restart ho jaata hai; safety poori configuration par depend karti hai, sirf free pool par nahi.

Error dhundho

Ek student likhta hai: "Jab process $P_{i}$ simulation mein finish ho, toh $W or k = W or k + M a x [i]$ karo."

Wrong resource return ho raha hai — ek process sirf

A l l oc a t i o n [i]

hi hold karti thi,

M a x [i]

nahi; uska extra

N ee d

"kya yeh finish ho sakti hai?" test mein

W or k

se temporarily borrow kiya gaya tha, isliye

M a x

return karna aisi resources invent kar deta hai jo kabhi thi hi nahi.

Ek student request check karta hai: "Agar $R e q u es t_{i} \leq A v ai l ab l e$ , toh ise immediately grant karo."

Do errors hain — yeh

R e q u es t_{i} \leq N ee d_{i}

safety/validity check skip karta hai, aur resulting state par Safety Algorithm dobara run karna bhi skip karta hai;

A v ai l ab l e

mein fit ho jaana yeh nahi batata ki sab baad mein finish ho payenge ya nahi.

Ek student vectors compare karta hai: " $N ee d_{i} \leq W or k$ agar $N ee d_{i}$ ka sum $\leq$ $W or k$ ke sum se ho."

Wrong comparison — yahan

\leq

componentwise hai: yeh har ek resource type ke liye alag se hold karna chahiye. Ek process agar ek bhi single resource ki ek unit short hai toh proceed nahi kar sakti, totals chahe kuch bhi ho.

Ek student Safety Algorithm ki shuruat mein $W or k = 0$ set karta hai.

Wrong initialization —

W or k

A v ai l ab l e

se start hota hai, jo ki abhi actually free resources hain; zero se start karna pretend karta hai ki kuch bhi kabhi lend nahi kiya ja sakta, jo ki pehla hi "kya koi process finish ho sakti hai?" test tod deta hai.

Ek student conclude karta hai "request refuse ho gayi, toh system deadlocked hai."

Refusal aur deadlock mein confusion — refusal ka matlab hai ki grant unsafe hoga, isliye

P_{i}

sirf wait karta hai; current state unchanged hai aur abhi bhi safe hai, koi deadlock nahi hua.

Ek student compute karta hai $N ee d_{i} = A l l oc a t i o n_{i} - M a x_{i}$ .

Subtraction ulta hai —

N ee d = M a x - A l l oc a t i o n

(ceiling minus jo already hold kar rahe ho). Ulta karne par negative numbers aate hain aur yeh galat bata deta hai ki har process aur kitna demand kar sakta hai.

Ek student kehta hai " $R e q u es t_{i} > N ee d_{i}$ ka matlab sirf yeh hai ki $P_{i}$ queue mein wait karta hai."

Wrong handling — apne declared

M a x

se zyada maangna ek violation/error hai, resource shortage nahi; ise bug ki tarah flag karna chahiye, legitimate wait ki tarah politely queue nahi karna chahiye.

Why questions

Banker's algorithm safety verify karne ke liye pretend grant kyun karta hai, current state check karne ki jagah?

Kyunki khatre sirf resulting state mein dikhti hai — grant

A v ai l ab l e

reduce karta hai aur

A l l oc a t i o n

aur

N ee d

change karta hai, isliye tumhe post-grant configuration inspect karni padti hai yeh jaanne ke liye ki koi safe sequence abhi bhi survive karti hai ya nahi.

Banker's algorithm ko "conservative" kyun kehte hain?

Kyunki yeh kuch aise requests refuse karta hai jo practically kabhi deadlock nahi banate; iske liye sirf itna zaroori hai ki ek safe sequence guaranteed ho, isliye yeh caution ki taraf error karta hai aur resource utilization reduce kar sakta hai.

$M a x$ pehle se declare kyun karni chahiye, processes ke run hote hue discover kyun nahi?

Algorithm worst-case future demand ke baare mein reason karta hai guarantee karne ke liye ki ek escape plan exist karta hai; ceiling jaane bina yeh future ki aisi request rule out nahi kar sakta jo system ko trap kar de.

$A l l oc a t i o n [i]$ ( $N ee d [i]$ nahi) ko $W or k$ mein add karna ek finish hoti process ko correctly model kyun karta hai?

Ek finish hoti process exactly wahi release karti hai jo usne physically hold kiya tha, jo ki

A l l oc a t i o n [i]

hai; uska

N ee d

temporarily

W or k

se borrow kiya gaya tha use finish hone dene ke liye, isliye sirf

A l l oc a t i o n

return karna bookkeeping balanced rakhta hai.

Critical systems mein avoidance ko detection-and-recovery se zyada prefer kyun kiya jaata hai?

Avoidance guarantee karta hai ki deadlock kabhi hoga hi nahi, isliye koi costly rollback, victim termination, ya lost work nahi; Deadlock detection and recovery deadlock pehle hone deta hai aur phir use fix karne ki cost pay karta hai.

Banker's algorithm aisi resources handle kyun nahi kar sakta jo runtime par appear ya vanish ho jaayein?

Yeh ek fixed total of each resource type assume karta hai ek fixed

A v ai l ab l e

compute karne ke liye; agar total unpredictably change ho, toh jo "escape plan" usne guarantee kiya tha woh ab valid nahi raha.

Edge cases

Kya hota hai jab ek process ka $N ee d$ already zero vector ho?

Woh chahe

W or k

kuch bhi ho immediately finish ho sakti hai (zero

\leq

kuch bhi componentwise), apna

A l l oc a t i o n

release karti hai aur pool badata hai — aksar yahi woh process hoti hai jo ek tight state ko unblock karti hai.

Agar ek request $R e q u es t_{i}$ zero vector ho toh kya hoga?

Teeno checks trivially pass ho jaate hain aur state unchanged rehti hai, isliye yeh grant ho jaata hai; zero request naa safety help karta hai naa harm.

Ek naya process arrive karta hai $A l l oc a t i o n = 0$ ke saath lekin bada $M a x$ hai. Kya state automatically unsafe hai?

Nahi — kuch bhi allocate na hone par uska

N ee d

uske

M a x

ke barabar hai, aur jab tak woh

N ee d

kisi sequence mein satisfy ho sake (possibly last, doosron ke release karne ke baad), state abhi bhi safe ho sakti hai.

Agar har process exactly apna $M a x$ hold kar rahi ho (sab $N ee d = 0$ ), state kaisi hogi?

Trivially safe — har process kisi bhi order mein finish ho sakti hai kyunki kisi ko kuch aur chahiye hi nahi; pool sirf badata jaata hai jaise har ek apni held resources release karta hai.

Ek state mein $A v ai l ab l e$ kai processes ke liye kaafi bada hai lekin ek process ko ek aisi resource ki aur zyada zaroorat hai jo poore system mein exist hi nahi karti. Iska kya matlab hai?

Yeh ek inconsistent/invalid configuration hai —

M a x

kabhi bhi system total se zyada nahi hona chahiye; Banker's model assume karta hai ki har

M a x [i] [j]

resource

j

ke total units se zyada nahi hoga.

Do processes mein se har ek ko ek hi single-unit resource ki ek aur unit chahiye, aur koi free nahi hai. Safe hai ya nahi?

Unsafe (ek classic deadlock setup) jab tak koi teesri process pehle finish nahi ho sakti aur woh resource release nahi karti; sirf inhi do ke saath aur kuch bhi free na ho, naa koi aage badh sakta hai aur koi safe sequence exist nahi karti.

Recall Jaane se pehle ek-line self-test

Kya tum apne words mein "unsafe" aur "deadlocked" ke beech ek hi difference bata sakte ho? ::: Deadlocked = abhi stuck, koi ordering possible nahi; unsafe = algorithm koi ordering guarantee nahi kar sakta, isliye deadlock forced ho sakta hai — unsafe bada set hai jo sab deadlocked states aur risky-but-still-running ones ko contain karta hai.