Самый ранний срок первого планирования

Earlyest deadline first ( EDF ) или least time to go — это динамический алгоритм приоритетного планирования, используемый в операционных системах реального времени для помещения процессов в приоритетную очередь . Всякий раз, когда происходит событие планирования (завершение задачи, выпуск новой задачи и т. д.), в очереди будет выполнен поиск процесса, ближайшего к его крайнему сроку. Этот процесс будет следующим запланированным для выполнения.

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

При планировании периодических процессов, имеющих сроки, равные их периодам, EDF имеет предел использования 100%. Таким образом, тест на планируемость ^[1] для EDF выглядит следующим образом:

U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq 1,

где — наихудшее время вычислений процессов , а — соответствующие им периоды между поступлениями (предполагается, что они равны относительным срокам). ^[2] $\left\{C_{i}\right\}$ $n$ $\left\{T_{i}\right\}$

То есть EDF может гарантировать соблюдение всех сроков при условии, что общая загрузка ЦП не превышает 100%. По сравнению с методами планирования с фиксированным приоритетом, такими как планирование с монотонной скоростью , EDF может гарантировать соблюдение всех сроков в системе при более высокой нагрузке.

Обратите внимание, что используйте формулу теста на возможность планирования под крайним сроком в качестве периода. Когда крайний срок меньше периода, все по-другому. Вот пример: четыре периодические задачи требуют планирования, где каждая задача отображается как TaskNo(время вычисления, относительный крайний срок, период). Это T0(5,13,20), T1(3,7,11), T2(4,6,10) и T3(1,1,20). Эта группа задач соответствует утилизации, которая не превышает 1,0, где утилизация рассчитывается как 5/20+3/11+4/10+1/20 = 0,97 (две цифры округлены), но она все еще не может быть запланирована, проверьте показатель EDF Scheduling Failure для получения подробной информации.

Ошибка планирования EDF

EDF также является оптимальным алгоритмом планирования на невытесняющих однопроцессорных компьютерах, но только среди класса алгоритмов планирования, которые не допускают вставленного простоя. При планировании периодических процессов, имеющих крайние сроки, равные их периодам, достаточным (но не необходимым) тестом на планируемость для EDF становится: ^[3]

U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq {1-p},

Где p представляет собой штраф за отсутствие приоритета, заданный как max / min . Если этот фактор можно сохранить небольшим, невытесняющий EDF может быть выгоден, поскольку он имеет низкие накладные расходы на реализацию. $\left\{C_{i}\right\}$ $\left\{T_{i}\right\}$

Однако, когда система перегружена, набор процессов, которые пропустят крайние сроки, в значительной степени непредсказуем (он будет функцией точных крайних сроков и времени, в которое происходит перегрузка). Это значительный недостаток для проектировщика систем реального времени. Алгоритм также трудно реализовать на оборудовании , и существует сложная проблема представления крайних сроков в разных диапазонах (крайние сроки не могут быть точнее, чем гранулярность часов, используемых для планирования). Если для вычисления будущих крайних сроков относительно настоящего используется модульная арифметика, поле, хранящее будущий относительный крайний срок, должно содержать по крайней мере значение (("duration" {самого длинного ожидаемого времени до завершения} * 2) + "now"). Поэтому EDF обычно не встречается в промышленных компьютерных системах реального времени.

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

Существует значительный объем исследований, посвященных планированию EDF в вычислениях в реальном времени ; можно рассчитать наихудшее время отклика процессов в EDF, работать с другими типами процессов, отличными от периодических, и использовать серверы для регулирования перегрузок.

Пример

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

В этом примере единицы времени можно рассматривать как планируемые временные отрезки . Крайние сроки — это то, что каждый периодический процесс должен завершиться в течение своего периода.

Временная диаграмма

Временная диаграмма, показывающая часть одного из возможных графиков для примера.

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

Первый процесс, запланированный EDF, — это P2, поскольку его период самый короткий, и поэтому у него самый ранний срок. Аналогично, когда P2 завершается, P1 планируется, а затем P3.

