Планирование задач в системах реального времени. Понятие оптимального алгоритма планирования. Классификация алгоритмов планирования. Примеры алгоритмов планирования.

Характер возникновения событий на управляемом объекте отражается в следующей классификации задач:

• Периодические задачи

• Спорадические задачи (непериодические задачи с жестким крайним сроком)

• Апериодические задачи (непериодические задачи с мягким крайним сроком)

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

* * * * * * *

| | | | | | |

| * * * * * *

-+---+---+---+---+---+---+---+---+---+---+---+---+---+----> t (у.е.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13

Период может быть больше относительного крайнего срока:

r1 d1 r2 d2 r3 d3 r4 d4 r5

* | * | * | * | *

| | | | | | | | |

| * | * | * | * |

-+---+---+---+---+---+---+---+---+---+---+---+---+---+----> t (у.е.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13

Период может быть меньше относительного крайнего срока:

r1 r2 d1 r3 d2 r4 d3 r5

* * | * | * | *

| | | | | | | |

| | * | * | * |

-+---+---+---+---+---+---+---+---+---+---+---+---+---+----> t (у.е.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13

В последнем случае в один и тот же промежуток времени могут "сосуществовать" несколько экземпляров одной и той же задачи.

В дальнейшем будут использоваться следующие обозначения. {T_j} будет обозначать набор задач. Моменты времени, когда возникает необходимость в выполнении j-ой задачи, будут обозначаться как r_jk. При этом для периодической задачи r_j1 будет называться фазой задачи. Периодическая задача будет обозначаться как T_j[φ_j, p_j, e_j, D_j], где

• j - номер задачи

• φ_j - фаза этой задачи

• p_j - период задачи

• e_j - время исполнения задачи

• D_j - относительный крайний срок задачи

При этом, если фаза задачи равна нулю, задача будет обозначаться как T_j[p_j, e_j, D_j]. Если же еще имеет место равенство периода и относительного крайнего срока, то будет использоваться обозначение T_j[p_j, e_j].

Для периодических задач имеют место следующие определения:

Определение. Система периодических задач называется синхронной, если фазы всех задач равны нулю. В противном случае система называется асинхронной.

Определение. Гиперпериодом системы периодических задач называется наименьшее общее кратное периодов этих задач.

Определение. Коэффициентом использования процессорного времени периодической задачи называется отношение ее времени исполнения к ее периоду:

u_j = e_j/p_j

Определение. Коэффициентом использования процессорного времени системы периодических задач называется сумма отношений времени исполнения каждой задачи к ее периоду:

U = ∑u_j = ∑ e_j/p_j

Задачи могут быть зависимыми и независимыми. Задачи являются зависимыми, если имеет место одна из двух видов зависимостей:

• Критические секции (более подробно - далее)

• Ограничения на порядок исполнения

В противном случае задачи называются независимыми.

Классификация алгоритмов планирования (АП), применяемых в СРВ. Выделяют 2 класса АП:

• Алгоритмы со статическим расписанием (другие названия - off-line, static, clock-driven)

• Алгоритмы с динамическим расписанием (другие названия - on-line)

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

• Алгоритмы со статическими приоритетами

• Алгоритмы с динамическим приоритетами

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

Определение. Расписание называется корректным, если соблюдены все крайние сроки.

Определение. Набор задач {T_j} называется планируемым некоторым АП, если этот АП всегда дает корректное расписание для этого набора задач.

Определение. Оптимальным АП называется такой АП, который для ЛЮБОГО набора задач дает корректное расписание, если таковое вообще существует для данного набора задач.