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

Сентябрь 3, 2022

Главная
Алгебра
Планирование задач

Содержание

2. 9. Планирование задач. 2002 v.0.2. Алгоритм планирования (scheduling algorithm) - правило, определяющее порядок выполнения задач Статическое
3. 9. Планирование задач. 2002 v.0.2. N1 N2 Nn Циклический исполнитель (Round Robin) Таблица обработчиков событий pt1
4. 9. Планирование задач. 2002 v.0.2. Циклический исполнитель (2) Достоинство – простота реализации Недостаток – при большом
5. 9. Планирование задач. 2002 v.0.2. Приоритетное планирование Статические алгоритмы – приоритеты задач определяются на этапе проектирования
6. 9. Планирование задач. 2002 v.0.2. Rate monotonic (RM) – правило статического (off-line) назначения приоритетов: Пусть имеется
7. 9. Планирование задач. 2002 v.0.2. Задача 1 p1 t t pn Задача n Задача 2 p2
8. 9. Планирование задач. 2002 v.0.2. Тест Rate Monotonic 0.69
9. 9. Планирование задач. 2002 v.0.2. Зависимость (*) представляет нижнюю границу значения R В случае, когда частоты
10. 9. Планирование задач. 2002 v.0.2. Особенности Rate Monotonic Rate Monotonic называют «устойчивым» (stable) алгоритмом – подмножество
11. 9. Планирование задач. 2002 v.0.2. Приоритетное планирование, динамические алгоритмы Earliest Deadline First (EDF) – значения приоритетов,
13. Скачать презентацию

Слайд 2

9. Планирование задач. 2002 v.0.2.
Алгоритм планирования (scheduling algorithm) - правило, определяющее

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

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

Слайд 3

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

. .

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

. . . .

pt2

ptn

Обработка 1

Обработка 2

Обработка n

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

Таймер

Обработка

Слайд 4

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

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

Слайд 5

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

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

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

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

НОВЫЕ ЗАДАЧИ

ДИСПЕТЧЕР

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

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

Слайд 6

9. Планирование задач. 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)

Слайд 7

9. Планирование задач. 2002 v.0.2.
Задача 1
p1
t
t
pn
Задача n
Задача 2
p2
t
C1
C2
Cn
Высший приоритет
Низший приоритет
Rate monotonic

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

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

Слайд 8

9. Планирование задач. 2002 v.0.2.
Тест Rate Monotonic
0.69

Слайд 9

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

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

Тест Rate Monotonic (2)

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

Слайд 10

9. Планирование задач. 2002 v.0.2.
Особенности Rate Monotonic
Rate Monotonic называют «устойчивым» (stable)

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

Слайд 11

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

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

Сi / pi

I = 1

I = n

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

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

Содержание

9. Планирование задач. 2002 v.0.2.Алгоритм планирования (scheduling algorithm) - правило, определяющее

9. Планирование задач. 2002 v.0.2.N1N2NnЦиклический исполнитель (Round Robin)Таблица обработчиков событий pt1. .

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

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

9. Планирование задач. 2002 v.0.2.Rate monotonic (RM) – правило статического (off-line)

9. Планирование задач. 2002 v.0.2.Задача 1p1ttpnЗадача nЗадача 2p2tC1C2CnВысший приоритетНизший приоритетRate monotonic

9. Планирование задач. 2002 v.0.2.Тест Rate Monotonic0.69

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

9. Планирование задач. 2002 v.0.2.Особенности Rate MonotonicRate Monotonic называют «устойчивым» (stable)

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

Похожие презентации