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

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

Yeh page parent topic se belong karta hai. Shuru karne se pehle, kuch words se comfortable ho jao jinpar hum zyada depend karenge:

A mutex (mutual-exclusion lock) — ek token jo ek waqt mein sirf ek hi task hold kar sakti hai. Dekho Mutexes vs Semaphores.
A critical section (CS) — code ka woh hissa jo ek task tab run karta hai jab woh mutex hold kar raha hota hai. Jab tak holder release nahi karta, koi aur usi mutex waale critical section mein enter nahi kar sakta.
Preemption — ek higher-priority task ka ek lower task ko instantly CPU se hata dena. Dekho RTOS task states and context switching.
==Blocking time $B_{H}$ == — woh total time jitni ek high task $H$ ko wait karna padta hai kyunki koi lower task ek aisa lock hold kar raha hai jo $H$ ko chahiye.

We will also use three protocol names repeatedly, so pin them down now:

Definition Is page par use hone wale teen protocol acronyms

==PIP — Priority Inheritance Protocol==: woh task jo kisi higher wale ko block kar rahi hai, temporarily higher task ki priority inherit (borrow) karti hai, sirf jab tak woh lock hold karti hai.
==PCP — Priority Ceiling Protocol==: har mutex ek static ceiling carry karta hai (us highest task ki priority jo kabhi bhi ise lock karegi); koi task ek lock tab hi le sakti hai jab uski priority strictly greater than ( $>$ ) system ceiling (neeche define kiya gaya) ho. Ties ( $\geq$ ) kaafi nahi hain — ek strict " $>$ " zaroori hai. Yeh inheritance ke upar ek gate add karta hai.
==ICPP — Immediate Ceiling Priority Protocol==: PCP ka practical variant jahan ek task ko lock ka ceiling usi waqt mil jaata hai jab woh lock acquire karta hai, bina actually kisi ko block kiye.
==System ceiling==: kisi bhi moment mein, un sab mutexes mein se sabse highest ceiling jo abhi doosri tasks ne lock kar rakhi hain. Yeh woh number hai jisse PCP tumhari priority ko compare karta hai (strictly, " $>$ " ke saath) naya lock lene se pehle. Agar koi doosri task koi lock hold nahi kar rahi, toh system ceiling "sab se neeche" hai, isliye koi bhi task lock kar sakti hai.

Throughout, priority order hai $H > M > L$ (H sabse zyada urgent hai). Hum time milliseconds (ms) mein likhte hain.

Level 1 — Recognition

Problem 1.1 (L1)

Priority inversion ke liye teen ingredients ka sab ka sab present hona zaroori hai. Neeche di gayi list mein se exactly woh teen tick karo jo required hain:

(a) preemptive priority scheduling, (b) ek shared resource jo mutex se guarded ho, (c) ek network connection, (d) kam se kam teen priority levels, (e) ek floating-point unit.

Recall Solution 1.1

Required teen hain (a), (b), (d).

(a) Preemption ke bina, koi running task kabhi side mein nahi dhakeli ja sakti — koi inversion nahi.
(b) Shared mutex ke bina koi lock nahi hai jo low task hostage le sake.
(d) Tumhein teen levels chahiye taaki ek medium task (na holder, na waiter) beech mein ghus sake aur unbounded case create kare. (c) aur (e) irrelevant hardware details hain.

Problem 1.2 (L1)

Har term ko uske one-line meaning se match karo:

Ceiling of a resource — 2. Priority inheritance — 3. Bounded inversion — 4. Unbounded inversion.

A. High sirf ek low task ke critical section ka wait karta hai. B. Ek medium task CPU hog karta hai jab low lock hold kare, toh wait ka koi upper limit nahi hota. C. Us highest task ki priority jo kabhi bhi resource lock karegi. D. Ek blocking low task temporarily waiter ki priority borrow kar leta hai.

Recall Solution 1.2

1↔C, 2↔D, 3↔A, 4↔B. Key sanity check: inheritance (D) ek action hai jo block ke baad li jaati hai; ceiling (C) ek static number hai jo runtime se pehle compute hoti hai.

