Operating Systems
Real-Time Systems
1997. Mars Pathfinder on the surface of Mars begins to reboot unexpectedly. A $265 million mission is at risk. The reason? Priority inversion - a bug in the RTOS scheduler. NASA engineers upload a patch via radio (300 million km!), enable priority inheritance, and the rover works. Real-Time systems are not just "fast code." They are mathematical guarantees that a critical task will complete BEFORE the deadline. Missing a deadline in an airbag = death. In a nuclear reactor = catastrophe. RT OS save lives every day.
- **Mars Pathfinder (1997):** Priority inversion was crashing the system on Mars. A patch with priority inheritance saved the mission. A classic case study in FAANG interviews.
- **Automotive safety (Tesla, Waymo):** PREEMPT_RT Linux for ADAS (camera → decision in <10ms). ISO 26262 ASIL D requires formal proof of WCET.
- **Medical devices (pacemakers):** FreeRTOS on ARM Cortex-M. Hard RT guarantees: heart impulse EXACTLY every 1000ms ±10μs. A miss = heart stop.
Цели урока
- Distinguish hard vs soft real-time; deadline vs throughput as metrics
- Real-time schedulers: Rate Monotonic, EDF (Earliest Deadline First)
- Priority inversion: the problem, priority inheritance, priority ceiling protocol
- PREEMPT_RT patch: spinlock → mutex, threaded IRQs, turning Linux into an RTOS
- WCET (Worst Case Execution Time) analysis and why it is non-trivial
Real-Time Scheduling
**Real-Time Operating System (RTOS)** is an operating system that guarantees task execution within strictly defined time frames. The difference from regular OS is not in speed, but in **determinism** - the predictability of execution time.
Difference between Fast OS and Real-Time OS
A regular OS can process a request in 5ms on average, but sometimes in 500ms (if an interrupt occurs, garbage collector runs, another process is preempted). RTOS **guarantees**: a task with a 10ms deadline will be completed in a maximum of 10ms. Even if the average delay is higher, the upper limit is strictly observed. For avionics, this is the difference between life and death.
Real-time systems are divided into two types: **Hard Real-Time** - missing a deadline is catastrophic (aviation, medicine, nuclear reactors). Example: missing a turbine control tick on an aircraft by 1ms → engine failure. **Soft Real-Time** - missing a deadline is undesirable but not fatal (video streaming, VoIP). Example: a 50ms video packet delay → artifact on the screen, but the system works.
**RT schedulers use priority-based preemptive scheduling.** Each task is assigned a priority. The scheduler always executes the task with the highest priority. If a more prioritized task arrives, the current one is immediately preempted.
**Linux RT policies:** - **SCHED_FIFO:** Fixed priority, no time slicing. Runs until it blocks or a higher priority task arrives. - **SCHED_RR:** Round-Robin with fixed priority. Tasks with the same priority alternate through time quantum. - **SCHED_DEADLINE:** Earliest Deadline First (EDF). The scheduler selects the task with the nearest deadline.
**Rate Monotonic Scheduling (RMS)** - a classic algorithm for periodic RT tasks. Rule: tasks with shorter periods receive higher priority. Mathematically proven optimal for static priority scheduling under certain conditions.
What is the key difference between a Hard Real-Time system and a regular High-Performance system?
Priority Inversion
**Priority Inversion** - a catastrophic problem in RT systems when a high-priority task is blocked by a low-priority task through a shared resource. It can lead to missed deadlines and system failure.
Mars Pathfinder: a real Priority Inversion bug
1997. NASA Mars Pathfinder on Mars began to reboot unexpectedly. **Cause:** Priority inversion in VxWorks RTOS. - High-priority task: `bc_dist` (communication with Earth) - Low-priority task: `ASI/MET` (meteorological data collection) - Shared resource: `information bus` (mutex) `ASI/MET` locked the mutex → medium tasks preempted it → `bc_dist` waited for the mutex → watchdog reset → reboot. **Solution:** Enabled priority inheritance in VxWorks, uploaded a patch via radio from Earth (300 million km away!).
**Priority Inheritance Protocol (PIP)** - a solution to priority inversion. When a high-priority task is blocked on a mutex, the mutex owner temporarily inherits its priority. After unlocking, the priority is restored.
**Solutions to Priority Inversion:** 1. **Priority Inheritance:** the mutex owner inherits the priority of the blocked task 2. **Priority Ceiling Protocol:** the mutex has a "ceiling" priority. The owner gets this priority upon locking 3. **Lock-Free algorithms:** avoid mutexes through atomic operations (but more complex to implement)
**Priority Ceiling Protocol (PCP)** - a more aggressive approach. Each mutex is assigned a ceiling priority (the maximum priority of tasks using the mutex). A task can lock the mutex only if its priority is higher than the ceiling of all already locked mutexes in the system.
When Priority Inversion is NOT a problem
In non-RT systems (Linux desktop, Windows) priority inversion is acceptable. The scheduler uses dynamic priorities, fair scheduling (CFS in Linux). Short-term blocking is not critical. But in RT systems even a 1ms delay can violate a deadline. Therefore, all RT OS (VxWorks, QNX, FreeRTOS, PREEMPT_RT Linux) implement priority inheritance by default for mutexes.
How does the Priority Inheritance Protocol solve the problem of priority inversion?
PREEMPT_RT Linux
**PREEMPT_RT (Real-Time preemption patch)** - a set of patches that turn standard Linux into a Hard Real-Time system. Goal: make the kernel fully preemptable, remove sources of unbounded latency.
Regular Linux is a General-Purpose OS. The scheduler optimizes throughput and fairness but does not guarantee latency. For example, spin_lock in the kernel disables preemption for an unpredictable time. Interrupt handlers (IRQ) block the system.
**Key changes in PREEMPT_RT:** 1. **Spinlocks → rt_mutex:** In vanilla Linux, spin_lock spins in a loop, disabling preemption. In RT, it is replaced with a sleeping mutex with priority inheritance. 2. **Threaded IRQ:** Interrupt handlers run in kernel threads with priority. An IRQ handler can be preempted by a more important RT task. 3. **High-resolution timers:** Precision up to microseconds instead of jiffies (usually 1-10ms).
**Levels of preemption in Linux:** - **PREEMPT_NONE:** No forced preemption (server) - **PREEMPT_VOLUNTARY:** Voluntary preemption (desktop) - **PREEMPT:** Preemptible kernel (low-latency desktop) - **PREEMPT_RT:** Full real-time preemption (hard RT) Configured during kernel compilation via `make menuconfig`.
PREEMPT_RT in automotive (Tesla, Waymo)
Cars use Linux with PREEMPT_RT for: - **ADAS (Advanced Driver Assistance):** Real-time processing of camera/lidar data. Deadline: <10ms from frame capture to decision. - **CAN bus communication:** Sending commands to ECU (engine control units) with guaranteed latency. - **Infotainment + safety:** One OS for multimedia (soft RT) and safety-critical systems (hard RT) through cgroups isolation. Example: **Automotive Grade Linux (AGL)** - a distribution based on PREEMPT_RT for the automotive industry.
**Limitations of PREEMPT_RT:** - **Throughput vs Latency trade-off:** RT optimizes the worst-case, sacrificing average-case throughput. For servers with thousands of connections, this is a downside. - **Drivers:** Not all drivers are compatible with RT. Proprietary drivers (Nvidia) often disable preemption. - **Debugging complexity:** Timing bugs appear only under load, making them difficult to reproduce.
Why are interrupt handlers (IRQ) executed in kernel threads in PREEMPT_RT Linux?
Latency and Worst-Case Analysis
**Latency analysis** is a critical stage in RT system development. It's not enough to simply measure average delay - the worst-case execution time (WCET) must be mathematically proven to fit within the deadline.
Sources of latency in the system: 1. **Interrupt latency:** Time from interrupt to handler start 2. **Preemption latency:** Time from preemption request to context switch 3. **Scheduling latency:** Time from wake-up to CPU acquisition 4. **Critical section latency:** Time blocked on locks
**Stress testing for worst-case:** It's not enough to measure latency on an idle system. Load is needed: - **CPU stress:** `stress-ng --cpu 8` - load all cores - **Memory stress:** `stress-ng --vm 4 --vm-bytes 1G` - page faults, cache misses - **Disk I/O:** `dd if=/dev/zero of=/tmp/test bs=1M count=1024` - DMA, interrupts - **Network:** `iperf3 -c server` - network interrupts
**WCET (Worst-Case Execution Time) analysis:** For safety-critical systems (aviation, medicine), **static WCET analysis** is needed - a mathematical proof of the upper execution time limit. Tools: - **aiT WCET Analyzer:** Static analysis at the machine code level - **RapiTime:** Hybrid analysis (static + tracing) - **Bound-T:** Open-source WCET for embedded Required for certification (DO-178C for aviation, IEC 61508 for industry).
Automotive: ISO 26262 and latency requirements
The ISO 26262 standard (functional safety for automobiles) defines ASIL levels (Automotive Safety Integrity Level): - **ASIL D** (critical): Airbag, steering, brakes → deadline <10ms, WCET must be proven - **ASIL B** (important): ABS, ESC → deadline <50ms - **QM** (non-critical): Infotainment → best-effort For ASIL D, it requires: 1. Static WCET analysis 2. Formal verification (model checking) 3. Redundant execution + voting 4. Extensive testing (millions of test cases)
**Deadline Miss handling:** What to do if an RT task misses its deadline? 1. **Logging:** Record the event for analysis (via lock-free ring buffer) 2. **Degradation:** Switch to safe mode (e.g., the vehicle slows down) 3. **Failover:** Switch to a backup system 4. **Panic:** For Hard RT (airbag) better to crash than make a wrong decision
A Real-Time system is just a very fast system; the fix is the fastest hardware and aggressive code optimization
Real-Time is about predictability (determinism), not speed. A slow but deterministic system is better than a fast unpredictable one
An RTOS can run on a slow microcontroller (ARM Cortex-M @ 48MHz) and be Hard RT. A supercomputer on Linux without PREEMPT_RT will not provide RT guarantees. The key is bounded latency: WCET must be mathematically proven. This is achieved through architecture (priority inheritance, preemptable kernel, lock-free algorithms), not GHz processors. Mars Pathfinder crashed not because of a slow CPU, but due to priority inversion - an architectural problem. The essence of RT: better to execute in 10ms ALWAYS than in 1ms on average but sometimes in 1000ms.
Key Ideas
- **RT ≠ Fast. RT = Deterministic.** RTOS guarantees worst-case latency, not average. A slow RTOS on a microcontroller is more reliable than a supercomputer without RT.
- **Priority Inversion - the killer of RT systems.** A high-priority task is blocked through a shared resource. Solution: Priority Inheritance Protocol (the mutex owner inherits the priority of the blocked task).
- **PREEMPT_RT turns Linux into Hard RT.** Spinlocks → rt_mutex, IRQ → threads, priority inheritance everywhere. Latency <100μs instead of milliseconds.
- **WCET analysis is critical for safety.** For aviation/medicine, the upper execution time limit must be mathematically proven. Static analysis + stress testing under load.
Related Topics
Real-Time systems are built on the foundation of OS scheduling and synchronization:
- CPU Scheduling — RT schedulers (SCHED_FIFO, RMS, EDF) vs general-purpose (CFS). Priority-based preemptive scheduling as the basis of RT
- Synchronization and locks — Priority inheritance for mutex. The problem of priority inversion is solved at the level of synchronization primitives
- Deadlocks — In RT systems, deadlock is especially dangerous - it leads to a deadline miss. Priority Ceiling Protocol prevents deadlocks
- Linux internals — PREEMPT_RT patches change the Linux kernel: threaded IRQ, rt_mutex, high-resolution timers. Deep understanding of kernel internals
Вопросы для размышления
- Why did Mars Pathfinder use VxWorks RTOS instead of regular Linux? What requirements for space missions make RT critical?
- An autonomous vehicle scenario: the camera captured a pedestrian. How to distribute RT priorities between tasks: object detection, path planning, brake control?
- Trade-off: PREEMPT_RT provides bounded latency but reduces throughput by ~10-15%. When is this acceptable, and when is it not? Compare a web server vs an industrial robot.