Real-time operating system architecture

The scheduling theory of the previous lessons assumes a machine that switches instantly to the highest-priority ready task, releases periodic tasks exactly on time and charges nothing for doing so. A real-time operating system (RTOS) is the software that makes this assumption nearly true. It provides tasks, a priority scheduler, timers, interrupt management and communication primitives, and it does so with services whose worst-case execution time is bounded and documented. An RTOS for a microcontroller is usually a small kernel, a few thousand to a few tens of thousands of lines, linked directly with the application into one image. CMP-320 Operating Systems, cross-listed as CMPUT-379, covers processes, threads, context switching and scheduling in general-purpose systems; this lesson assumes those basics and concentrates on what changes when every service must have a bounded worst case. It looks inside such a kernel: how it represents tasks, how it chooses and switches between them, how it handles time and interrupts, and how its own overheads are folded back into the response-time analysis of lesson 4.

The NS-5 uses a small preemptive kernel supplied in source form with the RISC-V microcontroller's development kit. Before relying on it, Jonah reads its scheduler, measures its overheads on the board and writes them into the task table, because a timing analysis that ignores the kernel is an analysis of a machine that does not exist.

Tasks, stacks and task control blocks

A kernel task is an independent thread of execution with its own stack and its own saved processor state. The kernel describes each task with a task control block (TCB), a structure holding the saved stack pointer, the task's priority, its state and the links that place it in the kernel's queues. When a task is not running, all of its registers are saved on its own stack, and the TCB records where. Switching tasks means saving the running task's registers on its stack, storing its stack pointer in its TCB, choosing the next task, loading that task's stack pointer and restoring its registers.

#include <stdint.h>

typedef enum { TASK_READY, TASK_RUNNING, TASK_BLOCKED, TASK_SUSPENDED } task_state_t;

typedef struct tcb {
    uint32_t     *sp;            /* saved stack pointer: must be the first member     */
    uint8_t       prio;          /* 0 = highest; fixed unless raised by inheritance   */
    uint8_t       base_prio;     /* assigned priority, restored when a lock is freed  */
    task_state_t  state;
    uint32_t      wake_tick;     /* absolute tick at which a delayed task is released */
    struct tcb   *next;          /* link in a ready list or a wait list               */
    void         *waiting_on;    /* the mutex, semaphore or queue that blocks it      */
} tcb_t;

/* every stack and TCB is allocated statically: no heap in the kernel */
static uint32_t radar_stack[256];
static tcb_t    radar_tcb;

Real-time kernels almost always allocate tasks, stacks and kernel objects statically, at compile time or once at startup. General-purpose heaps have allocation times that depend on fragmentation, and they can fail at run time, two properties a hard real-time system cannot accept. Stack sizes are set from a worst-case stack analysis, either by a tool that walks the call graph or by filling each stack with a known pattern, exercising the task and measuring the high-water mark, with a generous margin added either way.

Task states

Every task is in one of a small number of states. A running task is executing on the processor. A ready task could run but a higher-priority task is running. A blocked task is waiting for something: a delay to expire, a semaphore to be given, a message to arrive. A suspended task has been taken out of scheduling altogether by an explicit call. Transitions between states happen only through kernel calls and interrupts, and each transition is a point where the scheduler may have to choose a new running task.

Constant-time scheduling

The scheduler must find the highest-priority ready task quickly and in bounded time, however many tasks exist. The usual structure is an array of ready lists, one per priority level, plus a bitmap with one bit per level, set when the corresponding list is non-empty. Finding the highest ready priority is then a single count-leading-zeros or find-first-set instruction on the bitmap, and the chosen task is the head of that list. Insertion and removal are constant-time list operations. With 32 priority levels the bitmap is one word; with 256 levels a two-level bitmap keeps the operation to two instructions. The scheduler's worst-case cost is therefore fixed and small, which is what makes it analyzable.

static uint32_t ready_bitmap;            /* bit p set when ready_list[p] is non-empty */
static tcb_t   *ready_list[32];

static inline uint8_t highest_ready(void)
{
    /* priority 0 is the highest and maps to bit 31 */
    return (uint8_t)__builtin_clz(ready_bitmap);
}

static void make_ready(tcb_t *t)
{
    uint8_t p = t->prio;
    t->state = TASK_READY;
    t->next = ready_list[p];             /* simplified: real kernels keep FIFO order */
    ready_list[p] = t;
    ready_bitmap |= 1u << (31 - p);
    if (p < current->prio)
        request_context_switch();        /* pend a software interrupt */
}

