Real-time constraints — hard and soft deadlines: Visual walkthrough

5.5.12 · D2 · Coding › Embedded Systems & Real-Time Software › Real-time constraints — hard and soft deadlines

Yeh parent topic ka picture-first companion hai. Har symbol pehle draw kiya jaata hai, use karne se pehle. Agar aapne kabhi letters wala fraction nahi dekha, tab bhi aap sahi jagah par hain.

Step 1 — Timeline par ek single job kaisa dikhta hai

KYA. Ek horizontal line draw karo: yeh time hai, jo left se right flow karta hai. Ek job kaam ka ek tukda hai jo computer ko karna hai. Yeh kisi moment par appear hota hai, kuch der chalta hai, aur khatam hota hai.

KYU. "Deadlines meet karna" ki baat karne se pehle hamein un teen moments ko dekhna hoga jo matter karte hain. Baad ki saari cheez sirf is ek line par distances count karna hai.

PICTURE. Neeche ke figure mein, time line par teen marks hain:

==Release time $r$ == (deep teal tick): woh instant jab job ready ho jaati hai — jaise homework aapko diya jaane ka moment.
==Deadline $d$ == (plum tick): latest allowed finish time — bus yahan se jaati hai.
Finish time (burnt-orange dot): jab job actually khatam hui.

Figure — Real-time constraints — hard and soft deadlines

Step 2 — Response time, aur woh ek rule jo "on time" define karta hai

KYA. Release se actual finish tak ka distance measure karo. Isse ==response time $R$ == kaho. Release se deadline tak ka distance measure karo. Isse ==relative deadline $D$ == kaho, toh $d = r + D$ .

KYU. "On time" koi feeling nahi hai — yeh do lengths ka comparison hai. Hume ek single, checkable rule chahiye. Yeh raha:

$job actually kitna time laga R \leq kitna time lene ki permission thi D$

Agar orange finish plum deadline par ya pehle aata hai, toh $R \leq D$ aur hum kehte hain job ne deadline meet ki. Agar baad mein aata hai, toh $R > D$ — ek miss.

PICTURE. Green arrow (neeche) $R$ ko span karta hai; plum arrow $D$ ko span karta hai. On time bas yahi hai: green arrow plum arrow se lamba na ho.

Step 3 — "Worst case" kyun, na ki "usual case" (WCET)

KYA. Ek job hamesha same time nahi leti — cache miss, branch, slow sensor read sab isko stretch karte hain. Hum sabse zyada woh time lete hain jo yeh kabhi bhi run kar sakti hai aur ise ==WCET $C$ == (Worst-Case Execution Time) kehte hain. Worst-Case Execution Time analysis dekho.

KYU. Deadline bure din miss hoti hai, average din kabhi nahi. Agar hum average length se plan karein, toh hum ek aise din ke liye plan kar rahe hain jo shayad humein kabhi bachaye nahi. Picture danger ko obvious bana deti hai.

PICTURE. Ek hi job ke kai possible run-lengths faint bars ke roop mein stack ki gayi hain; average comfortably deadline ke andar hai, lekin sabse lamba bar (burnt orange, WCET) plum deadline ke baahr jhankta hai. Uss bar ke liye plan karo, average ke liye nahi.

Step 4 — Ek repeating task: "utilisation" kya measure karta hai

KYA. Ek periodic task sirf ek baar nahi chalti — yeh har ==period $T$ == seconds mein re-release hoti hai (dekho Periodic vs Aperiodic Tasks). $T$ length ki har window mein ise $C$ seconds CPU chahiye. CPU ka fraction jo yeh consume karta hai:

$U_{i} = \frac{C _{i} per release kaam ke seconds}{releases ke beech seconds T _{i}}$

KYU. Hum ek ratio introduce kar rahe hain kyunki hum ek single number chahte hain — ek share — jise hum tasks ke across add kar sakein. Akele seconds fairly add nahi hote (har 2 s mein ek 1-second job aur har 100 s mein ek 1-second job wildly different loads hain). Period se divide karne par raw seconds machine ka comparable percentage ban jaate hain.