В интервале времени 5 у P2 и P3 одинаковый срок выполнения, и они должны быть завершены до интервала времени 10, поэтому EDF может запланировать любой из них.

Использование

Использование будет следующим:

$\left({\frac {1}{8}}+{\frac {2}{5}}+{\frac {4}{10}}\right)=\left({\frac {37}{40}}\right)=0.925={\mathbf {92.5\%} }$

Поскольку наименьшее общее кратное периодов равно 40, шаблон планирования может повторяться каждые 40 временных срезов. Но только 37 из этих 40 временных срезов используются P1, P2 или P3. Поскольку использование, 92,5%, не превышает 100%, система может планироваться с помощью EDF.

Крайний срок обмена

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

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

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

Анализ интенсивного трафика для очередей EDF с отказом

В анализе интенсивного трафика поведения односерверной очереди при политике планирования «ранний крайний срок — первый» с отказом ^[4] процессы имеют крайние сроки и обслуживаются только до тех пор, пока не истекут их крайние сроки. Доля «отказанной работы», определяемая как остаточная работа, не обслуженная из-за истекших крайних сроков, является важным показателем производительности.

Сравнение с планировщиками с фиксированным приоритетом

Обычно считается, что реализация упреждающего планирования с фиксированным приоритетом (FPS) проще, чем динамический приоритетный планировщик, такой как EDF. Однако при сравнении максимального использования оптимального планирования при фиксированном приоритете (с приоритетом каждого потока, заданным планированием с монотонной скоростью ), EDF может достигать 100%, в то время как теоретическое максимальное значение для планирования с монотонной скоростью составляет около 69%. Кроме того, наихудшие накладные расходы реализации EDF (полностью упреждающее или ограниченное/не упреждающее) для периодических и/или спорадических задач можно сделать пропорциональными логарифму наибольшего представления времени, требуемого данной системой (для кодирования крайних сроков и периодов) с использованием цифровых деревьев поиска. ^[5] В практических случаях, таких как встроенные системы, использующие фиксированное 32-битное представление времени, решения о планировании могут быть приняты с использованием этой реализации за небольшое фиксированно-постоянное время, которое не зависит от количества системных задач. В таких ситуациях эксперименты не выявили заметной разницы в накладных расходах между EDF и FPS, даже для наборов задач (сравнительно) большой мощности. ^[5]

Обратите внимание, что EDF не делает никаких конкретных предположений относительно периодичности задач; следовательно, его можно использовать для планирования как периодических, так и апериодических задач. ^[2]

Ядра, реализующие планирование EDF

Хотя реализации EDF не распространены в коммерческих ядрах реального времени, вот несколько ссылок на ядра с открытым исходным кодом и ядра реального времени, реализующие EDF:

