Real-time constraints — hard and soft deadlines: Worked examples

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

Shuru karne se pehle, char quantities ka ek reminder (sab parent topic note mein build hue hain): $C_{i}$ = worst-case execution time (dekho Worst-Case Execution Time analysis), $T_{i}$ = period, $D_{i}$ = relative deadline, $U_{i} = C_{i} / T_{i}$ = wo fraction jitna ek CPU ka task $i$ khaata hai.

Scenario matrix

Har schedulability question inhi cells mein se kisi ek mein aata hai. Neeche ke examples cell(s) ke saath label kiye gaye hain, aur mil ke yeh sab cells ko touch karte hain.

Cell	Input situation	Kya hona chahiye
A	$U > 1$ (over-subscribed)	Instant FAIL — physics, koi scheduler save nahi kar sakta
B	$U \leq$ RM bound (quick test passes)	PASS sirf sufficient test se prove hota hai
C	RM bound $< U \leq 1$ (quick test fails)	Verdict UNKNOWN → exact RTA zaroor chalao
C1	Cell C, RTA converges with $R_{i} \leq D_{i}$	PASS despite failing quick test
C2	Cell C, RTA gives some $R_{i} > D_{i}$	FAIL — confirmed unschedulable
D	$n = 1$ (single task)	Bound $= 1$ ; degenerate limit
E	$n = 0$ (empty task set)	Trivially schedulable; $U = 0$
F	$U$ exactly equals a bound	Boundary — kya $\leq$ inclusive hai?
G	RM says FAIL but EDF says PASS	Same tasks, scheduler choice matters
H	Word problem: hard vs firm vs soft	Cost-of-miss se classify karo, numbers se nahi
I	$D_{i} < T_{i}$ (deadline period se choti hai)	Sirf utilisation test invalid hai

Example 1 — Cell B: clean PASS

Utilisation. $U = \frac{1}{5} + \frac{2}{8} + \frac{1}{10} = 0.2 + 0.25 + 0.1 = 0.55$ . Yeh step kyun? $U$ pehla gate hai: yeh total CPU share demand kiya gaya hai. $1$ se neeche ho to aage badho; upar ho to ruk jao.
$n = 3$ ke liye RM bound. $3 (2^{1/3} - 1) = 3 (1.2599 - 1) = 0.7798$ . Yeh step kyun? Fixed-priority scheduling bad phasings par CPU waste kar sakta hai, isliye ise $1$ ke neeche ek bound chahiye. Yahi woh bound hai.
Compare karo. $0.55 \leq 0.7798$ → PASS. Yeh step kyun? Liu–Layland test sufficient hai: ise clear karna proof hai ki sab deadlines meet hoti hain.

Verify: $U = 0.55$ comfortably $0.78$ se neeche hai — margin $0.23$ . Units: sab $U_{i}$ dimensionless fractions hain (seconds/seconds), isliye summing legal hai.

Example 2 — Cell A: physics se instant FAIL

Utilisation. $U = \frac{3}{5} + \frac{4}{6} = 0.6 + 0.6667 = 1.2667$ . Yeh step kyun? Kisi bhi clever test se pehle, check karo ki demand physically fit hoti hai ya nahi.
1 se compare karo. $1.2667 > 1$ → FAIL, unconditionally. Yeh step kyun? Tum ek processor ka $126.7%$ maang rahe ho. Koi bhi scheduler — RM, EDF, ya magic — $100%$ se zyada serve nahi kar sakta. Koi deadline zaroor slip karegi.

Verify: $U > 1$ matlab longer task ke ek period mein tum processor se zyada CPU-seconds demand karte ho. $T_{2} = 6$ s mein tum $6 \cdot 1.2667 = 7.6$ CPU-seconds request karte ho lekin sirf $6$ available hain. Impossible.

RTA notation, ek baar define karo

Definition

$h p (i)$ = higher-priority set Exact Response-Time Analysis (RTA) ke liye humein ek naya symbol chahiye. == $h p (i)$ woh sab tasks ka set hai jinka priority task $i$ se zyada hai== — precisely woh tasks jo task $i$ ko interrupt (preempt) kar sakte hain aur CPU chura sakte hain jab task $i$ run karne ki koshish kar raha hota hai. Rate-Monotonic ke under, higher priority matlab shorter period, isliye $h p (i)$ har woh task hai jiska period task $i$ ke period se chota hai.

