Rate Monotonic vs Earliest Deadline First: A Practical Comparison

Rate Monotonic (RM) and Earliest Deadline First (EDF) are the two scheduling policies every real-time engineer learns first, and for good reason. Both were analyzed in the same landmark 1973 paper by Liu and Layland, both remain at the core of modern real-time operating systems, and the choice between them still shapes how much processor capacity you can use, how your system behaves under overload and how hard it is to implement and certify.

This article compares the two in practical terms: the theory you need, the schedulability tests, a worked example where the two policies give different answers, and the engineering trade-offs that usually decide the matter. If you are new to the vocabulary of periods, deadlines and WCET, start with What Is a Real-Time Embedded System?

The common system model

Both analyses assume a single processor and a set of n independent periodic (or sporadic) tasks. Each task τi has a worst-case execution time Ci, a period Ti and a relative deadline Di. In the classic Liu and Layland setting, deadlines are implicit (Di = Ti), tasks are fully preemptible, they do not block on shared resources and scheduling overheads are negligible. The total utilization is U = Σ Ci/Ti. No policy can schedule a task set with U > 1 on one processor, so U is the natural yardstick for comparison. Terms used here are defined in our glossary.

Rate Monotonic scheduling

Under RM, each task receives a static priority inversely related to its period. The scheduler always runs the highest-priority ready job, preempting lower-priority work. Liu and Layland proved that RM is optimal among fixed-priority assignments for implicit-deadline tasks: if any fixed priority order can schedule the set, RM can. When deadlines are shorter than periods, the optimal fixed-priority order becomes Deadline Monotonic (shorter relative deadline, higher priority), as shown by Leung and Whitehead in 1982. For more general cases, Audsley’s optimal priority assignment algorithm searches for a feasible order.

The Liu and Layland utilization bound

The famous sufficient test states that n tasks are schedulable under RM if

U = Σ Ci/Ti ≤ n(2^(1/n) − 1)

The bound is sufficient but not necessary. A task set above it may still be schedulable. Two refinements help:

• Hyperbolic bound (Bini, Buttazzo and Buttazzo, 2003): RM is schedulable if Π (Ui + 1) ≤ 2. It is strictly less pessimistic than Liu and Layland at the same O(n) cost.
• Harmonic periods: if every period divides every longer one, RM schedules any set with U ≤ 1. More generally, the closer periods are to harmonic, the higher the achievable utilization.

Exact analysis

For a definitive answer, fixed-priority systems use response-time analysis (RTA). For each task, the worst-case response time is the smallest fixed point of

Ri = Ci + Σ_{j ∈ hp(i)} ⌈Ri / Tj⌉ · Cj

where hp(i) is the set of higher-priority tasks. The task set is schedulable if Ri ≤ Di for all i. RTA handles constrained deadlines, release jitter and blocking, and it is exact for the basic model. Our step-by-step RTA worked example shows each iteration in detail. In experiments with randomly generated task sets, Lehoczky, Sha and Ding (1989) found that RM typically remained schedulable up to roughly 88% utilization, well above the worst-case bound.

Earliest Deadline First scheduling

EDF is a dynamic-priority policy: at every scheduling point it runs the ready job with the earliest absolute deadline. Priorities belong to jobs, not tasks, so the relative order of two tasks can change from one job to the next.

Optimality and the utilization test

Liu and Layland showed, and Dertouzos generalized, that EDF is optimal on a uniprocessor: if any preemptive algorithm can meet all deadlines, EDF can. For implicit deadlines this gives an exact and remarkably simple test:

Schedulable under EDF  ⇔  U = Σ Ci/Ti ≤ 1

Constrained and arbitrary deadlines

When Di < Ti, the utilization test is no longer sufficient. The density test Σ Ci/min(Di, Ti) ≤ 1 is sufficient but pessimistic. The exact method is the processor demand criterion (Baruah, Mok and Rosier, 1990): the set is schedulable if and only if U ≤ 1 and, for every interval length t,

h(t) = Σ max(0, ⌊(t − Di)/Ti⌋ + 1) · Ci ≤ t

It suffices to check t at absolute deadlines up to a computable bound, and techniques such as Quick Processor-demand Analysis (QPA) make the check fast in practice.

Worked example: where RM and EDF disagree

Consider two implicit-deadline tasks:

Total utilization is 0.971. The Liu and Layland bound for n = 2 is 0.828, so the sufficient test fails. The hyperbolic test gives 1.4 × 1.571 = 2.2 > 2, also inconclusive. Running RTA for τ2:

R2 has already exceeded D2 = 7, so τ2 misses its deadline under RM. Intuitively, τ1’s second job arrives at time 5, preempts τ2 with one unit of work remaining, and τ2 completes at 8.

Under EDF, U = 0.971 ≤ 1, so the set is schedulable. At time 5, τ1’s new job has absolute deadline 10 while τ2’s current job has deadline 7, so τ2 keeps the processor and finishes at 6. EDF reorders priorities exactly when it matters. You can reproduce both schedules as Gantt charts in our schedulability calculator.

The same logic in compact Python:

