Priority inversion — problem and solutions (priority inheritance, priority ceiling): Worked examples

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

Intuition Yeh page kya hai

Parent note ne tumhe priority inversion ke rules aur do fixes bataye the. Yeh page drill hall hai: hum har tarah ki situation dhundhte hain jo yeh rules produce kar sakte hain — tasks, locks, protocols, aur degenerate edge cases ki har combination — aur har ek ko step by step stopwatch pe time karte hain.

Shuru karne se pehle, vocabulary ka ek reminder, kyunki hum ise line one se use karenge:

Ek task = kaam ki ek unit jo CPU chalata hai. Har ek ki ek priority hoti hai (ek number jo batata hai kitna urgent hai). Hum H (high), M (medium), L (low) use karte hain, highest CPU jeetta hai.
Ek mutex (dekho Mutexes vs Semaphores) = ek lock. Ek waqt mein sirf ek hi task guarded region ke andar ho sakta hai (critical section, "CS"). Baaki ko block (wait, not running) karna padta hai.
Blocking time $B$ = kitna waqt urgent task kisi kam urgent cheez ka intezaar karne mein force hota hai. Yeh puri page $B$ measure karne ke baare mein hai.

Definition Notation glossary — pehle yeh padho, har symbol yahan define hai

Is page par sab kuch milliseconds mein duration hai. Exactly char symbols hain; hum koi aur use nahi karte:

$CS_{t, R}$ = us critical section ki length jo task $t$ resource $R$ hold karte waqt run karta hai. Subscript ko "kaun andar hai, kaun sa lock" ke roop mein padho. Example: $CS_{L, R_{1}}$ = "L kitni der $R_{1}$ se guarded region ke andar rehta hai". Jab sirf ek lock aur ek holder ho, toh hum doosra subscript chhod dete hain aur $CS_{L}$ likhte hain — "L ka critical section".
$run (t)$ = task $t$ ko apna kaam khatam karne ke liye jitna CPU time chahiye — uska poora run, sirf ek critical section nahi. Example: $run (M)$ = "medium task CPU ko overall kitni der busy rakhta hai". Yeh woh symbol hai jo arbitrarily large ho sakta hai.
$B_{H}$ = H ka worst-case blocking time — high task ko lower tasks ka kitna intezaar karna padta hai. Yeh woh number hai jo har example compute karta hai.
$W$ = watchdog limit — woh deadline jiske baad ek supervisor timer system reset kar deta hai agar H nahi chala (sirf Ex 9 mein use hota hai).

Ek rule yaad rakhna: $CS$ values bounded hoti hain (ek critical section chhoti aur jaani-pehchani hoti hai); $run (M)$ nahi hoti — aur yahi difference is page ki poori kahani hai.

Scenario matrix

Is topic ki har case in cells mein se kisi ek mein aati hai. Neeche har worked example us cell ke saath tagged hai jise woh cover karta hai.

#	Case class	Kya vary karta hai	Example
C1	Bounded inversion (baseline)	H sirf L ke CS ka intezaar karta hai	Ex 1
C2	Unbounded inversion (bug)	M ghus jaata hai, koi protocol nahi	Ex 2
C3	PIP fix — single lock	boosting M ko hata deta hai	Ex 3
C4	PIP limit — chained/nested locks	blocking sum hoti hai	Ex 4
C5	PCP — nested locks, ek baar blocked	ceiling gate	Ex 5
C6	Deadlock case: PIP allow karta hai, PCP forbid karta hai	do locks, opposite order	Ex 6
C7	Degenerate: sirf 2 priority levels / koi shared lock nahi	koi inversion possible nahi	Ex 7
C8	Limiting value: CS length → 0 aur M runtime → ∞	bound kahan hai	Ex 8
C9	Real-world word problem (Mars Pathfinder numbers)	ek story pe apply karo	Ex 9
C10	Exam twist: ICPP timing — shuru hone se pehle block hona	immediate ceiling	Ex 10

Hum har cell mein $B_{H}$ (H ki blocking) compute karte hain. Har worked example jisme time-geometry hai (ek schedule on a clock) uska apna timeline figure hai, taaki tum blocking dekh sako, sirf number padho nahi.

Ex 1 — C1: Bounded inversion (acceptable baseline)

Worked example Statement