PICTURE. Width $T$ ka ek box ki tarah draw kiya ek period; width $C$ ka orange work-bar uske andar baitha hai. $U$ literally "box ka kitna fraction orange hai" hai.

KYA. Ek CPU par $n$ tasks ke saath, unki demands same resource ke shares hain, toh yeh add hoti hain:

$U = \sum_{i = 1}^{n} \frac{C _{i}}{T _{i}} = \frac{C _{1}}{T _{1}} + \frac{C _{2}}{T _{2}} + \dots + \frac{C _{n}}{T _{n}}$

Bada $\sum$ ("sigma") ka matlab sirf "in sabko $i = 1$ se $n$ tak add karo" hai.

KYU. Ek pie, kaafi saare khaane waale. Agar maange gaye slices puri pie se zyada sum karein, koi bhookha rahega — ek deadline zaroor miss hogi. Yeh pehla, unbreakable gate hai.

PICTURE. Teen orange slices ek single CPU bar mein stack ki gayi hain. Agar yeh 100% line se overflow ho jaayein, toh CPU over-subscribed hai — physically impossible satisfy karna.

Step 6 — Catch: $U \leq 1$ fixed priority ke liye kaafi nahi

KYA. Rate-Monotonic scheduling (Rate-Monotonic Scheduling) ke under — shorter period ko higher, fixed priority milti hai — yahan tak ki $U$ 100% se neeche hone par bhi miss ho sakta hai. Worst phasing par (jab ek bada low-priority job kai high-priority arrivals ke beech mein caught hota hai) CPU bilkul galat moment par idle baithne par majboor hota hai.

KYU. Fixed priorities rigid hote hain: ek high-priority task hamesha queue jump karta hai, chahe ek low-priority task apni deadline blow karne wala ho. Yeh rigidity usable time waste karti hai, isliye ek safe fixed-priority system mein headroom chhodni chahiye.

PICTURE. Worst-case line-up: ek low-priority job (plum) baar baar high-priority arrivals (orange) se preempted hoti rehti hai (related hazard ke liye dekho Priority Inversion and Priority Inheritance), apna finish deadline ke baad push karte hue — even though total load 100% se neeche hai.

Step 7 — Liu–Layland ceiling, aur 0.693 kahan se aata hai

KYA. Liu & Layland ne RM ke liye ek sufficient bound prove kiya:

$U \leq n tasks ke liye safe ceiling n (2^{1/ n} - 1)$

Har symbol: $n$ = tasks ki sankhya; $2^{1/ n}$ = 2 ka $n$ -th root; puri right side $n$ badhne par shrink hoti hai.

KYU. Yeh exactly utni headroom hai jitni Step 6 ne demand ki thi, worst phasing ke liye compute ki gayi. Jaise aap zyada tasks pile karte hain ( $n \to \infty$ ) ceiling $ln 2 \approx 0.693$ tak sink hoti hai — aap safely sirf CPU ka lagbhag 69% use kar sakte hain fixed priorities ke saath.

PICTURE. $n$ ke versus ceiling ka ek curve: $n = 1$ par $1.00$ se shuru hota hai, $n = 2$ par $0.828$ tak girta hai, $n = 3$ par $0.780$ , aur dotted plum line par $0.693$ par flatten ho jaata hai. Full-CPU line $1.0$ par (Earliest Deadline First (EDF) ceiling) contrast ke liye upar baithti hai.

Step 8 — Real numbers par test run karna

KYA. Tasks: $C_{1} = 1, T_{1} = 4$ ; $C_{2} = 2, T_{2} = 6$ ; $C_{3} = 1, T_{3} = 8$ .

$U = \frac{1}{4} + \frac{2}{6} + \frac{1}{8} = 0.25 + 0.333 \dots + 0.125 = 0.708$

$n = 3$ ke liye RM ceiling: $3 (2^{1/3} - 1) = 3 (1.2599 - 1) = 0.780$ .

KYU. Step 5 physical gate check karta hai ( $0.708 \leq 1$ ✓). Step 7 RM ceiling check karta hai: $0.708 \leq 0.780$ ✓. Ek sufficient test pass karna ek proof hai ki saari hard deadlines meet ho rahi hain.

