Планирование реального времени

Планирование реального времени — это совокупность методов и алгоритмов диспетчеризации задач, используемых в операционных системах реального времени (ОСРВ) и встраиваемых системах, где критически важно гарантировать выполнение вычислительных операций в строго определённые временные интервалы. В отличие от обычных систем общего назначения, где основная цель — максимизация пропускной способности или минимизация среднего времени отклика, системы реального времени ориентированы на предсказуемость и детерминизм: каждая задача должна быть завершена до наступления своего дедлайна (крайнего срока).

Основные понятия и классификация

Задачи реального времени

Задача (или поток) в контексте планирования реального времени характеризуется следующими параметрами:

Время поступления (release time) — момент, когда задача становится доступной для выполнения.
Время выполнения (execution time) — время, необходимое для полного выполнения задачи при отсутствии прерываний.
Дедлайн (deadline) — крайний срок, к которому задача должна быть завершена.
Период (period) — для периодических задач интервал между последовательными запусками.

Типы систем по жёсткости временных ограничений

Жёсткое реальное время (hard real-time) — пропуск дедлайна считается катастрофическим отказом системы. Примеры: системы управления двигателем автомобиля, автопилоты, медицинские имплантаты.
Мягкое реальное время (soft real-time) — пропуск дедлайна допустим, но снижает качество работы. Примеры: видеоплееры, онлайн-игры, системы видеоконференций.
Твёрдое реальное время (firm real-time) — пропуск дедлайна не приводит к катастрофе, но результат задачи становится бесполезным. Примеры: системы обработки данных в реальном времени с отбрасыванием устаревших пакетов.

Классификация задач

Периодические — запускаются через строго равные интервалы времени. Составляют основу большинства систем управления.
Спорадические — запускаются в случайные моменты, но с минимальным известным интервалом между поступлениями.
Апериодические — запускаются нерегулярно, без гарантированного минимального интервала.

Алгоритмы планирования

Статические (офлайн) алгоритмы

Расписание составляется до начала работы системы на основе полного знания о задачах. Подходит для жёстких систем с фиксированным набором задач.

Rate-Monotonic Scheduling (RMS) — приоритет назначается обратно пропорционально периоду задачи: чем короче период, тем выше приоритет. Является оптимальным статическим алгоритмом для периодических задач с независимыми дедлайнами, равными периодам.
Deadline-Monotonic Scheduling (DMS) — приоритет назначается обратно пропорционально длине дедлайна. Более гибкий, чем RMS, так как дедлайн может быть меньше периода.

Динамические (онлайн) алгоритмы

Приоритеты задач определяются в процессе выполнения на основе текущих параметров.

Earliest Deadline First (EDF) — в каждый момент выполняется задача с ближайшим дедлайном. Является оптимальным динамическим алгоритмом для однопроцессорных систем. Позволяет достичь загрузки процессора до 100% при условии, что суммарное время выполнения задач не превышает доступного времени.
Least Slack Time First (LST) — приоритет отдаётся задаче с наименьшим запасом времени (slack), то есть разницей между дедлайном и оставшимся временем выполнения. Требует больше вычислительных ресурсов для оценки запаса.

Алгоритмы на основе вытеснения и кооперативные

Вытесняющее планирование (preemptive) — текущая задача может быть прервана более приоритетной. Обеспечивает лучшую реакцию на критичные события, но увеличивает накладные расходы на переключение контекста.
Кооперативное планирование (non-preemptive) — задача выполняется до завершения или до явного освобождения процессора. Проще в реализации, но может приводить к блокировкам высокоприоритетных задач.

Проблемы и ограничения

Инверсия приоритетов

Ситуация, когда низкоприоритетная задача удерживает ресурс, необходимый высокоприоритетной задаче, в результате чего средняя задача выполняется раньше высокой. Для решения используется протокол наследования приоритетов (Priority Inheritance Protocol) или протокол потолка приоритетов (Priority Ceiling Protocol).

Проблема перегрузки

При превышении суммарной загрузки процессора (обычно более 69–100% в зависимости от алгоритма) гарантии выполнения дедлайнов нарушаются. В жёстких системах применяется анализ наихудшего времени выполнения (Worst-Case Execution Time, WCET) и тесты на планируемость (schedulability test).

