Worst-Case Execution Time

1996 год. Ракета Ariane 5, первый полёт. 37 секунд после старта - взрыв. Причина: переполнение 16-битного целого числа в программе инерциальной навигации, скопированной с Ariane 4. Код работал отлично 10 лет - но Ariane 5 летела быстрее. Один worst-case сценарий, не предусмотренный при тестировании. 500 миллионов долларов и десятки лет работы - в труху за 37 секунд. WCET-анализ существует именно для того, чтобы таких сценариев не пропускать.

• **Airbus:** каждая задача Flight Control Computer проходит формальный WCET-анализ через aiT; без этого самолёт не получит сертификат
• **Automotive (ISO 26262):** WCET-анализ обязателен для ASIL-D (наивысший уровень безопасности) - автопилоты, ABS
• **SpaceX:** Falcon 9 использует Linux, но с тщательным профилированием и margins для timing каждой задачи

От сбоя Ariane 5 до индустриальных стандартов WCET

После катастрофы Ariane 5 в 1996 году и нескольких других инцидентов с safety-critical системами индустрия осознала: тестирование не даёт гарантий для hard RT. В 1999 году Lunqvist и Stenstrom формально описали timing anomalies - парадоксы кешей, которые делают простой компонентный анализ некорректным. В 2000-е появились промышленные инструменты: aiT (AbsInt, 2000), Bound-T, Chronos. DO-178C (2011) закрепил требования к WCET-анализу для авиации. ISO 26262 (2011) - для automotive. Сегодня WCET-анализ - обязательный шаг сертификации любой safety-critical системы класса A/SIL-4.

Предварительные знания

• Task Scheduling: Rate Monotonic

Что такое WCET

Для schedulability analysis нужен ответ: «сколько **максимально** займёт эта задача?» Не в среднем, не обычно - **в самом худшем случае**. Это **WCET** (Worst-Case Execution Time) - верхняя граница времени выполнения задачи на данном процессоре.

**WCET зависит от входных данных и состояния hardware.** Один и тот же код может выполняться за 50 мкс (кеш горячий, branch predicted) или 500 мкс (cache cold, branch mispredicted, TLB miss). WCET - максимум по ВСЕМ возможным входам и состояниям hardware.

Измеренный максимум (HWMET) - **не WCET!** Это нижняя граница WCET. Реальный worst-case может быть значительно выше и проявиться раз в миллион запусков - именно тогда, когда критично. Для hard RT нужен гарантированный WCET, а не «я тестировал 1000 раз и не видел дольше».

Статический анализ WCET

**Статический анализ** вычисляет WCET без запуска программы. Анализируется код (какие пути выполнения возможны), модель процессора (сколько тактов на каждую инструкцию) и состояние памяти (кеш, pipeline). Результат - **доказанная** верхняя граница.

**aiT** (AbsInt) - ведущий промышленный инструмент статического WCET-анализа. Используется в авиации (Airbus), автомобилях (BMW, Daimler), космосе (ESA). Поддерживает модели конкретных процессоров: ARM Cortex-M, PowerPC e500, LEON3. Результат: «WCET задачи X на процессоре Y <= 347 мкс» - формальная гарантия.

Ограничение статического анализа: он даёт **пессимистичную** оценку. WCET_analyzed >= WCET_real. Чем сложнее процессор (out-of-order, speculative execution), тем больше разрыв. Для простых ARM Cortex-M разрыв ~10-20%, для Intel x86 - может быть 5-10x.

Измерительный подход

Статический анализ дорог и сложен. Альтернатива - **измерение**: запускаем код много раз с разными входами и замеряем время. Получаем HWMET (максимальное наблюдённое). Проблема: нет гарантии, что покрыли worst-case. Поэтому чистое измерение - не для hard RT.

**MBPTA** (Measurement-Based Probabilistic Timing Analysis) - компромисс: измерения + теория экстремальных значений (EVT). Экстраполирует распределение хвоста для оценки вероятности P(exec_time > T) < 10^-9. Используется в ISO 26262 (automotive). Не формальная гарантия, но статистически обоснованная.

На практике большинство automotive RT-систем используют гибридный подход: измерения для bulk оценки + статический анализ для критических путей + запасы (margins). Чисто формальный анализ требуется только для высших уровней безопасности (DAL-A в авиации).

Аномалии timing в современных процессорах

Современные процессоры полны оптимизаций, которые делают timing **непредсказуемым**: кеши, pipeline, branch prediction, out-of-order execution, speculative execution. Каждая из этих оптимизаций - nightmare для WCET-анализа.

**Timing anomalies** - парадоксальные ситуации, когда ускорение одной части программы замедляет всю программу. Впервые описаны Lunqvist & Stenstr (1999). Они делают **компонентный анализ** (WCET = sum of worst-case per instruction) **некорректным**. Нужен анализ всей системы целиком.

Поэтому в критичных RT-системах используют **простые процессоры**: ARM Cortex-M (in-order, no cache) вместо Intel i7 (out-of-order, 3 уровня кеша, speculative). Простой процессор медленнее, но **анализируемый**. Время выполнения предсказуемо.

Тренд **WCET-aware hardware**: процессоры, спроектированные для предсказуемого timing. PRET (PRecision-Timed) архитектура гарантирует fixed-latency для каждой инструкции. Scratchpad memory вместо кеша (программист контролирует, что в быстрой памяти). Пока - исследования, но потребность растёт с развитием автопилотов.

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

• **WCET** - верхняя граница времени выполнения; HWMET (наблюдённый максимум) - лишь нижняя граница WCET
• **Статический анализ** даёт формально доказанный WCET, но пессимистичный; нужна модель процессора
• **Измерения** дешевле, но не гарантируют; MBPTA даёт статистические гарантии
• **Timing anomalies** (кеш, pipeline, speculation) создают 5-20x разброс; простые процессоры предсказуемее

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

WCET - мост между hardware и RT-планированием:

• Планирование: Rate Monotonic — WCET - входной параметр для schedulability analysis
• Что такое RT-системы — WCET определяет, какие дедлайны достижимы
• Компьютерная архитектура — Cache, pipeline, branch prediction - источники timing непредсказуемости

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

• Почему кеш - одновременно великое изобретение для производительности и nightmare для RT-систем?
• Если статический анализ даёт WCET = 500 мкс, а измерения - max 100 мкс, стоит ли «сжимать» WCET? Какие риски?
• Вернёмся к началу: как инженер Airbus доказывает WCET для программы на процессоре с cache и branch prediction?

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

• rts-02 — Rate Monotonic schedulability использует WCET как входной параметр
• rts-01 — Понятие hard/soft RT определяет требуемую строгость WCET-анализа
• ca-01 — Cache, pipeline, branch prediction - источники timing непредсказуемости
• par-01 — Параллельные задачи и timing interference - связанная проблема
• alg-02-space