M7-T4: Real-time operating systems

Learning objectives

After this lesson, you should be able to:

• Define hard, firm and soft real-time and give a UAV example of each.
• Run a response-time analysis for fixed-priority tasks.
• Explain priority inversion and priority inheritance.
• Compare how NuttX on a flight controller and Linux on a companion handle real-time requirements.

Conceptual explanation

Established Fixed-priority scheduling theory is from Liu and Layland (1973) and the response-time analysis literature; priority inheritance from Sha, Rajkumar and Lehoczky (1990). Whether a particular OS configuration meets a deadline is a measurement, not a property of its name.

A real-time system must produce results within deadlines. Hard real-time means a missed deadline is a failure (an attitude loop that misses its cycle); firm means a late result is useless but not catastrophic (a late camera frame is dropped); soft means lateness degrades quality (a slightly late video preview).

An RTOS provides preemptive priority scheduling: the highest-priority ready task always runs, a task is preempted as soon as a higher-priority one becomes ready, and the time to do so is bounded. Ingredients that must also be bounded: interrupt latency, the time interrupts are masked, and the time a task can be blocked by lower-priority tasks holding shared resources.

• NuttX (used by PX4 on flight controllers) is a POSIX-like RTOS with priority scheduling; PX4 runs its modules as tasks or work-queue items with priorities.
• Linux (on a companion) is a general-purpose OS: it can provide soft or, with the PREEMPT_RT patch and care, firm real-time behaviour, but its worst-case latency depends on drivers, kernel configuration and load, and must be measured (for example with cyclictest).

Engineering intuition

Imagine a small office where the phone (highest priority) interrupts a report (lower priority), and the report-writer occasionally holds the only photocopier that the phone-answerer also needs. If the phone-answerer waits for the copier while a medium-priority errand runs, the urgent job is delayed by an unrelated one: priority inversion. Priority inheritance fixes it by temporarily raising the copier holder’s priority so it finishes quickly.

The key mental shift is from average to worst case. The average execution time of the EKF is irrelevant; its worst-case execution time and the worst-case interference from higher-priority tasks decide whether its deadline holds.

Mathematical formulation

For fixed-priority preemptive tasks with execution time $C_{i}$, period $T_{i}$ (deadline $D_{i}\le T_{i}$), blocking $B_{i}$, tasks indexed by decreasing priority, the worst-case response time $R_{i}$ is the smallest fixed point of

Iterate from $R_{i}^{(0)}=C_{i}+B_{i}$ until it converges or exceeds $D_{i}$. For rate-monotonic priorities (shorter period, higher priority) and implicit deadlines $(D=T)$ the Liu-Layland sufficient bound is $U\le n(2^{1/n}-1)$. Priority inheritance bounds blocking to the length of one critical section of each lower-priority task per resource instead of unbounded blocking by medium-priority tasks. Jitter of a periodic task’s start, $J=R_{\max}-R_{\min}$, enters the control design as extra delay.

$C_{i}$, $T_{i}$, $D_{i}$

worst-case execution time, period, deadline.

$B_{i}$

worst-case blocking from lower-priority tasks.

$R_{i}$

worst-case response time.

Architecture and data flow

Sensor interrupt (IMU data ready) → driver task (high priority) → estimator task → controller tasks → output driver. Lower-priority tasks: navigator, commander, MAVLink, logger. In PX4, modules run on work queues with defined priorities (rate controllers on the highest, logging and communication lower). Shared data goes through uORB, which is designed to avoid long blocking; any additional shared resource you add (a mutex in a custom module) becomes a candidate source of priority inversion.

Real-world UAV applications

• Choosing priorities and periods for custom flight-controller modules.
• Setting up a PREEMPT_RT or isolated-core configuration on a companion.
• Explaining jitter in a flight log.
• Writing the timing section of a safety case.

Implementation example

This runs as shown. Response-time analysis for a PX4-like task set (illustrative periods and worst-case execution times, not PX4’s actual values), with a blocking term to show priority inversion’s effect, and a check against a brute-force preemptive schedule simulation.

import math, numpy as np
tasks = [  # (name, period s, WCET s) rate-monotonic order: shortest period first. Illustrative values.
    ('rate ctrl', 0.004, 0.0006), ('attitude', 0.008, 0.0010), ('ekf', 0.010, 0.0025), ('navigator', 0.050, 0.0060), ('logger', 0.100, 0.0150)]
def response_times(tasks, blocking=None):
    R = []
    for i, (n, T, C) in enumerate(tasks):
        B = (blocking or {}).get(n, 0.0); r = C + B
        while True:
            r_new = C + B + sum(math.ceil(r / tasks[j][1]) * tasks[j][2] for j in range(i))
            if abs(r_new - r) < 1e-12 or r_new > T: r = r_new; break
            r = r_new
        R.append(r)
    return R
R = response_times(tasks); Rb = response_times(tasks, {'attitude': 0.0030})            # attitude blocked 3 ms by a lower-priority critical section
for (n, T, C), r, rb in zip(tasks, R, Rb): print(f"{n:>9}: T {T * 1e3:5.0f} ms  C {C * 1e3:5.2f} ms  R {r * 1e3:6.2f} ms  R with blocking {rb * 1e3:6.2f} ms  {'OK' if rb <= T else 'MISS'}")
# brute-force check by simulating preemptive fixed-priority scheduling in 10 us ticks
dt = 1e-5; H = 0.2; remaining = [0.0] * len(tasks); rel = [0.0] * len(tasks); worst = [0.0] * len(tasks)
for k in range(int(H / dt)):
    t = k * dt
    for i, (n, T, C) in enumerate(tasks):
        if abs((t / T) - round(t / T)) < dt / T / 2 and t > 0 or k == 0: remaining[i] += C; rel[i] = t
    for i in range(len(tasks)):
        if remaining[i] > 1e-12:
            remaining[i] -= dt
            if remaining[i] <= 1e-12: worst[i] = max(worst[i], t + dt - rel[i])
            break
print("simulated worst response (ms):", [round(w * 1e3, 2) for w in worst])
assert all(w <= r + 2e-4 for w, r in zip(worst, R)) and R[2] < tasks[2][1] and Rb[1] > R[1]

Common engineering mistakes

Failure modes

Debugging approach

1. Measure per-task execution time distributions and the worst case.
2. Trace scheduling events to find preemption and blocking.
3. Check for mutexes shared across priorities.
4. Timestamp at the interrupt, not in the task.

Practical exercises

1. Compute $R$ for each task in your own module set and compare with the measured values.
2. Add a task with a 20 ms period and 4 ms WCET and find which deadlines then fail.
3. Run cyclictest on your companion with and without load and report the maximum latency.
4. Explain priority inversion with a timeline for three tasks.

Interview questions

Write an answer in your own words, then reveal the model answer. Nothing is sent anywhere.

References and further reading

Primary papers, official documentation and standards. Each claim above that is specific to a tool or version points here.

• Liu, C. L. & Layland, J. W. (1973). Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20(1)
• Sha, L., Rajkumar, R. & Lehoczky, J. P. (1990). Priority inheritance protocols: an approach to real-time synchronization. IEEE Trans. Computers 39(9)
• Apache NuttX documentation
• Linux Foundation: Real-Time Linux (PREEMPT_RT)

What’s next