Real-time constraints — hard and soft deadlines: Question bank

Before the traps, we build the five symbols they all lean on — from scratch, on a picture — so this page stands on its own.

The symbols, on one timeline

Every question below talks about tasks running on a single CPU. A task is a piece of code (say, "read the sensor") that gets released again and again. Each release is called a job. Picture time flowing left→right; each job is a stopwatch that starts when the job is released and stops when it finishes.

Definition The five symbols — read them off the timeline above

== $C_{i}$ (WCET)== — the longest the code can ever take to run once, the widest possible green block. "Worst-Case Execution Time". We always use the worst case, never the average.
== $T_{i}$ (period)== — the spacing between two consecutive releases of the same task (the two blue release arrows).
== $D_{i}$ (relative deadline)== — how long after release the job must be done (the red flag). The job is on time if it finishes at or before the flag.
== $R_{i}$ (response time)== — the actual gap from release to finish (the black bracket). The job meets its deadline exactly when $R_{i} \leq D_{i}$ .
== $U$ (utilisation)== — the fraction of the CPU a task set demands. One task needs $C_{i}$ seconds every $T_{i}$ seconds, so it eats a slice $U_{i} = C_{i} / T_{i}$ ; add the slices for all $n$ tasks to get $U = \sum_{i} C_{i} / T_{i}$ .

Where the exact test comes from — a picture, not a formula drop

The utilisation bound is only a rough gate. The exact question "does task $i$ ever miss?" is answered by watching how many times higher-priority tasks shove ahead of it. Let $h p (i)$ mean "the set of tasks with higher priority than $i$ ". Under Rate-Monotonic, those are the ones with shorter periods.

Formula Response-Time Analysis — built term by term

Look at the figure. Task $i$ needs $C_{i}$ of its own work (the base yellow block). But every time a higher-priority task $j$ is released inside the window, it preempts $i$ and pushes $i$ 's finish later.

In a window of length $R_{i}$ , task $j$ is released $⌈ \frac{R _{i}}{T _{j}} ⌉$ times — the ceiling because even a partial overlap still triggers one whole release. Each release costs $C_{j}$ of interference. Summing over all higher-priority tasks: $R_{i} = C_{i} + \sum_{j \in h p (i)} ⌈ \frac{R _{i}}{T _{j}} ⌉ C_{j}$ Why does $R_{i}$ sit on both sides? A longer window admits more preemptions, which lengthens the window again — so we iterate: start at $R_{i} = C_{i}$ , plug in, get a bigger $R_{i}$ , plug in again, until it stops growing. The task is schedulable iff the converged $R_{i} \leq D_{i}$ . $⌈ \cdot ⌉$ is the ceiling — round up to the next whole number, because you can't get "half a preemption".

True or false — justify

A hard real-time system just needs a very fast CPU.

False. Hard real-time needs a provably bounded worst case, not speed; a fast CPU with unbounded pauses (garbage collection, cache misses) can miss deadlines a slow-but-deterministic MCU never would.

If total utilisation

U \leq 1

, any task set is schedulable.

False.

U \leq 1

only means the CPU is not physically over-subscribed; under fixed-priority scheduling worst-case phasing wastes CPU, so you may need

U \leq n (2^{1/ n} - 1)

