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

This is the picture-first companion to the parent topic. Every symbol is drawn before it is used. If you have never seen a fraction with letters in it, you are still in the right place.

Step 1 — What a single job looks like on a timeline

WHAT. Draw one horizontal line: that is time, flowing left to right. A job is a piece of work the computer must do. It appears at some moment, runs for a while, and finishes.

WHY. Before we talk about "meeting deadlines" we must be able to see the three moments that matter. Everything later is just counting distances on this one line.

PICTURE. In the figure below, three marks sit on the time line:

The ==release time $r$ == (deep teal tick): the instant the job becomes ready — like the moment homework is handed to you.
The ==deadline $d$ == (plum tick): the latest allowed finish time — the bus leaves here.
The finish time (burnt-orange dot): when the job actually finished.

Figure — Real-time constraints — hard and soft deadlines

Step 2 — Response time, and the single rule that defines "on time"

WHAT. Measure the distance from release to actual finish. Call it the ==response time $R$ ==. Measure the distance from release to deadline. Call it the ==relative deadline $D$ ==, so $d = r + D$ .

WHY. "On time" is not a feeling — it is a comparison of two lengths. We need a single, checkable rule. Here it is:

$how long the job actually took R \leq how long it was allowed to take D$

If the orange finish arrives at or before the plum deadline, $R \leq D$ and we say the job met its deadline. If it arrives after, $R > D$ — a miss.

PICTURE. The green arrow (below) spans $R$ ; the plum arrow spans $D$ . On time is simply: green arrow no longer than plum arrow.

Step 3 — Why "worst case" and not "usual case" (WCET)

WHAT. A job does not always take the same time — a cache miss, a branch, a slow sensor read all stretch it. We take the longest it can ever run and call it ==WCET $C$ == (Worst-Case Execution Time). See Worst-Case Execution Time analysis.

WHY. A deadline is missed on the bad day, never the average day. If we plan using the average length, we are planning for a day that may never save us. The picture makes the danger obvious.

PICTURE. Several possible run-lengths of the same job are stacked as faint bars; the average sits comfortably inside the deadline, but the longest bar (burnt orange, the WCET) pokes past the plum deadline. Plan for that bar, not the average.

Step 4 — One repeating task: what "utilisation" measures

WHAT. A periodic task doesn't run once — it re-releases every ==period $T$ == seconds (see Periodic vs Aperiodic Tasks). In each window of length $T$ it needs $C$ seconds of CPU. The fraction of the CPU it consumes is:

$U_{i} = \frac{C _{i} seconds of work per release}{seconds between releases T _{i}}$

WHY. We introduce a ratio because we want a single number — a share — that we can add up across tasks. Seconds alone don't add fairly (a 1-second job every 2 s and a 1-second job every 100 s are wildly different loads). Dividing by the period turns raw seconds into a comparable percentage of the machine.

PICTURE. One period drawn as a box of width $T$ ; the orange work-bar of width $C$ sits inside it. $U$ is literally "what fraction of the box is orange."

WHAT. With $n$ tasks on one CPU, their demands are shares of the same resource, so they add:

$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}}$

The big $\sum$ ("sigma") just means "add these up for $i = 1$ to $n$ ."

WHY. One pie, many eaters. If the slices requested sum to more than the whole pie, someone goes hungry — a deadline must be missed. That is the first, unbreakable gate.

PICTURE. Three orange slices stacked into a single CPU bar. If they overflow the 100% line, the CPU is over-subscribed — physically impossible to satisfy.

Step 6 — The catch: $U \leq 1$ is not enough for fixed priority

WHAT. Under Rate-Monotonic scheduling (Rate-Monotonic Scheduling) — shorter period gets higher, fixed priority — even $U$ below 100% can miss. At the worst phasing (when a big low-priority job is caught mid-flight by many high-priority arrivals) the CPU is forced to sit idle at exactly the wrong moment.

WHY. Fixed priorities are rigid: a high-priority task always jumps the queue, even when a low-priority task is about to blow its deadline. That rigidity wastes usable time, so a safe fixed-priority system must leave headroom.

PICTURE. The worst-case line-up: a low-priority job (plum) keeps getting preempted (see Priority Inversion and Priority Inheritance for the related hazard) by high-priority arrivals (orange), pushing its finish past the deadline — even though total load is under 100%.

Step 7 — The Liu–Layland ceiling, and where 0.693 comes from