Task $i$ ke liye RTA equation hai $R_{i} = C_{i} + \sum_{j \in h p (i)} ⌈ \frac{R _{i}}{T _{j}} ⌉ C_{j}$ isko aise padho: task $i$ ka finish time = uska apna kaam $C_{i}$ , plus, har higher-priority task $j$ ke liye, $j$ ke window ke andar release hone ki baar ( $⌈ R_{i} / T_{j} ⌉$ ) multiplied by $j$ ka cost $C_{j}$ . Kyunki $R_{i}$ dono sides par hai, hum ise iteration se solve karte hain jab tak yeh change karna band na ho jaye (a fixed point).

Example 3 — Cell C + C1: quick test fails, exact test rescues

Utilisation. $U = \frac{1}{4} + \frac{2}{6} + \frac{2}{10} = 0.25 + 0.3333 + 0.2 = 0.7833$ . Yeh step kyun? Pehla gate. $U < 1$ , to physically impossible nahi hai.
RM bound. $3 (2^{1/3} - 1) = 0.7798$ . Compare karo: $0.7833 > 0.7798$ → quick test FAILS. Yeh step kyun? Sufficient test fail hua → verdict unknown hai, "unschedulable" NAHI. Hum escalate karte hain.
Lowest-priority task (task 3) par exact test. RTA equation apply karo $h p (3) = {1, 2}$ ke saath (dono doosre tasks ke shorter periods hain, isliye dono task 3 ko preempt kar sakte hain). Yeh step kyun? Task 3 ka least priority hai, isliye yeh sabse zyada interference suffer karta hai aur satisfy karna sabse mushkil hai. $⌈ \cdot ⌉$ count karta hai ki task 3 ke response window mein har higher task ke kitne releases aate hain aur CPU churaate hain.
Iterate karo. $R_{3}^{(0)} = C_{3} = 2$ se shuru karo.
- $R_{3}^{(1)} = 2 + ⌈ 2/4 ⌉ \cdot 1 + ⌈ 2/6 ⌉ \cdot 2 = 2 + 1 + 2 = 5$ .
- $R_{3}^{(2)} = 2 + ⌈ 5/4 ⌉ \cdot 1 + ⌈ 5/6 ⌉ \cdot 2 = 2 + 2 + 2 = 6$ .
- $R_{3}^{(3)} = 2 + ⌈ 6/4 ⌉ \cdot 1 + ⌈ 6/6 ⌉ \cdot 2 = 2 + 2 + 2 = 6$ . $R_{3} = 6$ par Converged. Yeh step kyun? Hum iterate karte hain kyunki $R_{3}$ dono sides par hai — ek fixed-point. Jaise window badhti hai, zyada preemptions fit ho sakte hain; jab value change karna band ho jaaye, koi nayi preemption appear nahi hoti aur hume true worst-case finish time milta hai.
Compare karo. $R_{3} = 6 \leq D_{3} = 10$ → task 3 apni deadline meet karta hai. (Tasks 1 aur 2 aur bhi aasaan hain — verify dekho.) → PASS. Yeh step kyun? Schedulable iff $R_{i} \leq D_{i}$ har task ke liye.

Neeche figure yeh worst-case timeline draw karta hai: teeno tasks $t = 0$ par ek saath release hote hain (the "critical instant"), aur tum dekh sakte ho ki task 3 higher-priority tasks ke haath push hota hai phir bhi $t = 6$ par finish karta hai, apni deadline $t = 10$ se kaafi pehle.

Figure — Real-time constraints — hard and soft deadlines

Figure ko teen stacked lanes ki tarah padho (ek per task). Coloured blocks dikhate hain jab har task CPU actually hold karta hai. Notice karo task 3 ka block split hai: yeh run karta hai, $t = 4$ par task 1 re-release hone par preempt ho jaata hai (lavender interruption), phir resume karta hai aur $t = 6$ par complete karta hai — woh point $R_{3} = 6$ mark kiya gaya hai. $t = 10$ par dashed coral line uski deadline hai; $6$ aur $10$ ke beech gap safety margin hai.