Priorities $H > L$ . Sirf do tasks, sharing mutex $R$ . L ka critical section = $4$ ms. Koi medium task nahi hai. H ka worst-case blocking $B_{H}$ kya hai?

Forecast: padhne se pehle guess karo — kya H thodi, bahut, ya hamesha ke liye atkegi?

Steps: (neeche timeline figure follow karo — red hatched band exactly $B_{H}$ hai)

L, $R$ ko lock karta hai aur apni CS mein enter karta hai. Yeh step kyun? Kisi ko lock ke andar hona chahiye taki H ke paas wait karne ke liye kuch ho — ek empty lock kabhi block nahi karta.
H ready hoti hai, L ko preempt karti hai, $R$ lock karne ki koshish karti hai → blocks, kyunki mutual exclusion CS ke andar priority ko beat karti hai. Yeh step kyun? Yeh woh moment hai jab inversion shuru hoti hai; $B_{H}$ ka clock yahan start hota hai (figure mein red band ka start).
Sirf L hi $R$ release kar sakta hai, toh scheduler L ko run karta hai. L ko interrupt karne ke liye koi M nahi hai. L apna bacha hua CS run karta hai. Yeh step kyun? Kyunki L se higher koi bhi task ready nahi hai (H blocked hai, koi M nahi), scheduler ke paas exactly ek runnable task hai — L — toh woh bina interrupt ke run karta hai; yahi wajah hai ki wait bounded rehta hai.
L, $4$ ms CS khatam karne ke baad $R$ release karta hai. H immediately unblock hoti hai aur run karti hai. Yeh step kyun? Release CS khatam karta hai; highest ready task (H) ab CPU jeetti hai (red band ka end).

$B_{H} = CS_{L} = 4 ms$

Verify: Units ms hain (ek duration) ✓. Wait exactly ek critical section ke barabar hai aur iske bahar kisi bhi cheez par depend nahi karta — koi unbounded quantity nahi. Yeh bounded inversion hai: avoid nahi kar sakte lekin safe hai.

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

Ex 2 — C2: Unbounded inversion (koi protocol nahi, the bug)

Worked example Statement

Priorities $H > M > L$ . H & L, $R$ share karte hain; M kuch nahi share karta. L ka CS = $5$ ms. M ka total runtime $run (M) = 50$ ms, aur M H ke block hone ke theek baad ready ho jaata hai. Koi protocol nahi. H ki blocking nikalo.

Forecast: kya $B_{H}$ $5$ ms hoga (sirf L ka CS) ya kuch bada?

Steps: (timeline figure dekho — orange M bar red band ko stretch karte dekho)

L, $R$ ko lock karta hai, CS mein enter karta hai. Kyun? Held lock establish karta hai.
H preempt karti hai, $R$ try karti hai, block hoti hai. Scheduler L par fall back karta hai. Kyun? Sirf L hi $R$ release kar sakta hai.
M ready ho jaata hai. M ko $R$ ki zaroorat nahi, aur $prio (M) > prio (L)$ , toh M, L ko preempt kar leta hai. Yeh step kyun? Yahi poison hai: scheduler priority obey karta hai (M > L) aur use nahi pata ki L kuch aisa hold kar raha hai jo H ko chahiye.
M apna poora $run (M) = 50$ ms run karta hai. L mid-CS mein frozen hai. H abhi bhi blocked hai. Kyun? Koi bhi M ko lower task ke liye yield karne par force nahi karta.
M finish hota hai, L resume hota hai, apna bacha hua CS khatam karta hai, $R$ release karta hai, H run karti hai.

$B_{H} = CS_{L} + run (M) = 5 + 50 = 55 ms$

Verify: $55$ ms — lekin " $50$ " $run (M)$ ki value hai, M ki arbitrary runtime. Ise $500$ se replace karo toh $B_{H} = 505$ . Bound ek unrelated task track karta hai → unbounded. Neeche picture se compare karo.

Ex 3 — C3: PIP single-lock case fix karta hai

Worked example Statement

Ex 2 ke same numbers ( $CS_{L} = 5$ , $run (M) = 50$ ), lekin $R$ par priority inheritance enable hai. $B_{H}$ nikalo.

Forecast: kya M ka $50$ ms abhi bhi count karega?

