Real-Time Scheduling

Every scheduler so far optimised an average — mean turnaround, a fair long-run share. A real-time system does not care about averages. It cares about a single question asked of every job: will it finish before its deadline? When an airbag controller detects a crash, computing the correct deployment 10 ms late is not "a bit slow" — it is a failure as total as computing the wrong answer. The engine controller, the flight surface actuator, the software-defined radio, the robot joint: all are governed not by throughput but by deadlines.

Real-time scheduling flips the whole problem. Instead of "make good jobs run well on average", it asks "can I prove, before we ship, that every deadline will always be met?" That proof is a schedulability test, and this lesson is about the two classic algorithms that come with one — Rate-Monotonic (RM) and Earliest-Deadline-First (EDF) — and the nasty surprise (priority inversion) that once nearly killed a Mars mission.

Hard, soft, and the periodic task model

A hard real-time deadline must never be missed — a miss is a system failure (avionics, anti-lock brakes, a pacemaker). A soft deadline should usually be met; an occasional miss degrades quality but is survivable (a dropped video frame, a stutter in audio). The classic analysis models a set of periodic tasks: task i releases a new job every period T_i, each job needs up to C_i of CPU time (its worst-case execution time), and must finish within the period. The single most important derived quantity is the utilization each task demands:

U \;=\; \sum_{i=1}^{n} \frac{C_i}{T_i}.

If U > 1 you are asking for more than 100% of one CPU and no algorithm can help. The interesting question is what happens below 1 — and here RM and EDF give very different answers.

Rate-Monotonic: shorter period, higher priority

Rate-Monotonic scheduling assigns each task a fixed priority once, by its rate: the shorter the period, the higher the priority. It is a static priority scheme — priorities never change at run time — which makes it simple, predictable, and cheap to implement in a small RTOS. Below is a concrete RM schedule for two tasks, T_1 (period 4, cost 1) and T_2 (period 6, cost 2), over their hyperperiod of 12. Because T_1 has the shorter period it wins every conflict and preempts T_2 the instant it is released.

Liu and Layland proved (1973) that RM is the optimal fixed-priority assignment, and that any set of n tasks is guaranteed schedulable if its utilization stays under a bound:

U \;\le\; n\left(2^{1/n} - 1\right) \;\xrightarrow{\;n\to\infty\;}\; \ln 2 \approx 0.693.

Read that ceiling carefully: as the number of tasks grows, the guaranteed-safe utilization falls to about 69\%. With RM you may have to leave nearly a third of your CPU idle to be certain every hard deadline holds. That "wasted" headroom is the price of a simple static scheme.

EDF: let priorities move

Earliest-Deadline-First throws out fixed priorities. At every instant it runs whichever ready job has the nearest absolute deadline — a dynamic priority that changes as deadlines approach. This flexibility buys a remarkable result: EDF is optimal for a single processor, and a periodic task set is schedulable under EDF if and only if U \le 1. No wasted headroom — you can load the CPU right up to 100\% and still meet every deadline. The chart contrasts the two bounds: EDF's flat line at 1.0, and RM's curve sagging toward 0.693.

A schedulability test in code

An admission controller runs exactly this arithmetic before accepting a new task: compute U, compare it against the RM bound and against 1.0 for EDF. Try editing the task set — push the utilization up and watch RM reject a set that EDF still accepts.

// Schedulability tests for a periodic task set. Each task: worst-case cost C, period T. interface RtTask { name: string; C: number; T: number; } const tasks: RtTask[] = [ { name: "sensor", C: 1, T: 4 }, { name: "control", C: 2, T: 6 }, { name: "log", C: 1, T: 8 }, ]; const n = tasks.length; const U = tasks.reduce((s, t) => s + t.C / t.T, 0); const rmBound = n * (Math.pow(2, 1 / n) - 1); console.log("task C T utilisation C/T"); for (const t of tasks) console.log(`${t.name.padEnd(8)} ${t.C} ${t.T} ${(t.C / t.T).toFixed(3)}`); console.log(`total utilisation U = ${U.toFixed(3)}`); console.log(`RM bound for n=${n}: ${rmBound.toFixed(3)} -> ` + (U <= rmBound ? "RM: guaranteed schedulable" : "RM: bound EXCEEDED (test exactly, may still be ok)")); console.log(`EDF bound: 1.000 -> ` + (U <= 1 ? "EDF: schedulable" : "EDF: INFEASIBLE (U > 1, no scheduler can help)"));

Days after landing, Pathfinder began mysteriously resetting itself. The cause was priority inversion. A low-priority weather task grabbed a shared data bus (protected by a mutex), then was preempted. A high-priority bus-management task then needed the same mutex — and had to wait for the low-priority task to release it. But medium-priority tasks kept preempting the low-priority one, so it never ran, never released the mutex, and the high-priority task missed its deadline. A watchdog timer, seeing the critical task overrun, dutifully reset the spacecraft. JPL diagnosed it on a replica on Earth and uploaded a fix that switched on priority inheritance — the mutex temporarily lends the blocking low-priority task the high task's priority so it can finish and release. It is the canonical real-time bug, and we will meet its cure in full when we study kernel synchronization.

The Liu–Layland bound n(2^{1/n}-1) is sufficient, not necessary: pass it and you are guaranteed safe, but fail it and you know nothing yet. Plenty of task sets with U above the bound — even up to 1.0 — are perfectly schedulable under RM, especially when periods are harmonic (each a multiple of the next, e.g. 2, 4, 8, 16), where the RM bound effectively rises to 1.0. When the simple utilization test fails, you do not give up; you run an exact response-time analysis, iterating each task's worst-case response against interference from higher-priority tasks. The bound is a fast screen, not the final word.

Choosing between them

If EDF is optimal and wastes no CPU, why does so much safety-critical code still use RM? Because RM's static priorities are dead simple to reason about, cheap to implement, and — crucially — degrade predictably under overload: when the system is over-committed, RM sheds the lowest-rate tasks first, in a known order, while EDF can suffer a domino effect where one missed deadline cascades into many. Certification authorities like predictability. So RM (and its cousin deadline-monotonic) rules avionics and automotive RTOSes, while EDF and its variants power systems that prize utilization — real-time multimedia, and Linux's own \texttt{SCHED\_DEADLINE} class, which implements EDF with bandwidth reservations. Both are worlds away from the fairness-chasing CFS: here, being late is the only thing that counts.