Scheduling Without a Scheduler: Superloops and Their Latency Budget

A bare-metal program with no scheduler is usually structured as an infinite loop that calls a sequence of functions, with interrupt handlers doing the work that cannot wait for the loop to come around. The structure is called a cyclic executive, and its attraction is not simplicity for its own sake: it makes the worst-case response time of every activity a computable sum rather than an argument about a scheduler’s decisions. It also stops working in a way that is easy to predict in advance, which is worth knowing before the firmware is built around it.

What the structure guarantees

The loop runs each task in a fixed order, and each task runs to completion. Tasks do not pre-empt each other, so no task can be interrupted in the middle of an update by another task; the only concurrency is between the loop and the handlers, which is the case covered by critical sections without an operating system. There is no context to switch, no per-task stack to size, and no scheduler state to corrupt. The loop is a single execution context with a known stack depth.

The response time of an event follows from that structure. An interrupt handler runs as soon as its priority allows, which depends on the longest interval the program spends with exceptions masked. A task that responds to an event the handler recorded waits for the remainder of the task currently running, plus every task ahead of it in the loop order, which is at most the sum of all task execution times once the loop has been traversed from the worst starting point. The bound is therefore the sum of the task times plus the worst-case masked interval plus the longest handler, and it can be computed by measuring or estimating each term independently.

Ordering matters more than it does in a pre-emptive system. Placing the shortest-deadline tasks first and the long-running background work last reduces the average wait for the tasks that need it, and the worst case remains the sum. A task whose execution time varies with input makes the sum a maximum over inputs rather than a constant, which is why a loop performing work proportional to a received message length has a worst case set by the largest message the protocol allows.

Converting blocking work into bounded steps

The common reason a cyclic executive fails its bound is not the number of tasks; it is one task whose execution time is not bounded. A task that waits for a peripheral to finish — a conversion, a byte shifted out of a serial port, a flash write — spends the loop’s time doing nothing, and the whole system waits with it.

The fix is to turn waiting into state. The task records what it was doing, returns, and is re-entered on the next iteration to check whether the hardware has finished. Its execution time then becomes a maximum over the states rather than the duration of the slowest operation, and the loop’s total becomes a sum of small numbers.

/* A blocking wait replaced by a state machine: each call performs bounded work,
   so the loop period does not depend on how long the peripheral takes. */
typedef struct { volatile uint32_t CR, SR, DR; } adc_regs_t;
#define ADC0 ((adc_regs_t *)0x40012000u)

static enum { IDLE, CONVERTING } state = IDLE;
volatile uint32_t sample;
volatile uint32_t tick;            /* incremented by the periodic timer handler */
void init(void);

void task_conversion(void)
{
    switch (state) {
    case IDLE:
        ADC0->CR = 1u;             /* start a conversion, no waiting */
        state = CONVERTING;
        break;
    case CONVERTING:
        if (ADC0->SR & 1u) {       /* completion flag set by the hardware */
            sample = ADC0->DR;
            state = IDLE;
        }
        break;
    }
}

int main(void)
{
    init();
    uint32_t seen = tick;
    for (;;) {
        if (tick != seen) {        /* paced by the timer, not by elapsed work */
            seen = tick;
            task_conversion();     /* the rest of the loop's tasks follow */
        }
    }
}

The loop above is paced by a counter the timer handler increments, which is a deliberate choice with a consequence: if the loop’s total execution time ever exceeds the interval between ticks, the comparison sees a tick that has already passed and the loop runs again immediately. That behaviour keeps the system responsive under a transient overload, but it also hides the overload, because the loop silently runs faster than its nominal period. Counting missed ticks and reporting the count makes the overload visible.

Where jitter and drift come from

Jitter in a free-running loop comes from the variance in task execution times. A conditional branch inside a task that takes different paths for different inputs shifts the start of every later task by the difference, and the effect accumulates around the loop. Pacing the loop on a periodic tick removes the accumulation for everything after the first task but does not remove the within-period variance. The residual jitter is the spread in execution time of the tasks between the tick and the task in question, which is the quantity that matters for activities that must be periodic rather than merely bounded.

Drift comes from the timebase. A loop paced by a crystal-referenced timer inherits the crystal’s accuracy, which is specified in parts per million and is a few tens of ppm for common crystals at room temperature. A loop paced by the internal RC oscillator inherits its accuracy, which is specified in percent and moves with temperature and supply voltage. Both numbers are datasheet properties of the part, and the difference between them is roughly two to three orders of magnitude in frequency error, which turns into minutes of accumulated error per day for the RC case and a few seconds for the crystal case. A design that timestamps events or holds a calendar clock has to start from that difference.

Measuring the terms that matter

The terms in the bound are obtainable from the hardware rather than from estimation, since every part with a timer can measure its own program. A free-running counter read at the loop boundary gives the loop period; reads taken before and after each task give the per-task execution times for the input at hand. The instrumentation costs a counter read at each boundary, which is a handful of cycles, and it perturbs the very quantity being measured by that amount, so the numbers are upper bounds on the tasks and exact for the loop.

Two details decide whether the measurement is usable. A counter narrow enough to wrap during the measured interval requires the difference to be computed modulo the counter’s width, and an interval that spans several wraps is unrecoverable; a 16-bit counter clocked at a megahertz wraps roughly every 65 ms, which is shorter than the period of a slow background loop and longer than any individual task. And the counter’s clock must be the same clock the rest of the timing reasoning assumes, which is the reason the startup sequence recomputes any software delay constant after the system clock changes: a counter configured before that point measures a different unit.

Worst-case execution time is not the same as the observed maximum, which is why the measurement is a starting point rather than the bound. A task whose duration depends on the data it processes has a worst case at the input that maximises a loop count, and the honest way to reduce the bound is to change the task so that its worst input is bounded by construction.

When the loop stops being the right structure

Three symptoms indicate that a cyclic executive has been pushed past its structure. The first is a loop whose total execution time is close to its period, so any added work causes missed ticks; the bound has become the design constraint rather than a property of it. The second is a growing set of flags and ordering rules between the tasks — the tasks have become a scheduler, with the ordering constraints of a scheduler and none of its accounting. The third is an activity whose deadline is shorter than the loop’s traversal time, which no amount of reordering fixes, because the work simply cannot be reached in time from the worst starting point. That activity becomes an interrupt handler, and the set of things done in interrupts grows until the handler’s own execution time is a term in the latency budget of everything else.

The transition away from the cyclic executive is not necessarily to a kernel. A two-level structure — a short fixed-rate loop for the time-critical tasks, and a slower background loop for the rest — is a common and workable extension, and it preserves the computability of the bound as the sum of the tasks in the fastest loop. What it gives up is the property that any task can run at any point in the loop; the tasks now have a period, and their periods are chosen by the loop structure rather than derived from their deadlines.

Where the structure is retained, the accounting is the work. A loop’s period, the execution time of each task on its worst input, the longest interval with interrupts masked, and the longest interrupt handler are four numbers, and their sum is the worst-case response time of everything that the loop does. Systems that fail tend to fail because nobody computed the third and fourth terms: a critical section added inside a driver, or a handler that grew a loop, can each exceed the sum of the visible tasks. The mechanisms that keep those two terms measurable are the same ones discussed in interrupt entry and exit mechanics, since every cycle spent inside a handler is a cycle during which the loop makes no progress.