Real Time Scheduling

Real-Time Scheduling (avionics/fsw/real-time-scheduling)

Use when you must decide whether a periodic hard-real-time task set can meet every deadline on a single processor, before it ever runs. Each task is a (C, T) pair: worst-case execution time C and period T, with the implicit deadline D = T, all in one time unit. This leaf implements the standard public feasibility mathematics (Liu and Layland 1973 plus exact iterative response-time analysis) in pure Python stdlib: the processor utilization, the Liu-Layland sufficient bound for rate-monotonic fixed-priority scheduling, exact per-task response times with an RM verdict, and the earliest-deadline-first full-utilization verdict. It schedules the processes and partitions inside an ARINC 653 style avionics software partition layout, pairing with avionics/ima/ima-partitioning, which owns the major-frame cyclic window arithmetic that surrounds this leaf's process set.

Domain quick reference

• Task set convention: n tasks, each (C_i, T_i) with implicit deadline D_i = T_i, all in the same time unit. Shorter period means higher priority under RM; equal periods are broken by list index (the earlier task in the list is higher priority).
• Utilization: U = sum_i C_i / T_i. This is the fraction of the processor the task set demands in the long run.
• Liu-Layland bound: U_rm(n) = n (2^(1/n) - 1). Anchor values: U_rm(2) = 0.828427, U_rm(3) = 0.779763, U_rm(4) = 0.756828, and U_rm(1) = 1. The bound decreases toward ln 2 ~ 0.693 as n grows.
• RM sufficient test: if U <= U_rm(n) the set is feasible under RM. The bound is sufficient, not necessary: a set with U above the bound may still be RM-feasible, which is exactly when the exact analysis earns its keep.
• Exact RM response time of task i (fixed-point iteration): R_i = C_i + sum_{j in hp(i)} ceil(R_i / T_j) * C_j, iterated from R_i = C_i until the value stops changing, where hp(i) is the set of higher-priority tasks. RM is feasible iff every converged R_i <= T_i.
• Divergence handling: the response-time sequence is monotone non-decreasing, so when an iterate grows past the task period, or past the cap 1000 * max(T) of the set, it can never converge to a schedulable value and the analysis reports divergence. A diverging or deadline-crossing task makes the whole set RM-infeasible.
• EDF feasibility (implicit deadlines): U <= 1 is necessary and sufficient, because EDF is optimal among all scheduling algorithms on a single processor.
• Scheduling verdicts: "RM-guaranteed-by-UB" when the bound test passes; "RM-exact-feasible (UB inconclusive)" when the bound test fails but exact response-time analysis converges within every period; "EDF-feasible-only" when RM exact analysis fails but EDF can schedule the U <= 1 set; "RM-infeasible" otherwise.
• Scope notes: WCET estimation, jitter and blocking analysis, and arbitrary-deadline response-time extensions are out of scope; the model is the classic implicit-deadline periodic task set. ARINC 653 partition schedule windows and message bus response windows are not this leaf.

Workflow

1. Collect the task set as a list of (C, T) pairs in one time unit, worst-case execution time and period each, implicit deadline D = T. Every C and T must be positive; an empty list, a non-positive value, or a malformed entry raises ValueError from every function.
2. Compute the processor demand: utilization(tasks) returns U. If U > 1 the processor is oversubscribed: no single-processor scheduling algorithm can work, and EDF feasibility will fail.
3. Run the cheap sufficient test first: rm_ub_feasible(tasks) applies the Liu-Layland bound U <= U_rm(n). A True verdict closes the case (RM is guaranteed). A False verdict is inconclusive, not a failure.
4. When the bound is inconclusive, run the exact analysis: rm_response_times(tasks) returns the converged R_i list, or None when the iteration diverges (an iterate exceeded its period or the 1000 * max(T) cap), and rm_feasible(tasks) gives the exact RM verdict. This is where rate-monotonic analysis beats the utilization bound: a set that fails step 3 can still pass here.
5. Check the EDF alternative: edf_feasible(tasks) reports whether U <= 1, which for implicit-deadline sets is a complete EDF test.
6. Run scheduling_summary(tasks) once to gather every result: keys utilization, n_tasks, liu_layland_bound, rm_ub_verdict, rm_exact_response_times, rm_exact_feasible, edf_feasible, and a single verdict string.
7. Record the verdict and the response times in the scheduling analysis artifact for the certification package; re-run the contract test after any change to the task set.

Worked example

Spec task set A, [(1, 3), (1, 4), (2, 8)] (times in ms):

• Utilization: U = 1/3 + 1/4 + 2/8 = 0.8333333333333333.
• Liu-Layland bound for 3 tasks: 0.7797631496846196, so U > bound and rm_ub_feasible returns False: the bound test is inconclusive.
• Exact response-time analysis converges: rm_response_times(A) = [1.0, 2.0, 6.0] ms, all within their periods (3, 4, 8 ms), so rm_feasible returns True.
• EDF: U = 0.8333 <= 1, so edf_feasible returns True.
• scheduling_summary(A)["verdict"] is "RM-exact-feasible (UB inconclusive)": the key demonstration that response-time analysis proves schedulability where the Liu-Layland bound stays silent.