Steps: (figure mein, M ka bar ab right mein push ho gaya hai — woh red band ko touch nahi kar sakta)

L, $R$ lock karta hai, CS mein enter karta hai. H preempt karti hai, $R$ par block hoti hai.
PIP kick in karta hai: kyunki L, H ko block kar raha hai, L ki priority boost hoti hai H ki tarah, jab tak woh $R$ hold karta hai. Yeh step kyun? "Agar tum kisi important ko block kar rahe ho, unka rank udhar lo." Ab L, M se zyada rank ka hai.
M ready ho jaata hai — lekin $prio (M) < prio (L_{boosted}) = prio (H)$ , toh M, L ko preempt nahi kar sakta. M wait karta hai. Kyun? Boost scheduler ko L ko urgent treat karne par majboor karta hai, woh gap band kar deta hai jise M exploit karta tha.
L apna $5$ ms CS khatam karta hai, $R$ release karta hai, apni low priority par wापस aa jaata hai. H unblock hoti hai aur run karti hai; M baad mein run karta hai. Kyun? Release inheritance khatam karta hai; normal priorities resume hoti hain.

$B_{H} = CS_{L} = 5 ms$

Verify: $run (M) = 50$ term formula se gayab ho gaya — exactly wahi jo hum chahte the. $5$ ms = ek critical section = Ex 1 se bounded floor. PIP ne C2 ko C1 mein convert kar diya. ✓

Ex 4 — C4: PIP ki limit — chained (nested) blocking sum up hoti hai

Worked example Statement

Tasks $H > M > L$ . Do mutexes $R_{1}, R_{2}$ . PIP ke under: L, $R_{1}$ hold karta hai (toh $CS_{L, R_{1}} = 3$ ms) aur, separately, M, $R_{2}$ hold karta hai (toh $CS_{M, R_{2}} = 4$ ms). H ko apne run ke dauran dono $R_{1}$ aur $R_{2}$ chahiye. PIP ke under H ka worst-case blocking kya hai?

Forecast: ek CS ya dono?

Steps: (figure dekho — do alag red bands, har lock ke liye ek)

H, $R_{1}$ try karta hai (L ke paas held). L ko H tak boost kiya jaata hai, apna $3$ ms CS run karta hai, release karta hai. Yeh block #1 hai. Kyun? H ko har distinct lower holder ke liye wait karna pad sakta hai.
H aage badhta hai, baad mein $R_{2}$ chahiye (M ke paas held). M ko H tak boost kiya jaata hai, apna $4$ ms CS run karta hai, release karta hai. Yeh block #2 hai. Yeh step kyun? PIP har block ko ek CS tak bound karta hai lekin nested/alag locks mein distinct blocks ki sankhya limit nahi karta.
Total blocking relevant critical sections ka sum hai:

$B_{H} \leq CS_{L, R_{1}} + CS_{M, R_{2}} = 3 + 4 = 7 ms$

Yeh step kyun (kyun add hote hain)? Dono blocks H ke run ke alag-alag moments par hote hain — pehle jab H $R_{1}$ grab karta hai, phir baad mein jab $R_{2}$ grab karta hai. Kyunki yeh kabhi overlap nahi karte, H har ek ke dauran "blocked" state mein baith'ta hai separately, toh total wait unka arithmetic sum hai, max nahi. PIP ke paas koi mechanism nahi hai jo ek doosre lower task ko mid-CS pakde jaane se rokta ho jaise M yahan hai.

Verify: $7$ ms. Yeh bounded hai (koi $run (M)$ term nahi) — PIP abhi bhi kaam karta hai — lekin H ne do baar bhugta. Yeh woh "chained/transitive blocking" weakness hai jiske baare mein parent note ne warn kiya tha. ✓

Ex 5 — C5: PCP — nested locks, zyada se zyada ek baar blocked

Worked example Statement

Ex 4 jaise hi setup ( $CS_{L, R_{1}} = 3$ ms; $CS_{M, R_{2}} = 4$ ms), dono locks ka ceiling $= H$ (kyunki H hi highest task hai jo kabhi unhe lock karta hai). Ab Priority Ceiling Protocol use karo. $B_{H}$ nikalo.

Forecast: abhi bhi $7$ , ya kam?

