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

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

Pehle hum priority-inversion problem ko saaf se state bhi kar sakein, uske liye hume kuch ideas ka ek chhota toolbox chahiye. Parent note mein preemptive, mutex, critical section, priority, bounded, aur $B_{H}$ aur $CS_{j, k}$ jaise symbols use hote hain. Yeh page unhe ek-ek karke bilkul zero se build karta hai, ek aisi order mein jahan har idea usse pehle wale pe tika ho.

1. Task — woh cheez jo run karna chahti hai

Picture: teen logon (teen tasks) aur ek kursi (processor) ki kalpana karo. Sirf woh insaan jo kursi par hai, running hai. Baaki line mein khade hain — yeh ready hai. Jo koi delivery ka intezaar karne ke liye side mein chala gaya hai woh blocked hai — woh kursi khali hone par bhi baith nahi sakta.

Topic ko yeh kyun chahiye: priority inversion ek kahaani hai ki har pal kaun kursi par hai, isliye pehle hume yeh tay karna hoga ki task kya hoti hai aur woh kis state mein hai. Poore state machine ke liye dekho RTOS task states and context switching.

2. Priority — woh number jo decide karta hai kaun baithega

Picture: har insaan par ek "VIP rank" tag socho. Jab do log ek hi kursi chahte hain, jo zyada rank wala hoga use milegi.

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

Figure dekho: jitna zyada bar ucha, utni zyada priority. H, M se upar hai, M, L se upar. Yeh height-picture apne dimag mein rakhho — baad ki har timeline bas inhi teen heights ki kursi mein baari-baari hai.

3. Preemption — kisi ko kursi se nikalna

Picture: ek VIP andar aata hai; security turant jo currently baithe hain unhe kursi se uthati hai (dheere se, unki jagah bachake) aur VIP ko baitha deti hai. Woh uthana-aur-badalna context switch kehlata hai.

Topic ko yeh kyun chahiye: yeh do takraane wale rules mein se rule #1 hai. Yeh kehta hai "urgency akele kursi decide karti hai." Priority inversion isliye hoti hai kyunki ek doosre rule (mutex, agle mein) ko yeh todne ki permission deni padti hai.

4. Shared resource aur mutual exclusion — ek-chaabi wala darwaza

Picture: ek phone booth (resource) aur bilkul ek chaabi. Jo chaabi pakde hua hai woh booth ke andar hai = apne critical section ke andar. Jo bhi aur andar jaana chahta hai use bahar locked darwaze ke saamne ruka rehna hoga, blocked.

Topic ko yeh kyun chahiye: yeh rule #2 hai, aur yeh rule #1 se takrata hai. Mutex kehta hai "jo pehle chaabi le gaya, wahi rahega, rank se farq nahi padta." Isliye chaabi pakde hua ek low-rank task ek high-rank task ko ruka sakta hai — priority temporarily ulti. Woh contradiction hi inversion ka beej hai. (Mutex aur uske cousin semaphore ke beech fark ke liye, dekho Mutexes vs Semaphores.)

5. Blocking — apne se neeche waale ka intezaar karna

Picture: VIP (H) phone booth ke bahar frozen khada hai jabki ek aam insaan (L) andar baat kar raha hai aur sirf ek chaabi pakde hua hai. VIP ka rank darwaze par bekaar hai — chaabi, rank nahi, entry decide karti hai.

Topic ko yeh kyun chahiye: parent note mein har solution isi backwards wait ke kitne lambe chalne se naapa jaata hai. Us length ka apna symbol hai, aage.

6. Bounded vs unbounded — kya wait ka time mein ek ceiling hai?

Picture: bounded = ek wall wali wait jise tum maap sakte ho (kaho "zyada se zyada 5 ms"). Unbounded = ek gali jo har baar tab lambi hoti rehti hai jab task M aur run karne ka decide kare.

