Системы реального времени
Multicore Real-Time Scheduling
Современный автомобиль содержит до 100 ECU. AUTOSAR Adaptive Platform объединяет ABS (ASIL-D), управление трансмиссией (ASIL-C) и навигацию (QM) на одном multicore процессоре. Без cache partitioning и mixed-criticality scheduling ISO 26262 сертификация невозможна - и автомобиль не выйдет на рынок.
- **AUTOSAR (automotive)** - стандарт для ECU, определяет требования к multicore scheduling и memory protection для ISO 26262
- **Intel RDT (Resource Director Technology)** - CAT + MBA (Memory Bandwidth Allocation) для контроля cache и памяти в cloud и embedded RTS
- **ARINC 653 (avionics)** - spatial/temporal partitioning в IMA (Integrated Modular Avionics), прародитель mixed-criticality концепции
Partitioned Scheduling: задача привязана к ядру
Переход от одноядерного к многоядерному RTS - не просто «больше ядер». Общие кеши L2/L3 создают **cache interference**: задача на ядре 0 вытесняет данные задачи на ядре 1 из shared L3. Это делает WCET (Worst-Case Execution Time) непредсказуемым - основу RTS-анализа. **Partitioned scheduling** решает проблему: каждая задача статически привязана к одному ядру, каждое ядро работает как независимый одноядерный планировщик.
**Bin Packing при partitioned scheduling:** оптимальное распределение задач по ядрам - NP-hard. На практике используют эвристики: First Fit Decreasing (FFD), Worst Fit. Критерий - утилизация CPU не превышает schedulability bound (обычно ≤ 69% для RM на каждом ядре).
Главное преимущество partitioned scheduling перед global:
Global Scheduling: Dhall's Effect и пределы утилизации
**Global scheduling** позволяет задачам мигрировать между ядрами - планировщик выбирает m наиболее приоритетных задач из глобальной очереди для m ядер. Гибкость высока, но утилизация ограничена неожиданно: **Dhall's Effect** показывает, что G-EDF не гарантирует schedulability даже при утилизации близкой к 1.
| Подход | Утилизация bound | WCET предсказуемость | Миграция задач |
|---|---|---|---|
| Partitioned (RM) | ≤ 69% на ядро | Высокая | Нет |
| Global EDF (G-EDF) | ≤ m - (m-1)·u_max | Низкая | Да (overhead) |
| Partitioned EDF | ≤ 100% на ядро (теория) | Высокая | Нет |
| Semi-partitioned | Компромисс | Средняя | Ограниченная |
Dhall's Effect показывает, что G-EDF может не справиться даже при утилизации близкой к 1. Почему?
Mixed-Criticality Systems: разные гарантии для разных задач
Современный automotive ECU объединяет задачи разной критичности: ABS (safety-critical, ASIL-D), навигация (non-critical), мультимедиа (best-effort). **Mixed-Criticality Systems (MCS)** формализуют это: задачи имеют уровень критичности, и под перегрузкой менее критичные задачи могут быть сброшены.
**Ключевая идея MCS:** вместо worst-case планирования для ВСЕХ задач (пессимистично), используем оптимистичный WCET в нормальном режиме и переключаемся на safety mode только при реальной перегрузке. Это позволяет разместить больше задач на одном процессоре.
В Mixed-Criticality системе при переходе в HI-режим что происходит с LO-criticality задачами?
Cache Partitioning: изоляция кеша для предсказуемого WCET
Общий L3 кеш - главный источник непредсказуемости WCET в multicore системах. Задача на ядре 0 загружает свои данные в L3; задача на ядре 1 вытесняет их своими. При cache-intensive задачах WCET с interference в 10 раз выше, чем без. **Cache partitioning** разделяет кеш между ядрами, устраняя interference.
| Метод | Hardware требования | Гранулярность | Применение |
|---|---|---|---|
| Intel CAT | Intel Xeon с RDT | Cache ways (16-32) | Server RTS, automotive on x86 |
| Page Coloring | Нет (software) | Cache sets | Embedded Linux RTOS |
| WCSA Analysis | Нет | Аналитический | Статический WCET анализ |
**AUTOSAR на практике:** ISO 26262 (automotive safety) требует доказательства отсутствия interference между ASIL-D и QM задачами. Intel CAT или Page Coloring - стандартные инструменты для получения этого доказательства. Без cache partitioning ASIL-D сертификация на multicore процессоре невозможна.
На многоядерном процессоре можно просто запустить N одноядерных RTOS на N ядрах без дополнительных мер.
Shared caches (L2/L3), DRAM bus contention и interconnect interference делают WCET непредсказуемым без cache partitioning и careful memory scheduling. Прямое масштабирование одноядерного RTOS на multicore нарушает RTS гарантии.
Одноядерный WCET анализ предполагает изолированную систему. В multicore common resources (кеш, память, шина) создают contention - WCET задачи зависит от активности соседних ядер, что делает timing анализ невозможным без дополнительных мер.
Зачем нужен cache partitioning в safety-critical multicore системах?
Multicore Real-Time Scheduling
- **Partitioned scheduling:** задача привязана к ядру; детерминированный WCET; назначение = NP-hard bin packing
- **Global scheduling (G-EDF):** задачи мигрируют; Dhall's Effect ограничивает утилизацию; высокий overhead миграции
- **Mixed-Criticality:** два WCET на задачу (LO/HI); при перегрузке LO задачи сбрасываются; Vestal model - основа AUTOSAR
- **Cache partitioning:** Intel CAT или Page Coloring; устраняет interference; обязательно для ASIL-D сертификации на multicore
Связанные темы
Multicore RTS строится на одноядерных алгоритмах планирования и теории schedulability.
- Priority Inversion и протоколы — На multicore priority inversion сложнее из-за shared locks и миграции
- Rate Monotonic Scheduling — RM schedulability analysis применяется к каждому ядру в partitioned схеме
Вопросы для размышления
- Почему Dhall's Effect делает G-EDF неприменимым для тяжёлых задач с высокой утилизацией, и как semi-partitioned scheduling пытается решить этот компромисс?
- Как Mixed-Criticality scheduling меняет традиционный подход к WCET анализу - почему два разных WCET лучше одного консервативного?
- Каковы trade-offs между Intel CAT и Page Coloring для cache partitioning в safety-critical embedded системах?