Deadline Monotonic Scheduling

Deadline-Monotonic Scheduling (avionics/fsw/deadline-monotonic-scheduling)

Use when an avionics flight software task set has per-task relative deadlines D_i that are not the implicit D_i = T_i of the pack sibling, so the periodic-only model cannot admit the set at all: a 40 ms-period navigation task that must finish within 25 ms, or a 30 ms-period recording task that tolerates a 60 ms relative deadline. This leaf assigns priorities by deadline-monotonic order (shorter deadline, higher priority; the fixed-priority assignment Leung and Whitehead (1982) proved optimal for constrained deadlines), then runs the exact jitter-aware fixed-point response-time iteration task by task against each task's own deadline. Constrained deadlines (D <= T) need only the converged first-job completion; arbitrary deadlines (D > T) whose first-job completion exceeds the period additionally run the busy-period job scan and take the worst job response as the exact response time. Pure Python stdlib, closed form (math.ceil only), deterministic. Pairs with avionics/fsw/real-time-scheduling for the implicit-deadline feasibility verdicts of a set where every D = T and with avionics/fsw/shared-resource-access-control when a shared-resource blocking term must be added to the fixed point.

Domain quick reference

• Task shape: each task is a dict {name, C, T, D, J} in one time unit, worst-case execution C, period T, relative deadline D, optional release jitter J (default 0.0); name is optional. Every function rejects, with ValueError, an empty task list, a malformed entry, a missing C/T/D key, a boolean or non-positive C, T or D, a boolean or negative J, and a non-numeric value.
• Deadline-monotonic order: tasks sorted by D ascending, stably, so the shorter deadline ranks higher (index 0) and equal deadlines keep their input order. For constrained deadlines this assignment is optimal among fixed priorities (Leung and Whitehead, "On the Complexity of Fixed-Priority Scheduling of Periodic Real-Time Tasks", Performance Evaluation 2(4), 1982). The analysis functions require the list to already be in this order and raise ValueError otherwise; dm_priority_order produces it.
• Busy-window completion of job q of task i (Audsley, Burns, Richardson and Wellings, "Applying New Scheduling Theory to Static Priority Pre-emptive Scheduling", Software Engineering Journal, 1993): w_i(q) = (q + 1) * C_i + sum over higher-priority j of ceil((w_i(q) + J_j) / T_j) * C_j, iterated from w = (q + 1) * C_i until an iterate repeats within CONVERGENCE_TOL (1e-12). For q = 0 this is the classic fixed point R_i = C_i + sum of ceil((R_i + J_j) / T_j) * C_j, with the Tindell and Clark (1994) release-jitter term in the interference count. The map is monotone non-decreasing.
• Convergence rule: job q of task i releases at q * T_i and completes at w_i(q), so its response is w_i(q) - q * T_i and it must satisfy w_i(q) <= q * T_i + D_i. An iterate past that per-job bound can never converge under the deadline, so the solve reports None; a solve that still moves after MAX_RTA_ITERATIONS (100) passes also reports None.
• Constrained deadlines (D <= T): the converged first-job completion w_i(0) is the exact worst-case response time, feasible iff w_i(0) <= D_i; successive jobs never overlap, so no job scan runs.
• Arbitrary deadlines (D > T): when w_i(0) <= T_i the first-job completion is again the exact response. When w_i(0) > T_i, jobs queue and the exact response is the maximum of w_i(q) - q * T_i over the busy period, scanned while w_i(q) > (q + 1) * T_i and stopped at the first q with w_i(q) <= (q + 1) * T_i. A job response past D_i, or a scan past MAX_BUSY_PERIOD_JOBS (1000), reports None.
• Release jitter: J_j of a higher-priority task delays its releases by up to J_j and enters only the interference counts of lower-priority tasks through ceil((w + J_j) / T_j); a task's own J never enters its own equation. Jitter can inflate lower responses by whole preemptions and can push a first-job completion past T_i, opening the queueing regime.
• Utilization: U = sum of C_i / T_i, reported for context only; it is not a verdict when deadlines differ from periods, but U > 1 always ends in None through the never-ending busy period.
• Module constants: MAX_RTA_ITERATIONS = 100, MAX_BUSY_PERIOD_JOBS = 1000, CONVERGENCE_TOL = 1e-12. Imports math only.

Workflow