Level 2 — Application

Problem 2.1 (L2)

$H$ , $L$ share karte hain mutex $R$ . $L$ ka critical section $8$ ms ka hai. Ek medium task $M$ (koi lock nahi chahiye) $40$ ms run karta hai. Koi protocol nahi hai, aur neeche diye timing assumptions ke under — (i) $L$ ne abhi-abhi $R$ acquire kiya hai aur apna koi bhi critical section execute nahi kiya, (ii) $H$ , $L$ ke $R$ acquire karne ke turant baad ready ho jaata hai, aur (iii) $M$ right after $H$ ke block hone par ready ho jaata hai — toh $H$ se se kam kitna wait karega?

Recall Solution 2.1

Sequence: $L$ locks $R$ → (assumption ii) $H$ preempts immediately, tries $R$ , blocks → $L$ resumes → (assumption iii) $M$ becomes ready, preempts $L$ (M outranks L) → $M$ runs $40$ ms → $L$ finishes its remaining CS → releases $R$ → $H$ runs. Kyun L ka poora $8$ ms CS abhi bhi pending hai: assumption (i) ke mutabiq, $H$ ne $L$ ko pehle preempt kar diya tha jab $L$ ne apna critical section kuch bhi run nahi kiya tha, isliye jab $M$ finally side hota hai, $L$ par abhi bhi poora $8$ ms baaki hai — pehle kuch consume nahi hua. (Agar $L$ ne $H$ ke aane se pehle, maan lo, $3$ ms CS already run kar li hoti, toh sirf $5$ ms bacha hota; hum worst case lete hain jahan sab $8$ ms baaki hain.) Wait $=$ $M$ ka run $+$ $L$ ka remaining critical section $= 40 + 8 = 48$ ms (at minimum — aur zyada M activations se aur bura hoga). Yeh principle mein unbounded hai: $40$ ki jagah koi bhi number rakh do aur wait badhta jaata hai.

Problem 2.2 (L2)

Wahi tasks, lekin ab $R$ par PIP enable hai. $H$ kitna blocked rahega?

Recall Solution 2.2

Jab $H$ , $R$ par block hota hai, $L$ ko $H$ ki priority inherit ho jaati hai. Ab $L$ , $M$ se upar hai, isliye $M$ $L$ ko preempt nahi kar sakta. $L$ apna $8$ ms critical section finish karta hai, $R$ release karta hai, wapas neeche aa jaata hai; $H$ run karta hai. $H$ ki blocking $=$ $L$ ka critical section $= 8$ ms. Bounded — $M$ ke $40$ ms se independent. ✅

Problem 2.3 (L2)

Do mutexes $R_{1}$ aur $R_{2}$ . $R_{1}$ ko kuch point par tasks ${H, L}$ lock karte hain; $R_{2}$ ko ${M, L}$ lock karte hain. Har mutex ki ceiling batao.

Recall Solution 2.3

Ceiling = us highest task ki priority jo ise kabhi bhi lock kare.

$ceiling (R_{1}) = max (H, L) = H$ .
$ceiling (R_{2}) = max (M, L) = M$ . Note karo ki $R_{2}$ ki ceiling sirf $M$ hai, chahe $L$ bhi ise lock kare — ceiling highest locker track karta hai, lowest nahi.

Level 3 — Analysis

Problem 3.1 (L3)

Neeche diye figure mein timeline study karo. Tasks $H, M, L$ ; $H$ aur $L$ share karte hain $R$ . Koi protocol nahi chal raha. Identify karo (i) woh instant jab unbounded inversion shuru hoti hai, aur (ii) kaunsi task $R$ se unrelated hai phir bhi $H$ ki delay dominate karti hai.

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

