Skip to content

Section 35: Real-Time Systems

Purpose and Scope

Real-time systems are computing systems where correctness depends not only on the logical result of a computation but also on the time at which that result is produced. A control system that computes the correct motor command 10 milliseconds too late may crash a robot arm. An audio driver that misses its deadline produces a glitch the user hears. This section covers the theoretical foundations of real-time scheduling, the practical implementations (PREEMPT_RT, Xenomai, QNX, VxWorks), the sources of latency and jitter in Linux and RTOS environments, real-time networking (TSN, EtherCAT), and lock-free techniques for real-time contexts. It bridges theory (EDF optimality, utilization bounds) and practice (measuring cyclictest numbers, configuring irq affinity).

Prerequisites

  • Operating system scheduling concepts (Section 09)
  • Linux kernel internals (Section 04)
  • Synchronization primitives (Section 10)
  • Embedded systems basics (Section 34)
  • C programming and Linux system administration

Learning Objectives

By the end of this section, you will be able to:

  1. Distinguish hard, soft, and firm real-time requirements and categorize a given system
  2. Apply Rate Monotonic Scheduling theory to a task set and compute utilization bound
  3. Apply Earliest Deadline First scheduling and prove its optimality for preemptive scheduling
  4. Identify and measure all major sources of latency in a Linux system
  5. Configure a PREEMPT_RT kernel for minimal latency (irq threading, CPU isolation, cpufreq, tickless)
  6. Explain priority inheritance and why it is necessary to prevent priority inversion
  7. Compare QNX, VxWorks, RTEMS, FreeRTOS, and Zephyr for a given application profile
  8. Describe TSN (Time-Sensitive Networking) and how EtherCAT achieves deterministic communication

Architecture Overview

Real-Time Classification

  Hard Real-Time:
  +----------timeline---------+
  Computation completes:  OK  |
  Deadline:                   D
  Miss deadline:          CATASTROPHIC (system failure, safety violation)
  Examples: airbag control, fly-by-wire, pacemaker

  Firm Real-Time:
  Deadline:                   D
  Miss (occasional):      Result discarded, no cumulative harm
  Miss (frequent):        Quality of service degrades unacceptably
  Examples: video frame decoding, industrial PLC cycle

  Soft Real-Time:
  Deadline:                   D
  Miss:                   Degraded experience, not catastrophic
  Examples: audio playback, interactive UI, game physics

Latency Sources in Linux

  Hardware IRQ fires
       |
       v (interrupt latency)
  CPU acknowledges IRQ (after IRET from current instruction)
       |
       v (IRQ handler execution)
  Interrupt handler runs (hardirq context)
       |
       v (threaded IRQ or bottom-half)
  Softirq / tasklet / threaded IRQ runs
       |
       v (scheduler invocation)
  Scheduler selects highest-priority runnable task
       |
       v (context switch latency)
  CPU performs context switch (save/restore registers)
       |
       v
  Real-time task begins execution

  Latency budget:
  +-----------+    Vanilla Linux    PREEMPT_RT
  | Interrupt |    ~1-50 us         ~1-10 us
  | Latency   |
  +-----------+
  | Scheduler |    ~50-500 us       ~10-50 us
  | Latency   |    (spinlocks block)|
  +-----------+
  | Context   |    ~2-10 us         ~2-10 us
  | Switch    |
  +-----------+
  | Total     |    ~100-1000 us     ~20-100 us
  | Worst-case|    (unbounded with  (bounded with
  |           |    high IRQ load)   RT config)
  +-----------+