Steps: (figure mein, M ko darwaze par hi rok diya jaata hai, toh sirf EK red band bachta hai)

Maano L pehle $R_{1}$ lock karta hai. System ceiling (dusron ke paas locks ki highest ceiling) $H$ ho jaati hai. Yeh step kyun? PCP ka extra gate: woh har held lock ki ceiling record karta hai.
M ab $R_{2}$ lock karne ki koshish karta hai. PCP rule: tum tab hi lock kar sakte ho jab teri priority strictly system ceiling se upar ho. $prio (M) < H = system ceiling$ → M ko entry denied hai, chahe $R_{2}$ free ho. Kyun? Yahan deny karna us tangle ko rokta hai jahan H ko baad mein do holders ka intezaar karna padta.
Toh zyada se zyada ek lower task ek relevant lock hold kar sakta hai jab H arrive karta hai. H exactly ek CS ka intezaar karta hai — single longest relevant wala:

$B_{H} \leq max (CS_{L, R_{1}}, CS_{M, R_{2}}) = max (3, 4) = 4 ms$

Verify: $4$ ms vs PIP ka $7$ ms — strictly tighter. PCP ne sum ki jagah max le liya. Yeh "zyada se zyada ek baar blocked" property hi wajah hai ki hard real-time systems ise pasand karte hain (directly Schedulability analysis & response-time analysis mein jaata hai). ✓

Ex 6 — C6: Deadlock case — PIP allow karta hai, PCP forbid karta hai

Worked example Statement

Tasks $H$ aur $L$ . Do mutexes $A, B$ . L, $A$ phir $B$ order mein lock karta hai; H, $B$ phir $A$ order mein lock karta hai (opposite order — Deadlock — conditions and prevention se classic circular-wait setup). Ceilings: dono $= H$ . Kya PIP deadlock karta hai? Kya PCP?

Forecast: kaun sa protocol tumhe bachata hai?

Steps (PIP): (figure dekho — do arrows ek circle banate hain = deadlock)

L, $A$ lock karta hai. H preempt karta hai, $B$ lock karta hai. Kyun? Koi bhi cheez kisi bhi lock ko individually rok nahi sakti.
H ab $A$ chahiye (L ke paas held) → H block hoti hai; L (boosted) ko $B$ chahiye (H ke paas held) → L block hoti hai. Har ek doosre ka intezaar karta hai → deadlock. Yeh step kyun? PIP sirf priorities boost karta hai; yeh lock ordering ke baare mein kuch nahi karta, toh circular wait form ho jaata hai.

Steps (PCP):

L, $A$ lock karta hai → system ceiling $= H$ . Yeh step kyun? PCP held lock ki ceiling record karta hai (upar System-ceiling definition dekho).
H, $B$ lock karne ki koshish karta hai: kya $prio (H)$ strictly system ceiling $H$ se upar hai? $H > H$ false hai → H darwaze par hi block ho jaata hai, $B$ acquire karne se pehle. Yeh step kyun? Ceiling gate H ko $B$ grab karne se rokta hai jab L $A$ hold karta hai, toh do locks kabhi tasks ke beech split nahi ho sakte. Koi circular wait form nahi ho sakta.
L run karta hai (boosted), $A$ aur $B$ dono ko order mein khatam karta hai, release karta hai; phir H dono ko cleanly acquire karta hai.

Verify (count): PIP → 1 deadlock possible; PCP → 0. PCP ki acyclic ordering ek proof hai, luck nahi. Yeh comparison table ki "Deadlock possible?" row se match karta hai. ✓

Ex 7 — C7: Degenerate inputs — jab inversion impossible hai

Worked example Statement

Do alag degenerate systems. (a) Sirf do priority levels $H > L$ shared lock ke saath. (b) Teen levels $H > M > L$ lekin koi shared resource bilkul nahi. Kya dono mein se kisi mein unbounded priority inversion ho sakti hai?

Forecast: tumhe teen ingredients chahiye — har ek mein kaun sa missing hai?

Steps: (figure dekho — do "ingredient checklists", har ek mein ek box unticked)

