Системы реального времени
Планирование задач: Rate Monotonic
Mars Pathfinder 1997: марсоход начал перезагружаться на Марсе из-за priority inversion. Toyota 2009: отзыв 4 млн автомобилей связан с проблемами RT scheduling. DO-178C требует математического доказательства schedulability для любого самолёта. Формальное планирование задач - не академическая дисциплина, а инженерный инструмент с понятными последствиями.
- **AUTOSAR (автомобили):** стандарт использует RM scheduling; schedulability доказывается при проектировании
- **Mars Pathfinder (1997):** priority inversion чуть не погубила марсоход; priority inheritance спасла миссию
- **Авионика (DO-178C):** формальное доказательство schedulability - обязательное требование сертификации
Предварительные знания
Liu & Layland и рождение RT scheduling theory
Статья «Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment» (1973) написана в MIT при поддержке NASA. Авторов интересовали бортовые системы - задачи с жёсткими дедлайнами на одном процессоре. Статья заложила математический фундамент RT scheduling: понятие utilization bound, доказательство оптимальности RM, анализ schedulability. До публикации инженеры использовали эвристики. После - появился формальный аппарат, который сегодня обязателен в automotive и авиации.
Rate Monotonic Scheduling
Toyota, 2009. Внезапное ускорение Prius привело к отзыву 4 млн автомобилей. Одна из версий: задача управления дроссельной заслонкой не укладывалась в дедлайн из-за неправильного приоритета. В каждом современном автомобиле работают 50-100 задач на одном микроконтроллере: ABS (каждые 5 мс), контроль двигателя (каждые 20 мс), обновление дисплея (каждые 100 мс). Одно ядро. **Rate Monotonic** даёт лаконичный ответ: чем короче период, тем выше приоритет.
**Rate Monotonic** - оптимальный среди алгоритмов с **фиксированными приоритетами**. Теорема Liu & Layland (1973): если набор задач schedulable каким-либо fixed-priority алгоритмом, то он schedulable и через RM. Приоритеты назначаются один раз и не меняются.
Liu & Layland, 1973
Статья C.L. Liu и James Layland «Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment» - одна из самых цитируемых в computer science. Они доказали оптимальность RM и дали простой тест schedulability. Почти все современные RTOS используют RM как базовый алгоритм. Статья написана в MIT при поддержке NASA - авторов интересовали бортовые системы Apollo.
Задачи: T1(period=10, exec=3), T2(period=20, exec=5). U = 3/10 + 5/20 = 0.55. Граница для n=2: 0.828. Schedulable?
Earliest Deadline First
RM тратит до 30% процессора впустую (граница ~0.69 для многих задач). Можно лучше? **EDF** (Earliest Deadline First) - динамический алгоритм: кто ближе к дедлайну, тот и работает. EDF **оптимален** для uniprocessor: если задачи schedulable вообще, EDF найдёт расписание. Это теорема, не эвристика.
| Свойство | Rate Monotonic (RM) | Earliest Deadline First (EDF) |
|---|---|---|
| Приоритеты | Статические (фиксированные) | Динамические (меняются) |
| Оптимальность | Среди fixed-priority | Абсолютная для uniprocessor |
| Utilization bound | ~0.69 (ln 2) для n->inf | 1.0 (100% CPU!) |
| Реализация | Простая (приоритеты раз и навсегда) | Сложнее (пересчёт каждый tick) |
| При перегрузке (U>1) | Предсказуемо: низкие пропускают | Непредсказуемо: domino effect |
| Использование | RTOS: FreeRTOS, VxWorks | Исследования, Linux SCHED_DEADLINE |
**EDF оптимален, но опасен при перегрузке.** Если U > 1 (задач больше, чем CPU может выдержать), RM предсказуемо «роняет» низкоприоритетные задачи, а высокоприоритетные работают. EDF при перегрузке может пропустить дедлайн у **любой** задачи - эффект домино. Поэтому в safety-critical системах часто предпочитают RM.
Linux поддерживает EDF через SCHED_DEADLINE (с ядра 3.14). Задача объявляет runtime, deadline и period, ядро гарантирует выделение CPU. Но в промышленных RTOS (VxWorks, QNX) доминирует fixed-priority: предсказуемость важнее оптимальности.
U = 0.85. RM bound для 5 задач = 0.743. Какой планировщик гарантирует schedulability?
Priority Inversion
4 июля 1997 года марсоход Pathfinder начал случайно перезагружаться на Марсе. Причина: **priority inversion** - низкоприоритетная задача блокировала высокоприоритетную через разделяемый mutex. Один из самых знаменитых багов в истории software engineering. Исправлен командой с Земли - с расстояния 191 млн км.
Mars Pathfinder Bug (1997)
На Pathfinder низкоприоритетный meteorological task захватывал mutex шины данных. Высокоприоритетный bus management task не мог получить mutex. Watchdog timer обнаруживал задержку и перезагружал компьютер. Инженеры JPL починили баг удалённо, включив priority inheritance через команду с Земли. Баг существовал в VxWorks, но не проявился при тестировании - тестирование не покрыло этот timing scenario.
**Priority Inheritance** - реактивный: поднимает приоритет при конфликте. **Priority Ceiling** - проактивный: предотвращает конфликт заранее. Ceiling сложнее в настройке, но гарантирует отсутствие deadlock и ограничивает blocking time до одного критического участка.
HIGH(приоритет 1) ждёт mutex от LOW(приоритет 3). MED(приоритет 2) готов к выполнению. С priority inheritance, кто работает?
Тест schedulability
Авиационный стандарт DO-178C (Boeing, Airbus, все гражданские самолёты). Раздел 6.4: каждая задача RT-системы должна иметь формальное доказательство schedulability. Не «тестирование показало» - именно формальное доказательство. Без него нет сертификации FAA. Без сертификации нет полётов. **Schedulability analysis** - математическое доказательство, что все дедлайны будут выполнены при любых условиях.
| Тест | Тип | Сложность | Точность |
|---|---|---|---|
| Utilization bound (RM) | Достаточный | O(n) | Консервативный (может отвергнуть schedulable) |
| Response Time Analysis (RM) | Точный (необх. и дост.) | Псевдо-полиномиальный | Точный для RM |
| Utilization test (EDF) | Необх. и достаточный | O(n) | Точный для periodic tasks |
| Processor Demand Analysis (EDF) | Точный для sporadic | Экспоненциальный | Точный для EDF |
**Utilization bound** - быстрый, но консервативный: может сказать «нет» на schedulable задачи. **Response Time Analysis** - точный: вычисляет worst-case response time для каждой задачи. Если R_i <= D_i, задача schedulable. RTA - стандартный метод в automotive (AUTOSAR).
В сертифицированных системах (DO-178C для авиации, ISO 26262 для автомобилей) schedulability analysis - **обязательный** этап. Инженер должен формально доказать, что все задачи укладываются в дедлайны при worst-case условиях.
Тесты schedulability предполагают **идеальный процессор**: нет context switch overhead, нет cache miss, нет interrupt jitter. В реальности нужно добавлять запасы (margins). Типичная практика: U < 0.7 для hard RT с запасом на непредвиденное.
EDF всегда лучше RM - он оптимальный и использует CPU на 100%
EDF оптимален для schedulability, но при перегрузке (U > 1) ведёт себя непредсказуемо. RM проще, предсказуемее и безопаснее.
EDF schedulable при U <= 1.0 vs RM при U <= ~0.69 - EDF выигрывает по utilization. Но при кратковременной перегрузке RM предсказуемо жертвует низкоприоритетными задачами, а EDF может пропустить дедлайн у ЛЮБОЙ задачи (domino effect). В safety-critical системах предсказуемость отказа важнее максимальной утилизации. Поэтому VxWorks, QNX и AUTOSAR используют fixed-priority (RM), а не EDF.
Три задачи: T1(5,1), T2(10,3), T3(20,4). U=0.20+0.30+0.20=0.70. RM bound для 3 = 0.780. Гарантированно schedulable?
Ключевые идеи
- **RM:** статические приоритеты по периоду; оптимален среди fixed-priority; bound ~ln(2) approx 0.693
- **EDF:** динамические приоритеты по дедлайну; schedulable при U <= 1.0; оптимален для uniprocessor
- **Priority Inversion:** low блокирует high через mutex; решение: priority inheritance или priority ceiling
- **Schedulability analysis:** формальное доказательство выполнения дедлайнов; обязательно для сертификации
Связанные темы
Планирование RT-задач связано с анализом времени выполнения:
- Что такое RT-системы — Классификация hard/soft/firm определяет требования к планированию
- WCET анализ — Без знания worst-case execution time невозможен schedulability analysis
- Синхронизация — Mutex в RT-системах требует протоколов priority inheritance/ceiling
Вопросы для размышления
- Почему automotive предпочитает RM (не оптимальный) вместо EDF (оптимальный)?
- Как инженеры NASA починили баг priority inversion на Pathfinder, находясь на расстоянии 191 млн км?
- Если U = 0.70 и RM гарантирует schedulability, стоит ли добавлять запас? Почему?
Связанные уроки
- rts-01 — Классификация hard/soft/firm задаёт требования к планированию
- rts-03 — WCET-анализ - без него schedulability analysis невозможен
- par-03 — Mutex в RT-системах требует priority inheritance/ceiling протоколов
- emb-01 — Embedded microcontroller firmware - главная среда запуска RT schedulers
- os-04-scheduling — OS scheduling - общий случай, RT scheduling добавляет deadline-гарантии
- alg-01-big-o — Scheduling algorithms - специализированный класс задач оптимизации распределения ресурсов