PREEMPT_RT Transformation

  Vanilla Linux kernel:
  +-----------+  +-----------+  +-----------+
  | Process A |  | Process B |  |  IRQ Hdlr |
  |  (user)   |  |  (user)   |  | (hardirq) | <-- non-preemptible
  +-----------+  +-----------+  +-----------+
        |              |              |
  +-----+--------------+--------------+--+
  |  Linux Kernel                        |
  |  Spinlocks: cli/sti, disables preempt|  <-- latency source
  |  Softirqs: run with preempt off      |  <-- latency source
  +--------------------------------------+

  PREEMPT_RT (full preemption):
  - Spinlocks converted to rt_mutex (sleepable)
  - IRQ handlers become preemptible kernel threads
  - All critical sections preemptible by higher-priority RT task
  - Result: worst-case latency bounded and measurable

  Key sysctl/config settings:
  CONFIG_PREEMPT_RT=y
  CONFIG_HZ=1000
  isolcpus=2,3 (CPU isolation from kernel housekeeping)
  nohz_full=2,3 (tickless idle on isolated CPUs)
  irqbalance disabled, IRQs manually affined

Real-Time Scheduling Algorithms

  Rate Monotonic Scheduling (RMS):
  - Static priorities: shorter period -> higher priority
  - Optimal for fixed-priority preemptive scheduling
  - Utilization bound: U = sum(Ci/Ti) <= n(2^(1/n) - 1)
    For n tasks: n=1: 100%, n=2: 82.8%, n->inf: 69.3%

  Task set example:
  Task T1: period=10ms, WCET=3ms  -> prio HIGH,  util=30%
  Task T2: period=20ms, WCET=5ms  -> prio MED,   util=25%
  Task T3: period=50ms, WCET=10ms -> prio LOW,   util=20%
  Total utilization = 75% < 77.9% (bound for n=3) -> schedulable

  Earliest Deadline First (EDF):
  - Dynamic priorities: earliest absolute deadline -> highest priority
  - Optimal for preemptive uniprocessor scheduling
  - Can achieve 100% CPU utilization (vs 69% for RMS)
  - More complex to implement; used in QNX, RTEMS, Linux SCHED_DEADLINE

  Linux SCHED_DEADLINE:
  sched_setattr(pid, {policy=SCHED_DEADLINE,
                      sched_runtime=3ms,
                      sched_deadline=10ms,
                      sched_period=10ms});
  Implements EDF + CBS (Constant Bandwidth Server) for isolation

Priority Inversion and Inheritance

  Priority Inversion scenario:

  Time ->
  T_high (prio 90): ----BLOCKED(waiting for mutex)----RUNS--
  T_medium (prio 50): --------RUNS(preempts T_low)----------
  T_low (prio 10): RUNS, holds mutex----(preempted)----------

  T_high effectively blocked behind T_medium indefinitely!

  Priority Inheritance Protocol:
  When T_high blocks on mutex held by T_low:
    T_low's priority is temporarily raised to T_high's priority
    T_low can now preempt T_medium and complete critical section
    T_low releases mutex, priority drops back to 10
    T_high unblocked, runs

  Priority Ceiling Protocol:
    Mutex has a ceiling priority = highest priority of any task that uses it
    Task acquires priority ceiling when it locks mutex
    Prevents deadlock and limits blocking to one critical section

