Real-time constraints — hard and soft deadlines: Exercises

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

Yeh page ek self-testing ladder hai. Har problem ek difficulty level par hai (L1 → L5). Problem padho, solution cover karo, khud try karo, phir collapsible [!recall]- kholo aur check karo. Yahan har number machine-verified hai.

Prerequisite ideas parent note the topic note aur uske neighbours par hain: Rate-Monotonic Scheduling, Earliest Deadline First (EDF), Worst-Case Execution Time analysis, Priority Inversion and Priority Inheritance, RTOS scheduler design, Periodic vs Aperiodic Tasks, Jitter and Latency.

Level 1 — Recognition

L1.1 — Deadline ko classify karo

Har system ke liye batao ki timing requirement hard, firm, ya soft hai, aur late result ki value se justify karo.

(a) Ek car ka airbag controller crash ke 20 ms ke andar fire karna chahiye. (b) Ek video decoder frame 900 produce karta hai; yeh apne display slot ke 5 ms baad aata hai. (c) Ek music streaming app ka buffer refill kuch milliseconds late run karta hai.

Recall Solution

Rule yeh hai: deadline ke baad deliver hue result ki utility dekho.

(a) Hard. Ek late airbag catastrophic hai — late result ki value effectively $- \infty$ hai. Yeh total system failure hai, slowness nahi.
(b) Firm. Ek video frame jo apna display slot miss kar de uski zero value hai (tum use show nahi kar sakte), isliye tum discard karte ho — lekin kuch break nahi hota. Late value = 0, koi catastrophe nahi.
(c) Soft. Thoda sa late buffer refill quality degrade karta hai (ek choti si stutter), lekin result ki abhi bhi reduced value hai; kabhi-kabhi misses tolerated hain.

L1.2 — Utilisation padho

Ek single periodic task hai jisme $C_{1} = 3$ ms aur $T_{1} = 12$ ms hai. CPU ka kitna fraction yeh demand karta hai?

Recall Solution

$U_{1} = \frac{C _{1}}{T _{1}} = \frac{3}{12} = 0.25$ Yeh formula kyun? Har $12$ ms ki window mein task ko $3$ ms CPU chahiye, isliye yeh processor ka average mein $3/12 = 1/4$ occupy karta hai. CPU ka $75%$ free rehta hai.

Level 2 — Application

L2.1 — Task set ki total utilisation

Tasks: $C_{1} = 1, T_{1} = 4$ ; $C_{2} = 2, T_{2} = 8$ ; $C_{3} = 2, T_{3} = 16$ . Total utilisation $U$ compute karo.

Recall Solution

$U = \frac{C _{1}}{T _{1}} + \frac{C _{2}}{T _{2}} + \frac{C _{3}}{T _{3}} = \frac{1}{4} + \frac{2}{8} + \frac{2}{16}$ $U = 0.25 + 0.25 + 0.125 = 0.625$ Sum kyun? Teeno tasks ek ek CPU share karte hain, aur unki demands us single resource ke additive fractions hain. Kyunki $U = 0.625 < 1$ hai, CPU over-subscribed nahi hai — schedulable hone ki ek necessary (abhi sufficient nahi) condition hai.

L2.2 — Rate-Monotonic bound compute karo

$n = 3$ tasks ke set ke liye, Liu–Layland utilisation bound $n (2^{1/ n} - 1)$ compute karo.

Recall Solution

$n (2^{1/ n} - 1) = 3 (2^{1/3} - 1) = 3 (1.259921 - 1) = 3 (0.259921) = 0.779763$ 1 se neeche kyun? Fixed priorities ke under worst-case phasing (saare tasks ek saath release) kabhi-kabhi CPU ko idle force karta hai jab bhi work exist karta hai, isliye tum safely use $100%$ nahi fill kar sakte. $n = 3$ ke liye safe ceiling lagbhag $0.780$ hai.

L2.3 — RM test apply karo

Kya L2.1 ka task set ( $U = 0.625$ ) Rate-Monotonic scheduling ke under schedulable hai?

Recall Solution

$U$ ko L2.2 ke $n = 3$ bound se compare karo: $0.625 \leq 0.779763 ✓$ Haan — RM har deadline guarantee karta hai. Ek sufficient test pass karna schedulability ka proof hai; hum done hain aur kisi exact test ki zaroorat nahi.

Level 3 — Analysis

L3.1 — Jab bound fail ho lekin set theek ho

Tasks: $C_{1} = 1, T_{1} = 3$ ; $C_{2} = 1, T_{2} = 5$ ; $C_{3} = 3, T_{3} = 8$ . (a) $U$ compute karo. (b) Kya yeh $n = 3$ ke liye RM bound pass karta hai? (c) Bound fail karna kya prove karta hai?

