Real-Time Systems

Definitions and Classification

A real-time system must produce correct results within specified timing constraints. Correctness is a function of both logical output and temporal behavior.

Hard vs. Soft Real-Time

| Property | Hard Real-Time | Soft Real-Time | |------------------|-----------------------------|-------------------------------| | Deadline miss | System failure (catastrophic) | Degraded quality of service | | Examples | Airbag controller, ABS, pacemaker | Video streaming, audio playback | | Guarantee type | Deterministic worst-case | Statistical / best-effort | | Analysis method | WCET + schedulability proof | Average-case + overload management |

Firm real-time is an intermediate category: a missed deadline makes the result worthless (no catastrophe), but late results are discarded (e.g., financial trading, sensor fusion).

Real-Time Scheduling

Task Model

A periodic task set: each task T_i has period P_i, worst-case execution time C_i, and relative deadline D_i.

Implicit deadline: D_i = P_i
Constrained deadline: D_i <= P_i
Arbitrary deadline: D_i can be anything

Utilization: U = sum(C_i / P_i) for all tasks. This is the fraction of CPU time consumed.

Rate Monotonic Scheduling (RMS)

Fixed-priority, preemptive -- highest priority to the shortest period
Optimal among fixed-priority algorithms for implicit-deadline task sets
Schedulability bound: U <= n(2^(1/n) - 1), converging to ln(2) ~ 0.693 as n grows
If U <= 0.693, the task set is guaranteed schedulable under RMS

Example:
  Task A: C=1, P=4  -> Priority 2 (shorter period = higher priority)
  Task B: C=2, P=6  -> Priority 1
  U = 1/4 + 2/6 = 0.583 < 0.693 -> Schedulable under RMS

Earliest Deadline First (EDF)

Dynamic-priority -- at each scheduling decision, run the task with the nearest absolute deadline
Optimal among all preemptive uniprocessor algorithms
Schedulability bound: U <= 1.0 (can use 100% of CPU)
More complex to implement (dynamic priority tracking), but strictly better utilization than RMS

Deadline Monotonic Scheduling (DMS)

Extension of RMS for constrained-deadline task sets (D_i <= P_i)
Assign priority by relative deadline (shorter deadline = higher priority)
Optimal among fixed-priority algorithms for constrained-deadline systems
Reduces to RMS when D_i = P_i

Comparison

| Algorithm | Priority | Optimal For | Max Utilization | Overhead | |-----------|-----------|-----------------------|-----------------|------------| | RMS | Fixed | Implicit-deadline, FP | ~69.3% | Low | | DMS | Fixed | Constrained-deadline | ~69.3% | Low | | EDF | Dynamic | All preemptive uni-proc| 100% | Medium | | LLF | Dynamic | Uniprocessor | 100% | High |

Priority Inversion

Priority inversion occurs when a high-priority task is blocked waiting for a resource held by a low-priority task, while a medium-priority task preempts the low-priority task.

Classic Mars Pathfinder bug (1997):
  High-priority: bus manager task
  Medium-priority: communication task
  Low-priority: meteorological task (holding shared mutex)

  Timeline:
  Low takes mutex -> Medium preempts Low -> High arrives, needs mutex
  High is blocked behind Low, which is blocked behind Medium
  Result: High-priority task misses deadline -> system watchdog resets

Priority Inheritance Protocol (PIP)

When a low-priority task blocks a high-priority task, the low-priority task temporarily inherits the high-priority task's priority. This prevents medium-priority tasks from preempting the lock holder.

Bounded priority inversion (duration = critical section length)
Does not prevent deadlock -- must handle separately
Can chain: if task C blocks B which blocks A, C inherits A's priority

Priority Ceiling Protocol (PCP)

Each mutex is assigned a priority ceiling equal to the highest priority of any task that may lock it. A task can only acquire a mutex if its priority is strictly higher than all ceilings of mutexes currently locked by other tasks.

Prevents deadlock (no circular wait possible)
Bounds blocking to at most one critical section
The Immediate Priority Ceiling Protocol (IPCP) raises the task's priority to the ceiling upon lock acquisition

Worst-Case Execution Time (WCET) Analysis

WCET analysis determines the longest possible execution time for a code segment. This is essential for proving schedulability.

Static Analysis

Parse the control flow graph (CFG), identify all paths
Model cache behavior, pipeline effects, branch prediction
Tools: aiT (AbsInt), OTAWA, Chronos
Must bound loops, eliminate recursion, restrict dynamic dispatch

Measurement-Based

Run code on target hardware with worst-case inputs
Add safety margin (typically 20-50%)
Less precise but practical for complex hardware

Challenges

Modern hardware (out-of-order execution, multi-level caches, speculative execution) makes static WCET extremely pessimistic
Multi-core interference: shared cache and bus contention is difficult to bound
WCET estimates can be 10-100x larger than average-case execution time

Real-Time Operating Systems

FreeRTOS