Is figure ko kaise padhein: teen horizontal lanes, ek per task, left par label kiye gaye hain (bottom = L low, middle = M medium, top = H high). Time left→right ms mein run karta hai, dotted vertical guides ke saath events $t_{0}, t_{1}, t_{3}, t_{4}, t_{5}$ par. Blue bar = $L$ actively $R$ hold/run kar raha hai; pink bar H lane par = $H$ blocked hai (frozen, $R$ ka wait kar raha hai); pink bar M lane par = $M$ apna unrelated kaam run kar raha hai; yellow bar = ek task finally normally run kar rahi hai. Yellow arrow unbounded gap mark karta hai.

Recall Solution 3.1

(i) Unbounded inversion $t_{3}$ par shuru hoti hai — woh moment jab $M$ ne $L$ ko preempt kiya jabki $L$ abhi bhi $R$ hold kar raha tha. $t_{3}$ se pehle, $H$ sirf $L$ ke critical section ka wait kar raha tha (bounded); $t_{3}$ par yeh wait $M$ ke runtime ka hostage ban jaata hai. (ii) $M$ $R$ se unrelated hai (na koi lock chahiye) phir bhi uska runtime $H$ ki delay dominate karta hai — yahi is bug ka signature hai. $t_{3}$ aur $t_{4}$ ke beech lamba pink $M$ bar dekho: isme kuch bhi $R$ ko touch nahi karta, phir bhi $H$ (blocked, top lane) poore time frozen hai.

Problem 3.2 (L3)

Wahi teen tasks ko PIP ke under compare karo (neeche figure). Figure use karke explain karo ki medium bar kyun disappear ho jaata hai $L$ ke critical section ke beech mein se.

Is figure ko kaise padhein: pehle jaisi teen lanes aur time axis. Dashed yellow vertical line woh instant mark karti hai jab $L$ boosted hota hai — yeh bottom (L) lane se top (H) lane par jump karta hai. Hatched blue bar jo top lane mein hai woh $L$ hai apna critical section H ki priority par boosted hokar run karta hua. Dotted "release" line mark karta hai jahan $L$ ne $R$ free kiya aur wapas neeche aa gaya; yellow bar $H$ hai finally run karta hua, aur pink bar M lane par $M$ hai, ab release ke baad push kiya gaya.

Recall Solution 3.2

Jis instant $H$ , $R$ par block hota hai, $L$ ki priority $H$ ki wali tak boost ho jaati hai (dashed yellow line dikhata hai $L$ top lane par jump karta hua). Boost hone ke baad, $L$ , $M$ se upar hai, isliye jab $M$ ready hota hai toh use preempt nahi karne diya jaata — $M$ apni baari ka wait karta hai. Isliye $L$ apna critical section completion tak bina interruption ke run karta hai, $R$ release karta hai (yellow "release" tick), aur instantly apne low lane par drop ho jaata hai. Tabhi $H$ run kar sakta hai. Medium bar release ke baad push ho jaata hai, isliye woh ab $L$ ke critical section ke andar nahi baithta — unbounded gap khatam ho jaata hai.

Problem 3.3 (L3)

PIP ke under nested mutexes ke saath: $H$ ko $R_{1}$ chahiye ( $M$ hold kar raha hai), aur $M$ ko $R_{2}$ chahiye ( $L$ hold kar raha hai). Trace karo ki priority boosts kaise propagate hoti hain. Ise chained (transitive) blocking kaha jaata hai — name explain karo.

Recall Solution 3.3

Chain of dependence: $H \to R_{1} \to M \to R_{2} \to L$ .

$H$ , $R_{1}$ par block hota hai ( $M$ hold kar raha hai) → $M$ ko $H$ ki priority inherit hoti hai.
Lekin $M$ khud $R_{2}$ par blocked hai ( $L$ hold kar raha hai) → $L$ ko $M$ ki (ab $= H$ ki) priority inherit hoti hai.
Boost chain mein neeche propagate ho gayi $L$ tak. $L$ , $H$ ke level par run karta hai, $R_{2}$ par CS finish karta hai, release karta hai; $M$ un-block hota hai, $R_{1}$ par CS finish karta hai, release karta hai; aakhirkar $H$ run karta hai. "Chained" = $H$ ka wait, $L$ ke CS plus $M$ ke CS ka sum hai — do critical sections stack hokar aa jaate hain, kyunki block ek chain of holders se travel kiya. PIP har link ko bound karta hai lekin inhe add up kar deta hai.

