Real-Time системы

1997 год. Mars Pathfinder на поверхности Марса начинает внезапно перезагружаться. Миссия за 265 миллионов под угрозой. Причина? Priority inversion - баг планировщика RTOS. Инженеры NASA загружают патч через радио (300 млн км!), включают priority inheritance, ровер работает. Real-Time системы - это не просто «быстрый код». Это математические гарантии, что критичная задача выполнится ДО deadline. Пропуск deadline в airbag = смерть. В nuclear reactor = катастрофа. RT OS спасают жизни каждый день.

• **Mars Pathfinder (1997):** Priority inversion роняла систему на Марсе. Патч с priority inheritance спас миссию. Классический case study FAANG интервью.
• **Automotive safety (Tesla, Waymo):** PREEMPT_RT Linux для ADAS (camera → decision за <10ms). ISO 26262 ASIL D требует формального доказательства WCET.
• **Medical devices (pacemakers):** FreeRTOS на ARM Cortex-M. Hard RT гарантии: сердечный импульс ТОЧНО через 1000ms ±10μs. Пропуск = остановка сердца.

Цели урока

• Различать hard vs soft real-time; deadline vs throughput как метрики
• Real-time schedulers: Rate Monotonic, EDF (Earliest Deadline First)
• Priority inversion: проблема, priority inheritance, priority ceiling protocol
• PREEMPT_RT patch: spinlock → mutex, threaded IRQs, превращение Linux в RTOS
• WCET (Worst Case Execution Time) analysis и почему этот анализ нетривиален

Real-Time планирование

**Real-Time Operating System (RTOS)** - это операционная система, гарантирующая выполнение задач в строго определённые временные рамки. Отличие от обычных OS не в скорости, а в **детерминированности** - предсказуемости времени выполнения.

Real-time системы делятся на два типа: **Hard Real-Time** - пропуск deadline катастрофичен (авиация, медицина, ядерные реакторы). Пример: пропуск такта управления турбиной самолёта на 1мс → отказ двигателя. **Soft Real-Time** - пропуск deadline нежелателен, но не фатален (видеостриминг, VoIP). Пример: задержка пакета видео на 50мс → артефакт на экране, но система работает.

**RT планировщики используют priority-based preemptive scheduling.** Каждой задаче назначается приоритет. Планировщик всегда выполняет задачу с наивысшим приоритетом. Если приходит более приоритетная задача - текущая немедленно вытесняется (preemption).

**Linux RT policies:** - **SCHED_FIFO:** Fixed priority, no time slicing. Выполняется пока не заблокируется или не придёт более приоритетная задача. - **SCHED_RR:** Round-Robin с фиксированным приоритетом. Задачи с одинаковым приоритетом чередуются через time quantum. - **SCHED_DEADLINE:** Earliest Deadline First (EDF). Планировщик выбирает задачу с ближайшим deadline.

**Rate Monotonic Scheduling (RMS)** - классический алгоритм для периодических RT задач. Правило: задачи с меньшим периодом получают более высокий приоритет. Математически доказано оптимальным для static priority scheduling при определённых условиях.

Priority Inversion

**Priority Inversion (инверсия приоритетов)** - катастрофическая проблема RT систем, когда высокоприоритетная задача блокируется низкоприоритетной через shared resource. Может привести к пропуску deadline и отказу системы.

**Priority Inheritance Protocol (PIP)** - решение priority inversion. Когда высокоприоритетная задача блокируется на mutex, владелец mutex временно наследует её приоритет. После unlock приоритет возвращается.

**Решения Priority Inversion:** 1. **Priority Inheritance:** владелец mutex наследует приоритет заблокированной задачи 2. **Priority Ceiling Protocol:** mutex имеет "потолок" приоритета. Владелец получает этот приоритет при захвате 3. **Lock-Free алгоритмы:** избегаем mutex через atomic операции (но сложнее в реализации)

**Priority Ceiling Protocol (PCP)** - более агрессивный подход. Каждому mutex назначается ceiling priority (максимальный приоритет задач, использующих mutex). Задача может захватить mutex только если её приоритет выше ceiling всех уже захваченных mutex в системе.

PREEMPT_RT Linux

**PREEMPT_RT (Real-Time preemption patch)** - набор патчей, превращающих стандартный Linux в Hard Real-Time систему. Цель: сделать ядро полностью вытесняемым (preemptable), убрать unbounded latency источники.

Обычный Linux - General-Purpose OS. Scheduler оптимизирует throughput и fairness, но не гарантирует latency. Например, spin_lock в ядре отключает preemption на непредсказуемое время. Обработчики прерываний (IRQ) блокируют систему.