import math

def rm_schedulable(tasks):            # tasks: list of (C, T), sorted by T
    for i, (C, T) in enumerate(tasks):
        R = C
        while True:
            R_new = C + sum(math.ceil(R / Tj) * Cj for Cj, Tj in tasks[:i])
            if R_new > T:
                return False
            if R_new == R:
                break
            R = R_new
    return True

def edf_schedulable(tasks):           # implicit deadlines
    return sum(C / T for C, T in tasks) <= 1.0

tasks = [(2, 5), (4, 7)]
print(rm_schedulable(tasks), edf_schedulable(tasks))   # False True

Behavior under overload

Analysis assumes WCETs are never exceeded. Real systems face bugs, unexpected inputs and misestimated WCETs, so overload behavior matters.

• Fixed priorities degrade gracefully. If a task overruns, only tasks of lower priority are affected. High-priority tasks keep meeting deadlines, which makes it straightforward to protect the most critical functions by assigning them the highest priorities (with care, since that can conflict with RM ordering).
• EDF can suffer a domino effect. When the processor is overloaded, a job that is about to miss its deadline still has the earliest deadline and keeps running, pushing other jobs past their deadlines in turn. In a sustained overload, potentially every task misses.

Practical comparison

A detailed analysis by Buttazzo (2005), “Rate Monotonic vs. EDF: Judgment Day,” challenged several common beliefs. EDF’s implementation complexity is often overstated, and because it causes fewer preemptions, its total overhead can be lower than RM’s at high load. RM remains easier to reason about informally and is supported by virtually every certified RTOS and timing-analysis tool.

Accounting for overheads and non-ideal behavior

Textbook tests assume free context switches and full preemptibility. On real hardware you must inflate each Ci by the cost of the context switches it can cause (commonly two per job under preemptive scheduling), model interrupt handlers as high-priority sporadic tasks, and account for non-preemptive sections in the kernel or drivers as blocking. Cache-related preemption delays can be significant on processors with large caches, and they penalize whichever policy preempts more often. Both RM and EDF analyses extend cleanly to include release jitter, blocking terms and limited-preemption models, so these effects should be part of the argument rather than an afterthought covered by a generic safety margin.

Shared resources need their own protocol under either policy. For fixed priorities, see our article on priority inversion and the priority ceiling protocol; for EDF, Baker’s Stack Resource Policy plays the equivalent role. On multicore hardware, neither policy retains its uniprocessor optimality, as discussed in multicore real-time scheduling.

How to choose

Whichever you choose, the analysis is only as good as its inputs: the WCET values, the overhead model and the task model’s match to reality. If you would like an independent check of an existing design, our real-time schedulability audit reviews priorities, utilization and response times against your requirements.

Frequently asked questions

Why is the Rate Monotonic bound 69.3%?

Liu and Layland found the least upper bound on utilization below which any n-task set is RM-schedulable: n(2^(1/n) − 1). As n grows, this expression converges to the natural logarithm of 2, about 0.693. It reflects worst-case period ratios; real task sets usually tolerate more.

If EDF is optimal, why is fixed-priority scheduling more common?

Fixed priorities are simpler to implement, universally supported by RTOSes and standards such as POSIX and OSEK/AUTOSAR, well covered by analysis tools, and degrade predictably under overload. Those practical advantages usually outweigh EDF’s higher schedulable utilization.

Is Deadline Monotonic the same as Rate Monotonic?

They coincide when deadlines equal periods. When deadlines are shorter than periods, Deadline Monotonic assigns priorities by relative deadline and is the optimal fixed-priority ordering for that case, whereas RM is not.

Can I use EDF on Linux?

Yes. The SCHED_DEADLINE policy, available since Linux 3.14, schedules tasks by EDF and enforces each task’s runtime budget per period using a Constant Bandwidth Server, with admission control to prevent overload.

Does exceeding the Liu and Layland bound mean my system will fail?

No. The bound is only sufficient. Above it, run an exact response-time analysis; many task sets remain schedulable well beyond 69% and up to 100% when periods are harmonic.

References and further reading

1. Liu, C. L. and Layland, J. W. (1973). “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment.” Journal of the ACM, 20(1).
2. Buttazzo, G. C. (2005). “Rate Monotonic vs. EDF: Judgment Day.” Real-Time Systems, 29(1).
3. Bini, E., Buttazzo, G. C. and Buttazzo, G. M. (2003). “Rate Monotonic Analysis: The Hyperbolic Bound.” IEEE Transactions on Computers, 52(7).
4. Lehoczky, J., Sha, L. and Ding, Y. (1989). “The Rate Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior.” Proceedings of the IEEE Real-Time Systems Symposium.
5. Baruah, S., Mok, A. and Rosier, L. (1990). “Preemptively Scheduling Hard-Real-Time Sporadic Tasks on One Processor.” Proceedings of the IEEE Real-Time Systems Symposium.
6. Rate-monotonic scheduling — Wikipedia
7. Earliest deadline first scheduling — Wikipedia
8. Deadline Task Scheduling — Linux kernel documentation