Level 4 — Synthesis

Problem 4.1 (L4)

Design assignment. Tasks $H, M, L$ . Resources $R_{1}$ (ceiling $H$ ), $R_{2}$ (ceiling $H$ ). PIP ke under, $H$ , $R_{1}$ aur $R_{2}$ par alag-alag block ho sakta hai, CS lengths $6$ ms aur $4$ ms. PCP (Priority Ceiling Protocol) ke under, dikhao ki $H$ zyada se zyada ek baar block hota hai, aur dono protocols ke under worst-case blocking do.

Recall Solution 4.1

PIP ke under — timeline walk karo dekhne ke liye ki do critical sections kyun sum hoti hain:

$L$ , $R_{1}$ lock karta hai aur apna $6$ ms CS shuru karta hai. $L$ ko preempt kar diya jaata hai (maan lo $H$ ke activate hone se), isliye $L$ , $R_{1}$ ke CS ke andar ruk jaata hai.
Alag se, $L$ (pehle ya interleaved run mein) $R_{2}$ lock karta hai — YA ek doosra lower task $L_{2}$ , $R_{2}$ $4$ ms ke liye hold karta hai. Dono taraf, $R_{2}$ par ek $4$ ms CS hai jo $H$ ko bhi chahiye hogi.
$H$ start karta hai. Pehle $R_{1}$ chahiye → holder finish hone aur release karne tak $6$ ms ke liye blocks karta hai. Yeh ek block hai.
$H$ resume karta hai, run karta hai, phir baad mein $R_{2}$ chahiye → woh $R_{2}$ abhi bhi held paata hai → dobara $R_{2}$ release hone tak $4$ ms ke liye blocks karta hai. Yeh doosra, alag block hai. Kyunki PIP mein doosre lock ko kabhi na lene se rokne ka koi gate nahi hai, dono critical sections independently "in progress" ho sakti hain aur har ek $H$ ko ek poora block cost karti hai, ek ke baad ek. Kuch bhi inhe merge nahi karta. Isliye yeh add hoti hain: $B_{H}^{PIP} = 6 + 4 = 10 ms (sum — chained/multiple blocking) .$ PCP ke under: maan lo $L$ , $R_{1}$ lock karta hai. System ceiling (abhi-locked mutexes mein sabse highest ceiling) $H$ ban jaati hai. Ab agar koi task $R_{2}$ lock karne ki koshish kare, uski priority strictly greater than system ceiling $H$ honi chahiye — impossible, kyunki koi task strictly $H$ se upar nahi hai. Isliye doosra lock tab tak deny hota hai jab tak $R_{1}$ free na ho: woh situation jahan dono $R_{1}$ aur $R_{2}$ simultaneously locked-and-blocking hoon, kabhi form hi nahi ho sakti. $H$ zyada se zyada ek critical section se blocked hota hai — sabse lamba relevant wala: $B_{H}^{PCP} = max (6, 4) = 6 ms .$ PCP yahan worst-case blocking mein $10 - 6 = 4$ ms bachata hai, aur "at most once" guarantee deta hai.

Problem 4.2 (L4)

Paanch tasks ek mutex $R$ lock karti hain: unki priorities hain $H = 5, T_{2} = 4, T_{3} = 3, T_{4} = 2, L = 1$ (bada = zyada high). $ceiling (R)$ kya hai? ICPP (Immediate Ceiling Priority Protocol — ek task ko lock ka ceiling usi waqt milta hai jab woh lock acquire kare) ke under, $T_{4}$ ki priority $R$ lock karne ke instant kitni ho jaati hai, aur kya koi task $T_{4}$ ko preempt kar sakta hai jabki woh $R$ hold kare?

Recall Solution 4.2

