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

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

Shuru karne se pehle, teen words jo hum baar baar use karte hain:

True or false — justify

Priority inversion sirf do priority levels se ho sakti hai

False — tumhe kam se kam teen levels chahiye, kyunki unbounded inversion ke liye ek Medium task chahiye (jo lock se unrelated ho) jo Low ko preempt kare; sirf H aur L ke saath koi teesra task nahi hai jo unbounded delay inject kare.

Priority inversion scheduler ke code mein ek bug hai

False — yeh do correct rules ke beech ek emergent interaction hai (priority CPU choose karti hai, mutex critical section choose karta hai); har rule akela bilkul theek hai, bas dono ek saath disagree karte hain.

Bounded priority inversion ko hamesha eliminate karna chahiye

False — bounded inversion unavoidable aur acceptable hai: H ko L ka wait karna hi padega jab tak woh apna critical section finish kare, kyunki mutual exclusion apna kaam kar raha hai; sirf unbounded wala hissa dangerous bug hai.

Priority Inheritance (PIP) deadlock prevent karta hai

False — PIP sirf priority boost karta hai taaki Medium, Low ko preempt na kar sake; lock-ordering ke baare mein yeh kuch nahi karta, isliye do tasks agar R1 aur R2 ko ulte order mein grab karen to deadlock ho sakta hai (dekho Deadlock — conditions and prevention).

Priority Ceiling Protocol (PCP) deadlock prevent karta hai

True — ceiling gate lock acquisition pe ek acyclic ordering impose karta hai, isliye deadlock ke liye circular-wait condition kabhi form nahi ho sakti.

PIP ke under ek high task ko kaafi lower tasks se sequence mein block kiya ja sakta hai

True — har lower task jo ek relevant critical section hold karta hai, H ko ek baar block kar sakta hai, isliye worst-case blocking lower tasks ke upar sum hoti hai; yeh chained/transitive blocking hai.

PCP ke under ek high task ko har activation mein zyada se zyada ek baar block kiya ja sakta hai

True — ceiling gate nested tangle ko kabhi form nahi hone deta, isliye H ek single (sabse lambi relevant) critical section ka wait karta hai, na ki ek sum ka.

PIP mein, low task boost hone ke baad hamesha ke liye apni boosted priority rakhta hai

False — boost temporary hai: L apni original priority pe wapas aata hai jis pal woh mutex release karta hai.

ICPP (immediate ceiling) ka worst-case blocking bound original PCP se zyada kharab hai

False — ICPP same worst-case bound deta hai; bas lock hote hi priority turant raise karta hai, na ki sirf jab block actually occur ho.

Priority inversion ka matlab hai CPU idle hai jab H wait kar raha hai

False — CPU busy hai (Low ya Medium run kar raha hai); problem yeh hai ki busy work sabse urgent work nahi hai, isliye "CPU utilised" metrics is bug ko chupa dete hain.

ICPP ke under ek task run shuru hone ke baad block ho sakta hai

False — kyunki ICPP ek task ko lock karte hi resource ceiling tak raise kar deta hai, ek task sirf shuru hone se pehle block ho sakta hai; ek baar run karne ke baad use koi aisa task preempt nahi kar sakta jo uske saath ek lock share karta ho.

Rate-Monotonic schedulability analysis priority inversion ko ignore kar sakti hai

False — blocking time

B_{H}

ko response-time equation mein add karna padta hai; ignore karne se ek "un-schedulable" set schedulable lag sakta hai aur deadlines miss ho sakti hain.

Spot the error

"Inversion fix karne ke liye, low task ko permanently high priority de do." — kya toot jaata hai?

Yeh priority scheduling ko poori tarah se defeat kar deta hai: Low ab genuinely urgent kaam ko hamesha preempt karega; boost temporary aur conditional hona chahiye — sirf tab jab actually ek needed lock hold ho.

"PIP medium task ko boost karta hai taaki woh interfere karna band kare." — kya galat hai?

