Aperiodic Server Scheduling

Aperiodic Server Scheduling (avionics/fsw/aperiodic-server-scheduling)

Use when an avionics flight software task set must also service aperiodic or event-driven jobs (fault and health events, command handling, mode-change requests) beside its periodic hard-real-time tasks, and the periodic-only model of the pack sibling cannot admit the event release at all. This leaf inserts a fixed-priority aperiodic server with capacity C_s and period T_s, in polling-server, deferrable-server or sporadic-server budget semantics, into the periodic (C, T) task set so the aperiodic jobs get a bounded worst-case service without breaking any periodic deadline. It reduces the event load to its load utilization, sizes the budget from that load with a burst margin, folds the budget into the fixed-priority response-time analysis exactly as a periodic task at its priority slot, and reports the insertion index with the augmented response times, the worst-case aperiodic response bounds and the no-feasible-slot verdict. Pure Python stdlib, closed form (math.ceil only), deterministic. Pairs with avionics/fsw/real-time-scheduling for the periodic-only feasibility verdicts of a task set with no aperiodic jobs and with avionics/fsw/shared-resource-access-control when shared resource blocking must be added to the fixed point.

Domain quick reference

• Event load: each aperiodic event stream is an (s, a) pair of worst-case execution s and minimum inter-arrival a in the same time unit as the periodic task set. Load utilization u_a = sum over streams of s_j / a_j; an empty stream list carries u_a = 0.
• Server sizing: U_s = u_a + margin, C_s = U_s * T_s, with u_a >= 0, margin >= 0 and u_a + margin in (0, 1]. The margin is explicit burst headroom, so the stability condition U_s >= u_a always holds (margin 0 allowed). Doubling T_s at fixed U_s doubles C_s and leaves U_s invariant.
• Budget as a periodic task: in the fixed-priority response-time analysis of the augmented set, task i below the server iterates R_i = C_i + sum over higher-priority periodic tasks j of ceil(R_i / T_j) * C_j + ceil(R_i / T_s) * C_s, and the server's own response iterates the same fixed point for a task of execution C_s and period T_s over the tasks above it. The iteration is monotone non-decreasing; an iterate that repeats within 1e-12 has converged, and an iterate that exceeds the task's own period, or the 100 pass cap (MAX_RTA_ITERATIONS), reports None. This budget-as-periodic-task insertion is the standard fixed-priority treatment of polling, deferrable and sporadic server budgets (Sprunt, Sha and Lehoczky, Aperiodic task scheduling for hard-real-time systems, The Journal of Real-Time Systems 1(1), 1989; the deferrable server mechanism from Lehoczky, Sha and Strosnider, RTSS 1987; public science, summary-only).
• Server mechanisms: polling capacity exists only at the poll instants k * T_s and is forfeited when a poll finds an empty queue; deferrable capacity is preserved through the period and replenished to C_s at each period start; sporadic replenishes a consumed budget T_s after the consumption started, so its budget is never forfeited on idleness.
• Aperiodic worst-case bound: a burst of total demand d (each job at most C_s) needs k = ceil(d / C_s) service windows, and the final unit of service completes at k * T_s + d - (k - 1) * C_s after the arrival. A single job of execution C_a <= C_s has the bound T_s + C_a. The bound arithmetic is identical for all three mechanisms; they differ only in which arrival phases attain it.
• Single-job phase response (empty queue, budget available): polling serves at phase 0.0 in C_a and otherwise waits for the next poll, R = (T_s - phase) + C_a, sup T_s + C_a approached as phase tends to 0 from above; deferrable and sporadic serve immediately at every phase, R = C_a (capacity preservation).
• Replenishment wait after a full-budget consumption [start, end]: polling and deferrable wait ceil(end / T_s) * T_s - end for the next poll or period start; sporadic waits T_s - (end - start), independent of where in the period the consumption sat. A consumption ending exactly on a boundary has polling and deferrable wait 0.
• The model is single-processor fixed-priority, one time unit per task set; WCETs are inputs, never estimated here.

Workflow

1. Establish the periodic baseline feasibility check: periodic_utilization over the (C, T) task set and the plain response times from server_response_times with the budget at the bottom slot.
2. Reduce the aperiodic load: aperiodic_utilization over the (s, a) event streams gives u_a.
3. Size the server budget: server_parameters(u_a, T_s, margin) returns the period, the capacity C_s = U_s * T_s and the utilization U_s.
4. Insert the budget into the response-time analysis: server_response_times at each candidate priority slot above_index reports the server response, the task responses (None per diverged task), the feasibility verdict and the total utilization.
5. Place the server: place_server scans the n + 1 priority slots from the highest and returns the first feasible insertion index, or raises the no-feasible-slot verdict when no placement works.
6. Bound the aperiodic worst-case response: aperiodic_response_bound gives the burst bound of the final unit of service.
7. Compare the mechanisms: polling_server_response against deferrable_server_response and sporadic_server_response over the arrival phases shows the forfeit-versus-preservation trade.
8. Compute the capacity-loss wait: replenishment_wait for the polling, deferrable and sporadic kinds after a full-budget consumption.
9. Confirm with the deterministic contract test run under both interpreters (see Contract test).