Set B, [(2, 3), (2, 5), (2, 7)]: U = 1.3523809523809525 > 1, so edf_feasible is False, rm_response_times returns None (the second task response time crosses its period and the iteration diverges), and the verdict is "RM-infeasible".

Set C, [(1, 5), (1, 6), (2, 10)]: U = 0.5666666666666667 <= 0.7798, so rm_ub_feasible is True and the verdict is "RM-guaranteed-by-UB"; the exact analysis confirms with response times [1.0, 2.0, 4.0].

Verification

• Confirm the Liu-Layland anchors: liu_layland_bound(2) = 0.828427, liu_layland_bound(3) = 0.779763, liu_layland_bound(4) = 0.756828 (each within 1e-5).
• Confirm worked set A gives U 0.8333, rm_ub_feasible False (bound inconclusive), rm_response_times [1.0, 2.0, 6.0] with rm_feasible True, edf_feasible True, verdict "RM-exact-feasible (UB inconclusive)".
• Confirm worked set B gives U 1.3524 > 1, edf_feasible False, RTA divergence (None), rm_feasible False.
• Confirm worked set C gives U 0.5667, rm_ub_feasible True, response times [1.0, 2.0, 4.0], verdict "RM-guaranteed-by-UB".
• Confirm adding a task raises U and doubling a task's C doubles that task's utilization contribution.
• Confirm an empty task list, C <= 0, T <= 0, malformed or non-numeric entries, and a fractional task count raise ValueError from every public function.
• Confirm identical outputs run to run (no randomness anywhere).
• Run the deterministic contract test offline: python3 scripts/test_real_time_scheduling.py (35 tests).

Related leaves

• avionics/ima/ima-partitioning: ARINC 653 major-frame cyclic window arithmetic; this leaf schedules the periodic process sets that run inside those partition windows.
• avionics/fsw/cfs-architecture: flight software application routing; its periodic applications carry the C and T budgets this leaf checks.
• avionics/data-bus/mil-std-1553: bus command/response protocol timing; its response-window concept is a bus term, not a task response time.

Pitfalls

• Reading a failed utilization bound as infeasibility: the Liu-Layland bound is sufficient, not necessary - worked set A fails the bound (U 0.8333 above U_rm(3) 0.7798) yet is exactly RM-feasible with response times [1.0, 2.0, 6.0], so a False rm_ub_feasible verdict means run the exact analysis, not declare the set unschedulable.
• Treating divergence as a numeric hiccup: the response-time sequence is monotone non-decreasing, so an iterate that crosses its period or the 1000 * max(T) cap can never converge - rm_response_times returns None and the whole set is RM-infeasible (set B), which is a verdict, not an error to paper over.
• Mixing time units in one task set: every C_i and T_i must share one time unit and the implicit deadline is D_i = T_i - a task listed in seconds against milliseconds, or with an explicit different deadline, is outside this leaf's model and corrupts U and the response-time iteration.
• Ignoring the priority order: RM assigns priority by shorter period, with equal periods broken by list index, and the exact analysis sums only over higher-priority tasks hp(i) - the response-time result is only valid for the task list in RM priority order.
• Assuming EDF always saves the set: EDF is complete only for U <= 1, so an over-subscribed set (U 1.3524, set B) is infeasible under any single-processor algorithm, and the "EDF-feasible-only" verdict means the exact RM analysis failed - the schedule then needs an EDF runtime, not rate-monotonic priorities.
• Routing adjacent timing domains here: WCET estimation, jitter and blocking analysis, arbitrary-deadline extensions, ARINC 653 partition schedule windows (ima/ima-partitioning), and bus response windows (data-bus/mil-std-1553) are not this leaf's classic implicit-deadline periodic model.

Behavior contract (gate 3)

Run the deterministic contract test (stdlib unittest, offline, no network, exits 0):

python3 scripts/test_real_time_scheduling.py

The test covers the Liu-Layland anchors U_rm(2/3/4), the three worked task sets A, B and C from the spec plus an EDF-feasible-only set D, exact response times with integrality for integer input, divergence detection returning None, single-task closed forms (R = C, feasible iff C <= T), utilization monotonicity and doubling, the EDF unit-utilization boundary, the exact convenience-dict keys, ValueError rejection of empty, non-positive and malformed task lists, and run-to-run determinism.

Compliance

• Standards referenced, not reproduced: DO-178C (avionics software lifecycle, including scheduling analysis of the software partition task sets) is listed reference-only per standards-map.yaml; the feasibility mathematics above is pure public science (Liu and Layland, 1973), summary-only.
• ARINC 653 is not in standards-map.yaml and is not needed: the process-level scheduling theory is independent of the partition standard text.
• compliance: STANDARDS-REF, gated: false.