(as low as

0.693

Failing the Liu–Layland RM bound proves the task set is unschedulable.

False. The bound is sufficient, not necessary — many sets above the bound still meet every deadline; you must run exact Response-Time Analysis to be certain.

A firm deadline miss and a soft deadline miss are equally harmful.

False. A firm miss makes the result worthless so you discard it (value = 0); a soft miss leaves reduced but nonzero value, so you keep the late result.

EDF can schedule any single-processor periodic set with

U \leq 1

True (when each

D_{i} = T_{i}

). EDF is optimal for periodic tasks on one CPU, so it meets all deadlines exactly when

U \leq 1

under the implicit-deadline model — the full processor is usable.

Using average execution time instead of WCET gives a safe schedulability verdict.

False. Deadlines are missed in the worst case; averages under-count demand and produce a falsely "safe" answer, so you must use WCET

C_{i}

A missed deadline in a soft real-time system is a system error.

False. In soft real-time occasional misses are tolerated by design; the goal is bounding statistics (e.g. 99.9% on time), not proving zero misses.

Rate-Monotonic assigns higher priority to tasks with longer periods.

False. RM gives higher fixed priority to shorter periods (higher frequency), because those tasks have less slack

D_{i}

before their next release.

If every task's response time equals its WCET, the CPU has no preemption happening.

True.

R_{i} = C_{i} + \sum ⌈ R_{i} / T_{j} ⌉ C_{j}

collapses to

R_{i} = C_{i}

only when the interference sum is zero, meaning no higher-priority task preempted it.

Spot the error

"We tested the loop 10,000 times and it always finished in time, so the hard deadline is guaranteed."

Testing measures observed cases, not the worst case; a hard guarantee needs a proof (WCET

C_{i}

+ schedulability test), because the untested worst path may still exist.

"Our utilisation is

0.79

for

n = 3

, which fails the RM bound

0.78

, so we must redesign."

Failing the sufficient RM bound does not prove unschedulability; run exact Response-Time Analysis first — the set may still meet all deadlines.

"We used average CPU cost

C_{i}

in the utilisation sum and got

U = 0.6

, safely schedulable."

The utilisation test requires WCET, not average cost; with real worst-case values

U

could exceed the bound and deadlines could be missed.

"Deadline equals period, so we can ignore the period in the analysis."

The period

T_{i}

still governs how often the task releases and how often higher-priority tasks preempt it (the

⌈ R_{i} / T_{j} ⌉

term), so it cannot be ignored even when

D_{i} = T_{i}

"A late video frame should be buffered and shown as soon as it arrives."

A video frame is a firm deadline — once its display slot passes it has zero value and should be discarded, not shown late, which would corrupt playback timing.

"Since our airbag controller usually fires in 5 ms and the deadline is 20 ms, we have huge margin."

"Usually" is irrelevant for a hard deadline; the guarantee must hold for the worst-case execution (

C_{i}

) and worst-case interference, not the typical run.

"We raised the CPU clock, so priority inversion is no longer a concern."

A faster clock does not remove unbounded blocking — a low-priority task holding a lock still stalls a high-priority one; you need priority inheritance, not more MHz.

"Our tasks arrive on a strict fixed period, so their arrivals are jitter-free by definition."

A periodic model assumes perfect spacing

T_{i}

, but real releases suffer arrival jitter; if arrivals can bunch up (a sporadic/jittery model), your worst-case interference is higher than the pure-periodic analysis predicts.

Why questions

Why does correctness in real-time include when, not just what?

Because a logically correct result delivered after its deadline

D_{i}

can be useless or dangerous (e.g. firing an airbag after the crash), so timeliness is part of the specification.

Why is the RM utilisation bound below

1

while EDF's is exactly

1

Fixed priorities can force the CPU idle at worst-case phasing, wasting capacity; EDF re-decides priority by nearest deadline, so it never idles while work is pending under

U \leq 1

Why does the ceiling

⌈ R_{i} / T_{j} ⌉

appear in Response-Time Analysis?

It counts how many times a higher-priority task

j

is released — and thus preempts task

i

— within the response window

R_{i}

, and preemptions come in whole releases so we round up.

Why must Response-Time Analysis be solved by iteration?

R_{i}

appears on both sides (a bigger response window admits more preemptions, which grows the window), so you fix-point iterate from

R_{i} = C_{i}

until the value stops changing.

Why does

U > 1

guarantee a missed deadline regardless of scheduler?

Because the tasks collectively demand more than 100% of one CPU's time — a physical impossibility — so no scheduling order can serve all of them on time.

Why is graceful degradation the design knob for soft, not hard, systems?

Soft systems keep partial value under overload (drop quality, skip frames), whereas a hard system must never miss at all, so shedding load is not an acceptable substitute for a proof.

Why does a sporadic task (only a minimum inter-arrival gap) still get analyzed like a periodic one?

Its worst case for the CPU is arriving as fast as allowed, i.e. exactly every minimum-gap; treating that minimum gap as the period

T_{i}

gives a safe upper bound on interference.

Edge cases

What happens to schedulability when a single task's WCET is unbounded?

No bound exists, so no hard guarantee is possible; the task must be redesigned to have a finite, analyzable

C_{i}

before any test applies.

At exactly

U = n (2^{1/ n} - 1)

, is an RM task set schedulable?

Yes — the bound is

U \leq

the threshold, so equality still passes the sufficient test and guarantees all deadlines.

n \to \infty

, what does the RM utilisation bound approach, and what does that mean?

It approaches

ln 2 \approx 0.693

, meaning with many tasks you can safely use only ~69% of the CPU under RM in the worst case.

What is the value of a hard-deadline result delivered one instant late?

Effectively

- \infty

(invalid/catastrophic) — a hard deadline is a cliff, so even a tiny overrun is treated as total failure.

If a task's relative deadline

D_{i}

is shorter than its period

T_{i}

(constrained deadline), does

U \leq 1

still suffice for EDF?

Not necessarily — the simple

U \leq 1

bound assumes

D_{i} = T_{i}

; with

D_{i} < T_{i}

you need a demand-bound or processor-demand test, since less slack can cause misses even below full utilisation.

If a task's relative deadline

D_{i}

is longer than its period

T_{i}

(arbitrary deadline), what breaks in the simple analysis?

A new job can be released before the previous job of the same task has finished, so you must track multiple outstanding jobs per task; the plain single-job RTA and the

U \leq 1

EDF test no longer apply, and a processor-demand / busy-period analysis is required.

For a sporadic task with arrival jitter, which value do we plug in as the effective period to stay safe?

The minimum inter-arrival time (worst-case bunching), because that maximises how often the task preempts others; using the average or nominal spacing would under-count interference and give a false pass.

A soft task that misses by 0 ms (finishes exactly at

D_{i}

) — did it meet its deadline?

Yes — the condition is

R_{i} \leq D_{i}

(inclusive), so finishing exactly at the deadline counts as meeting it, with tardiness

max (0, R_{i} - D_{i}) = 0

For the deeper machinery behind these traps, see Worst-Case Execution Time analysis, Rate-Monotonic Scheduling, Earliest Deadline First (EDF), Priority Inversion and Priority Inheritance, Periodic vs Aperiodic Tasks, and Jitter and Latency.

Recall One-line self-test before you leave

Cover the answers and re-do any three items from each section; if you can state the reason (not just the verdict) for all of them, you own this topic.