Worked example

Periodic task set A = [(1, 5), (2, 10), (3, 25)] ms in rate-monotonic order (task 0 highest priority, implicit deadlines 5, 10, 25 ms). The aperiodic load has two event streams, E1 (s 1.0 ms, a 20 ms: fault and health-event processing) and E2 (s 2.0 ms, a 40 ms: command handling), times in ms. Server period T_s = 25 ms, burst margin 0.02. Real module outputs:

• Periodic baseline: periodic_utilization(A) = 0.52 (1/5 + 2/10 + 3/25); the plain response times are [1.0, 3.0, 7.0] ms, every task inside its period.
• Aperiodic load and sizing: aperiodic_utilization([(1, 20), (2, 40)]) = 0.1 (0.05 + 0.05), so the event load demands 10% of the processor; server_parameters(0.1, 25, 0.02) returns period 25.0, capacity 3.000000 ms and utilization 0.120000: the budget C_s = 3 ms every 25 ms covers the 0.10 load with 0.02 of headroom. The same margin at T_s = 50 gives capacity 6.000000 at the same utilization 0.120000, and the capacity/period round trip is 0.120000.
• Worst-case aperiodic response bounds (T_s 25, C_s 3, job 2 ms): a single 2 ms job has the bound 27.000000 ms (T_s + C_a) at the worst arrival phase; a burst of demand 3, 6, 9 ms has the bounds 28.000000, 53.000000, 78.000000 ms, each extra full budget of backlog adding one 25 ms period; the 8 ms event burst from a storm of events has the bound 77.000000 ms; halving the server period to 10 ms cuts the single-job bound to 12.000000 ms.
• Phase responses of a 2 ms job (queue empty, budget available): polling (25, 3, 2, phase 0.0) = 2.000000, phase 12.5 = 14.500000, phase 24.0 = 3.000000: the polling server forfeits the budget at an empty poll, so an arrival just after the poll instant waits almost a full period while an arrival near the next poll is served quickly. deferrable and sporadic return 2.000000 at every one of those phases: the preserved budget serves the same mid-period arrival immediately, 14.5 ms sooner than polling. The polling worst case is the sup 27.0 ms approached as the phase tends to 0 from above.
• Replenishment waits after a full-budget consumption (T_s 25): consumption [0.0, 3.0]: polling 22.000000, deferrable 22.000000, sporadic 22.000000 (aligned to a period start, all three wait one period minus the 3 ms of service); consumption [17.0, 20.0]: polling 5.000000 and deferrable 5.000000 (next poll and period start at 25) against sporadic 22.000000 (replenishment at 17 + 25 = 42); consumption [22.0, 25.0]: polling 0.000000 and deferrable 0.000000 (ends exactly on the boundary) against sporadic 22.000000.
• Server placement on set A with the (C_s 3, T_s 25) budget: every slot is feasible; the slot scan shows the structure: above_index 0: server R_s = 3.000000, tasks [4.000000, 7.000000, 10.000000]; above_index 1: R_s = 4.000000, tasks [1.000000, 7.000000, 10.000000]; above_index 2: R_s = 7.000000, tasks [1.000000, 3.000000, 10.000000]; above_index 3: R_s = 10.000000, tasks [1.000000, 3.000000, 7.000000]. place_server(A) returns insertion_index 0, server_response_time 3.000000, tasks [4.000000, 7.000000, 10.000000], total_utilization 0.64, feasible True: the light event load (0.10) fits a 3 ms budget at the TOP of the priority order, and the periodic tasks still close at 4, 7 and 10 ms against their 5, 10 and 25 ms deadlines.
• Heavy event load, set B: add stream E3 (s 3.0 ms, a 12.5 ms: telemetry downlink request handling), so aperiodic_utilization = 0.340000 and server_parameters(0.34, 25, 0.06) gives capacity 10.000000 at utilization 0.400000. Slots 0 and 1 are infeasible (None entries: the 10 ms budget preempting the 5 ms or 10 ms task blows its deadline); place_server(B) returns insertion_index 2, server_response_time 18.000000, tasks [1.000000, 3.000000, 24.000000], total_utilization 0.92, feasible True. Push the load to u_a + margin 0.9 (capacity 22.5 ms) and place_server raises ValueError: "no feasible insertion point for the server in the 4 priority slots", the no-feasible-slot verdict.
• Read-off: a 10% event load rides free at the top of the priority order (set A, insertion index 0) with a 3 ms budget and worst-case single-job bound 27 ms; a 34% event load forces a 10 ms budget below the two fast tasks (insertion index 2) with worst case 77 ms for an 8 ms backlog storm, and the periodic set still closes at 1, 3 and 24 ms.

