Priority inversion — problem and solutions (priority inheritance, priority ceiling): Visual walkthrough

5.5.14 · D2 · Coding › Embedded Systems & Real-Time Software › Priority inversion — problem and solutions (priority inherit

Neeche sab kuch ek hi tarah ke diagram par hai: ek timeline. Pehle woh samjhte hain.

Step 1 — "Timeline" dikhata kya hai

WHAT. Kisi bhi bug se pehle, humein ek language chahiye yeh baat karne ke liye ki kaun kab run karta hai. Hum ek horizontal axis time ke liye banate hain (right = baad mein) aur teen horizontal lanes stack karte hain, har task ke liye ek. Ek lane mein coloured bar ka matlab hai woh task abhi CPU hold kar raha hai. Kisi bhi instant par sirf ek lane filled ho sakti hai, kyunki ek single CPU ek waqt mein ek hi task run karta hai.

WHY yeh picture aur koi table nahi. "Task states" ki table woh ek cheez chupa deti hai jo sabse important hai: woh gap jiske dauran sabse urgent task run NAHI ho raha. Timeline mein woh gap literally ek khali jagah ban jaati hai jise aap ruler se naap sakte ho. Hum woh gap naapne waale hain — isliye usse visible hona chahiye.

PICTURE. Teen lanes: H (high priority, magenta), M (medium, orange), L (low, violet). Upar wali lane = zyada priority. Abhi sirf L run ho raha hai.

Figure — Priority inversion — problem and solutions (priority inheritance, priority ceiling)

Step 2 — Lock: ek darwaza jisme sirf ek task fit hota hai

WHAT. H aur L dono ek shared cheez ko touch karte hain (ek buffer, ek pipe). Usse corrupt hone se bachane ke liye, woh ek mutex se guard karte hain — isko $R$ bulao. Mutex ek darwaza hai: jo andar jaata hai woh isse lock karta hai; baaki jo darwaze par pahunchte hain unhe wait karna padta hai jab tak yeh unlock nahi ho jaata.

WHY mutex aur bas "careful rehna" nahi. Do tasks ek hi buffer mein ek saath likhne se garbage produce hota hai. Mutual exclusion (dekho Mutexes vs Semaphores) rule ko physical bana deta hai: zyada se zyada ek task $R$ ke critical section ke andar hota hai — lock aur unlock ke beech ka code stretch — kisi bhi instant par.

PICTURE. L darwaze se $R$ mein ghusta hai (lock karta hai). Jab tak L andar hai, darwaza LOCKED dikhata hai. L ke bar ka woh hissa jo andar guzra, woh uska critical section hai, hatched banaya gaya.

Step 3 — H aata hai aur locked darwaze se takraata hai

WHAT. Jab L $R$ ke andar hai, task H ready ho jaata hai. Scheduler rule ke hisaab se H, L ko preempt karta hai (magenta bar shuru). H apna khud ka code run karta hai, phir shared cheez tak pahunchta hai aur $R$ ko lock karne ki koshish karta hai. Darwaza LOCKED hai (L abhi andar hai). Isliye H aage nahi badh sakta — H block ho jaata hai.

WHY yeh abhi bug nahi hai. H sirf ek cheez ka wait kar raha hai: L apna critical section finish kare aur darwaza unlock kare. Woh wait zyada se zyada $CS_{L}$ hai. Itna chhota aur predictable wait bounded inversion kehlata hai — yeh tab unavoidable hai jab do tasks ek lock share karein, aur yeh acceptable hai.

PICTURE. H ka bar shuru hota hai, phir $R$ ke darwaze par ek red wall se takra ke ruk jaata hai. Control wapas L (violet) ke paas jaana padta hai, kyunki L hi ek aisa task hai jo $R$ unlock kar sakta hai.

Step 4 — M andar aa jaata hai aur bound todo deta hai

WHAT. L resume ho gaya hai (usse hona hi hai, $R$ release karne ke liye). Ab M ready ho jaata hai. M ko $R$ se kuch nahi chahiye. Lekin M, L se upar hai. Scheduler rule fire karta hai: M, L ko preempt karta hai. L mid-critical-section freeze ho jaata hai, darwaza abhi bhi LOCKED. M run karta hai — aur M lamba, unspecified time tak run kar sakta hai.

WHY yeh disaster hai. Dependency chain follow karo:

H, L ka wait kar raha hai (taaki $R$ unlock ho).
L, M ka wait kar raha hai (taaki CPU mile).
M kisi ka wait nahi kar raha — woh bas run karta hai.

Toh H, sabse urgent task, effectively M ka wait kar raha hai — ek aisa task jisse H ka kuch share bhi nahi hai. Aur M ki runtime ki koi fixed limit nahi hai. H ko delay ab unbounded hai.

PICTURE. Orange M-bar, L ko side mein dhakelta hai. L ka hatched critical section paused hai (frozen, greyed). H ki red wall koi end nahi dikhte hue right ki taraf badhti jaati hai — ek arrow par likha hai "unbounded".

Step 5 — Fix ka idea: L ko apni urgency udhar do (Priority Inheritance)

WHAT. Ek rule badlo. Jis waqt H, $R$ par block ho jaata hai jo L hold kar raha hai, L ko H ki priority de do — L boost ho jaata hai. L yeh borrowed rank tab tak rakhta hai jab tak $R$ unlock nahi karta, phir wapas drop ho jaata hai.

WHY yeh exact move. Bug yeh tha ki "M, L se upar hai, isliye M, L ko preempt karta hai." L ko H ke level tak boost karo aur woh inequality flip ho jaati hai: ab L, M se upar hai. Jab M ready hota hai, scheduler rule kehta hai zyada wali task run kare — woh hai L (boosted). M preempt nahi kar sakta. L apna critical section jaldi finish karta hai, $R$ unlock karta hai, rank drop karta hai, aur H — darwaze par pehli line mein — turant run karta hai.

PICTURE. H ke block instant par, L ka violet bar magenta ho jaata hai ("H tak boosted"). Jab M aata hai (orange), woh ready lane mein roka jaata hai — ek dashed "denied preemption" bar — jab tak boosted-L finish nahi kar leta.

Step 6 — Inheritance kahan abhi bhi bleeding karta hai: chained blocking

WHAT. Inheritance delay ko bound karta hai, lekin nested locks ke saath woh bound stack ho sakta hai. Maano H ko $R_{1}$ aur $R_{2}$ dono chahiye ho sakti hain. Low, $R_{2}$ hold kar raha hai; Mid, $R_{1}$ hold kar raha hai aur saath hi $R_{2}$ ka wait bhi kar raha hai. Jab H aata hai toh use do critical sections sequentially wait karne par majboor kiya ja sakta hai — chain mein har lock ke liye ek.

WHY yeh hota hai. Inheritance sirf block hone ke baad react karta hai; yeh kisi task ko doosra lock pakadne se pehle kabhi prevent nahi karta jo chain shuru kare. Isliye boosts ek hierarchy mein ripple karte hain (yeh hai transitive inheritance), aur har nested critical section H ke wait mein add hota jaata hai. Inheritance deadlock bhi abhi bhi kar sakta hai — do tasks, dono ek-ek lock hold kiye hue dusre ka wait kar rahe hain (dekho Deadlock — conditions and prevention).

PICTURE. Ek chain: H → $R_{1}$ ka wait karta hai (Mid ke paas hai) → Mid, $R_{2}$ ka wait karta hai (Low ke paas hai). Do hatched critical sections H ke total block ke roop mein stack up hote hain. Ek chhota red "⚠ still possible: deadlock" flag do tasks ke beech baitha hai jo ek-dusre ka lock hold-and-want kar rahe hain.

Step 7 — Darwaze par bouncer lagao (Priority Ceiling)

WHAT. Har lock ko ek static number do, uska ceiling = us sabse zyada priority wale task ki priority jo isse kabhi lock karega. Naya rule: ek task lock mein tab hi enter kar sakta hai jab uski priority strictly upar ho un sabhi locks ki ceilings se jo doosre tasks abhi hold kar rahe hain (woh system ceiling hai). Warna use darwaze par hi rokaa jaata hai — kuch pakadne se pehle.

WHY yeh chain prevent karta hai, bas bound nahi. Step 6 mein tangle isliye bana kyunki Mid ko doosra lock lene ki permission thi. Ceiling ek gate-keeper hai jo entry se pehle check hota hai: agar koi lock lene se blocking chain ban sakti hai, toh aapko pehle se refuse kar dete hain, isliye chain kabhi assemble hi nahi ho sakti. Ceilings jo order enforce karte hain woh acyclic hai → no deadlock, aur ek task ko har activation mein zyada se zyada ek baar, ek critical section ke liye block kiya ja sakta hai.

PICTURE. Low, $R_{1}$ hold kar raha hai; system ceiling = H. M, $R_{2}$ ke darwaze par pahunchta hai — bouncer check karta hai: "teri priority (M) system ceiling (H) se strictly upar nahi hai" → DENIED. Step 6 ki chain kabhi ban hi nahi paati. H sirf ek critical section se block hota hai.

Step 8 — Degenerate cases (koi gap mat chhodo)

WHAT & WHY & PICTURE, ek panel each:

Koi shared lock nahi. Koi mutex nahi → koi darwaza nahi → koi inversion possible nahi. Ingredient 2 missing.
Sirf do priority levels hain (koi M nahi). Inversion automatically bounded ho jaata hai: H sirf $CS_{L}$ wait karta hai, kyunki CPU churaane wala koi medium task nahi hai. Unbounded bug ke liye teen levels chahiye.
M ko bhi lock chahiye. Tab M usi darwaze ke rules se bound hai — woh sirf barrel past nahi kar sakta; usse bhi wait karna padta hai, isliye woh unrelated hog nahi ban sakta.
Zero-length critical section ( $CS_{L} \to 0$ ). Blocking $\to 0$ : L kabhi lock hold karte hue caught nahi hota. Yeh limit har formula ko sanity-check karta hai: $B_{H} \to 0$ .

Recall Edge cases check karo

Shared lock hatao — kya inversion ho sakti hai? ::: Nahi. Koi mutex nahi toh koi darwaza nahi jahan wait karo; ingredient 2 gaya. Sirf H aur L ke saath (koi medium task nahi), kya inversion unbounded hai? ::: Nahi, yeh $CS_{L}$ tak bounded hai — unbounded bug ke liye ek teesra (medium) level chahiye. Jab $CS_{L} \to 0$ , toh $B_{H}$ kis taraf jaata hai? ::: $0$ — ek instant critical section kisi higher task ko kabhi trap nahi kar sakta.

Ek-picture summary

Ek figure, chaar stacked timelines: (a) bug — H ka block chart se baahar nikal jaata hai (unbounded, orange M hog kar raha hai); (b) PIP — L boosted magenta, M frozen, H ka block = ek $CS$ ; (c) PCP — bouncer, M ko darwaze par deny karta hai, chain prevent hoti hai; aur shrinking block-bar $\infty \to \sum CS \to max CS$ neeche likha hai.

Recall Feynman retelling — ek story ki tarah bolo

Ek CPU, teen workers: H urgent wala, M ek busybody, L slow wala. L ek shared room (ek lock) ke andar hai. H aata hai usse woh room chahiye aur darwaze par wait karna padta hai — theek hai, yeh thoda wait hai. Lekin phir M aa dhamakta hai; M ko room ki zarurat bilkul nahi, phir bhi M, L se upar hai, isliye M, L ko CPU se kick kar deta hai. Ab L frozen hai room ke andar, key abhi bhi pakde hue, aur H bahar atka hua hai — M ka wait kar raha hai, ek ajanabi jo forever dawdle kar sakta hai. Yahi hai unbounded bug.

Fix ek (Inheritance): jis waqt H, L ka wait karte hue atakta hai, hum L ko H ka rank udhar dete hain. Achanak L, M se upar ho jaata hai, isliye M, L ko kick nahi kar sakta; L jaldi finish karta hai, unlock karta hai, room H ko deta hai. H ka wait sirf L ke room mein rehne ke time tak simit ho jaata hai.

Fix do (Ceiling): ek bouncer hire karo. Har room mein ek sign hota hai jo us sबse fancy guest ki rank dikhata hai jo usse kabhi use karta hai. Aap room mein tab hi ghus sakte ho jab aap har sign se upar ho jo abhi use ho raha hai. M ko pehle se door kar diya jaata hai nested tangle shuru karne se — isliye yeh mess kabhi banta hi nahi, koi deadlock nahi, aur H zyada se zyada ek room ke time jitna delay hota hai.

Poora safar teen numbers mein: block time ∞ (bug) se critical sections ka sum (inheritance) se ek critical section (ceiling) tak jaata hai.