Приоритетное управление задачами
Задача A
I |
da |
Задача B
db
Задача A
II |
da |
Задача B
db
Пропуск deadline
t
t
Deadline не нарушен
tА всего-то изменили порядок выполнения!
t
Выполнимость набора задач – выполнение deadline для всех задач набора (жесткие системы), выполнение с высокой вероятностью (мягкие системы) Управление – процедура, определяющая порядок активизации задач Механизм – назначение приоритетов задачам Приоритетное управление – управление посредством приоритетов
10. Приоритетное управление 2018 v. 03 |
1 |
Статическое назначение приоритетов
Приоритеты задачам назначаются во время проектирования системы и не меняются в в процессе ее функционирования.
10. Приоритетное управление 2018 v. 01 |
2 |
Статическое назначение, правило RM
Пусть имеется n независимых периодических задач реального времени
pi - период i-й задачи, Сi – время выполнения в наихудшем случае; у каждой из задач значение deadline совпадает с периодом активизации pi
RM – правило: приоритеты задач назначаются (off-line) «обратно пропорционально» их pi
Использование RM-правила позволяет оценить выполнимость набора задач
C1
Задача 1 |
|
t |
Высший приоритет |
C2 |
p1 |
|
|
Задача 2 |
|
t |
|
|
p2 |
|
|
|
Cn |
|
|
Задача n |
|
t |
Низший приоритет |
|
pn |
|
|
10. Приоритетное управление 2018 v. 03 |
|
3 |
|
Тест Rate Monotonic
Набор из n периодических задач будет выполнимым (schedulable), если приоритеты назначены в соответствии с RM правилами и выполняется условие (1973 год, Liu):
I = n |
1/n |
|
|
R = S |
(*) |
||
Сi / pi <= n * (2 - 1) |
|||
I = 1 |
|
|
•Зависимость (*) представляет нижнюю границу значения R
•В случае, когда частоты активизации задач находятся в гармонической
зависимости, R <= 1
(Гармоническая зависимость – частота активизации любой задачи приложения кратна частоте каждой задачи с меньшей частотой; например - 1Hz, 5Hz, 10Hz, 20Hz)
• В большинстве практических случаев R < 0.88
10. Приоритетное управление 2018 v. 01 |
4 |
Тест Rate Monotonic
1/n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n * (2 |
- |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,95 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,85 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,75 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.69 |
|
|
0,65 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,55 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
17 |
19 |
21 |
23 |
25 |
27 |
29 |
31 |
33 |
35 |
37 |
10. Приоритетное управление 2018 v. 01 |
|
|
|
|
|
|
|
|
|
5 |
||||||||||
Динамические алгоритмы
Спорадический сервер
|
|
|
Снижение |
|
|
|
|
|
|
приоритета |
Восстановление |
||
|
|
R>0 |
|
R<=0 |
|
ресурса |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
R
C
Т
С - выделенный временной ресурс Т - период восстановления ресурса R - остаточный ресурс
t
t
10. Приоритетное управление 2018 v. 01 |
6 |
Спорадический сервер
|
|
|
Восстановление |
Приоритет |
R>0 |
R<=0 |
ресурса |
|
|||
N |
|
|
t |
|
С |
|
|
|
|
|
|
|
Т |
|
|
L |
|
|
t |
|
|
|
t |
struct { |
|
|
|
int32_t __ss_low_priority; |
|
// фоновый приоритет (L) |
|
int32_t __ss_max_repl; |
|
// * |
|
struct timespec __ss_repl_period; // период пополнения бюджета (Т) struct timespec __ss_init_budget; // начальный бюджет
}__ss;
• Максимальное количество пополнений бюджета за период
См. пример рис. 2.6 Цилюрик, Горшко «QNX/UNIX Анатомия параллелизма»
10. Приоритетное управление 2018 v. 01 |
7 |
Алгоритм Earliest Deadline First (EDF)
Задача A 
t
da
Задача B 
t
db
EDF – значения приоритетов назначаются задачам «обратно
пропорционально» длительности временных интервалов до наступления deadline (da < db PA выше PB )
EDF scheduling test: Сi / pi < 1
pi - период i-й задачи,
Сi – время выполнения в наихудшем случае
10. Приоритетное управление 2018 v. 01 |
8 |
Алгоритм Least Laxity First (LLF)
LLF – (laxity – (td - tr) - «расхлябанность») наивысший приоритет присваивается задаче с наименьшим laxity
t
tr
td
d
LLF scheduling test – аналогичен EDF
Признак laxity<0 - может быть использован для раннего обнаружения нарушения deadline (можно «бросить» исключение)
10. Приоритетное управление 2018 v. 01 |
9 |
Тесты выполнимости динамических алгоритмов
Earliest Deadline First (EDF)
EDF – значения приоритетов назначаются задачам обратно пропорционально длительности временных интервалов до наступления deadline (da < db PA выше PB )
Least Laxity First (LLF)
LLF – (laxity – (td - tr) - наивысший приоритет присваивается задаче с наименьшим laxity
I = n |
pi - период i-й задачи, |
|
S Сi / pi < 1 |
||
Сi – время выполнения в наихудшем случае |
||
I = 1 |
|
10. Приоритетное управление 2018 v. 01 |
10 |