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

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

Будем рассматривать систему независимых периодических задач {T_j}. Кроме того, будем предполагать, что, вообще говоря, могут иметься еще апериодические и спорадические задачи как некоторые особые случаи.

Расписание для периодических задач представляет собой таблицу, в которой указано, в какой момент времени какую задачу запускать на исполнение. Это расписание составляется на промежуток времени, равный гиперпериоду всех задач. Таким образом, планировщик периодически повторяет последовательность запуска задач, заданную в расписании.

Пример статического расписания. Пусть имеется набор из 4-х задач:

T₁[4,1] T₂[5,1.8] T₃[20,1] T₄[20,2]

Гиперпериод данной системы задач равен 20. На протяжении этого периода первая задача должна получить управление 5 раз, вторая - 4, а третья и четвертая - по одному разу. При этом, естественно, должны быть соблюдены все крайние сроки. Расписание для такой системы задач может выглядеть, например, следующим образом:

Время Задача

---------------------

0 T₁

1 T₃

2 T₂

3.8 I

4 T₁

5 I

6 T₄

8 T₂

9.8 T₁

10.8 I

12 T₂

13.8 T₁

14.8 I

16 T₁

17 I

18 T₂

19.8 I

Здесь I обозначает "задачу" простоя (idle task).

Планировщики рассматриваемого типа, как правило, работают по прерываниям от таймера, а "задачи" при этом представляют собой просто подпрограммы, которые вызываются в нужные моменты из обработчика прерываний.

Поскольку таймеры, как правило, программируются на генерацию прерывания НЕ через какой-то промежуток времени ОТ НАЧАЛА ОТСЧЕТА ВРЕМЕНИ, а на прерывание через какой-то промежуток времени ОТ ТЕКУЩЕГО МОМЕНТА ВРЕМЕНИ, то есть от момента, когда производится программирование, то с практической точки зрения приведенную таблицу удобнее представить в ином виде, а именно, вместо промежутков времени от начала цикла помещать в нее промежутки времени "относительные", от одного прерывания до другого (в рамках цикла). Соответствующим образом модифицированная таблица для приведенного примера набора задач будет выглядеть следующим образом:

Номер Время Задача

---------------------

0 0.2 T₁

1 1 T₃

2 1 T₂

3 1.8 I

4 0.2 T₁

5 1 I

6 1 T₄

7 2 T₂

8 1.8 T₁

9 1 I

10 1.2 T₂

11 1.8 T₁

12 1 I

13 1.2 T₁

14 1 I

15 1 T₂

16 1.8 I

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

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

Далее мы рассмотрим 2 разновидности планировщиков с динамическими приоритетами:

• EDF (earliest deadline first) - приоритет задачам назначается по принципу "в каждый момент времени наивысший приоритет имеет та задача, у которой осталось меньше всего времени до крайнего срока".

• LLF (least laxity first) - приоритет задачам назначается по принципу "в каждый момент времени наивысший приоритет имеет задача с наименьшим запасом времени". Понятие запаса времени будет определено чуть позже.

При этом имеются 2 модификации алгоритма EDF:

• с вытесненением задач

• без вытеснения задач

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