WHAT. Liu & Layland proved a sufficient bound for RM:

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

Each symbol: $n$ = number of tasks; $2^{1/ n}$ = the $n$ -th root of 2; the whole right side shrinks as $n$ grows.

WHY. This is the exact amount of headroom Step 6 demanded, computed for the worst phasing. As you pile on more tasks ( $n \to \infty$ ) the ceiling sinks to $ln 2 \approx 0.693$ — you can safely use only about 69% of the CPU with fixed priorities.

PICTURE. A curve of the ceiling versus $n$ : it starts at $1.00$ for $n = 1$ , drops to $0.828$ at $n = 2$ , $0.780$ at $n = 3$ , and flattens onto the dotted plum line at $0.693$ . The full-CPU line at $1.0$ (the Earliest Deadline First (EDF) ceiling) sits above it for contrast.

Step 8 — Running the test on real numbers

WHAT. 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$

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

WHY. Step 5 checks the physical gate ( $0.708 \leq 1$ ✓). Step 7 checks the RM ceiling: $0.708 \leq 0.780$ ✓. Passing a sufficient test is a proof all hard deadlines are met.

PICTURE. A thermometer: the measured load $0.708$ (orange fill) sits below the RM red line $0.780$ , which sits below the EDF line $1.0$ . Green zone = provably safe.

Step 9 — The degenerate case: when the ceiling says "don't know"

WHAT. Now imagine $U = 0.79$ with $n = 3$ . It fails the RM ceiling ( $0.79 > 0.780$ ). Does that mean unschedulable?

WHY. No — because the ceiling is sufficient, not necessary. Failing a sufficient test proves nothing. To decide for sure we run the exact Response-Time Analysis (RTOS scheduler design):

$R_{i} = its own work C_{i} + \sum_{j \in h p (i)} how many times j preempts i ⌈ \frac{R _{i}}{T _{j}} ⌉ cost of each preemption C_{j}$

$h p (i)$ = the set of tasks with higher priority than $i$ . The ceiling brackets $⌈ \cdot ⌉$ round up: a task that arrives even once inside the window steals a whole $C_{j}$ . We solve by iterating $R_{i}$ until it stops changing; schedulable iff $R_{i} \leq D_{i}$ .

PICTURE. A three-zone map of the load axis: green (below RM ceiling → proven safe), amber (above ceiling but $\leq 1$ → unknown, must run exact analysis, and jitter/latency matter — see Jitter and Latency), red (above 1 → proven impossible).

The one-picture summary

Everything compresses into a single decision funnel: measure worst-case load, drop it against the ceilings, read the colour.

Recall Feynman: the whole walkthrough in plain words

Picture a bus you must catch. A job is you leaving home; the deadline is when the bus leaves. First we drew one trip on a line and said "on time" just means your finish arrow is no longer than your allowed arrow. Then we admitted some mornings are slow — so we plan for your worst morning (WCET), never the average one. Next we noticed you catch this bus every day (a period), and the fraction of your day it eats is $C / T$ . Stack up several daily chores and their fractions add — ask for more than a whole day and something must be dropped. But there's a twist: with a rigid "always-do-the-urgent-one-first" rule (Rate-Monotonic), you waste a little time at the worst moments, so you can only safely fill about 69% of your day, not 100%. That safe ceiling is $n (2^{1/ n} - 1)$ . We tested real chores: load $0.708$ , ceiling $0.780$ → provably fine. Finally, the honest caveat: if your load pokes above the ceiling but stays under a full day, the simple test just shrugs — you must simulate the exact preemptions (Response-Time Analysis) to know for sure. Green = safe, amber = check carefully, red = give up. That is hard real-time: not fast, but provable.

Recall Quick self-check

Two lengths compared for "on time"? ::: Response time $R$ vs relative deadline $D$ ; met iff $R \leq D$ . Why divide $C$ by $T$ ? ::: To turn raw seconds into a comparable CPU fraction that can be summed across tasks. RM ceiling for $n = 3$ ? ::: $3 (2^{1/3} - 1) \approx 0.780$ . $U = 0.79$ , $n = 3$ fails RM — unschedulable? ::: No — bound is sufficient only; run Response-Time Analysis. Why $⌈ R_{i} / T_{j} ⌉$ ? ::: Counts how many whole times higher-priority task $j$ preempts $i$ within $R_{i}$ .