Общее планирование реального времени

Планирование однородных процессов

В качестве однородных процессов можно рассмотреть видео сервер с несколькими видео потоками (несколько пользователей смотрят фильм).

Т.к. все процессы важны можно использовать циклическое планирование.

Но так как количество пользователей и размеры кадров могут меняться, для реальных систем он не подходит.

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

Планировщик должен знать:

− частота, с которой должен работать каждый процесс

− объем работ, который ему предстоит выполнить

− ближайший срок выполнения очередной порции задания

Рассмотрим пример из трех процессов (рис.15).

Процесс А запускается каждые 30мс, обработка кадра 10мс

Процесс В частота 25 кадров, т.е. каждые 40мс, обработка кадра 15мс

Процесс С частота 20 кадров, т.е. каждые 50мс, обработка кадра 5мс

Проверяем, можно ли планировать эти процессы.

10/30 + 15/40 + 5/50 = 0.808 < 1

Условие выполняется, планировать можно.

Будем планировать эти процессы статическим (приоритет заранее назначается каждому процессу) и динамическим методами.

2.1. Статический алгоритм планирования RMS (Rate Monotonic Scheduling)

Процессы должны удовлетворять условиям:

− Процесс должен быть завершен за время его периода

− Один процесс не должен зависеть от другого

− Каждому процессу требуется одинаковое процессорное время на каждом интервале

− У непериодических процессов нет жестких сроков

− Прерывание процесса происходит мгновенно

Приоритет в этом алгоритме пропорционален частоте.

Процессу А он равен 33 (частота кадров)

Процессу В он равен 25

Процессу С он равен 20

Процессы выполняются по приоритету.

2.2. Динамический алгоритм планирования EDF (Earliest Deadline First)

Наибольший приоритет выставляется процессу у которого осталось наименьшее время выполнения (рис.16).

При больших загрузках системы EDF имеет преимущества.

Рассмотрим пример, когда процессу А требуется для обработки кадра 15мс.

Проверяем, можно ли планировать эти процессы.

15/30 + 15/40 + 5/50 = 0.975<1

Загрузка системы 97.5%

Алгоритм планирования RMS терпит неудачу.