Tasks at the same priority are normally scheduled first in, first out, with an optional round-robin time slice. Real-time analysis usually gives every task its own priority level, so that the ordering is fully defined and response-time analysis applies directly.

The context switch

On the NS-5's RISC-V core, a context switch is triggered by a software interrupt that the kernel pends whenever a scheduling decision might change the running task. The handler saves the general-purpose registers of the interrupted task on its stack, together with the machine exception program counter (mepc) that records where it was interrupted and, if the task uses the floating-point unit, the floating-point registers. It stores the stack pointer in the current TCB, calls the scheduler to select the next task, loads that task's stack pointer and restores its registers, finally executing mret to resume it. Jonah measures the full switch at 5 µs, about 240 cycles at 48 MHz, using the core's cycle counter and a logic analyzer on a GPIO toggled at the start and end of the handler.

Context-switch time is not the only cost of preemption. A preempted task returns to a cache and branch predictor disturbed by the preempting task, and must reload what it lost. This cache-related preemption delay can be larger than the switch itself on processors with large caches. The NS-5 avoids most of it by placing the radar and classification code in tightly coupled memory, which has no cache. Lesson 10 returns to the problem.

Time: ticks, timers and periodic release

Most kernels keep time with a periodic tick interrupt, typically every 1 ms, which advances a counter, releases any tasks whose delay has expired and may trigger a context switch. Ticks are simple but cost processor time and energy even when nothing is due, and they limit timing resolution to one tick. Tickless kernels instead program a hardware timer for the next pending expiry and let the processor sleep until then; CMP-315 used this to save battery power on the NS-4. Many kernels support both modes.

Periodic tasks must be released on a fixed time line. A task that calls 'delay for 10 ms' at the end of each job releases its next job 10 ms after the previous one finished, so any variation in its execution and preemption accumulates into drift. The correct primitive is an absolute delay, often called delay-until, which waits until a stored release time and then advances that time by exactly one period.

void cantx_task(void *arg)
{
    uint32_t next = kernel_ticks();           /* first release: now */
    for (;;) {
        send_status_frames();
        service_tx_queue();
        next += 10;                           /* exactly one period of 10 ticks */
        delay_until(next);                    /* not delay(10): that would drift */
    }
}

The simulation below runs 1,000 jobs of a 10 ms task whose execution and scheduling delay vary randomly within realistic bounds, once with a relative delay and once with an absolute delay, and reports how far the last job has drifted from its nominal release time.

import random
random.seed(5)

PERIOD = 10_000          # microseconds, a 10 ms task
N = 1_000                # releases to simulate

def run(absolute):
    now, next_release, starts = 0, 0, []
    for k in range(N):
        start = now + random.randint(0, 300)          # scheduling delay before the job runs
        starts.append(start)
        finish = start + random.randint(700, 900)     # the job's own execution
        if absolute:
            next_release += PERIOD                    # delay until a fixed time line
        else:
            next_release = finish + PERIOD            # delay for a period after finishing
        now = next_release
    drift = starts[-1] - (N - 1) * PERIOD
    return drift

print(f"relative delay: job {N} starts {run(False)/1000:8.1f} ms after its nominal time")
print(f"absolute delay: job {N} starts {run(True)/1000:8.1f} ms after its nominal time")

relative delay: job 1000 starts    946.6 ms after its nominal time
absolute delay: job 1000 starts      0.1 ms after its nominal time

With the relative delay, the 1,000th job starts almost a second late, because each period adds the job's own execution and its scheduling delay. With the absolute delay, the release time line is exact, and the 1,000th job starts within a fraction of a millisecond of its nominal time, the remaining offset being only its own scheduling delay. A task that drifts like the first case is no longer periodic, and the analysis that assumed a period of 10 ms no longer describes it.

Interrupts and deferred work

Interrupt handlers run above every task, whatever the task priorities. A long handler therefore delays every task in the system, and its execution must be counted as interference for all of them. Real-time designs keep handlers short: the handler acknowledges the device, captures the data, perhaps starts the next transfer, and signals a task through a semaphore or queue. The task, running at a priority chosen by rate-monotonic or deadline-monotonic reasoning, does the processing. This split, often called deferred interrupt handling, lets the designer choose the priority of the work instead of having it imposed by the hardware.

Kernels also disable interrupts, briefly, to protect their own data structures. The longest such section, together with the hardware interrupt entry time, determines the worst-case interrupt latency. A good RTOS documents this figure and keeps it to a few microseconds. Some kernels never disable interrupts above a configured priority, so that a few critical handlers that make no kernel calls have latency set only by the hardware.

