Deadline Monotonic Scheduling
Deadline monotonic assigns fixed priority by relative deadline: the shortest deadline gets the highest priority. Where deadlines equal periods it is identical to rate-monotonic; where deadlines are shorter, it is strictly better.
Priority by Deadline, Not Period
Deadline monotonic scheduling is a fixed-priority scheme: each task gets a priority once, before the system runs, ordered by its relative deadline. Deadline monotonic scheduling, or DMS, is the name for that rule. The task that must respond fastest after release gets the highest priority, and that priority never changes.
The contrast with rate-monotonic is precise and narrow. RM orders by period T; DM orders by relative deadline D. When every task has D = T the two produce the identical priority assignment and are the same algorithm. They differ only for constrained deadline task sets, where D < T — a task released every 100 ms that must complete within 20 ms.
That case is common in practice. A sensor sampled at 10 Hz whose reading must reach a control loop within 20 ms has D = 20, T = 100. Rate-monotonic would give it low priority because its period is long, and it would miss. Deadline monotonic gives it high priority because its deadline is tight, which is the property that actually matters.
Leung and Whitehead proved in 1982 that DM is optimal among fixed-priority algorithms for constrained-deadline task sets: if any fixed-priority assignment can schedule the set, the deadline-monotonic assignment can.
- Priority is fixed and ordered by relative deadline
- Identical to rate-monotonic when D equals T
- Differs only for constrained-deadline task sets
- Optimal among fixed-priority schemes when D ≤ T
Why Utilisation Bounds Stop Working
Rate-monotonic comes with the convenient sufficient test U ≤ n(2^(1/n) − 1). For deadline monotonic there is no equivalent simple bound, and the reason is worth stating: utilisation measures work per period, while the constraint being tested is completion within a deadline shorter than that period. A task set at 40% utilisation can be infeasible if the deadlines are tight enough.
The correct tool is response time analysis, which computes the worst-case response time of each task directly and compares it against that task's deadline. For task i with all higher-priority tasks in the set hp(i), the worst-case response Rᵢ is the smallest solution to the recurrence Rᵢ = Cᵢ + Σ ⌈Rᵢ/Tⱼ⌉ Cⱼ over j in hp(i).
Read the terms plainly. Cᵢ is the task's own execution. The ceiling term counts how many times each higher-priority task can be released during the interval Rᵢ, and multiplies by its cost — that is the interference. Because interference depends on the response time being computed, the equation is solved iteratively, starting at Rᵢ = Cᵢ and substituting until the value stops changing.
Two outcomes exist. The iteration converges to a fixed point, which is the worst-case response time; if that value is ≤ Dᵢ the task is schedulable. Or the value grows past Dᵢ, at which point the task set is infeasible and no further iteration is needed. This test is exact rather than merely sufficient, which is why safety-critical timing analysis uses it rather than a utilisation bound.
- No simple utilisation bound exists for DM
- Response time analysis is exact, not sufficient
- Interference depends on the response being computed
- The recurrence converges or exceeds the deadline
Where It Sits Against the Alternatives
Against rate monotonic: DM is never worse and is strictly better whenever any task has D < T. Since implementing DM costs nothing extra — both are static priority assignments computed offline — DM is the better default for constrained-deadline systems.
Against EDF: EDF achieves higher utilisation, up to 100% against DM's lower ceiling, because dynamic priorities let it adapt. DM keeps the advantages of fixed priority: cheaper dispatch, fewer context switches, mature tooling, and predictable behaviour under overload where the lowest-priority tasks are sacrificed first rather than the whole set collapsing.
This is why fixed-priority scheduling with deadline-monotonic assignment and response time analysis remains standard in automotive and avionics software. AUTOSAR and ARINC 653 systems are built on it, not because the theory is unaware of EDF, but because certification requires proving worst-case behaviour and fixed priority makes that proof tractable and familiar.
- Never worse than rate-monotonic, often better
- EDF reaches higher utilisation than any fixed priority
- Fixed priority is cheaper to dispatch and to certify
- AUTOSAR and ARINC 653 are built on this model
Response time analysis iterated to a fixed point, task by task
# Deadline-monotonic priority assignment + exact response time analysis.
# Utilisation bounds do NOT work when D < T. This recurrence is exact.
import math
def assign_priorities(tasks):
# DM: shortest RELATIVE DEADLINE gets highest priority. Not period.
return sorted(tasks, key=lambda t: t["D"])
def response_time(task, higher):
R = task["C"] # seed with own execution time
while True:
# interference: how many times each higher-priority task can be
# released inside R, times what each release costs
interference = sum(math.ceil(R / h["T"]) * h["C"] for h in higher)
nxt = task["C"] + interference
if nxt == R: # fixed point reached
return R
if nxt > task["D"]: # blew the deadline -- stop early
return None
R = nxt # substitute and iterate again
def analyse(tasks):
ordered = assign_priorities(tasks)
for i, t in enumerate(ordered):
R = response_time(t, ordered[:i])
ok = R is not None and R <= t["D"]
print("%s: R=%s D=%d %s" % (t["name"], R, t["D"], "ok" if ok else "MISS"))
if not ok:
return False
return True
TASKS = [{"name": "T1", "C": 1, "D": 4, "T": 10},
{"name": "T2", "C": 2, "D": 6, "T": 10},
{"name": "T3", "C": 3, "D": 12, "T": 20}]
print("schedulable:", analyse(TASKS))
// Deadline monotonic + exact response time analysis.
#include <iostream>
#include <optional>
#include <string>
#include <vector>
#include <algorithm>
struct Task {
std::string name;
int C, D, T;
};
// Smallest R satisfying R = C + sum( ceil(R/Tj) * Cj ) over higher priority.
std::optional<int> responseTime(const Task& t, const std::vector<Task>& higher) {
int R = t.C; // seed with own compute time
while (true) {
int interference = 0;
for (const auto& h : higher)
interference += ((R + h.T - 1) / h.T) * h.C; // ceil(R/Tj)*Cj
int next = t.C + interference;
if (next == R) return R; // converged
if (next > t.D) return std::nullopt; // exceeded deadline
R = next;
}
}
bool schedulable(std::vector<Task> tasks) {
// DM assignment: sort by relative deadline, shortest first
std::sort(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) { return a.D < b.D; });
for (size_t i = 0; i < tasks.size(); ++i) {
std::vector<Task> higher(tasks.begin(), tasks.begin() + i);
auto R = responseTime(tasks[i], higher);
if (!R || *R > tasks[i].D) return false;
std::cout << tasks[i].name << ": R=" << *R << " D=" << tasks[i].D << '\n';
}
return true;
}
int main() {
std::cout << std::boolalpha
<< schedulable({{"T1",1,4,10},{"T2",2,6,10},{"T3",3,12,20}}) << '\n';
}// Deadline-monotonic priorities with exact response-time analysis.
import java.util.*;
class DM {
record Task(String name, int C, int D, int T) {
}
// Iterate R = C + sum(ceil(R/Tj)*Cj) until it stops moving.
static OptionalInt responseTime(Task t, List<Task> higher) {
int R = t.C();
while (true) {
int interference = 0;
for (Task h : higher)
interference += Math.ceilDiv(R, h.T()) * h.C();
int next = t.C() + interference;
if (next == R) return OptionalInt.of(R); // fixed point
if (next > t.D()) return OptionalInt.empty(); // infeasible
R = next;
}
}
static boolean schedulable(List<Task> tasks) {
List<Task> ordered = new ArrayList<>(tasks);
ordered.sort(Comparator.comparingInt(Task::D)); // DM: by deadline
for (int i = 0; i < ordered.size(); i++) {
OptionalInt R = responseTime(ordered.get(i), ordered.subList(0, i));
if (R.isEmpty() || R.getAsInt() > ordered.get(i).D()) return false;
}
return true;
}
}Step through it
Running on T1(C=1,D=4,T=10) T2(C=2,D=6,T=10) T3(C=3,D=12,T=20) U = 0.45
Read all 13 Steps
- three tasks with deadlines shorter than their periods T1 runs every 10 ticks but must finish within 4. T2 every 10, must finish within 6. T3 every 20, must finish within 12. Every task has D < T, which is called a constrained-deadline set — and it is exactly the case where rate-monotonic gets the priorities wrong and deadline-monotonic gets them right.
- deadline monotonic assigns priority by D, not by T Sort by relative deadline: T1 (D=4) highest, T2 (D=6) next, T3 (D=12) lowest. Rate-monotonic would sort by period instead, giving T1 and T2 the same period of 10 and tie-breaking arbitrarily — it cannot see that T1 is twice as urgent as T2. Leung and Whitehead proved in 1982 that when D ≤ T, this deadline ordering is optimal among all fixed-priority assignments.
- why the utilisation shortcut does not apply here Total utilisation is 1/10 + 2/10 + 3/20 = 0.45, comfortably under any bound you might quote. But utilisation measures work per period, and the constraint being tested is completion within a deadline shorter than that period. A set at 40% utilisation can still miss deadlines if they are tight enough. There is no simple sufficient bound for DM — the exact test is required.
- T1 is highest priority, so nothing interferes with it The recurrence is R = C + Σ⌈R/Tj⌉·Cj summed over strictly higher-priority tasks. T1 has none, so the sum is empty and R1 = C1 = 1. It converges immediately. 1 ≤ 4, so T1 is schedulable with three ticks of slack.
- T2: seed the iteration with its own compute time For T2 the only higher-priority task is T1. Start at R = C2 = 2. Now ask: how many times can T1 be released inside a window of 2 ticks? ⌈2/10⌉ = 1, so T1 interferes once for 1 tick.
- T2: substitute and iterate again Now R = 3. Recompute the interference over the larger window: ⌈3/10⌉ = 1, still one release of T1, still 1 tick. So the next value is 2 + 1 = 3 — identical to the current one. The iteration has reached a fixed point.
- why the iteration is necessary at all Notice the circularity: interference depends on how long the task takes, and how long it takes depends on the interference. That is why this is solved by substitution rather than a formula. Each step uses a larger window, which may admit more releases of higher-priority tasks, which lengthens the window again. It either settles or exceeds the deadline.
- T3: both T1 and T2 are higher priority T3 has C = 3 and two tasks above it. Seed R = 3. Interference: ⌈3/10⌉×1 = 1 from T1, ⌈3/10⌉×2 = 2 from T2. Total interference 3, so the next value is 3 + 3 = 6.
- T3: the window grew, so recompute the interference R is now 6. In a 6-tick window: ⌈6/10⌉ = 1 release of T1 costing 1, and ⌈6/10⌉ = 1 release of T2 costing 2. Interference is still 3, so R² = 3 + 3 = 6. Same value — converged.
- all three converge inside their deadlines R1 = 1 ≤ 4, R2 = 3 ≤ 6, R3 = 6 ≤ 12. Every task completes in the worst case before its deadline, so the set is schedulable under deadline-monotonic priorities. This test is exact, not merely sufficient — a pass means it genuinely cannot miss, and a fail means no fixed-priority assignment could have worked either.
- what a failing task looks like Suppose T3 needed C = 9 instead of 3. Then R⁰ = 9, interference 3, R¹ = 12; at 12 ticks ⌈12/10⌉ = 2 releases of each, interference becomes 2 + 4 = 6, R² = 15. That exceeds D = 12, so the iteration stops immediately and reports infeasible. No further substitution is needed — once R passes D the answer is settled.
- what rate-monotonic would have done with this set RM sorts by period: T1 and T2 both have T = 10 and tie, T3 has T = 20 and comes last. If the tie resolves in T2's favour, T2 outranks T1 — and T1, which must finish within 4, is now waiting behind a task that has 6 ticks of slack. DM never makes that mistake because it ranks on the quantity that actually constrains the system.
- where DM sits between RM and EDF Against rate-monotonic, DM is never worse and is strictly better whenever any task has D < T — and it costs nothing extra, since both are static assignments computed offline. Against EDF, DM gives up utilisation: EDF is schedulable up to U ≤ 1 while fixed priority cannot reach that. What DM keeps in exchange is cheaper dispatch, fewer context switches, mature response-time tooling, and predictable overload behaviour where the lowest-priority tasks are sacrificed first rather than the whole set collapsing. That last property is why AUTOSAR and ARINC 653 systems in automotive and avionics are built on fixed priority with DM assignment — certification requires proving worst-case behaviour, and this recurrence is a proof.