Планирование с динамическими приоритетами
11.1. EDF-алгоритм планирования
Алгоритм самого раннего крайнего срока (EDF- EARLIEST DEADLINE FIRST) - это алгоритм динамического планирования, который выбирает задачи в соответствии с их абсолютными крайними сроками di. В частности, задачи с более ранними di будут иметь более высокие приоритеты. Поскольку абсолютный крайний срок периодической задачи зависит от текущего j-го запроса задачи следующим образом:
,
то EDF - это алгоритм с динамическим назначением приоритетов. Более того, он обычно осуществляется в режиме вытеснения (preemptive), поэтому выполняемая в текущее время задача вытесняется всякий раз, когда другая периодическая задача с более ранним крайним сроком di становится активной.
Обратите внимание, что EDF не делает каких-либо конкретных предположений о периодичности задач; следовательно, он может использоваться для планирования периодических, а также апериодических задач. Оптимальность EDF, доказанная для апериодических задач (см. Алгоритм Хорна), также справедлива для периодических задач.
ВНЗ периодического набора задач, обрабатываемых EDF-алгоритмом, может быть проверена с помощью коэффициента утилизации процессора U. В этом случае, максимальная верхняя граница U равна единице.
Критерий 1 Набор периодических задач можно запланировать с помощью EDF-алгоритма тогда и только тогда, когда выполняется следующее условие:
(11.1)
Пример:
Рассмотрим набор периодических задач, представленных на рисунке:
Рис. 11.1. Расписание для набора задач, запланированного
по RM- и EDF-алгоритмам
Коэффициент утилизации для данного набора равен:
, 
Это означает, что для выполнения периодических задач используется 97% процессорного времени, в то время как CPU остается только 3%. При 
(критерий Лью и Лайленда), ВНЗ не может быть гарантирована в рамках RM-алгоритма, тогда как по EDF-алгоритму она гарантирована. Действительно, как показано на рис.11.1.а, RM генерирует пропуски абсолютных крайних сроков di (в момент t = 7), тогда как EDF вариант выполняет все задачи в пределах своих крайних сроков (рис.11.1.b).
Еще одно важное различие между RM и EDF касается количества вытеснений, происходящих в расписании. Как показано на рисунке рис.11.1, в RM варианте общее количество вытеснений равно пяти. В EDF варианте одна задача вытесняется только один раз. Меньше количество вытеснений в EDF является прямым следствием назначения динамических приоритетов, которое в любой момент делает более приоритетной задачу с самым ранним крайним сроком di, независимо от периодов других задач.
Упражнения!
1. Проанализируйте ВНЗ на основе EDF-алгоритма.
A) Решение:
задача может быть запланирована по EDF-алгоритму, поскольку U < 1.
| 
|
B) Решение:
задача может быть запланирована по EDF-алгоритму, поскольку U < 1.
| 
|
Сравнение RM и EDF-алгоритмов
(из статьи Buttazzo, Rate Monotonic vs. EDF: Judgment Day)
Сопоставим подробнее каждый из алгоритмов, опираясь на некоторые критерии.
Сложность реализации
RM-алгоритм является наиболее часто используемым в приложениях реального времени, потому что его довольно просто реализовать для ядер современных коммерческих ОС. Действительно, RM-планировщик может быть реализован просто путем назначения каждой задаче фиксированного приоритета, обратно пропорционального его периоду. С другой стороны, реализуя схему динамического планирования, (например, EDF-алгоритм) требуются, чтобы ядро ОС отслеживало все абсолютные предельные сроки и выполняло динамическое сопоставление между абсолютными сроками и приоритетами для задач из имеющегося набора. Такое сопоставление должно выполняться каждый раз, когда новая инициированная задача получает свой приоритет. Такая дополнительная сложность реализации из-за динамического управления приоритетами не способствует внедрению EDF-планирования в ОСРВ, хотя это увеличило бы общую загрузку процессора.
Рассматривая разработку алгоритма планирования для уже существующего ядра действительно верно, что реализация EDF сложнее. Ядро ОС позволяет изменять приоритеты задач во время выполнения, но сопоставление динамических сроков с приоритетами не всегда может быть простым, если, например, в большинстве коммерческих ОС, количество уровней приоритета невелико (как правило, не более 256).
Преимущество RM по отношению к EDF заключается в том, что если количество уровней приоритетов для набора задач не является высоким, алгоритм RM может быть реализован более эффективно, разбив при этом очередь готовых задач на несколько очередей FIFO, по одной для каждого уровня приоритета. К сожалению, такое же решение не может быть принято для EDF, поскольку количество очередей в таком случае будет слишком большим. Другим недостатком EDF с точки зрения сложности реализации является то, что абсолютные крайние сроки меняются и их необходимо вычислять при каждой активации нового запроса.
Время выполнения
Несмотря на дополнительные вычисления, необходимые для обновления дедлайнов вновь инициированных запросов, EDF использует меньше служебных ресурсов во время выполнения, по сравнению с RM (при котором происходит большее число переключений контекстов задач за счет большего количества вытеснений).
Как показано на Рис. 11.2, 11.3, каждая кривая имеет две части: количество вытеснений, возникающих в обоих алгоритмах увеличивается для небольших наборов задач и уменьшается для больших наборов задач. Когда количество задач в наборе увеличивается, время выполнения каждой задачи в среднем становится меньше (чтобы поддерживать высокую загрузку процессора). Как видно из рис. 11.3, уменьшение количества вытеснений более существенно при EDF-алгоритме.
Интересно наблюдать различное поведение RM и EDF при увеличении загрузки процессора. В RM количество вытеснений постоянно увеличивается с увеличением коэффициента утилизации U, потому что задачи с более длинным временем выполнения имеют больше шансов быть вытесненными новыми задачами с высоким приоритетом. Однако, в рамках EDF увеличение времени выполнения задач не всегда означает большее количество вытеснений, потому что задача с длинным периодом может иметь дедлайн короче, чем задача с меньшим периодом.
| 
|
| Рис. 11.2. Количество вытеснений (ось у) в зависимости от количества задач в наборе (ось х) | Рис. 11.3. Кол-во вытеснений (ось у) в зависимости от загрузки процессора (U в %) (ось х) |
3) Надежность при перегрузках (при U>1)
Интересным свойством EDF-алгоритма при постоянных перегрузках является то, что он автоматически выполняет масштабирование периода задач. Это свойство доказано в следующей теореме:
Теорема Кервина: Имеется набор из n периодических задач, где каждая задача описывается своим фиксированным периодом Ti, фиксированной фазой Фi, фиксированным временем выполнения Ci, относительным крайним сроком Di. Если коэффициент утилизации U > 1 и задачи запланированы EDF-алгоритмом, то средний период Ti для каждой задачи задается как
Обратите внимание, что в RM-алгоритме постоянная перегрузка может привести к полной блокировке сегмента задач с низким приоритетом.
Джиттер
В периодическом наборе каждая задача должна выполняться после инициации и завершаться до установленных крайних сроков. Из-за присутствия других параллельных задач, которые конкурируют за процессор, текущая задача может выполняться по-разному от запроса к запросу; то есть инструкции, из которых состоит задача, могут выполняться на разных временных промежутках, относительно времени инициации.
Разница между максимальным и минимальным временем инициации всех запросов периодической задачи называется абсолютным джиттером (ARJ)
Максимальная разница между временем инициации двух последовательных запросов периодической задачи называется относительным джиттером (RRJ).
Следует отметить, что при U < 0,7%, оба алгоритма имеют идентичные абсолютные джиттеры, которые линейно возрастают с количеством задач. Для большей загрузки процессора при U > 0,9%, значение абсолютного джиттера в EDF случае меньше чем при RM.
| 
|
| |
| Рис.11.4 Графики зависимости абсолютного джиттера от количества задач в наборе. (примеры для разных значений коэффициента U для набора из 10 задач) |
Заключение: Реальное преимущество RM в отношении EDF заключается в его более простой реализации на основе современных коммерческих ядер, которые не обеспечивают явной поддержки временных ограничений (периоды и крайние сроки). Другие положительные свойства, заявляемые для RM, такие как предсказуемость во время перегрузки, относятся только к более приоритетным задачам из набора, но не выполняются в целом. С другой стороны, EDF обеспечивает больший коэффициент загрузки процессора, что предполагает более эффективную эксплуатацию вычислительных ресурсов и оперативное реагирование на апериодические задачи. Эти свойства становятся очень важными для встраиваемых систем, работающих с ограниченными вычислительными ресурсами, а также для мультимедийных системы, в которых качество обслуживания контролируется механизмами резервирования ресурсов.