Cyclic Executive Scheduling

Cyclic Executive Scheduling (avionics/fsw/cyclic-executive-scheduling)

Use when you must design and check the offline feasibility of a repeating, time-triggered cyclic executive (frame-based) schedule for a periodic avionics flight software task set. Each task is a dict {name, C, T} in one integer time unit: worst-case execution time C, period T, implicit deadline D = T. There are no priorities: the cyclic executive is priority-free, the frame table IS the schedule, and any task list order is accepted. This leaf implements the classic closed-form cyclic executive arithmetic (Baker and Shaw 1989, Locke 1992, Burns and Wellings 2009) in pure Python stdlib: the hyperperiod, the period gcd, the admissible frame lengths, the per-frame capacity check and the constructive frame table. It is the table-driven complement to this pack's priority-driven feasibility leaves, pairing with avionics/fsw/real-time-scheduling for single-estimate (C, T) priority verdicts and avionics/ima/ima-partitioning for the ARINC 653 partition window arithmetic one level above the task set.

Domain quick reference

• Hyperperiod (major cycle): H = lcm over all T_i, computed by folding lcm(a, b) = a * b // gcd(a, b) over the task periods. The frame table over frames 0..H/f - 1 repeats exactly every H time units.
• Period gcd: g = gcd over all T_i. A frame length divides every task period iff it divides g, so the candidate frame lengths are the divisors of g.
• Processor utilization (necessary condition only): U = sum of C_i / T_i. U <= 1 is necessary for a FITS verdict but never sufficient.
• Admissible frame lengths: the ascending divisors f of g with f at least max C_i, the frame-fit rule that every job fits inside its own frame.
• Frame dispatch: task i releases H / T_i jobs per hyperperiod, at times 0, T_i, 2T_i, .... The job released at time t = jf executes in frame j, so frame j carries exactly one job of task i iff (jf) mod T_i == 0. Frame j covers [jf, (j+1)*f).
• Per-frame load: load(j) = sum of C_i over the tasks releasing into frame j. A frame length f is capacity-feasible iff max over j of load(j) <= f.
• Verdicts: FITS when at least one admissible frame length is capacity-feasible, choosing the smallest such f; no-admissible-frame with reject_reason "frame-fit" when no divisor of g reaches max C_i, or "capacity" when admissible lengths exist but every candidate over-subscribes some frame.
• Units are one consistent integer time unit (ms in the worked examples) throughout; C and T are inputs, never estimated.

Workflow

1. Define the task set as {name, C, T} dicts, one integer time unit, implicit deadline D = T, no priorities and no required order.
2. Compute the hyperperiod H with hyperperiod (the lcm fold over the task periods) and the period gcd g with period_gcd.
3. Compute the necessary-condition utilization U with utilization.
4. Enumerate admissible frame lengths with admissible_frame_lengths, the ascending divisors of g that are at least max C_i (the frame-fit rule).
5. For each admissible frame length compute the per-frame loads with frame_loads and the worst frame with max_frame_load, then narrow to the capacity-feasible subset with feasible_frame_lengths.
6. Build the constructive frame table at the smallest feasible frame length with frame_table, reading each frame's jobs, load and slack.
7. Get the full verdict with cyclic_executive_report (hyperperiod, utilization, admissible and feasible frame lengths, verdict, reject reason and frame table), or the boolean shortcut with feasible.
8. Confirm the deterministic checks with the contract test scripts/test_cyclic_executive_scheduling.py.

Worked example

Task set A, three avionics fsw processes in ms, implicit deadlines D = T, no priorities: flight-control (C 3, T 25, a 40 Hz flight control law task), guidance (C 4, T 50, a 20 Hz guidance task), health-monitor (C 5, T 100, a 10 Hz health monitoring task).

• Set-level report: hyperperiod 100 (lcm of 25, 50, 100), period_gcd 25, max_execution_time 5, utilization 0.25. Admissible frame lengths (divisors of 25 at least 5): [5, 25]. Candidate f = 5 is rejected on capacity, max_frame_load(SET_A, 5) = 12 > 5, because frame 0 holds all three co-released jobs (3 + 4 + 5 = 12); candidate f = 25 is accepted, max_frame_load(SET_A, 25) = 12 <= 25. feasible_frame_lengths [25], verdict "FITS", frame_length 25 (the smallest capacity-feasible admissible f), frame_count 4 (100 / 25).
• Frame table at f = 25: frame_loads [12, 3, 7, 3], frame_slacks [13, 22, 18, 22]. Frame 0 [0,25) ms carries flight-control, guidance and health-monitor, load 12, slack 13 (the capacity-tight frame). Frame 1 [25,50) ms carries flight-control only, load 3, slack 22. Frame 2 [50,75) ms carries flight-control and guidance, load 7, slack
  18. Frame 3 [75,100) ms carries flight-control only, load 3, slack
  19. The table repeats every 100 ms.
