Cyclic executives and time-triggered design

The oldest and still one of the most trusted ways to build a hard real-time system is to decide, before the system ever runs, exactly what it will do at every instant. A cyclic executive is a table-driven scheduler: an offline tool, or an engineer with a spreadsheet, lays out the jobs of every task over one hyperperiod, and at run time a tiny loop driven by a timer interrupt simply works through the table. There are no priorities, no ready queue and no run-time scheduling decisions to analyze. Flight control computers, engine controllers and railway interlocking systems have used cyclic executives for decades, and time-triggered architectures extend the same idea to whole distributed systems. This lesson shows how to build a cyclic schedule, how to choose its frame size, what to do when a task does not fit, and why the approach is both very predictable and hard to maintain.

On the NS-5, the cyclic approach appears in a small but important place. Alongside the main processor sits a supervisor microcontroller that monitors the supply rails, checks that the radar front end is healthy and reports both to the main processor. Ines Carvalho insisted that this supervisor be as simple and predictable as possible, with no kernel at all, and asked Jonah to design its schedule.

Major cycles, minor frames and the clock

A cyclic executive repeats a major cycle, normally equal to the hyperperiod H of the task set. The major cycle is divided into equal minor frames of length f. A periodic timer interrupt fires at the start of each frame; the executive runs the jobs listed for that frame, in order, to completion, and then waits for the next interrupt. Because the decisions were made offline, the run-time code is a few lines long and its worst-case behaviour is obvious from the table.

/* Cyclic executive for the NS-5 supervisor: 10 frames of 2 ms, a 20 ms major cycle */
typedef void (*job_fn)(void);

static void supply(void);      /* rail voltages and currents, 1 ms worst case */
static void radhlth(void);     /* radar front-end health check, 2 ms worst case */
static void report(void);      /* status frame to the main processor, 2 ms worst case */

static job_fn const table[10][2] = {
    { supply,  0 }, { radhlth, 0 }, { supply, 0 }, { radhlth, 0 }, { supply, 0 },
    { radhlth, 0 }, { supply,  0 }, { report,  0 }, { radhlth, 0 }, { supply, 0 },
};

static volatile uint8_t frame_tick;     /* set by the 2 ms timer interrupt */

void frame_timer_isr(void) { frame_tick = 1; }

int main(void)
{
    uint8_t frame = 0;
    hw_init();
    start_frame_timer_2ms();
    for (;;) {
        while (!frame_tick) wait_for_interrupt();
        frame_tick = 0;
        if (frame_overrun_detected()) record_overrun(frame);   /* previous frame ran long */
        for (int j = 0; j < 2 && table[frame][j]; j++)
            table[frame][j]();
        frame = (uint8_t)((frame + 1) % 10);
    }
}

The frame overrun check matters. If a job runs longer than expected, the next timer interrupt arrives before the executive is waiting for it. A safe design detects this, for example by checking whether the timer flag was already set when the frame's jobs finished, and records or acts on it, because an overrun means the offline analysis has been violated. Cyclic executives usually treat an overrun as a fault: the supervisor logs it, and repeated overruns trigger a reset through the watchdog.

Choosing the frame size

The frame size f is not free. Baker and Shaw formalized three conditions in 1989 that a frame size must satisfy for a set of periodic tasks with periods T_i, execution times C_i and deadlines D_i. First, every job must fit in a single frame so that it never needs to be preempted:

Second, the frame size should divide the hyperperiod, so that the major cycle contains a whole number of frames and the table repeats cleanly. Third, between the release of any job and its deadline there must be at least one whole frame. The worst case occurs when a job is released just after a frame starts; the job cannot run until the following frame, and that frame must end by its deadline. The condition that guarantees this is:

The gcd term accounts for the fact that if f and T_i share factors, releases line up with frame boundaries more often than in the worst general case. The first condition pushes f up and the third pushes it down, so it is common for only one or two frame sizes to satisfy all three, and for some task sets none does.