Verify: Task 1 (highest priority) mein koi interference nahi: $R_{1} = C_{1} = 1 \leq 4$ . ✓ Task 2: $R_{2} = 2 + ⌈ R_{2} /4 ⌉ \cdot 1$ ; iterate karo $2 \to 3 \to 3$ , to $R_{2} = 3 \leq 6$ . ✓ Sab pass — to yeh set RM ke under schedulable hai even though quick bound ne "don't know" kaha.

Example 4 — Cell C + C2: exact test FAIL confirm karta hai

Utilisation. $U = \frac{3}{6} + \frac{3}{9} + \frac{1}{10} = 0.5 + 0.3333 + 0.1 = 0.9333$ . Yeh step kyun? Pehla gate. $U < 1$ , to nahi physically impossible — exact test meaningful hai.
RM bound. $3 (2^{1/3} - 1) = 0.7798$ . Compare karo: $0.9333 > 0.7798$ → quick test FAILS → RTA par escalate karo. Yeh step kyun? Sufficient test fail hua → verdict unknown, exact test zaroor chalao.
Task 2 ke liye RTA ( $h p (2) = {1}$ ; sirf task 1 ise preempt karta hai). $R_{2}^{(0)} = C_{2} = 3$ :
- $R_{2} = 3 + ⌈ 3/6 ⌉ \cdot 3 = 3 + 3 = 6$ .
- $R_{2} = 3 + ⌈ 6/6 ⌉ \cdot 3 = 3 + 3 = 6$ . Converged, $R_{2} = 6 \leq D_{2} = 9$ . ✓ Yeh step kyun? Bottom wale se pehle middle task check karo; yeh pass karta hai.
Task 3 ke liye RTA ( $h p (3) = {1, 2}$ ; dono ise preempt karte hain). $R_{3}^{(0)} = C_{3} = 1$ :
- $R_{3} = 1 + ⌈ 1/6 ⌉ \cdot 3 + ⌈ 1/9 ⌉ \cdot 3 = 1 + 3 + 3 = 7$ .
- $R_{3} = 1 + ⌈ 7/6 ⌉ \cdot 3 + ⌈ 7/9 ⌉ \cdot 3 = 1 + 6 + 3 = 10$ .
- $R_{3} = 1 + ⌈ 10/6 ⌉ \cdot 3 + ⌈ 10/9 ⌉ \cdot 3 = 1 + 6 + 6 = 13 > D_{3} = 10$ . FAIL. Yeh step kyun? Window deadline ke past badhti rehti hai; jab $R_{3} > D_{3}$ ho to hum ruk jaate hain — task 3 worst-case phasing mein kabhi time par finish nahi kar sakta.
Verdict. Task 3 miss karta hai → set RM ke under unschedulable hai, even though $U = 0.9333 < 1$ . Yeh step kyun? Schedulable hone ke liye har $R_{i} \leq D_{i}$ chahiye; ek miss poore set ko condemn karta hai.

Verify: $R_{3}$ $7 \to 10 \to 13$ climb karta hai aur converge hone se pehle $10$ exceed kar leta hai. $U < 1$ wala set fixed priorities ke under phir bhi fail ho sakta hai — exactly isliye quick test sirf sufficient hai.

Example 5 — Cell G: RM fails, EDF passes (same tasks)

EDF bound. $D_{i} = T_{i}$ wale periodic tasks ke liye ek CPU par, EDF schedulable hai iff $U \leq 1$ . Yeh step kyun? EDF hamesha nearest deadline wali job run karta hai, bad phasings par koi CPU waste nahi — isliye yeh safely poore processor ko use kar sakta hai.
Compare karo. $U = 0.9333 \leq 1$ → PASS under EDF. Yeh step kyun? EDF ke exact bound ko meet karna single-CPU periodic sets ke liye schedulability ka proof hai.

Verify: Same tasks, do verdicts: RM = FAIL, EDF = PASS. Isliye EDF ko single-CPU periodic sets ke liye optimal kaha jaata hai — yeh fixed-priority ko dominate karta hai. RM ki misses purely fixed priorities ki wajah se critical instant par CPU idle rehne se aayi.

Example 6 — Cells D, E, F: degenerate aur boundary inputs