**Ключевые изменения PREEMPT_RT:** 1. **Spinlocks → rt_mutex:** В vanilla Linux spin_lock крутится в цикле, отключая preemption. В RT заменяется на sleeping mutex с priority inheritance. 2. **Threaded IRQ:** Обработчики прерываний выполняются в kernel threads (потоки ядра) с приоритетом. Можно вытеснить IRQ handler более важной RT задачей. 3. **High-resolution timers:** Точность до microseconds вместо jiffies (обычно 1-10ms).

**Уровни preemption в 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) Настраивается при компиляции ядра через `make menuconfig`.

**Ограничения PREEMPT_RT:** - **Throughput vs Latency trade-off:** RT оптимизирует worst-case, жертвуя average-case пропускной способностью. Для серверов с тысячами подключений это минус. - **Драйверы:** Не все драйверы совместимы с RT. Проприетарные драйверы (Nvidia) часто отключают preemption. - **Сложность отладки:** Timing bugs проявляются только под нагрузкой, воспроизвести сложно.

Анализ latency и worst-case

**Latency analysis** - критический этап разработки RT систем. Недостаточно просто измерить среднюю задержку - нужно математически доказать, что worst-case execution time (WCET) укладывается в deadline.

Источники latency в системе: 1. **Interrupt latency:** Время от прерывания до начала обработчика 2. **Preemption latency:** Время от запроса вытеснения до context switch 3. **Scheduling latency:** Время от пробуждения до получения CPU 4. **Critical section latency:** Время блокировки на locks

**Stress testing для worst-case:** Недостаточно измерить latency на idle системе. Нужна нагрузка: - **CPU stress:** `stress-ng --cpu 8` - загрузить все ядра - **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` - сетевые прерывания

**WCET (Worst-Case Execution Time) analysis:** Для safety-critical систем (авиация, медицина) нужен **статический анализ WCET** - математическое доказательство верхней границы времени выполнения. Инструменты: - **aiT WCET Analyzer:** Static analysis на уровне машинного кода - **RapiTime:** Hybrid analysis (статика + трассировка) - **Bound-T:** Open-source WCET для embedded Требуется для сертификации (DO-178C для авиации, IEC 61508 для промышленности).

**Deadline Miss handling:** Что делать если RT задача не уложилась в deadline? 1. **Logging:** Записать событие для анализа (через lock-free ring buffer) 2. **Degradation:** Перейти в safe mode (например, автомобиль замедляется) 3. **Failover:** Переключиться на резервную систему 4. **Panic:** Для Hard RT (airbag) лучше crash чем неверное решение

Ключевые идеи

• **RT ≠ Fast. RT = Deterministic.** RTOS гарантирует worst-case latency, а не average. Медленная RTOS на микроконтроллере надёжнее суперкомпьютера без RT.
• **Priority Inversion - убийца RT систем.** High priority задача блокируется через shared resource. Решение: Priority Inheritance Protocol (владелец mutex наследует приоритет заблокированной задачи).
• **PREEMPT_RT превращает Linux в Hard RT.** Spinlocks → rt_mutex, IRQ → threads, priority inheritance везде. Latency <100μs вместо milliseconds.
• **WCET analysis критичен для safety.** Для авиации/медицины нужно математически доказать верхнюю границу времени выполнения. Static analysis + stress testing под нагрузкой.

Связанные темы

Real-Time системы строятся на фундаменте OS планирования и синхронизации:

• CPU Scheduling — RT планировщики (SCHED_FIFO, RMS, EDF) vs general-purpose (CFS). Priority-based preemptive scheduling как основа RT
• Синхронизация и locks — Priority inheritance для mutex. Проблема priority inversion решается на уровне примитивов синхронизации
• Deadlocks — В RT системах deadlock особенно опасен - приводит к deadline miss. Priority Ceiling Protocol предотвращает deadlocks
• Linux internals — PREEMPT_RT патчи меняют ядро Linux: threaded IRQ, rt_mutex, high-resolution timers. Глубокое понимание kernel internals

Вопросы для размышления

• Почему Mars Pathfinder использовал VxWorks RTOS вместо обычного Linux? Какие требования для космических миссий делают RT критичным?
• Autonomous vehicle: camera захватила пешехода. Как распределить RT приоритеты между задачами: object detection, path planning, brake control?
• Trade-off: PREEMPT_RT даёт bounded latency но снижает throughput на ~10-15%. Когда это приемлемо, а когда нет? Сравни web-сервер vs industrial robot.

Связанные уроки

• rt-01-what-is-realtime