$ceiling (R) = max (5, 4, 3, 2, 1) = 5$ (jo $H$ hai). ICPP ke under, jis moment $T_{4}$ , $R$ lock karta hai ise immediately ceiling $= 5$ tak raise kar diya jaata hai. $R$ hold karte waqt, $T_{4}$ priority $5$ par run karta hai — top par. Kya $H$ (priority $5$ ) ise preempt kar sakta hai? Page ke top mein diye scheduler ke tie-breaking rule ke mutabiq, preemption ke liye strictly higher priority chahiye. $H$ aur boosted- $T_{4}$ equal hain $5$ par, isliye $H$ preempt nahi karta: $T_{4}$ , jo already run kar raha hai, CPU hold karta rehta hai. Baaki sab tasks ( $T_{2}, T_{3}, L$ ) ki priority $< 5$ hai, isliye koi bhi preempt nahi kar sakta. Isliye koi bhi task $T_{4}$ ko preempt nahi kar sakta jab tak woh $R$ hold kare. $T_{4}$ apna critical section completion tak run karta hai, $R$ release karta hai, $2$ par wapas aa jaata hai. Isliye ICPP tasks "shuru hone ke baad kabhi blocked nahi hote": ya toh woh top rank hold karte hain ya unhe darwaaze par hi rok diya jaata hai.

Common mistake L4 trap — "PCP lock deny karta hai, toh yeh deadlock jaisa hi hai."

Kyun sahi lagta hai: entry refuse kiya gaya task permanently stuck lagta hai. Catch: denial temporary aur ordered hai — yeh kabhi cycle nahi bana sakta. Yahan exact reason hai kyun PCP deadlock-free hai. Deadlock ke liye circular wait chahiye: task $A$ , $B$ ke hold kiye lock ka wait karta hai, jabki $B$ , $A$ ke hold kiye lock ka wait karta hai. $A$ ke critical section ke andar hone ke liye, $A$ ki priority ko $A$ ke lock karne ke waqt system ceiling se strictly above hona tha. Woh system ceiling $\geq$ ceiling of har lock hai jo $B$ (ya koi bhi) abhi hold karta hai. Isliye jab $A$ apna lock hold karta hai, koi bhi task jiska priority us ceiling se $\leq$ ho, ek naya lock nahi le sakta jo $A$ ko trap kare — specifically, woh task jiska $A$ baad mein wait karne wala ho woh simultaneously $A$ ka wait nahi kar sakta, kyunki dono mein se kisi ek ne lock karne ke waqt strict-" $>$ " gate fail kar diya hota. Gate ceiling value se lock acquisition par ek total order enforce karta hai, aur total order mein koi cycle nahi hoti. No cycle ⇒ no circular wait ⇒ no deadlock. Denied task sirf ek current holder ke finish hone ka wait karta hai, phir proceed karta hai. Dekho Deadlock — conditions and prevention. Fix: deadlock ko circular wait chahiye; PCP ka strict ceiling gate lock acquisition ko acyclic banata hai, isliye circle kabhi close nahi ho sakta.

Level 5 — Mastery

Problem 5.1 (L5)

Response-time flavour. Task $H$ ka execution time $C_{H} = 12$ ms hai aur worst-case blocking $B_{H}$ hai. PIP ke under do lower tasks ek-ek baar block kar sakti hain: unke relevant critical sections $7$ ms aur $5$ ms hain. Is window mein koi medium interference nahi hai. Response-time idea use karke (dekho Schedulability analysis & response-time analysis), is simplified window mein $H$ ka response time $R_{H} = C_{H} + B_{H}$ hai. PIP aur PCP ke under $R_{H}$ compute karo.

Recall Solution 5.1

PIP (har lower task se zyada se zyada ek baar blocked → sum): $B_{H}^{PIP} = 7 + 5 = 12 ms, R_{H} = 12 + 12 = 24 ms .$ PCP (total zyada se zyada ek baar blocked → single longest): $B_{H}^{PCP} = max (7, 5) = 7 ms, R_{H} = 12 + 7 = 19 ms .$ PCP worst case ko $5$ ms tight karta hai — yeh tighter bound exactly wahi hai jo hard real-time WCET/response-time budgets mein prize ki jaati hai.

Problem 5.2 (L5)