Teen zaruri ingredients yaad karo: (i) preemptive priority scheduling, (ii) mutex-guarded shared resource, (iii) kam se kam teen priority levels. Kyun? Unbounded inversion ke liye ek teesra task (M) chahiye jo CPU hog kare jab L lock hold kare.
(a) Sirf $H$ aur $L$ ke saath, koi M nahi hai jo L ko preempt kare. Worst case Ex 1 hai: $B_{H} = CS_{L}$ , bounded. Unbounded scenarios ki sankhya $= 0$ . Yeh step kyun? Ingredient (iii) fail hota hai.
(b) Koi shared lock nahi hone se, H kabhi L par block nahi hoti — woh freely preempt karti hai. $B_{H} = 0$ . Kyun? Ingredient (ii) fail hota hai; blocking ke liye wait karne ke liye ek lock chahiye.

Verify: (a) $B_{H} = CS_{L}$ (bounded), unbounded count $= 0$ ; (b) $B_{H} = 0$ . Dono confirm karte hain: koi bhi ek ingredient hata do aur bug appear nahi ho sakta. ✓

Ex 8 — C8: Limiting values — bound asal mein kahan rehta hai

Worked example Statement

Koi protocol nahi, Ex 2 ka setup. Do knobs ko extremes tak push karo: (a) L ka CS $\to 0$ hone do; (b) M ka runtime $run (M) \to \infty$ hone do. Har limit mein $B_{H} = CS_{L} + run (M)$ track karo.

Forecast: kaun sa knob danger banata hai, chhota lock ya giant M?

Steps: (figure dekho — $B_{H}$ ko M ke runtime ke against plot kiya gaya, ek straight line jo kabhi flat nahi hoti)

(a) Jaise $CS_{L} \to 0$ : ek microscopic critical section bhi kaafi hai H ke block hone ke liye us waqt, M ko ghusne deta hai. Phir $B_{H} \to 0 + run (M) = run (M)$ . Yeh step kyun? Lock ko chhota karna tumhe save nahi karta — khatara lock ki size nahi hai, yeh sirf us window ka exist karna hai jisme H block hoti hai aur M CPU seize kar sakta hai.
(b) Jaise $run (M) \to \infty$ : $B_{H} = CS_{L} + run (M) \to \infty$ . Yeh step kyun? Yeh "unbounded" ka literal matlab hai: blocking ki koi upper limit nahi hai kyunki yeh $run (M)$ ki divergence inherit karta hai.
PIP ke under contrast: $B_{H} = CS_{L}$ hamesha, toh jaise $run (M) \to \infty$ , $B_{H}$ $CS_{L}$ par hi rehta hai (finite). Yeh step kyun? Protocol $run (M)$ term ko bilkul delete kar deta hai, $B_{H}$ ko diverging quantity se independent bana deta hai.

Conclusion: khatara poori tarah $run (M)$ mein rehta hai, kabhi $CS_{L}$ mein nahi. Lock ko chhota karna bekar hai; $run (M)$ term ko delete karna (jo PIP karta hai) hi cure hai.

Verify: No-protocol limit diverge hoti hai ( $B_{H} \to \infty$ ); PIP limit $CS_{L} = 5$ ms par rehti hai (finite). Unboundedness poori tarah $run (M)$ mein rehti hai, aur PIP exactly woh surgery hai jo us term ko remove karti hai. ✓

Ex 9 — C9: Real-world word problem (Mars Pathfinder, numbers ke saath)

Worked example Statement

1997 rover ko model karo. Tasks: bc_dist = H (bus manager), comms = M (communications), ASI/MET = L (weather data). H & L, pipe mutex share karte hain. Maano $CS_{L} = 8$ ms aur comms $run (M) = 200$ ms ke bursts run karta hai. Watchdog timer system reset karta hai agar H $W = 100$ ms se zyada starve ho. (a) Kya system bina protocol ke reset hota hai? (b) Priority inheritance upload karne ke baad, kya yeh survive karta hai?

Forecast: kya $8$ ms ya $200$ ms rover ki qismat decide karega?

Steps: (figure dekho — do bars red $W = 100$ ms watchdog line ke against)