1. Assemble the task set as {name, C, T, D, J} dicts in one time unit, with J and name optional; every function validates the shape and raises ValueError on an empty list, malformed entry, missing key, boolean or non-positive C/T/D, or boolean or negative J.
2. Order the priorities: dm_priority_order over the task list returns the deadline-monotonic priority order, shorter deadline higher priority with stable ties (the shorter-deadline-order assignment).
3. Compute the context utilization: utilization over the set gives U = sum of C/T, reported but never a verdict (deadlines differ).
4. Run the jitter-aware fixed-point response-time iteration against each per-task deadline: response_time on each index of the deadline-monotonic-ordered list converges w_i(0) against D_i; a constrained-deadline task needs only this first-job completion.
5. Run the arbitrary-deadline busy-period job scan: response_time on a task with D > T whose first-job completion exceeds T_i scans the queued jobs and returns the worst job response, or None on divergence (an iterate or a queued job's response past D_i).
6. Recompute with the release jitter zeroed: response_time on the jitter-free copy of the set isolates what the higher-priority task's release jitter costs each lower task.
7. Take the feasible verdict: dm_response_times (or feasible) over the ordered list reports names, per-task response times, the feasible verdict (every response at most its own deadline) and U.
8. Confirm with the deterministic contract test run under both interpreters (see Behavior contract).

Worked example

Task set A, four avionics fsw processes in ms, already in deadline-monotonic order (deadlines 10, 20, 25, 60 ms ascending): flight-control (C 2.0, T 10.0, D 10.0, J 4.0), guidance (C 1.0, T 20.0, D 20.0), navigation (C 4.0, T 40.0, D 25.0, a constrained deadline shorter than its period) and mission-recording (C 18.0, T 30.0, D 60.0, an arbitrary deadline beyond its period). Real module outputs:

• dm_priority_order(A) keeps the list as given: the 25 ms-deadline navigation task outranks the 60 ms-deadline mission-recording task even though its 40 ms period is longer, the opposite of a period-ordered assignment.
• Full analysis: dm_response_times(A) gives responses [2.0, 3.0, 9.0, 32.0] ms against deadlines [10, 20, 25, 60] ms, utilization 0.95, feasible True: every task closes inside its own deadline.
• Constrained deadline and the jitter cost: response_time(A, 2) = 9.0 ms against D 25 ms for navigation; with J_0 = 0 the same task closes at 7.0 ms, so the 4 ms release jitter on flight-control costs navigation exactly 2.0 ms = C_0, one extra flight-control preemption counted by ceil((R + 4) / 10) at the converged R = 9.
• Arbitrary deadline, jittered: response_time(A, 3) = 32.0 ms against D 60 ms for mission-recording. Its first-job completion w(0) = 32.0 ms exceeds T = 30 ms, so jobs queue and the busy-period scan runs: completions w(0..3) = 32.0, 62.0, 91.0, 114.0 ms with job responses 32.0, 32.0, 31.0, 24.0 ms, stopping at job 3 because w(3) = 114.0 <= 4 * T = 120.0 ends the busy period; the exact worst case is the max, 32.0 ms. Without the jitter the first-job completion is exactly 30.0 ms = T, so no job ever queues and the response is 30.0 ms: the jitter is what opens the queueing regime.
• Queued job strictly the worst (navigation C = 5 variant, still D 25 <= T 40): response_time(variant, 2) = 10.0 ms; the mission-recording completions become 33.0, 64.0, 94.0, 119.0 ms with responses 33.0, 34.0, 34.0, 29.0 ms, so the exact worst-case response is 34.0 ms, held by the queued first and second jobs, strictly above the first-job completion 33.0 ms: the job scan, not the first-job fixed point alone, gives the arbitrary-deadline answer.
• Ordering is the analysis: the same four tasks under period-order priorities (10, 20, 30, 40) close at 2.0, 3.0 and 26.0 ms for flight-control, guidance and mission-recording, but navigation now sits below mission-recording and its iterates run 25.0 then 30.0, crossing D 25 ms on the second pass, so navigation reports None and the period-ordered set is infeasible; the deadline-monotonic order is the difference between a feasible and an infeasible set.
• Implicit-deadline identity (D = T, J = 0): the pack sibling's sets reproduce exactly, [1.0, 2.0, 6.0] on [(1, 3), (1, 4), (2, 8)] and [1.0, 2.0, 4.0] on [(1, 5), (1, 6), (2, 10)], both feasible True, and [2.0, None, None] on the over-subscribed [(2, 3), (2, 5), (2, 7)], feasible False.
• Over-subscribed arbitrary-deadline variant (mission-recording C = 22.0): utilization 1.083333 > 1, and dm_response_times reports [2.0, 3.0, 9.0, None], feasible False: the busy period of the arbitrary-deadline task never ends and a queued job's response crosses D 60 ms, the divergence verdict.
• Single-task closed form: response_time of {(C 3, T 10, D 7)} is 3.0 = C, feasible; {(C 3, T 10, D 2)} (C > D) reports None.
• Real ValueError messages: an empty list raises "task list must be a non-empty list"; a non-deadline-monotonic list raises "tasks must be in deadline-monotonic priority order (non-decreasing D); sort with dm_priority_order first"; C = 0 raises "C must be a positive number, got 0.0"; J = -1 raises "J must be a non-negative number, got -1.0"; a missing D raises "task missing key(s) D"; index 4 on the four-task list raises "index out of range".

Verification

• dm_response_times(A) returns [2.0, 3.0, 9.0, 32.0], feasible True, utilization 0.95; each response sits at most its own deadline.
• response_time(A, 2) = 9.0 with J_0 = 4 and 7.0 with J_0 = 0, the 2.0 ms difference equal to C_0 (release-jitter recomputation).
• The busy-period completions of mission-recording, w(0..3) = 32.0, 62.0, 91.0, 114.0 ms, terminate with 114.0 <= 120.0; the C = 5 variant completes at 33.0, 64.0, 94.0, 119.0 ms with worst 34.0 ms.
• dm_priority_order is stable (equal deadlines keep input order), returns non-decreasing D, and never mutates its input.
• ValueErrors across the module: empty list, missing key, boolean or non-positive C/T/D, boolean or negative J, non-numeric value, non-deadline-monotonic order (from response_time, dm_response_times and feasible), and index outside [0, len(tasks)) (from response_time).
• The module is deterministic (identical outputs run to run), imports nothing beyond math, and MAX_RTA_ITERATIONS = 100 with MAX_BUSY_PERIOD_JOBS = 1000.
• Run the contract test offline: python3 scripts/test_deadline_monotonic_scheduling.py (42 tests, exits 0; also green under ~/.pyenv/versions/3.13.12/bin/python3).

Related leaves

• avionics/fsw/real-time-scheduling: the implicit-deadline (D = T) utilization, bound and response-time feasibility verdicts; a set with any per-task deadline D != T routes here, because that leaf's model has no deadline slot and no deadline-ordered priority.
• avionics/fsw/shared-resource-access-control: the priority-ceiling blocking term B_i that a shared-resource task set adds to the same fixed point under implicit deadlines.
• avionics/fsw/aperiodic-server-scheduling: polling, deferrable and sporadic server budgets for aperiodic jobs beside an implicit-deadline periodic set.
• avionics/ima/ima-partitioning: partition window schedules and sampling or queuing port latencies one level above process deadlines.
• avionics/fsw/cfs-architecture and avionics/fsw/fprime-component: software bus routing and cyclic rate-group dispatch layout.
• avionics/data-bus/mil-std-1553: bus command/response windows, a bus term rather than a task response.

Pitfalls

• Routing a per-task-deadline set to the implicit-deadline sibling: real-time-scheduling has no D != T slot, so a 40 ms-period task with a 25 ms deadline cannot even be represented there; the deadline-monotonic order and the per-task-deadline convergence are this leaf's job.
• Assuming period order equals deadline order: the worked set is feasible under deadline-monotonic priorities and infeasible under rate-monotonic-style period priorities (navigation's second iterate 30.0 crosses D 25.0); order the priorities by the shorter deadline before running any analysis.
• Quoting the first-job completion as the arbitrary-deadline answer: when w(0) > T_i a queued job can be strictly the worst (34.0 ms from a queued job against a 33.0 ms first-job completion); only the busy-period job scan finds the exact worst case.
• Forgetting the release-jitter term: J_j of a higher-priority task inflates every lower task's interference count through ceil((w + J_j) / T_j), can cost whole preemptions (2.0 ms = C_0 on navigation) and can push a first-job completion past T_i into the queueing regime; but a task's own jitter never changes its own response.
• Reading U as the verdict: with per-task deadlines, U <= 1 is not a feasibility test and U > 1 is not the only infeasibility; the per-task convergence against each D_i decides.
• Treating a diverged task as a large response: response_time returns None when an iterate crosses q * T_i + D_i (it can never converge under the deadline) or when the scan exceeds the caps; None is the divergence verdict, not a number to compare against D_i.

Behavior contract (gate 3)

Run the deterministic contract test (stdlib unittest, offline):

python3 scripts/test_deadline_monotonic_scheduling.py

The test covers the task-shape ValueErrors, the deadline-monotonic priority assignment with stable ties, the context utilization, the jitter-aware fixed-point iteration against each per-task deadline including the constrained-deadline first-job completions and the implicit-deadline equivalence with the pack sibling's classic results, the arbitrary-deadline busy-period job scan with the exact busy-period completions and the queued-job-worst identity, the release-jitter recomputation (2.0 ms cost, queueing-regime opening), the feasible verdict of the whole set, the ordering-is-the-analysis contrast, the real ValueError messages, and module discipline (determinism, math-only imports, MAX_RTA_ITERATIONS 100 and MAX_BUSY_PERIOD_JOBS 1000). 42 tests, offline and deterministic, exits 0 under both /usr/bin/python3 (3.9.6) and ~/.pyenv/versions/3.13.12/bin/python3.

Compliance

• Standards referenced, not reproduced: RTCA DO-178C (Software Considerations in Airborne Systems and Equipment Certification) frames the avionics software lifecycle context in which the scheduling analysis artifact is recorded; the mathematics above is public science (Leung and Whitehead 1982; Audsley, Burns, Richardson and Wellings 1993; Tindell and Clark 1994), summary-only per standards-map.yaml. No standard text is reproduced verbatim.
• compliance: STANDARDS-REF, gated: false.