The supervisor has three tasks: SUPPLY with C = 1 ms and T = D = 4 ms, RADHLTH with C = 2 ms and T = D = 5 ms, and REPORT with C = 2 ms and T = D = 20 ms. Their utilization is 0.25 + 0.40 + 0.10 = 0.75 and their hyperperiod is 20 ms. The code below checks every divisor of the hyperperiod against the three conditions and then builds a table by placing each job, in deadline order, in the earliest frame that starts at or after its release, ends by its deadline and has room.

from math import gcd
from functools import reduce

tasks = [("SUPPLY", 1, 4, 4), ("RADHLTH", 2, 5, 5), ("REPORT", 2, 20, 20)]  # name, C, T, D in ms

def lcm(a, b):
    return a * b // gcd(a, b)

H = reduce(lcm, [t for _, _, t, _ in tasks])
cmax = max(c for _, c, _, _ in tasks)
print(f"hyperperiod H = {H} ms, largest C = {cmax} ms")
print(" f  divides H  f >= Cmax  2f - gcd(f,T) <= D for all")
good = []
for f in range(1, H + 1):
    if H % f:
        continue
    c1 = f >= cmax
    c3 = all(2 * f - gcd(f, t) <= d for _, _, t, d in tasks)
    print(f"{f:2d}  yes        {'yes' if c1 else 'no ':3s}        {'yes' if c3 else 'no'}")
    if c1 and c3:
        good.append(f)
f = good[0]
print("chosen frame size", f, "ms")