PICTURE. Ek thermometer: measured load $0.708$ (orange fill) RM red line $0.780$ se neeche baitha hai, jo EDF line $1.0$ se neeche baitha hai. Green zone = provably safe.

Step 9 — Degenerate case: jab ceiling "don't know" kehti hai

KYA. Ab imagine karo $U = 0.79$ with $n = 3$ . Yeh RM ceiling fail karta hai ( $0.79 > 0.780$ ). Kya iska matlab unschedulable hai?

KYU. Nahi — kyunki ceiling sufficient hai, necessary nahi. Ek sufficient test fail karna kuch bhi prove nahi karta. Pakka decide karne ke liye hum exact Response-Time Analysis (RTOS scheduler design) run karte hain:

$R_{i} = apna kaam C_{i} + \sum_{j \in h p (i)} kitni baar j preempt karta hai i ko ⌈ \frac{R _{i}}{T _{j}} ⌉ har preemption ki cost C_{j}$

$h p (i)$ = $i$ se higher priority wale tasks ka set. Ceiling brackets $⌈ \cdot ⌉$ upar round karte hain: ek task jo window ke andar ek bhi baar arrive kare woh poora $C_{j}$ churata hai. Hum $R_{i}$ iterate karke solve karte hain jab tak yeh change karna band na ho; schedulable iff $R_{i} \leq D_{i}$ .

PICTURE. Load axis ka teen-zone map: green (RM ceiling se neeche → proven safe), amber (ceiling se upar lekin $\leq 1$ → unknown, exact analysis run karo, aur jitter/latency matter karta hai — dekho Jitter and Latency), red (1 se upar → proven impossible).

Ek-picture summary

Sab kuch ek single decision funnel mein compress hota hai: worst-case load measure karo, ceilings se compare karo, colour padho.

Recall Feynman: poora walkthrough simple words mein

Ek bus imagine karo jo aapko pakadni hai. Ek job hai aapka ghar se nikalna; deadline hai jab bus jaati hai. Pehle humne ek trip ko line par draw kiya aur kaha "on time" ka matlab sirf yahi hai ki aapka finish arrow aapke allowed arrow se lamba na ho. Phir humne maana ki kuch sawere slow hote hain — isliye hum aapki sabse buri sawer ke liye plan karte hain (WCET), average ke liye kabhi nahi. Aage humne notice kiya ki aap yeh bus har roz pakdte hain (ek period), aur aapke din ka fraction jo yeh khaata hai woh $C / T$ hai. Kai rozaana kaam stack karo aur unke fractions add hote hain — poore din se zyada maango aur kuch zaroor drop hoga. Lekin ek twist hai: ek rigid "hamesha urgent wala pehle karo" rule (Rate-Monotonic) ke saath, aap worst moments par thoda time waste karte hain, isliye aap safely apna sirf lagbhag 69% din fill kar sakte hain, 100% nahi. Woh safe ceiling hai $n (2^{1/ n} - 1)$ . Humne real kaam test kiye: load $0.708$ , ceiling $0.780$ → provably fine. Finally, honest caveat: agar aapka load ceiling se upar jata hai lekin poore din se neeche rehta hai, toh simple test bas shrug karta hai — exact preemptions simulate karne padenge (Response-Time Analysis) pakka jaanne ke liye. Green = safe, amber = dhyan se check karo, red = chhod do. Yahi hai hard real-time: fast nahi, balki provable.

Recall Quick self-check

"On time" ke liye compare ki jaane wali do lengths? ::: Response time $R$ vs relative deadline $D$ ; met iff $R \leq D$ . $C$ ko $T$ se kyun divide karte hain? ::: Raw seconds ko ek comparable CPU fraction mein convert karne ke liye jo tasks ke across sum ki ja sake. $n = 3$ ke liye RM ceiling? ::: $3 (2^{1/3} - 1) \approx 0.780$ . $U = 0.79$ , $n = 3$ RM fail karta hai — unschedulable? ::: Nahi — bound sirf sufficient hai; Response-Time Analysis run karo. $⌈ R_{i} / T_{j} ⌉$ kyun? ::: Count karta hai kitni baar higher-priority task $j$ , task $i$ ko $R_{i}$ ke andar preempt karta hai.