Key Concepts

  • Worst-Case Execution Time (WCET): The maximum time a task can take to execute in any possible input/hardware state. WCET analysis is the foundation of schedulability analysis. Requires consideration of cache behavior, pipeline stalls, and interrupt overhead.
  • Schedulability Analysis: Formal verification that a task set will always meet its deadlines under the assumed scheduling algorithm and WCET estimates. Rate Monotonic Analysis (RMA) and response-time analysis are standard methods.
  • PREEMPT_RT: Patch set for the Linux kernel (being merged upstream since 5.x) that converts most spinlock critical sections to rt_mutex (preemptible) and threads IRQ handlers. Reduces worst-case scheduling latency from milliseconds to tens of microseconds.
  • Xenomai: Dual-kernel real-time framework for Linux. Runs a real-time kernel (Cobalt) alongside Linux, with Linux tasks running at lower priority. Achieves microsecond latency but at the cost of complexity.
  • cyclictest: Standard tool for measuring scheduling latency on real-time Linux. Runs a high-priority SCHED_FIFO task, compares wake-up time to target, accumulates histogram. Worst-case over millions of iterations characterizes the system.
  • TSN (Time-Sensitive Networking): IEEE 802.1Q extension suite that adds determinism to Ethernet: time synchronization (802.1AS), traffic shaping (802.1Qbv Credit-Based Shaper), preemption (802.3br). Used in automotive, industrial, and AV streaming.
  • EtherCAT: Ethernet-based fieldbus that achieves sub-microsecond synchronization and <100 microsecond cycle times by having slaves process frames "on the fly" without buffering. Widely used in servo drives and motion control.
  • Lock-Free Real-Time: Avoiding mutexes in real-time code by using lock-free ring buffers, atomic operations, or double-buffering. Necessary when a real-time task cannot afford to wait for a mutex held by a non-real-time thread.

Major Historical Milestones

Year Milestone
1973 Liu & Layland paper — Rate Monotonic Scheduling theory established
1974 EDF optimality proven for preemptive uniprocessors
1988 Sha et al. — Priority Inheritance Protocol formally defined
1991 VxWorks widely deployed in industrial and aerospace
1997 Mars Pathfinder mission — priority inversion bug causes real-world reset
1998 POSIX.1b real-time extensions (SCHED_FIFO, SCHED_RR)
2002 Xenomai 1.0 — Adeos-based Linux real-time extension
2004 PREEMPT_RT patch first published by Ingo Molnar
2005 QNX Neutrino RTOS widely deployed in automotive infotainment
2006 Linux SCHED_DEADLINE RFC (merged in Linux 3.14, 2014)
2012 Zephyr Project started (open-sourced by Linux Foundation 2016)
2015 TSN standards work accelerates (IEEE 802.1Q-2018)
2017 PREEMPT_RT mainlining effort begins
2019 PREEMPT_RT fully in-tree for ARM architecture
2021 Linux 5.15: PREEMPT_RT base merged for x86 and ARM
2023 EtherCAT + TSN convergence for Industry 4.0

Modern Relevance

Real-time requirements are expanding: autonomous vehicles require end-to-end latency guarantees from sensor to actuator that vanilla Linux cannot provide. Industrial robots, CNC machines, and collaborative robots (cobots) demand microsecond-level cycle times. The ROS 2 (Robot Operating System) ecosystem is explicitly built around PREEMPT_RT Linux and DDS real-time middleware. 5G private networks use TSN for factory floor timing. As computing moves into physical systems — robotics, industrial IoT, medical devices — real-time systems knowledge becomes indispensable. Linux is increasingly used where RTOS was required before, but only when properly configured and validated.

File Map

35-real-time-systems/
├── 00-overview.md              <- This file
├── 01-real-time-definitions.md
├── 02-rms-and-utilization.md
├── 03-edf-and-deadline-scheduling.md
├── 04-preempt-rt-linux.md
├── 05-xenomai.md
├── 06-real-time-posix.md
├── 07-jitter-analysis.md
├── 08-latency-sources.md
├── 09-interrupt-latency.md
├── 10-lock-free-real-time.md
├── 11-priority-inheritance.md
├── 12-tsn-networking.md
├── 13-ethercat.md
└── 14-rtos-comparison.md

Cross-References

  • Section 09 (Scheduling): CFS, SCHED_FIFO, SCHED_RR baseline; priority concepts
  • Section 10 (Synchronization): rt_mutex, priority inheritance, lock-free structures
  • Section 34 (Embedded Systems): FreeRTOS, Zephyr; embedded RTOS where Linux is too heavy
  • Section 36 (Mobile OS): Android's real-time audio path; deadline scheduling for UI rendering
  • Section 15 (Networking): TSN as IEEE 802.1Q extension; EtherCAT as Ethernet-based fieldbus