(a) Koi protocol nahi: Ex 2 ki logic se, $B_{H} = CS_{L} + run (M) = 8 + 200 = 208$ ms. Kyun? comms (M), ASI/MET (L) ko preempt karta hai jab woh pipe hold karta hai; unbounded term $run (M) = 200$ hai.
Watchdog se compare karo: $208 > 100 = W$ → watchdog fire karta hai, reset. Yeh step kyun? H ko deadline se zyada starve karna exactly woh fault hai jo Mars par observe hua.
(b) PIP ke saath: $B_{H} = CS_{L} = 8$ ms. Compare karo: $8 < 100 = W$ → koi reset nahi, survive karta hai. Kyun? Boost comms ko ASI/MET preempt karne se rokta hai, $run (M) = 200$ ms term delete karta hai — literally woh fix jo Mars par upload kiya gaya tha.

Verify: Koi protocol nahi → $208 > 100$ (reset ✓, history se match); PIP → $8 < 100$ (survive ✓). Same watchdog, opposite outcome, poori tarah $run (M)$ term hatane se decide hota hai. ✓

Ex 10 — C10: Exam twist — ICPP tumhe shuru hone se pehle block karta hai

Worked example Statement

ICPP on hai. Resource $R$ ka ceiling $= H$ hai. Time $t = 0$ par, L, $R$ lock karta hai (toh L immediately $H$ ki priority tak raise ho jaata hai). CS length $CS_{L, R} = 6$ ms. H ko $t = 2$ ms par release kiya jaata hai. H ko actually kab run karne milta hai, aur kya woh apne execute karna shuru karne ke baad kabhi block hoti hai?

Forecast: plain PIP mein H shuru hoti hai, phir block hoti hai. Kya ICPP alag hai?

Steps: (figure dekho — H ka release $t = 2$ par L ke boosted CS ke andar hai)

$t = 0$ par, L, $R$ lock karta hai aur instantly priority $H$ tak boost ho jaata hai — ICPP actually kisi ke block hone ka intezaar nahi karta. Yeh step kyun? "Immediate" = acquire par raise karo, collision par nahi.
$t = 2$ par, H release hoti hai lekin L currently H ki priority par run kar raha hai. Ties running task ko jaate hain, toh H ready rehti hai lekin run nahi hoti — shuru hone se pehle block hoti hai. Yeh step kyun? ICPP ki signature guarantee: ek task sirf shuru mein block hoti hai, kabhi mid-execution mein nahi.
L apna CS $t = 0 + 6 = 6$ ms par khatam karta hai, low par aa jaata hai, $R$ release karta hai. H $t = 6$ ms par run karna shuru karti hai aur, ek baar shuru hone ke baad, $R$ par aage koi blocking ke bina completion tak run karti hai. Yeh step kyun? Sabhi lower locks jo H ko block kar sakte the, H ke shuru hone se pehle held-and-boosted the; baad mein koi appear nahi kar sakta.

$H starts at t = 6 ms, B_{H} = 6 - 2 = 4 ms$

Verify: H $6$ ms par shuru hoti hai; blocking $= 4$ ms (uske $2$ par release se $6$ par start tak), jo L ke bacha hua CS ke barabar hai ( $6 - 2 = 4$ ). H shuru hone ke baad 0 baar block hoti hai. PCP ke same worst-case bound, simpler mechanism. ✓

Recall

Recall Matrix par khud ko test karo

Kaun sa cell? Har ek ke liye, answer batao.

Do tasks, ek lock, koi M nahi — bounded ya unbounded? ::: Bounded, $B_{H} = CS_{L}$ (C1)
Woh kaun sa single term hai jo Ex 2 ko unbounded banata hai? ::: M ka runtime $run (M)$ , lock se unrelated (C2)
PIP on Ex 2: $B_{H}$ kya hai? ::: $5$ ms — sirf L ka critical section (C3)
PIP vs PCP ke under nested locks: sum ya max? ::: PIP CSs sum karta hai; PCP max leta hai (C4/C5)
Kaun sa protocol deadlock prevent karta hai? ::: PCP (acyclic ceiling ordering); PIP nahi karta (C6)
Critical section ko near-zero tak shrink karna — kya yeh unbounded inversion fix karta hai? ::: Nahi; khatara blocking window hai, CS size nahi (C8)
ICPP: ek task kab block ho sakta hai? ::: Sirf shuru hone se pehle, kabhi baad mein nahi (C10)

Yeh bhi dekho: Real-Time Scheduling — Rate Monotonic & EDF, RTOS task states and context switching, Worst-Case Execution Time (WCET) analysis.