(D) Ek task, $n = 1$ . $C_{1} = 7, T_{1} = 10$ .

Bound. $1 \cdot (2^{1/1} - 1) = 1 \cdot (2 - 1) = 1$ . Yeh step kyun? Single task ke saath koi interference nahi, isliye RM bound EDF bound ke barabar hoti hai: poora CPU.
Compare karo. $U = 0.7 \leq 1$ → PASS. Yeh step kyun? Single task CPU ka $70%$ consume karta hai, headroom chhod ke; $1$ ke bound ko clear karna prove karta hai ki yeh apni deadline meet karta hai.

Verify: Ek akela periodic task schedulable hai iff $C_{1} \leq T_{1}$ , yaani $U_{1} \leq 1$ . Yahan $7 \leq 10$ . ✓

(E) Empty set, $n = 0$ . Koi task nahi.

Utilisation. $U = \sum_{i = 1}^{0} (\cdot) = 0$ (empty sum). Yeh step kyun? Zero tasks ke saath add karne ke liye koi terms nahi hain, aur ek empty sum convention se $0$ hota hai — CPU kuch demand nahi karta.
Compare karo. $0 \leq$ kisi bhi bound → PASS trivially. Yeh step kyun? Agar koi task hi nahi hai, to miss karne ke liye koi deadline nahi; verdict schedulable hona chahiye, aur $U = 0$ har possible bound clear karta hai.

Verify: Miss karne ke liye kuch nahi ⇒ schedulable. Empty-sum convention $U = 0$ deta hai, consistent.

(F) $U$ exactly on the bound, $n = 2$ . Do-task RM bound hai $2 (2^{1/2} - 1) = 0.828427$ . Concrete tasks choose karo jo exactly ise hit karte hain. Task 1 lo $C_{1} = 1, T_{1} = 2$ , to $U_{1} = 0.5$ . Hume chahiye $U_{2} = 0.828427 - 0.5 = 0.328427$ . $T_{2} = 100$ aur $C_{2} = 32.8427$ choose karo, jisse $U_{2} = 32.8427/100 = 0.328427$ .

Total utilisation. $U = 0.5 + 0.328427 = 0.828427$ . Yeh step kyun? Humne deliberately $U$ ko boundary par daala inequality ke edge ko test karne ke liye.
Compare karo. RM bound $= 0.828427$ . Test hai $U \leq bound$ , aur $0.828427 \leq 0.828427$ holds → PASS. Yeh step kyun? Liu–Layland $\leq$ (inclusive) use karta hai, isliye exactly bound par land karna safe hai.

Verify: $2 (2 - 1) = 0.828427 \dots$ Hamara $U$ chhe decimals tak iske barabar hai. Exactly bound par hona pass karta hai; sirf $U$ strictly greater exact test force karta hai.

Example 7 — Cell H: word problem (hard / firm / soft)

(a) ek HARD deadline hai. Ek missed stabilisation update = loss of control = catastrophe. Late result ki utility effectively $- \infty$ hai. Yeh step kyun? Hum cost of a miss se classify karte hain, aur yahan cost total system failure hai — hard deadline ki defining mark. Yeh loop WCET-based proof obligation drive karta hai aur RTOS ke highest-priority band mein belong karta hai.
(b) ek FIRM deadline hai. Apne display slot ke baad aane wala frame zero value ka hota hai — tum ise discard karte ho — lekin kuch toot-ta nahi. Yeh step kyun? Late = worthless but harmless exactly firm category hai; sahi action stale frame drop karna hai, late display karna nahi.
(c) ek SOFT deadline hai. Thodi der se aane wali battery reading phir bhi reduced value rakhti hai (roughly sahi), aur occasional lateness tolerable hai. Yeh step kyun? Utility deadline ke baad gently degrade hoti hai rather than collapse — yeh soft deadline ki pehchaan hai. Design goal: statistics bound karo (jaise " $95%$ within $500 ms$ "), aur jitter tolerate karo.

Verify (design mapping):

(a) → zero misses prove karo via schedulability test + priority inversion ke against guard karo.

(b) → firm: discard-on-miss, zero misses ka proof zaruri nahi.