PIP Low (lock holder) ko H ki priority tak boost karta hai, Medium ko nahi; Low ko boost karna hi hai jo Medium ko use preempt karne se rokta hai — Medium ki priority kabhi touch nahi hoti.

"Ek resource ki ceiling woh priority hai jo bhi use abhi hold kar raha hai." — isse correct karo.

Ceiling static hai: yeh us highest-priority task ki priority hai jo kabhi bhi us resource ko lock karega, offline compute ki jaati hai — yeh current holder ki runtime property nahi hai.

"Original PCP ke under, ek task resource lock kar sakta hai agar uski priority system ceiling ke kam se kam barabar ho." — isse fix karo.

Uski priority strictly higher honi chahiye system ceiling se (highest ceiling un resources mein se jo doosre tasks ne lock kiya hua hai); "kam se kam" se tangle form ho jaata aur once-only guarantee toot jaati.

"Priority inversion sirf hard real-time systems ko affect karta hai." — kya overstated hai?

Yeh kisi bhi preemptive priority system ko affect karta hai jisme shared mutexes hain; hard real-time systems ise sirf zyada notice karte hain kyunki missed deadline catastrophic hoti hai (jaise Mars Pathfinder ka watchdog reset).

"Mutex ki jagah semaphore use karne se problem avoid hoti hai." — yeh misleading kyun hai?

Ek counting semaphore ka koi owner nahi hota, isliye koi task nahi hai jiski priority boost ki ja sake — inheritance/ceiling protocols ko ek owned lock (mutex) chahiye; semaphore pe switch karne se fix hatta jaata hai, problem nahi.

"PCP ko PIP ke unlike koi offline analysis nahi chahiye." — ise reverse karo.

Bilkul ulta hai: PCP ko runtime se pehle har resource ki ceiling ki static computation chahiye; PIP ko aisi koi analysis nahi chahiye (yeh purely runtime pe react karta hai jab block occur ho).

Why questions

Low ki priority raise karna (PIP) specifically unbounded delay kyun rokta hai?

Kyunki Medium ek boosted Low ko ab preempt nahi kar sakta, Low apna critical section bina interruption ke finish kar leta hai; H ka wait Low ke critical-section length tak shrink ho jaata hai — jo ek bounded, analyzable quantity hai jo Medium ke runtime se independent hai.

PCP ke under worst-case bound mein

\sum

ki jagah

max

kyun hota hai?

Ceiling gate guarantee karta hai ki H ko total zyada se zyada ek baar block kiya jaaye, isliye hum single longest relevant critical section lete hain (ek max), jabki PIP mein har lower task ke liye ek block allow hota hai (ek sum).

Real RTOSes mein ICPP popular kyun hai PCP ki tighter theory ke bawajood?

ICPP implement karna bahut simple hai — lock pe ceiling tak raise karo, unlock pe restore karo, system ceiling ya who's blocked ka koi runtime tracking nahi — aur phir bhi same worst-case blocking bound milta hai (yeh PTHREAD_PRIO_PROTECT hai).

Priority inheritance ko mutex mein ek owner kyun chahiye?

Boost ka matlab hai "holder ko H ki rank do"; yeh tab hi kar sakte ho jab lock record kare kaunsa task use hold karta hai — mutex apna owner track karta hai, ek unowned semaphore nahi karta.

Blocking time

B_{H}

add karna Rate-Monotonic feasibility ke liye kyun matter karta hai?

Ek high-priority task ka response time ab lower tasks ka wait karne mein bitaya time include karta hai, jo RM ka basic utilisation test ignore karta hai;

B_{H}

bhulaane se response time underestimate hota hai aur ek aisa set certify ho sakta hai jo actually deadlines miss karta hai.

Chained (transitive) blocking PIP ko costly kyun bana sakti hai, bhaade bounded hone ke bawajood?