Recall Solution

(a) $U = \frac{1}{3} + \frac{1}{5} + \frac{3}{8} = 0.333333 + 0.2 + 0.375 = 0.908333$ . (b) RM bound $= 0.779763$ . Kyunki $0.908 > 0.780$ hai, yeh utilisation test fail karta hai. (c) Fail karna unschedulability ke baare mein kuch prove nahi karta. Liu–Layland bound sufficient, not necessary hai: pass karna success guarantee karta hai, lekin fail karna inconclusive hai. Decide karne ke liye exact Response-Time Analysis run karo (L4 dekho).

L3.2 — Same set par EDF versus RM

L3.1 ke set ke liye ( $U = 0.908$ ), kya yeh EDF ke under schedulable hai? EDF kyun succeed karta hai jahan RM utilisation test inconclusive tha?

Recall Solution

EDF ka exact bound ( $D_{i} = T_{i}$ ke saath) $U \leq 1$ hai. Yahan $U = 0.908 \leq 1$ hai, isliye EDF ise schedule karta hai. EDF kyun jeetta hai: EDF hamesha earliest absolute deadline wali job pehle run karta hai, dynamically re-prioritise karta rehta hai. Yeh worst-case phasing par CPU kabhi waste nahi karta, isliye yeh safely poora processor use kar sakta hai. RM ke fixed priorities nahi kar sakte, aur yehi wajah hai ki RM ka sufficient bound 1 se neeche hota hai.

Agla figure RM-versus-EDF gap ko visual banata hai. Isse aise padho: horizontal axis tasks ki sankhya $n$ hai; vertical axis woh highest utilisation hai jo har policy safely accept kar sakti hai. Upar flat black line $1$ par EDF ceiling hai — EDF CPU hamesha completely fill kar sakta hai. Red curve RM bound $n (2^{1/ n} - 1)$ hai: yeh ek task ke liye $1$ par shuru hoti hai, phir sag karti hai, aur dashed marker $ln 2 \approx 0.693$ ko cross karti hai jiske paas yeh $n \to \infty$ hone par approach karti hai. Red dot hamara L3 set $n = 3, U = 0.908$ par mark karta hai — yeh red RM ceiling ke upar hai (isliye RM ka utilisation test inconclusive hai) lekin black EDF line ke neeche hai (isliye EDF ise schedule karta hai). Insight yeh hai: EDF choose karna tumhe red curve aur black line ke beech ka poora gap deta hai.

Figure — Real-time constraints — hard and soft deadlines

Level 4 — Synthesis

L4.1 — Exact Response-Time Analysis

Tasks (deadline = period), RM ke hisaab se priorities (shorter period = higher priority): $C_{1} = 2, T_{1} = 5$ ; $C_{2} = 2, T_{2} = 8$ ; $C_{3} = 3, T_{3} = 12$ . Iteration use karo: $R_{i} = C_{i} + \sum_{j \in h p (i)} ⌈ \frac{R _{i}}{T _{j}} ⌉ C_{j}$ $R_{3}$ (lowest-priority task ka response time) find karo aur decide karo ki yeh apni deadline $D_{3} = 12$ meet karta hai ya nahi.

Recall Solution

Task 3 ka period sabse lamba hai, isliye yeh lowest priority hai; higher-priority set $h p (3) = {1, 2}$ hai (dono ise preempt karte hain). Ceiling $⌈ R_{3} / T_{j} ⌉$ count karta hai kitni baar task $j$ window $R_{3}$ ke andar task 3 ko interrupt karta hai.

Start: $R_{3}^{(0)} = C_{3} = 3$ .

Iteration 1: $R_{3} = 3 + ⌈ \frac{3}{5} ⌉ \cdot 2 + ⌈ \frac{3}{8} ⌉ \cdot 2 = 3 + 1 \cdot 2 + 1 \cdot 2 = 7$

Iteration 2: $R_{3} = 3 + ⌈ \frac{7}{5} ⌉ \cdot 2 + ⌈ \frac{7}{8} ⌉ \cdot 2 = 3 + 2 \cdot 2 + 1 \cdot 2 = 9$

Iteration 3: $R_{3} = 3 + ⌈ \frac{9}{5} ⌉ \cdot 2 + ⌈ \frac{9}{8} ⌉ \cdot 2 = 3 + 2 \cdot 2 + 2 \cdot 2 = 11$

Iteration 4: $R_{3} = 3 + ⌈ \frac{11}{5} ⌉ \cdot 2 + ⌈ \frac{11}{8} ⌉ \cdot 2 = 3 + 3 \cdot 2 + 2 \cdot 2 = 13$