Verification

• periodic_utilization([(1, 5), (2, 10), (3, 25)]) = 0.52; an empty task list, zero or boolean C or T and malformed entries raise.
• aperiodic_utilization of streams A = 0.1, of an empty list exactly 0.0; doubling every execution s doubles the load; non-positive s or a raises.
• server_parameters(0.1, 25, 0.02): capacity 3.0, utilization 0.12, period 25.0, and capacity equals utilization times period; the T_s = 50 sizing doubles the capacity at the same utilization; negative margin, zero period, utilization above 1 and zero capacity raise.
• The three response functions return C_a at phase 0.0, polling alone is phase dependent ((T_s - phase) + C_a), deferrable and sporadic are phase independent; T_s 0, C_a 0, C_a above C_s, negative phase and phase at T_s raise in every response function.
• aperiodic_response_bound(25, 3, 2.0) = 27.0 (T_s + C_a); the demand ladder 3, 6, 9 gives 28.0, 53.0, 78.0 with each step one period of 25.0; the bound is monotone in demand and in T_s; non-positive demand, capacity or period raise.
• replenishment_wait returns 22.0 for all three kinds on [0, 3]; polling and deferrable 5.0 against sporadic 22.0 on [17, 20]; polling and deferrable 0.0 against sporadic 22.0 on [22, 25]; bad kind, negative start, end equal to start and a consumption longer than T_s raise.
• server_response_times accepts above_index in [0, len(tasks)] inclusive (the bottom slot reproduces the plain periodic responses; out-of-range indices, an empty task list and a capacity above the period raise). A diverged task or server reports None and the slot is infeasible.
• place_server returns the highest feasible slot (insertion_index 0 on set A, 2 on set B) and raises the no-feasible-slot verdict naming the priority slots when every slot fails.
• The module is deterministic (identical outputs run to run), imports nothing beyond math, and MAX_RTA_ITERATIONS is fixed at 100.
• Run the contract test offline: python3 scripts/test_aperiodic_server_scheduling.py (37 tests, exits 0; also green under ~/.pyenv/versions/3.13.12/bin/python3).

Related leaves

• avionics/fsw/real-time-scheduling: the periodic-only utilization, bound and response-time feasibility verdicts of a task set with no aperiodic jobs; the set augmented here must be checked there or here for its periodic baseline.
• 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.
• avionics/fsw/cfs-architecture and avionics/fsw/fprime-component: the software bus routing and cyclic rate-group dispatch layouts that these event servers sit beside.
• avionics/ima/ima-partitioning: the partition window schedule one level above process-level server budgets.
• avionics/data-bus/mil-std-1553: bus command/response windows, a bus term rather than a task or server response.

Pitfalls

• Treating the load utilization as the server utilization: U_s = u_a + margin, and the margin is the burst headroom that keeps U_s >= u_a stable; a zero margin server sized exactly at the stream average has no slack for bursty event arrivals.
• Placing the server by responsiveness alone: the top slot gives the best aperiodic response (set A) but a large budget at the top blows the fast task deadlines (set B slots 0 and 1 return None entries); the placement scan, not intuition, decides the insertion index.
• Quoting the phase-0 response as the polling worst case: an arrival just after an empty poll pays nearly a full period; the polling worst case is the sup T_s + C_a approached as the phase tends to 0 from above, attained by no single phase.
• Comparing mechanisms at one phase: polling is phase dependent (14.5 ms mid-period in the example) while deferrable and sporadic serve in C_a at every phase with an unspent budget; the difference is the forfeit-on-empty-poll semantics, not a speed difference in service.
• Sizing the bound from a single job: a burst of total demand d pays k * T_s + d - (k - 1) * C_s (77 ms for an 8 ms storm), far above the single-job bound T_s + C_a; bound the burst, not the average job.
• Forgetting that sporadic replenishment is start anchored: the sporadic wait after a consumption is T_s minus the consumption length wherever the consumption sat in the period, while polling and deferrable wait for the next boundary instant.

Behavior contract (gate 3)

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

python3 scripts/test_aperiodic_server_scheduling.py

The test covers the periodic baseline utilization and plain response times, the aperiodic load reduction and its doubling identity, the server budget sizing with the capacity/period round trip and the doubled-period identity, all three single-job phase responses with their ValueErrors, the aperiodic worst-case response bound ladder and monotonicity, the replenishment waits of all three kinds with the boundary cases, the response-time analysis with the inserted budget across the slot scan (None entries for diverged tasks), the placement verdicts on sets A and B, the no-feasible-slot raise, and module discipline (determinism, math-only imports, MAX_RTA_ITERATIONS 100). 37 tests, offline and deterministic, exits 0.

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 server mathematics above is public science (Sprunt, Sha and Lehoczky 1989; Lehoczky, Sha and Strosnider 1987), summary-only per standards-map.yaml. No standard text is reproduced verbatim.
• compliance: STANDARDS-REF, gated: false.