Agar H, R1 ka wait kare jo Mid hold karta hai, aur Mid, R2 ka wait kare jo Low hold karta hai, to boosts hierarchy ke through chain karte hain aur H ki blocking har nested critical section mein accumulate hoti hai — bounded hai, lekin sum bada aur analyse karna mushkil ho sakta hai.

In bounds ke liye key input kyun har critical section ka WCET hai?

Dono

B_{H}

formulas purely critical-section durations mein expressed hain, isliye guaranteed blocking bound compute karne ke liye tumhe har critical section ki worst-case length pata honi chahiye — ek loose WCET poori schedulability guarantee ko loose bana deta hai.

Edge cases

Agar H aur L kabhi actually ek resource share nahi karte — kya H phir bhi L se inversion-blocked ho sakta hai?

Nahi — inversion ke liye ek shared mutex chahiye; agar unke critical sections disjoint hain, to L ka lock H ke liye irrelevant hai aur priority scheduling normally behave karta hai.

Agar Medium kabhi ready nahi hota Low ke critical section ke dauran, kya tab bhi inversion hai?

Bounded inversion tab bhi hai (H, L ke critical section ka wait karta hai), lekin unbounded inversion nahi, kyunki unbounded case ke liye Medium ko actually Low ko preempt karna padta hai — danger latent hai, triggered nahi.

Do tasks, dono ICPP ke under, dono same single resource chahte hain jiska ceiling = dono mein se higher — kya ye deadlock kar sakte hain?

Nahi — ek single resource mein cycle banane ke liye koi doosra lock nahi hai, aur ICPP ka immediate raise matlab hai jo pehle lock karta hai woh apna critical section completion tak bina doosre ke preemption ke run karta hai; deadlock ke liye kam se kam do resources chahiye jo conflicting order mein acquire ho.

PCP ke under, ek task ek aisa resource lock karne ki koshish karta hai jiska ceiling uski apni priority ke barabar hai — allowed hai?

Rule uski priority ko doosre tasks ke held resources ki ceilings se compare karta hai; apna pehla resource lock karna hamesha allowed hai kyunki us moment koi doosra task kuch bhi hold nahi kar raha blocking ceiling ke saath.

Ek low task lock hold karta hai aur phir ek H-se-higher task (use VH kahein) ready ho jaata hai lekin koi lock nahi chahiye — kya inversion VH ko affect karta hai?

Nahi — VH koi resource share nahi karta, isliye woh simply preempt karta hai aur run karta hai; inversion kabhi sirf us task ko delay karta hai jisko wait karna padta hai ek lock par jo ek lower task hold karta hai.

Agar ek system mein priority levels hain lekin koi preemption nahi hai (cooperative scheduling), kya unbounded inversion ho sakti hai?

Nahi — unbounded inversion ke liye Medium ko Low ko preempt karna padta hai; preemption ke bina ek running task voluntarily yield karta hai, isliye Medium, Low ko CPU se force nahi kar sakta mid-critical-section mein.

Kya hoga agar low task, PIP ke under boosted hote hue, khud ek doosre mutex par block ho jaaye jo ek even lower task hold karta hai?

Boost transitively chain ke neeche propagate hota hai (doosra holder bhi boosted ho jaata hai); yeh exactly woh transitive/chained blocking hai jo PIP allow karta hai lekin PCP prevent karta hai — dekho RTOS task states and context switching jisme blocked→ready transitions cascade kaise karte hain.

Recall Two-line self-check

Woh single sentence jo PIP aur PCP ko alag karti hai? ::: PIP react karta hai — block hone ke baad holder ko boost karta hai (bound = lower tasks ka sum, deadlock phir bhi possible); PCP tangle ko pehle hi rokta hai ek static ceiling gate se (bound = single max, deadlock impossible). Woh single reason kyun inversion CPU-usage graph par "invisible" hai? ::: CPU poori tarah se busy rehta hai Low ya Medium run karte hue — utilisation healthy lagti hai jabki sabse urgent task starve karta rehta hai.