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

Before starting, a reminder of the four quantities (all built in the parent topic note): $C_i$ = worst-case execution time (see Worst-Case Execution Time analysis), $T_i$ = period, $D_i$ = relative deadline, $U_i=C_i/T_i$ = the fraction of the one CPU that task $i$ eats.

---

The scenario matrix

Every schedulability question falls into one of these cells. The examples below are labelled with the cell(s) they hit, and together they touch all of them.

Cell	Input situation	What must happen
A	$U>1$ (over-subscribed)	Instant FAIL — physics, no scheduler saves you
B	$U\le$ RM bound (quick test passes)	PASS proved by sufficient test alone
C	RM bound $<U\le 1$ (quick test fails)	Verdict UNKNOWN → must run exact RTA
C1	Cell C, RTA converges with $R_i\le 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 — is $\le$ inclusive?
G	RM says FAIL but EDF says PASS	Same tasks, scheduler choice matters
H	Word problem: hard vs firm vs soft	Classify by cost-of-miss, not by numbers
I	$D_i<T_i$ (deadline shorter than period)	Utilisation test alone is invalid

---

Example 1 — Cell B: the clean PASS

1. Utilisation. $U=\frac{1}{5}+\frac{2}{8}+\frac{1}{10}=0.2+0.25+0.1=0.55$. Why this step? $U$ is the first gate: it is the total CPU share demanded. Below $1$ we may proceed; above $1$ we stop.
2. RM bound for $n=3$. $3(2^{1/3}-1)=3(1.2599-1)=0.7798$. Why this step? Fixed-priority scheduling can waste CPU at bad phasings, so it needs a bound under $1$. This is that bound.
3. Compare. $0.55\le 0.7798$ → PASS. Why this step? The Liu–Layland test is sufficient: clearing it is a proof all deadlines are met.

Verify: $U=0.55$ sits comfortably below $0.78$ — margin $0.23$. Units: all $U_i$ are dimensionless fractions (seconds/seconds), so summing is legal.

---

Example 2 — Cell A: instant FAIL by physics

1. Utilisation. $U=\frac{3}{5}+\frac{4}{6}=0.6+0.6667=1.2667$. Why this step? Before any clever test, check if the demand physically fits.
2. Compare to 1. $1.2667>1$ → FAIL, unconditionally. Why this step? You are asking for $126.7\%$ of one processor. No scheduler — RM, EDF, or magic — can serve more than $100\%$. Some deadline must slip.

Verify: $U>1$ means over one period of the longer task you demand more CPU-seconds than exist. In $T_2=6$ s you request $6\cdot 1.2667=7.6$ CPU-seconds but only $6$ exist. Impossible.

---

The RTA notation, defined once

---

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

1. Utilisation. $U=\frac{1}{4}+\frac{2}{6}+\frac{2}{10}=0.25+0.3333+0.2=0.7833$. Why this step? First gate. $U<1$, so not physically impossible.
2. RM bound. $3(2^{1/3}-1)=0.7798$. Compare: $0.7833>0.7798$ → quick test FAILS. Why this step? Sufficient test failed → verdict is unknown, NOT "unschedulable". We must escalate.
3. Exact test on the lowest-priority task (task 3). Apply the RTA equation with $hp(3)=\{1,2\}$ (both other tasks have shorter periods, so both can preempt task 3). Why this step? Task 3 has the least priority, so it suffers the most interference and is the hardest to satisfy. The $\lceil \cdot \rceil$ counts how many releases of each higher task land inside task 3's response window and steal the CPU.
4. Iterate. Start $R_3^{(0)}=C_3=2$.
   • $R_3^{(1)}=2+\lceil 2/4\rceil \cdot 1+\lceil 2/6\rceil \cdot 2=2+1+2=5$.
   • $R_3^{(2)}=2+\lceil 5/4\rceil \cdot 1+\lceil 5/6\rceil \cdot 2=2+2+2=6$.
   • $R_3^{(3)}=2+\lceil 6/4\rceil \cdot 1+\lceil 6/6\rceil \cdot 2=2+2+2=6$. Converged at $R_3=6$. Why this step? We iterate because $R_3$ appears on both sides — a fixed-point. As the window grows, more preemptions might fit; when the value stops changing, no new preemptions appear and we have the true worst-case finish time.
5. Compare. $R_3=6\le D_3=10$ → task 3 meets its deadline. (Tasks 1 and 2 are even easier — see verify.) → PASS. Why this step? Schedulable iff $R_i\le D_i$ for every task.

The figure below draws this worst-case timeline: all three tasks are released together at $t=0$ (the "critical instant"), and you can watch task 3 get pushed around by the higher-priority tasks yet still finish at $t=6$, comfortably before its deadline at $t=10$.

Read the figure as three stacked lanes (one per task). Coloured blocks show when each task actually holds the CPU. Notice task 3's block is split: it runs, gets preempted when task 1 is re-released at $t=4$ (the lavender interruption), then resumes and completes at $t=6$ — the point marked $R_3=6$. The dashed coral line at $t=10$ is its deadline; the gap between $6$ and $10$ is the safety margin.

Verify: Task 1 (highest priority) has no interference: $R_1=C_1=1\le 4$. ✓ Task 2: $R_2=2+\lceil R_2/4\rceil \cdot 1$; iterate $2\to 3\to 3$, so $R_2=3\le 6$. ✓ All pass — so this set is schedulable under RM even though the quick bound said "don't know."

---

Example 4 — Cell C + C2: exact test confirms FAIL

1. Utilisation. $U=\frac{3}{6}+\frac{3}{9}+\frac{1}{10}=0.5+0.3333+0.1=0.9333$. Why this step? First gate. $U<1$, so not physically impossible — an exact test is meaningful.
2. RM bound. $3(2^{1/3}-1)=0.7798$. Compare: $0.9333>0.7798$ → quick test FAILS → escalate to RTA. Why this step? Sufficient test failed → verdict unknown, must run the exact test.
3. RTA for task 2 ($hp(2)=\{1\}$; only task 1 preempts it). $R_2^{(0)}=C_2=3$:
   • $R_2=3+\lceil 3/6\rceil \cdot 3=3+3=6$.
   • $R_2=3+\lceil 6/6\rceil \cdot 3=3+3=6$. Converged, $R_2=6\le D_2=9$. ✓ Why this step? Check the middle task before the bottom one; it passes.
4. RTA for task 3 ($hp(3)=\{1,2\}$; both preempt it). $R_3^{(0)}=C_3=1$:
   • $R_3=1+\lceil 1/6\rceil \cdot 3+\lceil 1/9\rceil \cdot 3=1+3+3=7$.
   • $R_3=1+\lceil 7/6\rceil \cdot 3+\lceil 7/9\rceil \cdot 3=1+6+3=10$.
   • $R_3=1+\lceil 10/6\rceil \cdot 3+\lceil 10/9\rceil \cdot 3=1+6+6=13>D_3=10$. FAIL. Why this step? The window keeps growing past the deadline; once $R_3>D_3$ we stop — task 3 can never finish in time under worst-case phasing.
5. Verdict. Task 3 misses → set is unschedulable under RM, even though $U=0.9333<1$. Why this step? Schedulable requires every $R_i\le D_i$; one miss condemns the set.

Verify: $R_3$ climbs $7\to 10\to 13$ and exceeds $10$ before converging. A set with $U<1$ can still fail under fixed priorities — exactly why the quick test is only sufficient.

---

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

1. EDF bound. For periodic tasks with $D_i=T_i$ on one CPU, EDF is schedulable iff $U\le 1$. Why this step? EDF always runs the job with the nearest deadline, wasting no CPU at bad phasings — so it can safely use the whole processor.
2. Compare. $U=0.9333\le 1$ → PASS under EDF. Why this step? Meeting EDF's exact bound is a proof of schedulability for single-CPU periodic sets.

Verify: Same tasks, two verdicts: RM = FAIL, EDF = PASS. This is why EDF is called optimal for single-CPU periodic sets — it dominates fixed-priority. The RM misses came purely from fixed priorities idling the CPU at the critical instant.

---

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

(D) One task, $n=1$. $C_1=7,T_1=10$.

1. Bound. $1\cdot (2^{1/1}-1)=1\cdot (2-1)=1$. Why this step? With a single task there is no interference, so the RM bound equals the EDF bound: the full CPU.
2. Compare. $U=0.7\le 1$ → PASS. Why this step? The single task consumes $70\%$ of the CPU, leaving headroom; clearing the bound of $1$ proves it meets its deadline.

Verify: A lone periodic task is schedulable iff $C_1\le T_1$, i.e. $U_1\le 1$. Here $7\le 10$. ✓

(E) Empty set, $n=0$. No tasks.

1. Utilisation. $U={\sum }_{i=1}^0(\cdot )=0$ (empty sum). Why this step? With zero tasks there are no terms to add, and an empty sum is $0$ by convention — the CPU demands nothing.
2. Compare. $0\le$ any bound → PASS trivially. Why this step? If there is no task, there is no deadline to miss; the verdict must be schedulable, and $U=0$ clears every possible bound.

Verify: Nothing to miss ⇒ schedulable. The empty-sum convention gives $U=0$, consistent.

(F) $U$ exactly on the bound, $n=2$. The two-task RM bound is $2(2^{1/2}-1)=0.828427$. Pick concrete tasks that hit it exactly. Let task 1 be $C_1=1,T_1=2$, so $U_1=0.5$. We need $U_2=0.828427-0.5=0.328427$. Choose $T_2=100$ and $C_2=32.8427$, giving $U_2=32.8427/100=0.328427$.

