Skip to main content

Real-Time Scheduling: Hard vs Soft, EDF, RMS

What This Concept Is​

A real-time task is one where timing correctness is part of correctness. Missing a deadline is a bug, not a performance issue. Two flavors:

  • Hard real time: missing a deadline is a system failure. Think airbag controller, flight control, medical infusion pumps.
  • Soft real time: missing a deadline degrades quality but does not kill the system. Think video playback (a dropped frame), VOIP jitter.

Two classic uniprocessor real-time policies:

  • Rate-Monotonic Scheduling (RMS): static priorities assigned inversely to period. Task with period 10 ms has higher priority than task with period 50 ms. Schedulable on a single CPU if CPU utilization U = sum (C_i / T_i) <= n * (2^(1/n) - 1), which tends to ln 2 ≈ 0.693 as n -> ∞.
  • Earliest-Deadline-First (EDF): dynamic priority equal to absolute deadline. Always run the task whose deadline is closest. Schedulable on a single CPU iff U = sum (C_i / T_i) <= 1.

C_i is worst-case execution time of task i, T_i is its period (= deadline in the basic model).

Why It Matters Here​

General-purpose schedulers optimize averages; real-time schedulers optimize worst cases. Even if you never ship control software, you will run audio, video, low-latency networking, or HFT code that leans on real-time scheduling classes (SCHED_FIFO, SCHED_DEADLINE on Linux). Knowing the feasibility tests prevents the "deadline misses under load" incident report.

Concrete Example​

Three periodic tasks on one CPU:

TaskPeriod T (ms)WCET C (ms)Utilization
T11030.30
T22040.20
T340100.25

Total U = 0.75.

RMS bound for n=3: 3 * (2^(1/3) - 1) ≈ 0.779. U = 0.75 <= 0.779, so RMS schedulable. Priorities: T1 > T2 > T3 (shorter period -> higher priority).

EDF bound: U <= 1, satisfied. EDF can handle utilizations RMS cannot.

A short Gantt for the first 40 ms under RMS (h = high-priority preempt):

 0   3         10    14        20   24   28        30   33    40
 │T1 │  T3     │ T1  │  T2     │ T1 │ T3 │ T3      │ T1 │ T3  │
                   h                    h                h

T1 fires at 0, 10, 20, 30; T2 fires at 0, 20; T3 fires at 0, runs when nobody else needs the CPU. All deadlines met.

If you added T4 with T=8, C=3 (U_4 = 0.375), total U = 1.125 > 1. No scheduler, EDF or RMS, can meet all deadlines.

Common Confusion / Misconception​

"High priority = real time." No. Classic Linux SCHED_FIFO at priority 99 is preemptive and high priority but has no knowledge of deadlines -- a runaway SCHED_FIFO loop can freeze the system. True deadline scheduling needs SCHED_DEADLINE (added 2014), which implements constant-bandwidth server EDF.

"EDF strictly dominates RMS." EDF has a better schedulability bound, yes. RMS has simpler analysis, simpler implementation, and more predictable behavior on overload (lower-priority tasks miss first, not arbitrary ones). In safety-critical certification, determinism often wins over raw utilization.

How To Use It​

To analyze a real-time workload:

  1. Write down each task's (T_i, C_i) and deadline D_i (often D_i = T_i).
  2. Compute total utilization U.
  3. Check U <= 1 (necessary condition, any policy).
  4. For RMS, check against n(2^(1/n) - 1) bound.
  5. For EDF, any U <= 1 is sufficient.
  6. If the bound fails, either reduce C_i (make tasks faster), increase T_i (loosen deadlines), or add a CPU.

Check Yourself​

  1. Why does EDF have a tighter bound than RMS in theory but harder behavior on overload?
  2. What is the difference between hard and soft real time, operationally?
  3. Why is SCHED_FIFO at priority 99 not the same thing as "real time"?

Mini Drill or Application​

Given:

TaskTC
A41
B52
C205
  1. Compute U.
  2. Apply the RMS bound for n=3.
  3. If RMS fails, does EDF succeed? Justify numerically.
  4. Sketch the first 20 time units under EDF.

Read This Only If Stuck​