Full formula application. Lower tasks aur unke relevant critical-section lengths ( $H$ ke liye relevant) hain: $L_{1} : {9, 3}$ ms, $L_{2} : {6}$ ms, $L_{3} : {8, 8}$ ms. (a) PIP ke under, worst-case $B_{H} = \sum_{lower j} max_{k} CS_{j, k}$ . Ise compute karo. (b) PCP ke under, worst-case $B_{H} = max_{j, k} CS_{j, k}$ same set par. Ise compute karo.

Recall Solution 5.2

Pehle, har lower task ka sabse lamba relevant CS:

$L_{1}$ : $max (9, 3) = 9$
$L_{2}$ : $max (6) = 6$
$L_{3}$ : $max (8, 8) = 8$

(a) PIP — un maximums ka sum: $B_{H}^{PIP} = 9 + 6 + 8 = 23 ms .$ (b) PCP — sab mein se single largest critical section: $B_{H}^{PCP} = max (9, 3, 6, 8, 8) = 9 ms .$ Ratio $23/9 \approx 2.56$ : PIP ka bound yahan $2.5 \times$ se zyada bada hai. Jaise-jaise lower tasks ki sankhya badhti hai, PIP ka sum badhta rehta hai jabki PCP ka max wahi rehta hai — yeh scaling hi woh deep reason hai ki PCP kai nested resources ke liye dominate karta hai.

Problem 5.3 (L5)

Reasoning synthesis. Ek colleague propose karta hai: "Bas ICPP har jagah use karo aur PIP bhool jao." Is choice ka ek sach faayda aur ek honest cost do, comparison table se wapas tie karte hue.

Recall Solution 5.3

Advantage: ICPP tightest blocking bound deta hai ("at most once total"), deadlock-freedom, no chained blocking, aur kam runtime cost (raise-on-lock ek assignment hai) — ek task shuru hone ke baad kabhi blocked nahi hota. Honest cost: ICPP ko static offline analysis chahiye — tumhein pata hona chahiye ki har task kabhi bhi har resource ko lock karegi ya nahi, ceilings compute karne ke liye, aur task set mein koi bhi change recomputation force karta hai. Ek task ko lock karne ke waqt hi boost ho jaata hai (chahe koi actually block hi na hota), jo unrelated higher tasks ko thoda delay kar sakta hai jo us resource ko touch bhi nahi karne wale the. PIP ko koi static analysis nahi chahiye aur sirf tab boost karta hai jab real block ho — aksar simpler to deploy jab task set baar baar change hota ho.

Common mistake L5 trap — "bada blocking formula matlab protocol

har case mein worse hai." Kyun sahi lagta hai: PIP ka worst-case sum hamesha $\geq$ PCP ka max hota hai, isliye PIP strictly inferior lagta hai. Catch: formulas worst-case bounds hain, typical runtime nahi. Single resource aur no nesting ke saath, PIP aur PCP same bound dete hain (exactly ek critical section of blocking), aur us case mein PIP ko koi offline ceiling analysis nahi chahiye — aksar pragmatic winner. Do formulas ke beech ka gap tabhi kholti hai jab locks nested ya numerous hon. Fix: protocol system shape se choose karo: single ya rarely-nested locks → PIP theek hai aur deploy karna sasta hai; deeply nested hard-real-time → PCP/ICPP tight bound aur deadlock-freedom ke liye. Parent note mein comparison table aur Real-Time Scheduling — Rate Monotonic & EDF dekho.

Quick self-check

Recall Numeric answers reveal karo

Prob 2.1 wait ::: $48$ ms Prob 2.2 wait ::: $8$ ms Prob 2.3 ceilings ::: $R_{1} = H, R_{2} = M$ Prob 4.1 PIP vs PCP ::: $10$ ms vs $6$ ms Prob 4.2 ceiling / raise ::: $5$ and $5$ Prob 5.1 $R_{H}$ PIP vs PCP ::: $24$ ms vs $19$ ms Prob 5.2 $B_{H}$ PIP vs PCP ::: $23$ ms vs $9$ ms