SHARK ОСРВ SHaRK, реализующая различные версии алгоритмов планирования EDF и резервирования ресурсов
ERIKA Enterprise ERIKA Enterprise, которая обеспечивает реализацию EDF, оптимизированную для небольших микроконтроллеров с API, аналогичным API OSEK .
Ядро Everyman Ядро Everyman реализует либо планирование EDF, либо монотонное планирование Deadline в зависимости от конфигурации пользователя.
MaRTE OS MaRTE OS выступает в качестве среды выполнения для приложений Ada и реализует широкий спектр алгоритмов планирования, включая EDF.
Проект AQuoSA представляет собой модификацию ядра Linux, обогащающую планировщик процессов возможностями планирования EDF. Синхронизация планирования не может быть такой же точной, как в случае вышеупомянутых жестких операционных систем реального времени, однако она достаточно точна, чтобы значительно повысить предсказуемость и, таким образом, выполнить требования реального времени мультимедийных приложений. AQuoSA является одним из немногих проектов, который предоставляет возможности планирования реального времени для непривилегированных пользователей в системе контролируемым образом с помощью правильно спроектированной модели контроля доступа. ^[6]
Ядро Linux имеет самую раннюю реализацию deadline first SCHED DEADLINE, которая доступна с версии 3.14.
Планировщик реального времени, разработанный в контексте IRMOS, архив 2018-10-10 в европейском проекте Wayback Machine, представляет собой многопроцессорный планировщик реального времени для ядра Linux, особенно подходящий для временной изоляции и предоставления гарантий QoS сложным многопоточным программным компонентам, а также целым виртуальным машинам . Например, при использовании Linux в качестве хостовой ОС и KVM в качестве гипервизора IRMOS можно использовать для предоставления гарантий планирования отдельным виртуальным машинам и в то же время изолировать их производительность , чтобы избежать нежелательных временных помех. IRMOS имеет комбинированный иерархический планировщик EDF/FP. На внешнем уровне имеется секционированный планировщик EDF на доступных ЦП. Однако резервирования являются многопроцессорными, а глобальный FP по многопроцессорным используется на внутреннем уровне для планирования потоков (и/или процессов), прикрепленных к каждому внешнему резервированию EDF. См. также эту статью на lwn.net для общего обзора и краткого руководства по теме.
Xen уже некоторое время имеет планировщик EDF. Страница man содержит краткое описание.
Операционная система Plan 9 от Bell Labs включает в себя EDFI, «легкий протокол планирования в реальном времени, который объединяет EDF с наследованием сроков через общие ресурсы». ^[7]
RTEMS: Планировщик EDF будет доступен в версии 4.11. RTEMS SuperCore
Litmus-RT — это расширение ядра Linux в реальном времени с фокусом на многопроцессорное планирование и синхронизацию в реальном времени. Его набор алгоритмов реального времени включает в себя планировщики Partitioned-EDF, Global-EDF и Clustered-EDF.
Планировщик XNU Clutch С 2018 года ядро XNU от Apple реализует алгоритм EDF в своем планировщике Clutch с целью повышения скорости реагирования.

Смотрите также

Ссылки

^ Сюй, Дж.; Парнас, Д.Л. (1990). «Планирование процессов с учетом времени выпуска, крайних сроков, отношений приоритета и исключения». Труды IEEE по программной инженерии . 16 (3): 360–369. doi :10.1109/32.48943.
^ ab Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Третье изд.), Нью-Йорк, штат Нью-Йорк: Springer, стр. 100, ISBN 9781461406761
^ Short, Michael (2011). «Улучшенный анализ планируемости неявных задач с крайним сроком при ограниченном прерывании планирования EDF». Международная конференция IEEE 2011 по новым технологиям и автоматизации производства. С. 1–8. doi :10.1109/ETFA.2011.6059008. ISBN 978-1-4577-0017-0. S2CID 7656331.
^ Крук, Лукаш; Лехоцки, Джон; Раманан, Кавита; Шрив, Стивен (2011). "Анализ интенсивного трафика для очередей EDF с отказом от обязательств" (PDF) . Анналы прикладной вероятности . 21 (2). doi :10.1214/10-AAP681. S2CID 12268649.
^ ab Short, Michael (апрель 2010 г.). «Улучшенные методы управления задачами для обеспечения планирования EDF для повторяющихся задач». 16-й симпозиум IEEE по технологиям и приложениям реального времени и встраиваемым технологиям 2010 г. стр. 56–65. doi :10.1109/RTAS.2010.22. ISBN 978-1-4244-6690-0. S2CID 13940378.
^ Кучинотта, Томмазо (2008). «Управление доступом для адаптивного резервирования в многопользовательских системах». Симпозиум IEEE 2008 года по технологиям и приложениям реального времени и встроенным технологиям . С. 387–396. doi :10.1109/RTAS.2008.16. ISBN 978-0-7695-3146-5. S2CID 1008365.
^ Пьер Г. Янсен, Сапе Дж. Маллендер, Пол Дж. М. Хавинга, Ханс Шолтен. Упрощенное планирование EDF с наследованием сроков