(c) → soft: graceful degradation, statistical target. Numbers ( $2$ / $33$ / $500 ms$ ) category decide nahi karte — lateness ka consequence karta hai. $500 ms$ deadline ek alag system mein hard ho sakti hai (jaise ek medical infusion controller).

Example 8 — Cell I: deadline period se choti hai

Utilisation. $U = \frac{2}{10} + \frac{1}{5} = 0.2 + 0.2 = 0.4$ . Bahut low! Yeh step kyun? Habit kehti hai "low $U$ ⇒ fine." Lekin deadlines periods se chhoti hain, isliye hum ise trust nahi kar sakte.
Yeh trap hai. Liu–Layland utilisation bound assume karta hai $D_{i} = T_{i}$ . Yahan $D_{1} = 4 < T_{1} = 10$ , isliye low $U$ schedulability prove nahi karta (matrix remark dekho). Hume RTA chalani hogi aur $D_{i}$ ke against compare karna hoga, $T_{i}$ ke nahi. Yeh step kyun? Utilisation demand ko pure period par average karta hai; ek choti deadline kaam ko jaldi maangti hai, jo $U$ dekh nahi sakta, isliye sirf exact test yahan valid hai.
Task 1 ke liye RTA (highest priority, $h p (1) = \emptyset$ , koi preempt nahi karta). $R_{1} = C_{1} = 2$ . Compare karo: $R_{1} = 2 \leq D_{1} = 4$ . ✓ Yeh step kyun? Highest-priority task mein koi interference nahi, isliye uska response time sirf uski apni cost hai — ise tight deadline $4$ ke against check karo, period $10$ ke nahi.
Task 2 ke liye RTA ( $h p (2) = {1}$ ; task 1 ise preempt karta hai). $R_{2}^{(0)} = C_{2} = 1$ :
- $R_{2} = 1 + ⌈ 1/10 ⌉ \cdot 2 = 1 + 2 = 3$ .
- $R_{2} = 1 + ⌈ 3/10 ⌉ \cdot 2 = 1 + 2 = 3$ . Converged, $R_{2} = 3 \leq D_{2} = 5$ . ✓ Yeh step kyun? Fixed point iterate karo; task 2 $3$ par finish karta hai, apni deadline $5$ ke andar.
Verdict. Dono apni (tighter) deadlines meet karte hain → PASS — lekin sirf isliye kyunki RTA ne confirm kiya. $U = 0.4$ number yahan kabhi valid proof nahi tha. Yeh step kyun? Cell I mein utilisation test silent hai; $D_{i}$ ke against exact test asli judge hai.

Verify: $R_{1} = 2 \leq 4$ aur $R_{2} = 3 \leq 5$ . Agar hum sirf $U = 0.4$ par trust karte to hum woh check skip kar dete jo actually matter karta tha. Note karo dono response times short $D_{i}$ ke against compare kiye gaye hain, periods ke nahi.

Recall Self-test: har set ke liye cell ka naam batao

A: $C = (3, 4), T = (5, 6)$ → ::: Cell A — $U = 1.27 > 1$ , instant FAIL. B: $C = (1, 2, 1), T = (5, 8, 10)$ → ::: Cell B — $U = 0.55 \leq 0.78$ , quick PASS. C1: $C = (1, 2, 2), T = (4, 6, 10)$ → ::: Cell C1 — quick test fails ( $0.783 > 0.780$ ) lekin RTA pass karta hai ( $R_{3} = 6 \leq 10$ ). C2/G: $C = (3, 3, 1), T = (6, 9, 10)$ → ::: Cell C2 RM ke under (RTA fails, $R_{3}$ $10$ exceed karta hai), Cell G EDF ke under (PASS, $U = 0.933 \leq 1$ ). D: single task $C = 7, T = 10$ → ::: Cell D — bound $= 1$ , PASS. E: koi task nahi → ::: Cell E — $U = 0$ , trivially schedulable. F: $C = (1, 32.8427), T = (2, 100)$ → ::: Cell F — $U = 0.828427$ exactly $n = 2$ RM bound par, PASS (inclusive $\leq$ ). I: $C = (2, 1), T = (10, 5), D = (4, 5)$ → ::: Cell I — $U = 0.4$ lekin $D_{1} < T_{1}$ , utilisation test invalid; RTA deta hai $R_{1} = 2, R_{2} = 3$ , PASS.