• Identity anchors: sum of frame loads 25 = sum_i C_i * H / T_i = 34 + 42 + 5*1 = 25 = H * U = 100 * 0.25 = 25.0; 7 jobs per hyperperiod (4 + 2 + 1) placed as 3 + 1 + 2 + 1 across the 4 frames; sum of per-frame slacks 75 = 4 * 25 - 25.
• Task set B, the necessary-not-sufficient capacity path: flight- control C 8 T 25, guidance C 9 T 50, health-monitor C 10 T 100. utilization 0.6, admissible_frame_lengths [25], feasible_frame_lengths [], verdict "no-admissible-frame", reject_reason "capacity": U = 0.6 is at most 1, yet frame 0 must hold all three co-released jobs, 8 + 9 + 10 = 27 > 25, so no frame length fits.
• Task set C, the frame-fit rejection path: flight-control C 3 T 25, display C 8 T 40. period_gcd 5, max_execution_time 8, admissible_frame_lengths [], verdict "no-admissible-frame", reject_reason "frame-fit": every common frame length divides 5 and is at most 5 ms, below the display task's 8 ms execution time, even though the processor is only 32% loaded.
• Coprime identity: hyperperiod on T = (3, 4, 5) equals 60 = 345, period_gcd 1.

Verification

• Confirm cyclic_executive_report(SET_A) returns verdict "FITS", frame_length 25 and max_frame_load 12, with feasible(SET_A) True.
• Confirm hyperperiod on periods (3, 4, 5) equals 60 and period_gcd equals 1, the coprime identity.
• Confirm the total-load identity: sum of frame_loads(SET_A, 25) equals sum of C_i * (H // T_i) equals H * U within tolerance.
• Confirm feasible(SET_B) is False with reject_reason "capacity" even though utilization 0.6 is at most 1 (necessary, not sufficient).
• Confirm feasible(SET_C) is False with reject_reason "frame-fit" when no divisor of the period gcd reaches max C_i.
• Confirm every non-physical input raises ValueError: an empty task list, a non-dict entry, a missing C or T key, a boolean or non-integer C or T, a non-positive T, and a frame length that does not divide every task period.
• Run the contract test offline: python3 scripts/test_cyclic_executive_scheduling.py (31 tests, deterministic).

Related leaves

• avionics/fsw/real-time-scheduling: the priority-driven feasibility fence for the same (C, T) task model, the RM bound, exact response-time analysis and EDF full-utilization verdicts this leaf never computes.
• avionics/fsw/deadline-monotonic-scheduling: per-task relative deadlines and deadline-monotonic priority assignment beyond the implicit D = T model here.
• avionics/ima/ima-partitioning: the ARINC 653 major-frame partition window arithmetic one level above this leaf's task-level frame table.
• avionics/data-bus/mil-std-1553-bus-loading: minor-frame bus command and response window schedules, a different timing domain.

Pitfalls

• Treating a low utilization as proof of feasibility: set C loads the processor at only 32% yet has zero admissible frame lengths, because the frame-fit rule f >= max C_i can fail even when U is small; U <= 1 is necessary, never sufficient, for a FITS verdict.
• Assuming the largest admissible frame length is best: set A's larger admissible length 25 is the only capacity-feasible one, but in general a larger frame coarsens the schedule without guaranteeing capacity feasibility; always check feasible_frame_lengths, not just admissible_frame_lengths.
• Forgetting that frame 0 collects every task's synchronous release: every task releases a job at time 0, so frame 0 is often the capacity-tight frame (set A load 12 of 25, set B load 27 of 25), and a schedule can fail purely on this one frame even when later frames are lightly loaded.
• Reading a capacity rejection as a frame-fit rejection: set B rejects with reason "capacity" (an admissible f = 25 exists but every candidate over-subscribes a frame) while set C rejects with reason "frame-fit" (no divisor of the period gcd ever reaches max C_i); the two reject reasons point to different fixes, shrinking C_i for capacity versus raising g for frame-fit.
• Routing adjacent timing domains here: WCET estimation, priority-driven feasibility verdicts (real-time-scheduling), per-task relative deadlines and release jitter (deadline-monotonic-scheduling), ARINC 653 partition configuration tables and MAF window durations (ima-partitioning), and bus command or response windows (data-bus/mil-std-1553-bus-loading) are not this leaf's task-level frame table.

Behavior contract (gate 3)

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

python3 scripts/test_cyclic_executive_scheduling.py

The test covers the worked sets A, B and C, the coprime hyperperiod identity on periods (3, 4, 5), the frame-fit and capacity rejection paths, the total-load, jobs-per-hyperperiod and slack-sum identities over one hyperperiod, the necessary-not-sufficient utilization check, the single-task idle-frame boundary, admissible-length enumeration bounds, run-to-run determinism, and ValueError rejection of an empty list, a non-dict entry, a missing key, a boolean or non-integer C or T, a non-positive T, and a frame length that does not divide every task period.

Compliance

• Standards referenced, not reproduced: DO-178C (avionics software lifecycle context in which the scheduling analysis artifact is recorded) is listed reference-only per standards-map.yaml; the cyclic executive arithmetic above is public science (Baker and Shaw 1989, Locke 1992, Burns and Wellings 2009), summary-only.
• ARINC 653 is not in standards-map.yaml and is not needed here: the task-level frame-table arithmetic is independent of the partition standard text, mirroring the stance in real-time-scheduling.
• compliance: STANDARDS-REF, gated: false.