# place each job, in deadline order, in the earliest frame that fits its window
jobs = []
for name, c, t, d in tasks:
    for k in range(H // t):
        jobs.append((k * t + d, k * t, name, c))
jobs.sort()
frames = [[] for _ in range(H // f)]
slack = [f] * (H // f)
for dl, rel, name, c in jobs:
    for i in range(H // f):
        start, end = i * f, (i + 1) * f
        if start >= rel and end <= dl and slack[i] >= c:
            frames[i].append(name)
            slack[i] -= c
            break
    else:
        print("no frame for", name, "released at", rel)
for i, fr in enumerate(frames):
    print(f"frame {i} [{i*f:2d},{(i+1)*f:2d}) ms: {', '.join(fr) or 'idle':18s} slack {slack[i]} ms")

hyperperiod H = 20 ms, largest C = 2 ms
 f  divides H  f >= Cmax  2f - gcd(f,T) <= D for all
 1  yes        no         yes
 2  yes        yes        yes
 4  yes        yes        no
 5  yes        yes        no
10  yes        yes        no
20  yes        yes        no
chosen frame size 2 ms
frame 0 [ 0, 2) ms: SUPPLY             slack 1 ms
frame 1 [ 2, 4) ms: RADHLTH            slack 0 ms
frame 2 [ 4, 6) ms: SUPPLY             slack 1 ms
frame 3 [ 6, 8) ms: RADHLTH            slack 0 ms
frame 4 [ 8,10) ms: SUPPLY             slack 1 ms
frame 5 [10,12) ms: RADHLTH            slack 0 ms
frame 6 [12,14) ms: SUPPLY             slack 1 ms
frame 7 [14,16) ms: REPORT             slack 0 ms
frame 8 [16,18) ms: RADHLTH            slack 0 ms
frame 9 [18,20) ms: SUPPLY             slack 1 ms

Only f = 2 ms satisfies all three conditions. A 1 ms frame is too short for the 2 ms jobs, and a 4 ms frame fails the third condition for RADHLTH: 2 × 4 − gcd(4, 5) = 7 ms, which exceeds its 5 ms deadline. With 2 ms frames, the greedy placement finds a slot for all 11 jobs of the hyperperiod: five SUPPLY jobs, four RADHLTH jobs and one REPORT job, using 15 ms of the 20 ms major cycle. The slack of 1 ms in each SUPPLY frame is spare capacity that can later absorb a small new job without disturbing the rest of the table.

The greedy placement worked here, but in general assigning jobs to frames is a bin-packing problem and is NP-hard. Practical tools formulate it as a network-flow problem when jobs are not split, as Baker and Shaw did, or as an integer program or constraint-satisfaction problem when there are precedence constraints, communication slots and multiple processors. For a supervisor with three tasks a spreadsheet suffices; for an avionics computer with hundreds of tasks the table is generated by a tool and checked independently.

When a job does not fit

Suppose a later version of the supervisor adds a self-test task with C = 5 ms and T = D = 20 ms. Now the first condition needs f ≥ 5 ms, but any f of 4 ms or more breaks the third condition for SUPPLY and RADHLTH. No frame size works. The standard remedy is job slicing: split the long job into pieces, each of which fits a frame, such as five slices of 1 ms or a 2 ms and a 3 ms slice. The task's code must then be restructured so that each slice ends at a consistent state, with its intermediate results kept in static variables until the next slice continues. Slicing is a manual form of preemption, decided at design time at points the designer chooses.

Slicing is effective but it is where cyclic executives start to hurt. The code no longer reflects the logical structure of the task, and each change to execution times can force a new set of slices. A related pain is that periods must fit the frame structure: if the supervisor needed a 3 ms task, the hyperperiod would grow to 60 ms and the whole table would have to be rebuilt. Designers often adjust periods to be harmonic, running a 3 ms activity every 2 ms, for example, using extra capacity to keep the structure simple.

Strengths and weaknesses

The strengths of a cyclic executive are considerable. The schedule is fully determined, so the worst-case response time of every job is read directly off the table, and tests run on the target exercise exactly the interleavings that will occur in service. Jitter is bounded by the frame size. There is no need for locks or semaphores between tasks, because jobs run to completion in a fixed order; a job that reads data written by another simply needs to be placed after it in the table. Overheads are tiny and constant: one interrupt per frame and a table lookup. This determinism is why certification authorities are comfortable with cyclic executives and why they remain common in the most critical systems.

The weaknesses are equally clear. Sporadic and aperiodic work fits poorly: an event that arrives just after its frame must wait up to a whole major cycle, or capacity must be reserved for it in every frame. Changes are expensive, because adding a task or changing a period may require a new table and new slices. Utilization is often wasted to keep periods harmonic and frames tidy. Long jobs must be sliced by hand. And the table hides the design intent: the knowledge of why a job is in frame 7 lives in the head of the engineer who built the table.

Time-triggered architectures

Time-triggered architectures extend the cyclic idea from one processor to a whole distributed system. Every node shares a synchronized global time base with bounded precision, and both computation and communication follow a common schedule: node A computes in a known window, sends its message in a reserved slot on the bus, and node B reads it in its own known window. Kopetz and colleagues developed the Time-Triggered Architecture and the Time-Triggered Protocol in the 1990s, and the same principles appear in FlexRay for automobiles, in time-triggered Ethernet in aircraft and spacecraft, and in the scheduled traffic of time-sensitive networking covered in lesson 11. The appeal is composability: each node can be tested against its schedule in isolation, and when nodes are integrated their timing does not change.

Time-triggered systems need fault containment as well as timing. A node that transmits outside its slot, called a babbling idiot, could block the bus for everyone; time-triggered networks therefore use bus guardians that only let a node transmit during its own slot. They also need clock synchronization that tolerates faulty clocks, which is why synchronization algorithms in these systems take the fault-tolerant average of several clocks rather than following a single master.

Choosing between cyclic and priority-driven designs

Most new systems use a priority-driven real-time operating system, covered from lesson 4 onward, because it handles sporadic events naturally and is far easier to change. Cyclic executives remain the right choice for small, highly critical subsystems with few, stable, mostly periodic tasks, where determinism and ease of certification outweigh flexibility. The NS-5 shows a common compromise: a cyclic supervisor that must be beyond doubt, and a priority-driven main processor that must adapt to traffic, firmware updates and new features over its life. Even on the main processor, time-triggered ideas appear: the radar task is released by the radar's own frame clock, and tasks exchange data through buffers written and read at known points in their periods.