Взаимоблокировки (deadlocks) и гонки данных

Требуют применения механизмов синхронизации (семафоры, мьютексы) и осторожного проектирования, чтобы не нарушить временные ограничения.

Применение

Промышленная автоматизация

Программируемые логические контроллеры (ПЛК) и системы управления технологическими процессами (SCADA) используют планирование реального времени для синхронизации датчиков, исполнительных механизмов и логики управления.

Авионика и космическая техника

Бортовые системы самолётов (например, система управления полётом) и космических аппаратов работают в жёстком реальном времени. Используются стандарты ARINC 653 и DO-178C.

Автомобильная электроника

Системы управления двигателем (ECU), антиблокировочные тормозные системы (ABS), подушки безопасности — все требуют детерминированного времени реакции.

Медицинские устройства

Имплантируемые кардиостимуляторы, инфузионные насосы, аппараты искусственной вентиляции лёгких — ошибка планирования может привести к летальному исходу.

Телекоммуникации и мультимедиа

Маршрутизаторы, базовые станции сотовой связи, системы потокового видео — относятся к мягкому реальному времени, но требуют низких задержек и джиттера.

Операционные системы реального времени

Примеры ОСРВ

FreeRTOS — открытая ОСРВ для микроконтроллеров, поддерживает вытесняющее и кооперативное планирование.
VxWorks — коммерческая ОСРВ для встраиваемых систем, используется в авионике и промышленности.
QNX — микроядерная ОСРВ, соответствует стандарту POSIX, применяется в автомобильной электронике и медицинской технике.
RT-Linux — расширение ядра Linux, обеспечивающее жёсткое реальное время за счёт выделенного потока задач.
Zephyr — открытая ОСРВ для IoT-устройств, поддерживает несколько алгоритмов планирования.

Особенности архитектуры

ОСРВ отличаются от систем общего назначения:

Минимальное время обработки прерываний.
Детерминированное время переключения контекста.
Возможность блокировки страниц памяти (запрет подкачки).
Приоритетное планирование с наследованием приоритетов.

Стандарты и нормативные документы

POSIX.1b (IEEE 1003.1b) — стандарт на расширения реального времени для UNIX-подобных систем.
ARINC 653 — стандарт для бортового программного обеспечения авионики, определяет разделение по времени и пространству.
IEC 61508 — функциональная безопасность электрических/электронных/программируемых систем.
ГОСТ Р МЭК 61508 — российский аналог стандарта функциональной безопасности.

Критика и ограничения

Сложность анализа — точное определение наихудшего времени выполнения (WCET) для современных процессоров с кэшами, конвейерами и спекулятивным исполнением крайне затруднительно.
Масштабируемость — классические алгоритмы (RMS, EDF) плохо работают на многоядерных и гетерогенных системах из-за проблем синхронизации и распределения ресурсов.
Энергопотребление — в мобильных и встраиваемых системах требуется баланс между производительностью и энергосбережением, что противоречит детерминизму.
Отсутствие единой теории — для распределённых систем реального времени не существует универсальных методов планирования, гарантирующих выполнение дедлайнов.

Интересные факты

Первые алгоритмы планирования реального времени (RMS) были предложены Чарльзом Лью и Джеймсом Лейландом в 1973 году.
В системах жёсткого реального времени часто используется так называемый «сторожевой таймер» (watchdog timer), который сбрасывает систему, если задача не завершилась вовремя.
В России разработкой ОСРВ занимаются такие компании, как «Астра-Софт» (ОС Astra Linux Special Edition с модулем реального времени) и «Эльбрус» (процессоры с аппаратной поддержкой реального времени).

Источники

Лью К. Л., Лейланд Дж. В. «Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment» (1973).
Буттаццо Дж. «Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications» (3-е издание, 2011).
Копец Х. «Real-Time Systems: Design Principles for Distributed Embedded Applications» (2-е издание, 2011).
ГОСТ Р МЭК 61508-1-2012 «Функциональная безопасность систем электрических, электронных, программируемых электронных, связанных с безопасностью».
Документация FreeRTOS, VxWorks, QNX, Zephyr.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →