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

2002 v.0.2.
9. Планирование задач (scheduling)
Задача

A

da

t

t

db

Задача B

I

Задача A

da

t

t

db

Задача B

II

Пропуск deadline

Пример

Deadline не нарушен

2002 v.0.2.
Алгоритм планирования (scheduling algorithm) -

правило, определяющее порядок выполнения задач
Статическое планирование (off-line) – условия активизации задач определяются до начала работы системы
Динамическое планирование (on-line) – условия активизации определяются в процессе работы системы на основе текущих условий
Приоритетное планирование (статическое /динамическое) – в качестве параметра, определяющего порядок активизации задач, выступает приоритет задачи
Предсказуемость (predictability) - для всех действий определимы временные границы их завершения

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

2002 v.0.2.
N1
N2
Nn
Циклический исполнитель (Round Robin)
Таблица обработчиков событий

pt1

. . . .

t2

Статический график активизации событий

t1

tn

N1

N2

Nn

. . . .

pt2

ptn

Обработка 1

Обработка 2

Обработка n

Процедуры обработки

Таймер

1

2

t

t

n

1

2

n

Обработка

t1

t2

tn

t1

t2

tn

p

2002 v.0.2.
Циклический исполнитель (2)
Достоинство – простота

реализации
Недостаток – при большом количестве задач «off-line» планирование может вызвать трудности
Проблема – планирование обработки асинхронных событий
Возможное решение – каждому асинхронному событию i ставится в соответствие момент времени ti, индекс Ni и Обработчик i. Если событие i происходит раньше момента ti, то запоминается факт его возникновения, а обработка активизируется в момент ti; если позже, то активизация осуществляется на следующем цикле
Недостаток решения – большие latency

2002 v.0.2.
Приоритетное планирование
Статические алгоритмы – приоритеты

задач определяются на этапе проектирования (off-line) и не изменяются в процессе работы системы
Динамические алгоритмы – приоритеты задач изменяются в процессе работы (on-line) в зависимости от текущих условий

ОЧЕРЕДЬ ГОТОВЫХ

ПЛАНИРОВЩИК
F = f(α)

RQ

НОВЫЕ ЗАДАЧИ

ДИСПЕТЧЕР

РАЗБЛОКИРОВАННЫЕ
ЗАДАЧИ

F – приоритет задачи, α - параметры задачи, состояние системы

2002 v.0.2.
Rate monotonic (RM) – правило

статического (off-line) назначения приоритетов:
Пусть имеется n независимых периодических задач реального времени (pi - период i-й задачи, Сi – время выполнения в наихудшем случае), у каждой из которых которых значение deadline совпадает с периодом активизации pi
Суммарная загрузка системы в этом случае определяется как

Тогда, если приоритеты задач будут назначены обратно пропорционально их pi , и будет выполнено условие
то выполнение задач будет проходить без нарушения их deadline (1973 год, Liu)

Rate monotonic планирование

R <= n * (2 1/n - 1)

2002 v.0.2.
Задача 1
p1

t


t

pn
Задача n
Задача 2
p2

t

C1
C2
Cn
Высший приоритет
Низший

приоритет

Rate monotonic планирование (2)

<= n * (2 1/n - 1)

2002 v.0.2.
Тест Rate Monotonic
0.69

2002 v.0.2.
Зависимость (*) представляет нижнюю границу

значения R
В случае, когда частоты активизации задач находятся в гармонической зависимости, R = 1
(Гармоническая зависимость – частота активизации любой задачи приложения кратна частоте каждой задачи с меньшей частотой; например - 1Hz, 5Hz, 10Hz, 20Hz)
В большинстве практических случаев R < 0.88

Тест Rate Monotonic (2)

Набор из n периодических задач будет «шедулируемым» (выполнимым) если приоритеты назначены в соответствии с RM и выполняется условие:

2002 v.0.2.
Особенности Rate Monotonic
Rate Monotonic называют

«устойчивым» (stable) алгоритмом – подмножество задач, которое удовлетворяет тесту, всегда будет выполняться без нарушения deadline

Rate Monotonic называют «оптимальным» алгоритмом – в том смысле, что если набор задач выполним при любой другой дисциплине планирования, то он выполним и при RM планировании

2002 v.0.2.
Приоритетное планирование,
динамические алгоритмы
Earliest Deadline

First (EDF) – значения приоритетов, которые назначаются задачам, обратно пропорциональны длительности временных интервалов до наступления deadline
EDF scheduling test:

1

Σ

Сi / pi

I = 1

I = n

<

EDF - характеризуется наименьшим количеством переключения задач

2002 v.0.2.
Приоритетное планирование,
динамические алгоритмы (2)
Least

Laxity First (LLF) – (laxity – (td - tr) - «расхлябанность») наивысший приоритет присваивается задаче с наименьшим laxity)

td

d

t

tr

LLF scheduling test – аналогичен EDF
Признак laxity<0 - может быть использован для раннего обнаружения нарушения deadline (исключение)