Iteration 5: $R_{3} = 3 + ⌈ \frac{13}{5} ⌉ \cdot 2 + ⌈ \frac{13}{8} ⌉ \cdot 2 = 3 + 3 \cdot 2 + 2 \cdot 2 = 13$

$R_{3} = 13$ par converge hua. Ab test karo: $R_{3} = 13 > D_{3} = 12$ → task 3 apni deadline MISS karta hai. Set not RM-schedulable hai, chahe (check karo) $U = \frac{2}{5} + \frac{2}{8} + \frac{3}{12} = 0.9 \leq 1$ ho.

Iterate kyun karte hain? $R_{3}$ dono sides par appear karta hai: ek lamba response window zyada preemptions admit karta hai, jo window ko phir se lengthen karta hai. Hum tab tak repeat karte hain jab tak value change nahi hoti (a fixed point), jo true worst-case response time hai.

Neeche ka timeline figure dikhata hai kyun $R_{3}$ $13$ tak stretch hota hai. Time (ms) left se right run karta hai. Top row (T1) task 1 ke releases $t = 0, 5, 10$ par dikhata hai, har ek $2$ -ms block of CPU jo yeh task 3 se pehle grab karta hai. Middle row (T2) task 2 ke releases $t = 0, 8$ par dikhata hai, phir se $2$ -ms blocks jo task 3 par priority liye hain. Bottom red row (T3) task 3 ka khud ka $3$ ms kaam hai — lekin upar ka har higher-priority block ise baad mein push karta hai, isliye uski completion $t = 13$ (solid red line) tak drag hoti hai. Dashed black line deadline $D_{3} = 12$ hai: kyunki red completion line uske daayein taraf land karti hai, task 3 miss karta hai. Picture concretely dikhati hai ki ceilings ne kya count kiya: preemptions gaps kha jaate hain aur response window ko deadline ke aage khiinch dete hain.

Level 5 — Mastery

L5.1 — Utilisation budget ke under schedulable set design karo

Tumhe $C_{1} = 1, T_{1} = 4$ ; $C_{2} = 1, T_{2} = 5$ mein ek third task add karna hai taaki teeno $n = 3$ ke liye RM utilisation bound (jo $0.779763$ hai) pass karen. Naye task ka $T_{3} = 10$ hai. Sabse bada integer $C_{3}$ (ms mein) kya choose kar sakte ho?

Recall Solution

Fixed part: $U_{12} = \frac{1}{4} + \frac{1}{5} = 0.25 + 0.2 = 0.45$ . Bacha hua budget: $0.779763 - 0.45 = 0.329763$ . Allowed $C_{3}$ : solve karo $\frac{C _{3}}{10} \leq 0.329763 \Rightarrow C_{3} \leq 3.29763$ . Sabse bada integer: $C_{3} = 3$ . Check: $C_{3} = 3$ ke saath, $U = 0.45 + 0.3 = 0.75 \leq 0.779763$ ✅. $C_{3} = 4$ ke saath, $U = 0.85 > 0.78$ , fail. Isliye answer hai $C_{3} = 3$ ms.

L5.2 — Hard vs soft design decision

Ek drone flight-control loop aur ek telemetry-logging task ek MCU share karte hain. Flight loop ka hard deadline hai; logger ka soft. Overload mein, kaun sa task work shed kare, aur yeh design principle kya govern karta hai?

Recall Solution

Soft telemetry logger work shed karta hai — log entries drop ya down-sample karo, ya ek cycle skip karo. Flight-control loop ka hard deadline kabhi bhi compromise nahi hona chahiye kyunki miss catastrophic hai. Principle: graceful degradation — overload mein tum low-value soft tasks ko degrade karte ho hard tasks ko protect karne ke liye. Yeh ek scheduling/priority design choice hai; hard task ko guaranteed CPU do (jaise highest RM priority + shared locks par priority inheritance) aur soft task ko best-effort banao.

Recall Feynman check: poora ladder ek saanth mein bolo

Pehle tum deadline type name karte ho (L1), phir CPU demand $U = \sum C_{i} / T_{i}$ measure karte ho (L2), phir ise sahi bound ke against judge karte ho — RM ke liye $n (2^{1/ n} - 1)$ , EDF ke liye $1$ — yeh jaante hue ki RM bound fail karna sirf "unknown, exact test run karo" matlab hai (L3). Exact test iterating Response-Time equation hai, jo true worst case par converge karta hai (L4). Aakhir mein tum budget ke andar design karte ho aur hard tasks ko soft wale degrade karke protect karte ho (L5).