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

И.Б. Бурдонов, А.С. Косачев, В.Н. Пономаренко
Препринт Института системного программирования РАН

Назад Оглавление Вперёд

1.2. Планирование, приоритеты

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

В связи с проблемами планирования в ОСРВ изучаются и развиваются два подхода – статические алгоритмы планирования (RMS – Rate Monotonic Scheduling) [LL73] и динамические алгоритмы планирования (EDF – Earliest Deadline First).

RMS используется для формального доказательства условий предсказуемости системы. Для реализации этой теории необходимо планирование на основе приоритетов, прерывающих обслуживание (preemptive priority scheduling). В теории RMS приоритет заранее назначается каждому процессу. Процессы должны удовлетворять следующим условиям:

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

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

В EDF приоритет присваивается динамически, и наибольший приоритет выставляется процессу, у которого осталось наименьшее время выполнения. При больших загрузках системы у EDF имеются преимущества перед RMS.

Во всех системах реального времени требуется политика планирования, управляемая дедлайнами (deadline-driven scheduling). Однако этот подход находится в стадии разработки.

Обычно в ОСРВ используется планирование с приоритетами, прерывающими обслуживание, которое основано на RMS. Приоритетное прерывание обслуживания (preemption) является неотъемлемой составляющей ОСРВ, т.к. в системе реального времени должны существовать гарантии того, что событие с высоким приоритетом будет обработано перед событием более низкого приоритета. Все это ведет к тому, что ОСРВ нуждается не только в механизме планирования на основе приоритетов, прерывающих обслуживание, но также и в соответствующем механизме управления прерываниями. Более того, ОСРВ должна быть способна запрещать прерывания, когда необходимо выполнить критический код, который нельзя прерывать. Длительность обработки прерываний должна быть сведена к минимуму.

ОСРВ должна обладать развитой системой приоритетов. Во-первых, это требуется потому, что система сама может рассматриваться как набор серверных приложений, подразделяющихся на потоки, и несколько высоких уровней приоритетов должно быть выделено системным процессам и потокам. Во-вторых, в сложных приложениях необходимо все потоки реального времени помещать на разные приоритетные уровни, а потоки не реального времени помещать на один уровень (ниже, чем любые потоки реального времени). При этом потоки не реального времени можно обрабатывать в режиме циклического планирования (RRS – round-robin scheduling), при котором каждому процессу предоставляется квант времени процессора, а когда квант заканчивается, контекст процесса сохраняется, и он ставится в конец очереди. Во многих ОСРВ для планирования задач на одном уровне используется RRS. Приоритетный уровень 0 обычно используется для холостого режима.

При планировании на основе приоритетов необходимо решить две обязательные проблемы:

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

Для борьбы с инверсией приоритетов в ОСРВ часто используется механизм наследования приоритетов, однако при этом приходится отказываться от планирования на основе RMS, поскольку приоритеты становятся динамическими.

Назад Оглавление Вперёд