Open-source, extremely small footprint (~6-15 KB kernel)
Tickless idle for power-efficient embedded systems
Fixed-priority preemptive scheduler with optional time-slicing
Runs on ARM Cortex-M, RISC-V, Xtensa, and many other MCUs
AWS maintains FreeRTOS with IoT libraries (TLS, MQTT, OTA updates)

VxWorks

Commercial RTOS from Wind River, used in aerospace and defense
Deployed on Mars rovers (Spirit, Opportunity, Curiosity)
POSIX-compliant, supports SMP multi-core
Certifiable to DO-178C (avionics), IEC 62304 (medical)
Deterministic interrupt latency: microsecond-range guarantees

QNX Neutrino

Microkernel RTOS (see also: microkernels chapter)
True POSIX compliance with real-time extensions (POSIX 1003.1b)
Adaptive partitioning: guaranteed CPU budgets even under overload
Used in automotive (BlackBerry QNX), nuclear, rail, medical

Zephyr

Linux Foundation project, Apache 2.0 licensed
Designed for resource-constrained IoT (as low as 8 KB RAM)
Supports 500+ boards across ARM, RISC-V, x86, ARC, Xtensa
Tickless kernel, preemptive and cooperative scheduling
Built-in Bluetooth, networking, USB, file system stacks

Comparison

| Feature | FreeRTOS | VxWorks | QNX | Zephyr | |----------------|-----------|-----------|-----------|-----------| | License | MIT | Commercial| Commercial| Apache 2.0| | Min RAM | ~4 KB | ~50 KB | ~100 KB | ~8 KB | | POSIX | Partial | Full | Full | Partial | | SMP support | Limited | Yes | Yes | Yes | | Certification | IEC 61508 | DO-178C | ISO 26262 | IEC 61508 | | Typical domain | MCU/IoT | Aerospace | Automotive| IoT |

Linux PREEMPT_RT

PREEMPT_RT transforms the mainline Linux kernel into a near-real-time system:

Key Modifications

Forced threaded interrupts: Interrupt handlers run as schedulable kernel threads with configurable priorities
Preemptible critical sections: Most spinlocks replaced with RT-mutexes (sleeping locks with priority inheritance)
Priority inheritance throughout: RT-mutexes implement PI in the kernel's locking infrastructure
High-resolution timers: Nanosecond-granularity timers, not limited to tick frequency
Reduced non-preemptible regions: Minimize code paths where preemption is disabled

Latency Characteristics

| Configuration | Worst-case latency | Jitter | |----------------------|--------------------|------------| | Vanilla Linux | 1-10 ms | High | | PREEMPT_RT | 10-100 us | Low | | Dedicated RTOS (QNX) | 1-10 us | Very low |

PREEMPT_RT is suitable for soft and some firm real-time workloads. For hard real-time on Linux, co-kernel approaches (Xenomai, RTAI) run a real-time kernel alongside Linux, giving the RT domain direct hardware access.

PREEMPT_RT in Mainline

As of Linux 6.x, most PREEMPT_RT patches have been merged into mainline. The remaining pieces (printk rework, per-CPU locking changes) are being upstreamed. The goal is full mainline integration.

Multiprocessor Real-Time Scheduling

Partitioned Scheduling

Each task assigned to a specific core (bin-packing problem)
Per-core scheduling with RMS or EDF
No migration overhead, good cache behavior
Utilization can be suboptimal (bin-packing is NP-hard)

Global Scheduling

Tasks can run on any core, single global run queue
Global EDF: Dhall's effect can cause failure at low utilization
Global EDF schedulability bound: U <= m - (m-1) * U_max (where m = cores)

Semi-Partitioned and Clustered

Semi-partitioned: most tasks pinned, a few allowed to migrate
Clustered: partition tasks among clusters of cores sharing a cache
Practical compromise for multi-core real-time systems

Applications

| Domain | Timing Requirement | Typical RTOS | Standard | |-----------------|-----------------------|--------------------|------------------| | Avionics | 1-10 ms cycle time | VxWorks, INTEGRITY | DO-178C | | Automotive ADAS | 10-50 ms cycle time | QNX, AUTOSAR OS | ISO 26262 | | Industrial PLC | 100 us - 1 ms cycle | VxWorks, QNX | IEC 61131 | | Medical devices | 1-100 ms | QNX, FreeRTOS | IEC 62304 | | Robotics | 1-10 ms control loop | ROS 2 + Zephyr | -- | | Audio processing| ~5 ms buffer latency | Linux PREEMPT_RT | -- |

Key Takeaways

Hard real-time requires provable worst-case timing guarantees; soft real-time tolerates occasional misses
EDF is optimal on uniprocessors (utilization up to 100%), RMS is simpler with a ~69.3% bound
Priority inversion is solved by inheritance (PIP) or ceiling (PCP) protocols
WCET analysis on modern hardware is increasingly difficult due to micro-architectural complexity
PREEMPT_RT brings Linux to soft real-time territory (~10-100 us latency); dedicated RTOSes achieve single-digit microseconds
Multi-core real-time scheduling remains an active research area with no single dominant approach