1. Total utilisation. $U=0.5+0.328427=0.828427$. Why this step? We deliberately engineered $U$ to sit on the boundary to test the inequality's edge.
2. Compare. RM bound $=0.828427$. The test is $U\le \text{bound}$, and $0.828427\le 0.828427$ holds → PASS. Why this step? Liu–Layland uses $\le$ (inclusive), so landing exactly on the bound is safe.

Verify: $2(\sqrt{2}-1)=0.828427\dots$ Our $U$ equals it to six decimals. Being exactly on the bound passes; only $U$ strictly greater forces the exact test.

---

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

1. (a) is a HARD deadline. A missed stabilisation update = loss of control = catastrophe. The utility of a late result is effectively $-\infty$. Why this step? We classify by the cost of a miss, and here the cost is total system failure — the defining mark of a hard deadline. This loop drives the WCET-based proof obligation and belongs in the RTOS's highest-priority band.
2. (b) is a FIRM deadline. A frame arriving after its display slot has zero value — you discard it — but nothing breaks. Why this step? Late = worthless but harmless is exactly the firm category; the right action is to drop the stale frame, not display it late.
3. (c) is a SOFT deadline. A battery reading a little late still has reduced value (roughly right), and occasional lateness is tolerable. Why this step? The utility degrades gently after the deadline rather than collapsing — the signature of a soft deadline. Design goal: bound the statistics (e.g. "$95\%$ within $500\text{ ms}$"), and tolerate jitter.

Verify (design mapping):

• (a) → prove zero misses via a schedulability test + guard against priority inversion.
• (b) → firm: discard-on-miss, no proof of zero misses needed.
• (c) → soft: graceful degradation, statistical target. The numbers ($2$/$33$/$500\text{ ms}$) do not decide the category — the consequence of lateness does. A $500\text{ ms}$ deadline could be hard in a different system (e.g. a medical infusion controller).

---

Example 8 — Cell I: deadline shorter than period

1. Utilisation. $U=\frac{2}{10}+\frac{1}{5}=0.2+0.2=0.4$. Very low! Why this step? Habit says "low $U$ ⇒ fine." But the deadlines are shorter than the periods, so we must not trust it.
2. The trap. The Liu–Layland utilisation bound assumes $D_i=T_i$. Here $D_1=4<T_1=10$, so a low $U$ does not prove schedulability (see the matrix remark). We must run RTA and compare against $D_i$, not $T_i$. Why this step? Utilisation averages demand over the whole period; a short deadline demands the work early, which $U$ cannot see, so only the exact test is valid here.
3. RTA for task 1 (highest priority, $hp(1)=\varnothing$, no one preempts it). $R_1=C_1=2$. Compare: $R_1=2\le D_1=4$. ✓ Why this step? The highest-priority task has no interference, so its response time is just its own cost — check it against the tight deadline $4$, not the period $10$.
4. RTA for task 2 ($hp(2)=\{1\}$; task 1 preempts it). $R_2^{(0)}=C_2=1$:
   • $R_2=1+\lceil 1/10\rceil \cdot 2=1+2=3$.
   • $R_2=1+\lceil 3/10\rceil \cdot 2=1+2=3$. Converged, $R_2=3\le D_2=5$. ✓ Why this step? Iterate the fixed point; task 2 finishes at $3$, within its deadline of $5$.
5. Verdict. Both meet their (tighter) deadlines → PASS — but only because RTA confirmed it. The $U=0.4$ number was never a valid proof here. Why this step? In Cell I the utilisation test is silent; the exact test against $D_i$ is the real judge.

Verify: $R_1=2\le 4$ and $R_2=3\le 5$. Had we trusted $U=0.4$ alone we'd have skipped the check that actually mattered. Note both response times are compared against the short $D_i$, not the periods.

---

Recall Self-test: name the cell for each set

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\le 0.78$, quick PASS. C1: $C=(1,2,2),T=(4,6,10)$ → ::: Cell C1 — quick test fails ($0.783>0.780$) but RTA passes ($R_3=6\le 10$). C2/G: $C=(3,3,1),T=(6,9,10)$ → ::: Cell C2 under RM (RTA fails, $R_3$ exceeds $10$), Cell G under EDF (PASS, $U=0.933\le 1$). D: single task $C=7,T=10$ → ::: Cell D — bound $=1$, PASS. E: no tasks → ::: Cell E — $U=0$, trivially schedulable. F: $C=(1,32.8427),T=(2,100)$ → ::: Cell F — $U=0.828427$ exactly on the $n=2$ RM bound, PASS (inclusive $\le$). I: $C=(2,1),T=(10,5),D=(4,5)$ → ::: Cell I — $U=0.4$ but $D_1<T_1$, utilisation test invalid; RTA gives $R_1=2,R_2=3$, PASS.