Folding overheads into the analysis

Lesson 4's equation charged nothing for the kernel. A standard way to include it is to add twice the context-switch time to each task's execution time, once for the switch into the job and once for the switch out, and to model the tick and each interrupt handler as a high-priority task with its own period and execution time. Jonah's measurements on the NS-5 are: tick handler 8 µs every 1 ms, radar DMA completion handler 15 µs every 6.25 ms, CAN receive handler 6 µs with a minimum separation of 188 µs, the duration of the shortest possible CAN frame at 500 kbit/s, and a context switch of 5 µs. The code below repeats the analysis of the 11 ms classifier variant with and without these overheads.

from math import ceil

CS = 5          # context switch, microseconds, charged twice per job
# (name, C, T, D) in microseconds, highest priority first; ISRs and the tick run above all tasks
isrs = [("tick", 8, 1_000), ("radar DMA", 15, 6_250), ("CAN rx", 6, 188)]
tasks = [("RADAR", 1_200, 6_250, 6_250), ("CANTX", 800, 10_000, 10_000),
         ("CLASS", 11_000, 25_000, 25_000), ("LOG", 8_000, 100_000, 100_000),
         ("HOUSE", 20_000, 1_000_000, 1_000_000)]

def rta(tasks, isrs, cs):
    out = []
    for i, (name, c, t, d) in enumerate(tasks):
        ci = c + 2 * cs
        r = ci
        while True:
            nxt = ci + sum(ceil(r / tj) * cj for _, cj, tj in isrs)
            nxt += sum(ceil(r / tj) * (cj + 2 * cs) for _, cj, tj, _ in tasks[:i])
            if nxt == r or nxt > d:
                break
            r = nxt
        out.append((name, nxt, d))
    return out

u_isr = sum(c / t for _, c, t in isrs)
print(f"interrupt and tick load: {100*u_isr:.1f} % of the processor")
plain = rta(tasks, [], 0)
real = rta(tasks, isrs, CS)
print("task    R without overheads   R with overheads   D")
for (n, r0, d), (_, r1, _) in zip(plain, real):
    print(f"{n:6s}  {r0/1000:10.2f} ms        {r1/1000:10.2f} ms   {d/1000:7g} ms  {'met' if r1 <= d else 'MISSED'}")

interrupt and tick load: 4.2 % of the processor
task    R without overheads   R with overheads   D
RADAR         1.20 ms              1.28 ms      6.25 ms  met
CANTX         2.00 ms              2.13 ms        10 ms  met
CLASS        16.20 ms             16.99 ms        25 ms  met
LOG          42.40 ms             45.71 ms       100 ms  met
HOUSE        99.20 ms            149.62 ms      1000 ms  met

The interrupt and tick load is 4.2 % of the processor, most of it from the CAN receive handler at its worst-case rate. Every response time grows: CLASS from 16.20 to 16.99 ms, LOG from 42.40 to 45.71 ms and HOUSE from 99.20 to 149.62 ms. All deadlines are still met. The growth is largest for the lowest-priority task because it suffers the overhead of every other task and interrupt over a long interval. Ignoring overheads would have put HOUSE's response time about a third too low, a reminder that the kernel is part of the system being analyzed.

Standard interfaces and general-purpose kernels

The POSIX real-time extensions define fixed-priority scheduling policies, SCHED_FIFO and SCHED_RR, along with priority-inheritance mutexes, high-resolution timers and real-time signals, and many kernels offer a POSIX-compatible interface. General-purpose operating systems have moved closer to real-time behavior as well. In Linux, the PREEMPT_RT work makes almost all kernel code preemptible by converting most spinlocks into sleeping locks with priority inheritance and running interrupt handlers in kernel threads; it was merged into the mainline kernel in 2024. Such systems can achieve worst-case latencies of tens of microseconds on suitable hardware, which suits many industrial and robotics applications, but their size makes a complete worst-case analysis impractical, so hard guarantees in the strict sense of this course still come from small kernels or from partitioning.

Partitioning is the other major architecture. A separation kernel or hypervisor divides one processor into partitions with fixed shares of time and memory, so that a fault or overload in one partition cannot affect another. The avionics standard ARINC 653 defines such an architecture: partitions are scheduled in a fixed cyclic major frame, like the cyclic executive of lesson 3, and within each partition tasks are scheduled by priority. This two-level design lets software of different criticality share hardware safely, which lesson 8 develops further.