Real-Time Systems
Prerequisite:
What Real-Time Actually Means
“Real-time” is one of the most misused terms in computing. It does not mean fast. It means predictable - a system where correctness depends not only on producing the right output but on producing it within a defined time bound.
A video game running at 60fps is not real-time in the engineering sense, even though it processes frames quickly. An airbag controller that must fire within 15 milliseconds of detecting a collision - and where firing at 16ms means the system has failed regardless of correctness - that is real-time.
Hard real-time: missing a deadline is a system failure. Failure may be catastrophic (flight control systems, airbag controllers, industrial robot arms). The system must guarantee worst-case response time, not average-case.
Soft real-time: deadlines are important and should be met, but occasional misses degrade quality rather than cause failure. Video streaming, voice calls, game physics. Statistical guarantees (99th percentile latency) are the typical metric.
Firm real-time: missing a deadline makes the result useless but not dangerous. An online auction bid that arrives after the auction closes. The result is discarded, not catastrophic.
Scheduling Theory
For hard real-time systems, schedulability analysis determines at design time whether a task set can always meet its deadlines. Two foundational algorithms:
Rate Monotonic Scheduling (RM): assign fixed priorities based on task period - shorter period means higher priority. Under RM, the schedulability bound for $n$ periodic tasks is:
$$\sum_{i=1}^{n} \frac{C_i}{T_i} \leq n(2^{1/n} - 1)$$
where $C_i$ is the worst-case execution time and $T_i$ is the period. As $n \to \infty$, this converges to $\ln 2 \approx 0.693$. A utilization above 69.3% does not guarantee schedulability under RM, but tasks can still be feasible - the bound is sufficient, not necessary.
Earliest Deadline First (EDF): dynamic priority - whichever task has the earliest absolute deadline runs next. EDF is optimal for uniprocessor scheduling: if any feasible schedule exists, EDF will find it. The schedulability condition simplifies to:
$$\sum_{i=1}^{n} \frac{C_i}{T_i} \leq 1$$
EDF can utilize the CPU to 100% while guaranteeing all deadlines, whereas RM wastes up to 30% of capacity. The tradeoff: EDF requires dynamic priority recalculation and is harder to analyze under overload conditions. RM’s fixed priorities degrade more predictably when the system is overloaded.
Priority Inversion
Priority inversion is the failure mode that made headlines when it nearly ended the Mars Pathfinder mission. The scenario:
- Low-priority task L acquires a mutex protecting shared data.
- High-priority task H becomes runnable and preempts L, but then needs the same mutex - H blocks.
- Medium-priority task M, which does not need the mutex, preempts L and runs.
- H is now indirectly blocked by M, despite H having higher priority than M.
If M runs long enough, H misses its deadline. The kernel sees nothing wrong - every scheduling decision was locally correct.
Priority inheritance protocol: when a low-priority task holds a mutex that a higher-priority task is waiting for, the low-priority task temporarily inherits the higher task’s priority. This ensures M cannot preempt L while L holds the mutex that H needs.
Without inheritance: With inheritance:
Time → Time →
H: blocked on mutex H: blocked on mutex
M: running (preempts L) M: blocked (L inherits H's priority)
L: blocked by M L: running at H's priority, completes quickly
H: unblocks, runs
POSIX mutexes support priority inheritance via pthread_mutexattr_setprotocol:
pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
pthread_mutex_init(&mutex, &attr);
Priority ceiling protocol: a stronger alternative - each mutex is assigned a priority ceiling equal to the highest priority of any task that may acquire it. A task can only acquire a mutex if its priority is higher than all currently locked mutexes' ceilings. This prevents deadlock in addition to priority inversion.
Real-Time Operating Systems
VxWorks: the dominant RTOS in safety-critical aerospace and defense. Used in the Mars rovers and the Boeing 787. Deterministic preemptive scheduling, hard real-time guarantees, DO-178C certification.
FreeRTOS: the dominant open-source RTOS for microcontrollers. Extremely small footprint (4-12KB RAM), widely used in IoT devices. Amazon acquired it and released FreeRTOS under MIT license.
QNX: a microkernel RTOS used in automotive (most major car infotainment and ADAS systems), medical devices, and industrial control. POSIX-compliant, which eases porting from Linux.
Linux with PREEMPT_RT: the Linux kernel is not a real-time OS by default. The standard kernel has non-preemptible sections where the scheduler cannot run, leading to latency spikes of hundreds of microseconds or more. The PREEMPT_RT patch converts spinlocks into preemptible mutexes, makes interrupt handlers preemptible, and converts the kernel into a fully preemptible system. As of Linux 6.12, PREEMPT_RT was merged into the mainline kernel. With PREEMPT_RT, Linux can achieve worst-case scheduling latencies of 50-100μs on commodity hardware, making it suitable for industrial automation and soft real-time applications.
Latency Sources and Mitigations
Understanding what causes latency spikes is prerequisite to eliminating them:
Page faults: if a thread accesses memory that has been paged out, the kernel must fetch it from disk - this can take milliseconds. Fix: mlockall(MCL_CURRENT | MCL_FUTURE) locks all current and future memory pages into RAM.
#include <sys/mman.h>
mlockall(MCL_CURRENT | MCL_FUTURE);
// Now no page faults can occur for this process
Dynamic memory allocation: malloc/free can take unpredictable time due to lock contention in the allocator, fragmentation, and calls to brk/mmap. Fix: pre-allocate all memory at startup using a pool allocator. The hot path never calls malloc.
Garbage collection: GC languages (Java, Go, Python) pause all threads during collection. Incompatible with hard real-time. Use C, C++, Rust, or Ada in the hard real-time path.
System calls: each syscall involves a context switch to kernel mode. Minimize syscalls in the hot path; use io_uring to batch them; use DPDK/RDMA to eliminate networking syscalls entirely.
Scheduler jitter: the OS may preempt your thread to run other tasks or handle interrupts. Fix: SCHED_FIFO scheduling policy with high priority, isolcpus to remove cores from general scheduling, irqbalance disabled with IRQs directed to non-critical cores.
Linux Real-Time Scheduling
Linux provides real-time scheduling policies for SCHED_FIFO and SCHED_RR:
#include <sched.h>
struct sched_param param;
param.sched_priority = 80; // 1-99 for RT policies
sched_setscheduler(0, SCHED_FIFO, ¶m);
// Thread now preempts any non-RT thread
// Will not be preempted by any thread with lower priority
SCHED_FIFO: FIFO within the same priority level. A thread runs until it voluntarily yields or is preempted by a higher-priority thread. Used for latency-critical threads.
SCHED_RR: round-robin at the same priority. Threads at the same priority share time in slices. Useful for groups of equal-priority threads.
SCHED_DEADLINE: implements EDF with explicit deadline parameters. The kernel performs admission control - it will reject the request if the task set is not schedulable.
struct sched_attr attr = {
.size = sizeof(attr),
.sched_policy = SCHED_DEADLINE,
.sched_runtime = 1000000, // 1ms WCET
.sched_deadline = 5000000, // 5ms deadline
.sched_period = 5000000, // 5ms period
};
syscall(SYS_sched_setattr, 0, &attr, 0);
Examples
Measuring scheduling latency with cyclictest (PREEMPT_RT):
# Install rt-tests package
# Run with SCHED_FIFO priority 99, measure latency over 1 million iterations
cyclictest --mlockall --smp --priority=99 --interval=200 --distance=0 \
--loops=1000000 --histogram=400
# On a standard kernel: max latency often > 1ms
# On PREEMPT_RT kernel: max latency typically < 100μs
# On isolated cores with PREEMPT_RT: max latency < 20μs
RM schedulability check for 3 tasks:
Task WCET (C) Period (T) Utilization (C/T)
1 2ms 10ms 0.20
2 3ms 15ms 0.20
3 2ms 8ms 0.25
Total utilization: 0.65
RM bound for n=3: 3 * (2^(1/3) - 1) ≈ 0.780
0.65 ≤ 0.78 → schedulable under RM ✓
Priority inheritance illustration in code:
// Thread L (priority 10) acquires mutex
pthread_mutex_lock(&shared_mutex);
// Thread H (priority 90) tries to acquire same mutex
// → Thread L temporarily runs at priority 90
// → Thread M (priority 50) cannot preempt thread L
do_work(); // completes without M interfering
pthread_mutex_unlock(&shared_mutex);
// → Thread H unblocks and runs
// → Thread L returns to priority 10
Real-time systems engineering is ultimately about eliminating non-determinism. Every source of variable latency - allocation, paging, scheduling, GC, syscalls - must be accounted for and either eliminated or bounded. The reward is a system where you can state with confidence: this task will always complete within N microseconds.
Read Next: