Real-time constraints — hard and soft deadlines: Exercises

This page is a self-testing ladder. Each problem sits at a difficulty level (L1 → L5). Read the problem, cover the solution, try it, then open the collapsible [!recall]- to check. Every number here is machine-verified.

Prerequisite ideas live on the parent note the topic note and its neighbours: 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 — Classify the deadline

For each system, state whether the timing requirement is hard, firm, or soft, and justify by the value of a late result.

(a) A car's airbag controller must fire within 20 ms of a crash. (b) A video decoder produces frame 900; it arrives 5 ms after its display slot. (c) A music streaming app's buffer refill runs a few milliseconds late.

Recall Solution

The rule: look at the utility of a result delivered after the deadline.

(a) Hard. A late airbag is catastrophic — the value of a late result is effectively $- \infty$ . This is a total system failure, not slowness.
(b) Firm. A video frame that misses its display slot has zero value (you can't show it), so you discard it — but nothing breaks. Late value = 0, no catastrophe.
(c) Soft. A slightly late buffer refill degrades quality (a tiny stutter) but the result still has reduced value; occasional misses are tolerated.

L1.2 — Read off the utilisation

A single periodic task has $C_{1} = 3$ ms and $T_{1} = 12$ ms. What fraction of the CPU does it demand?

Recall Solution

$U_{1} = \frac{C _{1}}{T _{1}} = \frac{3}{12} = 0.25$ Why this formula? In every window of $12$ ms the task needs $3$ ms of CPU, so it occupies $3/12 = 1/4$ of the processor on average. It leaves $75%$ of the CPU free.

Level 2 — Application

L2.1 — Total utilisation of a task set

Tasks: $C_{1} = 1, T_{1} = 4$ ; $C_{2} = 2, T_{2} = 8$ ; $C_{3} = 2, T_{3} = 16$ . Compute the total utilisation $U$ .

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$ Why sum? All three tasks share one CPU, and their demands are additive fractions of that single resource. Since $U = 0.625 < 1$ the CPU is not over-subscribed — a necessary (not yet sufficient) condition to be schedulable.

L2.2 — Compute the Rate-Monotonic bound

For a set of $n = 3$ tasks, compute the Liu–Layland utilisation bound $n (2^{1/ n} - 1)$ .

Recall Solution

$n (2^{1/ n} - 1) = 3 (2^{1/3} - 1) = 3 (1.259921 - 1) = 3 (0.259921) = 0.779763$ Why below 1? Under fixed priorities the worst-case phasing (all tasks released together) sometimes forces the CPU to idle even when work exists, so you cannot safely fill it to $100%$ . For $n = 3$ the safe ceiling is about $0.780$ .

L2.3 — Apply the RM test

Is the task set from L2.1 ( $U = 0.625$ ) schedulable under Rate-Monotonic scheduling?

Recall Solution

Compare $U$ against the $n = 3$ bound from L2.2: $0.625 \leq 0.779763 ✓$ Yes — RM guarantees every deadline. Passing a sufficient test is a proof of schedulability; we are done and don't need any exact test.

Level 3 — Analysis

L3.1 — When the bound fails but the set is fine

Tasks: $C_{1} = 1, T_{1} = 3$ ; $C_{2} = 1, T_{2} = 5$ ; $C_{3} = 3, T_{3} = 8$ . (a) Compute $U$ . (b) Does it pass the RM bound for $n = 3$ ? (c) What does failing the bound prove?

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$ . Since $0.908 > 0.780$ , it fails the utilisation test. (c) Failing proves nothing about unschedulability. The Liu–Layland bound is sufficient, not necessary: passing guarantees success, but failing is inconclusive. To decide, run the exact Response-Time Analysis (see L4).

L3.2 — EDF versus RM on the same set

For the set in L3.1 ( $U = 0.908$ ), is it schedulable under EDF? Why does EDF succeed where the RM utilisation test was inconclusive?

Recall Solution

EDF's exact bound (with $D_{i} = T_{i}$ ) is $U \leq 1$ . Here $U = 0.908 \leq 1$ , so EDF schedules it. Why EDF wins: EDF always runs the job with the earliest absolute deadline first, dynamically re-prioritising. This never wastes CPU on worst-case phasing, so it can safely use the whole processor. RM's fixed priorities can't, which is exactly why RM's sufficient bound sits below 1.

The next figure makes the RM-versus-EDF gap visual. Read it like this: the horizontal axis is the number of tasks $n$ ; the vertical axis is the highest utilisation each policy can safely accept. The black flat line at $1$ is the EDF ceiling — EDF can always fill the CPU completely. The red curve is the RM bound $n (2^{1/ n} - 1)$ : it starts at $1$ for a single task, then sags, crossing the dashed marker $ln 2 \approx 0.693$ that it approaches as $n \to \infty$ . The red dot marks our L3 set at $n = 3, U = 0.908$ — it sits above the red RM ceiling (so RM's utilisation test is inconclusive) but below the black EDF line (so EDF schedules it). The insight: choosing EDF buys you the whole gap between the red curve and the black line.

Figure — Real-time constraints — hard and soft deadlines

Level 4 — Synthesis

L4.1 — Exact Response-Time Analysis

Tasks (deadline = period), priorities by RM (shorter period = higher priority): $C_{1} = 2, T_{1} = 5$ ; $C_{2} = 2, T_{2} = 8$ ; $C_{3} = 3, T_{3} = 12$ . Use the iteration $R_{i} = C_{i} + \sum_{j \in h p (i)} ⌈ \frac{R _{i}}{T _{j}} ⌉ C_{j}$ to find $R_{3}$ (the response time of the lowest-priority task) and decide if it meets its deadline $D_{3} = 12$ .

Recall Solution

Task 3 has the longest period, so it is lowest priority; the higher-priority set is $h p (3) = {1, 2}$ (both preempt it). The ceiling $⌈ R_{3} / T_{j} ⌉$ counts how many times task $j$ interrupts task 3 within the window $R_{3}$ .

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$

Converged at $R_{3} = 13$ . Now test: $R_{3} = 13 > D_{3} = 12$ → task 3 MISSES its deadline. The set is not RM-schedulable, even though (check) $U = \frac{2}{5} + \frac{2}{8} + \frac{3}{12} = 0.9 \leq 1$ .

Why iterate? $R_{3}$ appears on both sides: a longer response window admits more preemptions, which lengthens the window again. We repeat until the value stops changing (a fixed point), which is the true worst-case response time.

The timeline figure below shows why $R_{3}$ stretches to $13$ . Time (ms) runs left to right. The top row (T1) shows task 1's releases at $t = 0, 5, 10$ , each a $2$ -ms block of CPU it grabs ahead of task 3. The middle row (T2) shows task 2's releases at $t = 0, 8$ , again $2$ -ms blocks with priority over task 3. The bottom red row (T3) is task 3's own $3$ ms of work — but every higher-priority block above pushes it later, so its completion is dragged all the way to $t = 13$ (the solid red line). The dashed black line is the deadline $D_{3} = 12$ : because the red completion line lands to the right of it, task 3 misses. The picture makes concrete what the ceilings counted: preemptions eat the gaps and stretch the response window past the deadline.

Level 5 — Mastery

L5.1 — Design a schedulable set under a utilisation budget

You must add a third task to $C_{1} = 1, T_{1} = 4$ ; $C_{2} = 1, T_{2} = 5$ so that all three pass the RM utilisation bound for $n = 3$ (which is $0.779763$ ). The new task has $T_{3} = 10$ . What is the largest integer $C_{3}$ (in ms) you may choose?

Recall Solution

Fixed part: $U_{12} = \frac{1}{4} + \frac{1}{5} = 0.25 + 0.2 = 0.45$ . Budget left: $0.779763 - 0.45 = 0.329763$ . Allowed $C_{3}$ : solve $\frac{C _{3}}{10} \leq 0.329763 \Rightarrow C_{3} \leq 3.29763$ . Largest integer: $C_{3} = 3$ . Check: with $C_{3} = 3$ , $U = 0.45 + 0.3 = 0.75 \leq 0.779763$ ✅. With $C_{3} = 4$ , $U = 0.85 > 0.78$ , fails. So the answer is $C_{3} = 3$ ms.

L5.2 — Hard vs soft design decision

A drone flight-control loop and a telemetry-logging task share one MCU. The flight loop has a hard deadline; the logger a soft one. Under overload, which task should shed work, and what design principle governs this?

Recall Solution

The soft telemetry logger sheds work — drop or down-sample log entries, or skip a cycle. The flight-control loop's hard deadline must never be compromised because a miss is catastrophic. Principle: graceful degradation — under overload you degrade the low-value soft tasks to protect the high-value hard tasks. This is a scheduling/priority design choice; give the hard task guaranteed CPU (e.g. highest RM priority + priority inheritance on shared locks) and make the soft task best-effort.

Recall Feynman check: say the whole ladder in one breath

First you name the deadline type (L1), then measure CPU demand $U = \sum C_{i} / T_{i}$ (L2), then judge it against the right bound — $n (2^{1/ n} - 1)$ for RM, $1$ for EDF — knowing that failing the RM bound only means "unknown, run the exact test" (L3). The exact test is the iterating Response-Time equation, which converges to the true worst case (L4). Finally you design within budget and protect hard tasks by degrading soft ones (L5).