Планирование задач

ПЛАНИРОВАНИЕ ЗАДАЧ
Проблема планирования задач
в многозадачных системах задачи (процессы, потоки) вынуждены делить между
собой процессорное время;
в системах реального времени, где важно ещё и время получения результата,
задачи «не могут ждать» слишком долго;
необходим алгоритм, который позволил бы поделить процессорное время
между задачами так, чтобы каждая из них смогла выполниться.

ПЛАНИРОВАНИЕ ЗАДАЧ
Виды алгоритмов планирования
в зависимости от того, какой тип многозадачности реализуется в системе,
алгоритмы планирования можно разделить на вытесняющие и невытесняющие.
АЛГОРИТМЫ ПЛАНИРОВАНИЯ
НЕВЫТЕСНЯЮЩИЕ
ВЫТЕСНЯЮЩИЕ
СТАТИЧЕСКИЕ ПРИОРИТЕТЫ
ДИНАМИЧЕСКИЕ ПРИОРИТЕТЫ

ПЛАНИРОВАНИЕ ЗАДАЧ
Невытесняющие алгоритмы планирования
неприоритетные алгоритмы не находят применения в системах реального
времени, так как не позволяют системе гибко реагировать на возникающие события.
наиболее простым неприоритетным алгоритмом (без вытеснения)
является циклическая очередь;
задачи выполняются в порядке их поступления, выполнившаяся или новая задача
встаёт в конец очереди.
while(1)
{
Task_A();
Task_B();
Task_C();
Task_D();
}

ПЛАНИРОВАНИЕ ЗАДАЧ
Невытесняющие алгоритмы планирования
более совершенным вариантом является алгоритм «кратчайшая задача - первая»;
«Кратчайшая задача - первая»:
Циклическая очередь:

ПЛАНИРОВАНИЕ ЗАДАЧ
Вытесняющие алгоритмы планирования
наиболее популярным алгоритмом является алгоритм с разделением времени
(«time-slicing»);
идея этого алгоритма состоит в том, что каждой задаче отводится свой квант
процессорного времени, по истечении которого активизируется планировщик и
переключает задачу на другую;
подобные алгоритмы широко применяются в ОС общего назначения ввиду
своей простоты.

ПЛАНИРОВАНИЕ ЗАДАЧ
Условие планируемости системы
для планирования периодических задач существуют более эффективные
алгоритмы, учитывающие приоритеты, блокировку задач, активно
использующие вытеснение;
однако такие алгоритмы могут не работать при высокой загрузке системы;
если система перегружена, то она может не поддаваться планированию ни одним
известным алгоритмом.

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS
RMS – rate-monotonic scheduling;
приоритет задачи обратно пропорционален длительности периода;
дэдлайн каждой задачи должен совпадать с периодом активизации;
задачи должны быть независимыми;
задачи должны быть вытесняемыми;
время выполнения задачи на каждом периоде должно быть одинаково.

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS
Рассмотрим систему с тремя периодическими задачами A, B и C (и относительно
слабым процессором ☺).

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS
При высоких нагрузках на систему RMS начинает «фейлить» и не может нормально
работать.

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS
Очевидно, для RMS общее условие планируемости не всегда точно показывает
возможность его надёжной работы.
Необходимо точно установить предельную загрузку системы для применения RMS
(Чунг Лью, Джеймс Лейланд)
UB-тест (utilisation bound test)

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS
очевидно, что UB-тест является достаточным, но не необходимым условием для
понимания возможности применения RMS
необходим иной критерий для определения точной возможности применения RMS

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS
необходимым условием является прохождение RT-теста (response time test);
RT-тест предложен Паритошем Пандья и Матайей Джозефом и основан на
следующей идее:
рассматривается ситуация наибольшего риска несоблюдения
дэдлайнов – когда все задачи активизируются одновременно (так называемый
критический момент);
если все задачи прошли тест, то система поддаётся планированию;
если система поддаётся планированию в наихудшем случае, то она будет
поддаваться планированию и в любом другом случае.

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS
время отклика для каждой из задач вычисляется по рекуррентной формуле:
множество задач с приоритетом, большим,
чем у i-ой
критерии остановки вычислений:

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS
применим RT-тест к нашим примерам;
сначала для случая, когда RMS работает:
для задачи А:

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS
для задачи B:

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS
для задачи C:
Все задачи прошли тест, следовательно, вся система поддаётся планированию

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS
теперь рассмотрим случай, когда RMS не работал;
для задачи А:

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS
для задачи B:

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: RMS
для задачи C:

ПЛАНИРОВАНИЕ ЗАДАЧ
Планирование периодических задач: EDF
алгоритм EDF (Earliest Deadline First) является алгоритмом с динамическими
приоритетами;
в отличие от RMS приоритет задачи зависит от её относительного дедлайна – того
дедлайна, который отсчитывается от момента начала работы планировщика;
EDF является оптимальным алгоритмом: если система в принципе поддаётся
планированию, то она может быть обслужена алгоритмом EDF даже при самых
высоких нагрузках;