Figure ko upar se neeche time ki tarah padho. Bounded row mein H sirf tab wait karta hai jab L apna chhota critical section khatam karta hai. Unbounded row mein, M barabar L se kursi cheen leta hai, isliye L chaabi wapas nahi kar sakta, isliye H ki wait M ke runtime ke saath stretch hoti hai — koi wall nahi.

Topic ko yeh kyun chahiye: Bounded inversion unavoidable hai aur theek hai. Unbounded inversion asli bug hai (isse Mars Pathfinder crash hua tha). Priority inheritance aur priority ceiling ka poora point unbounded ko bounded mein badalna hai. "Bounded" ko ek asli deadline guarantee mein badalne ke liye ise Schedulability analysis & response-time analysis mein feed karo.

7. Symbols: $B_{H}$ aur $CS_{j, k}$

Ab jab ideas exist karte hain, parent note ke math symbols sirf shorthand hain.

$B_{H}$ ki hume khaas zaroorat kyun hai: ek hard real-time task ko hamesha apni deadline se pehle khatam hona chahiye. Uska response time = uska apna kaam plus jo bhi use force karke wait karwaya gaya. Woh forced wait exactly $B_{H}$ hai. Agar $B_{H}$ bounded hai, toh hum ise add karke prove kar sakte hain ki deadline poori hogi; agar yeh unbounded hai, toh koi proof possible nahi — system design se hi unsafe hai. Isliye har protocol ko $B_{H}$ ke size se judge kiya jaata hai. (Har task ke apne run-time ka estimate karna ek alag kala hai — dekho Worst-Case Execution Time (WCET) analysis.)

Prerequisite map

Ise neeche se upar padho: tasks aur priorities preemption ko feed karti hain; resources mutex ko feed karte hain; woh do streams blocking par milti hain, jo yeh decide karti hai ki wait bounded hai ya unbounded, jo woh hai jo symbols measure karte hain — aur yeh sab priority-inversion topic mein hi pour hota hai.

Equipment checklist

Self-test — daayaa side dhako aur reveal karne se pehle jawab zor se bolo.

Is topic mein task ki teen possible states kya hain?

Running (kursi mein), Ready (apni baari ka intezaar kar raha hai), Blocked (kisi aur cheez ka intezaar kar raha hai).

Is topic mein, kya higher priority number ka matlab zyada urgent hai ya kam urgent?

Zyada urgent — urgency mein H > M > L.

Jaise hi ek higher task ready hoti hai, "preemptive" scheduling kya karta hai?

Turant lower task ko processor se nikalta hai aur higher wale ko run karta hai (context switch).

Critical section kya hai?

Code ka woh hissa jahan ek task actually ek shared resource use kar rahi hai, mutex se guarded.

Ek task ka mutex par "block" hone ka kya matlab hai?

Woh run nahi kar sakta kyunki jo task lock pakde hua hai (aksar ek lower-priority wala) usne abhi release nahi kiya.

"Unbounded" khatarnak word kyun hai?

Wait ka koi fixed maximum nahi hota — yeh ek unrelated task ke runtime ke saath badh sakta hai, isliye koi deadline guarantee nahi ho sakti.

CS_{j, k}

mein,

j

aur

k

kiske liye hain?

j

= kaun sa task,

k

= us task ke critical sections mein se kaun sa; poori cheez us section ki time length hai.

B_{H}

kya represent karta hai?

High-priority task H ka worst-case blocking time — sabse lambi duration jitnee woh lower tasks ke locks ka intezaar karte hua stuck reh sakta hai.

B_{H}

ki hume zaroorat kyun hai?

Ek task ka deadline check = uska apna kaam +

B_{H}

; sirf ek bounded

B_{H}

se hi hum prove kar sakte hain ki deadline poori hogi.

Agle page (D2) par priority ceiling number build hoga aur prove hoga ki ceiling rule kyun deadlock ko forbid karta hai. Hub par wapas: parent topic.