Анализ расписания

1996 год. Boeing 777 - первый коммерческий самолёт без механического резерва управления. 100+ задач реального времени, жёсткие дедлайны, нулевое право на ошибку. Математика расписания, разработанная за 23 года до первого полёта, стала единственным способом доказать безопасность 400 пассажиров.

• Boeing 777 и DO-178B Level A - формальное доказательство schedulability как обязательное условие сертификации, не опция
• Mars Exploration Rover - VxWorks с RMS, WCET-анализ каждой задачи управления манипулятором до запуска
• Кардиостимуляторы Medtronic - utilization намеренно удерживается ниже 50% как запас безопасности
• Tesla Autopilot - гибрид RMS для safety-critical слоя и EDF для perception/planning
• TCAS (предупреждение столкновений самолётов) - EDF для максимальной утилизации при критических ситуациях

RMS и DMS: приоритеты из математики

1996 год. Boeing 777 выходит в серийное производство. Первый коммерческий самолёт, полностью сертифицированный по DO-178B: fly-by-wire без механического резерва управления. Пилот двигает ручку - сигнал идёт в компьютер - компьютер двигает рули. 100+ задач управления, каждая со своим периодом и дедлайном. Если хоть одна задача управления закрылками не уложится в 20 мс - система теряет контроль над поверхностями. Вопрос не 'обычно ли укладывается', а 'всегда ли укладывается при любой комбинации нагрузок'. Математика, давшая ответ, была опубликована за 23 года до первого полёта.

Лю и Лейланд, 1973. Статья 'Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment'. Два фундаментальных результата: оптимальный статический алгоритм приоритетов и аналитический порог schedulability. На этих двух результатах летают самолёты, едут марсоходы, работают кардиостимуляторы.

**Rate Monotonic Scheduling (RMS)** - принцип прост до жёсткости: задача с более высокой частотой получает более высокий приоритет. Задача с периодом 10 мс всегда имеет приоритет выше, чем задача с периодом 50 мс. Статически. Навсегда. Без исключений.

RMS - не просто алгоритм, а теорема об оптимальности: если набор задач schedulable хоть каким-то статическим приоритетным алгоритмом - RMS тоже выполнит его. Среди всех фиксированных-приоритетных алгоритмов RMS доминирует. Более сильного статического алгоритма не существует.

**Deadline Monotonic Scheduling (DMS)** закрывает пробел RMS: когда дедлайн не равен периоду ($D_i < T_i$). Система управления антенной: период 50 мс (антенна двигается медленно), но критические данные нужны уже через 15 мс. Приоритет в DMS назначается по дедлайну, а не по периоду. DMS оптимален среди всех статических алгоритмов для случая $D_i \leq T_i$ - тоже теорема.

RMS - частный случай DMS: когда $D_i = T_i$ для всех задач, оба алгоритма дают идентичные приоритеты. В большинстве реальных систем $D_i = T_i$, поэтому в литературе RMS упоминается чаще.

Utilization Bound: граница Лю-Лейланда

Лю и Лейланд дали не только алгоритм - они дали формулу, отвечающую на вопрос 'schedulable ли система?' без единой симуляции. Загрузка каждой задачи: $U_i = C_i / T_i$, где $C_i$ - Worst Case Execution Time, $T_i$ - период. Суммарная загрузка $U = \sum U_i$. Если $U$ не превышает порог - система schedulable по RMS с математической гарантией.

При $n \to \infty$ правая часть стремится к $\ln 2 \approx 0.693$. Это знаменитые 69.3% - нижний предел utilization bound для RMS при любом числе задач. Любая система с $U \leq 0.693$ schedulable по RMS независимо от числа задач.

Главная ловушка: условие **достаточное, не необходимое**. Если $U > n(2^{1/n}-1)$ - это не приговор. Система может быть schedulable - нужен Response Time Analysis. Но если $U \leq$ порогу - гарантия абсолютная. Boeing 777 прошёл сертификацию DO-178B Level A не потому что инженеры прогнали 10 000 сценариев. Потому что посчитали utilization, применили RTA и математически доказали schedulability каждого раздела. Тестирование не даёт гарантии. Анализ - даёт.

Формула Лю-Лейланда предполагает независимые периодические задачи без разделяемых ресурсов. При наличии мьютексов - нужно учитывать блокирующее время (blocking time). Иначе система может промахнуться по дедлайну даже при U < 0.693.

EDF: динамический оптимум

RMS оставляет около 30% процессора незадействованными при большом числе задач. Это цена статических приоритетов. Существует алгоритм без этой цены - и он тоже доказан оптимальным.

**Earliest Deadline First (EDF)** - в каждый момент времени процессор получает задача с ближайшим абсолютным дедлайном. Приоритеты не фиксируются: при каждом событии (активация задачи, завершение, прерывание) планировщик пересчитывает приоритет для каждой готовой задачи. Это динамический алгоритм.

Порог schedulability для EDF - ровно 100%. Если суммарная загрузка не превышает единицы, EDF гарантирует выполнение всех дедлайнов. Никакой алгоритм не может работать с загрузкой выше 100% - это физический предел. EDF его достигает.

Почему же авиация и медицина не перешли на EDF? Цена - поведение при перегрузке. При $U > 1$ (transient overload после аппаратного сбоя) RMS деградирует предсказуемо: низкоприоритетные задачи страдают, высокоприоритетные выживают. Система управления полётом продолжает работать, только с пониженным числом второстепенных функций. EDF при перегрузке ведёт себя хаотично: любая задача может потерять дедлайн. В safety-critical системах контролируемая деградация ценнее теоретического оптимума.

Tesla Autopilot использует гибрид: задачи управления рулевым и тормозами - статические приоритеты (RMS-подобные), задачи восприятия и планирования маршрута - динамическое планирование. Два слоя с разными гарантиями для разных уровней безопасности. Именно такая гибридная архитектура позволяет использовать CPU на 90%+ при сохранении hard deadline гарантий для safety-critical задач.

Response Time Analysis - инструмент когда utilization test не даёт гарантии. Для каждой задачи $i$ итеративно решается уравнение: $R_i^{(k+1)} = C_i + \sum_{j \in hp(i)} \lceil R_i^{(k)} / T_j \rceil C_j$, где $hp(i)$ - задачи с более высоким приоритетом. Итерации сходятся если $R_i \leq D_i$. Если для каждой задачи $R_i \leq D_i$ - система schedulable. RTA сложнее utilization test, но точнее: ловит schedulable системы, которые utilization test отверг.

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

• RMS: статические приоритеты по частоте ($1/T_i$) - оптимален среди всех статических алгоритмов
• DMS: расширение для $D_i < T_i$ - приоритет по дедлайну, не по периоду
• Utilization bound: $U \leq n(2^{1/n}-1) \to \ln 2 \approx 69.3\%$ - достаточное (не необходимое) условие
• EDF: динамические приоритеты по ближайшему дедлайну, schedulable при $U \leq 100\%$ - теоретический оптимум
• RTA ($R_i = C_i + \sum_{j \in hp(i)} \lceil R_i/T_j \rceil C_j$) - точный анализ когда utilization test не достаточен
• В safety-critical системах предсказуемая деградация RMS при перегрузке ценнее оптимальной утилизации EDF

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

Schedulability analysis - центральный инструмент RTS-инженерии, связанный с планировщиком, примитивами и архитектурой:

• Priority Inversion — Следующая проблема после гарантии schedulability - блокировка высокоприоритетной задачи через мьютекс
• RTOS архитектура — Планировщик RTOS реализует RMS/EDF - теория встречается с кодом
• OS планирование CPU — Контрастный пример: throughput-оптимизация vs гарантия дедлайнов

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

• DO-178B требует формального доказательства schedulability, а не тестирования. Почему 'мы прогнали 10 000 тестов без промаха по дедлайнам' не является достаточным доказательством для сертификации авиационного ПО?

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

• rts-04 — Архитектура планировщика RTOS - основа для анализа расписания
• rts-07 — Priority Inversion - следующая проблема после гарантии schedulability
• os-04-scheduling — OS-планирование оптимизирует throughput, RTS-планирование доказывает дедлайны
• emb-05 — FreeRTOS реализует RMS-приоритеты - теория встречается с производственным кодом
• par-01 — Параллелизм и конкуренция задач - контекст для понимания интерференции
• os-01-intro