SCHED_DEADLINE

SCHED_DEADLINE
ЦП, планировщик доступный в ядре Linux начиная с версии 3.14, [1] [2] на основе самого раннего срока (EDF) и сервера с постоянной пропускной способностью (CBS) [3] алгоритмы, поддерживающие резервирование ресурсов: каждая задача, запланированная в соответствии с такой политикой, связана с бюджетом Q (он же время выполнения ) и периодом P, соответствующим объявлению ядру, что Q единиц времени требуется для этой задачи каждые P единиц времени, любой процессор. Это делает SCHED_DEADLINE
особенно подходит для приложений реального времени , таких как мультимедиа или промышленное управление, где P соответствует минимальному времени, прошедшему между последующими активациями задачи, а Q соответствует времени выполнения наихудшего случая, необходимому для каждой активации задачи.
Общие сведения о планировщиках ЦП в ядре Linux
[ редактировать ]Ядро Linux содержит различные классы планировщика. [4] По умолчанию ядро использует механизм планировщика, называемый Completely Fair Scheduler (CFS), представленный в версии ядра 2.6.23. [5] Внутри этот класс планировщика по умолчанию также известен как SCHED_NORMAL
, а ядро также содержит два POSIX-совместимых [6] классы планирования в реальном времени с именем SCHED_FIFO
( в режиме реального времени в порядке очереди ) и SCHED_RR
( циклический перебор в реальном времени ), оба из которых имеют приоритет над классом по умолчанию. [4] SCHED_DEADLINE
Класс планирования был добавлен в планировщик Linux в версии 3.14 основной ветки ядра Linux , выпущенной 30 марта 2014 года. [7] [8] и имеет приоритет над всеми другими классами планирования.
Планировщик по умолчанию, CFS, очень хорошо справляется с различными вариантами использования. Например, при смешивании пакетных рабочих нагрузок, таких как длительная компиляция кода или обработка чисел, и интерактивных приложений, таких как настольные приложения, мультимедийные и другие, CFS динамически снижает приоритет пакетных задач в пользу интерактивных. Однако, когда приложению требуется предсказуемое и точное расписание, обычно ему приходится обращаться к одному из других планировщиков реального времени, SCHED_RR или SCHED_FIFO, которые применяют фиксированный приоритет для планирования задач по приоритетам и чьи задачи планируются перед любой задачей. в классе SCHED_NORMAL.
Операция
[ редактировать ]При смешивании рабочих нагрузок реального времени с разнородными требованиями к времени в одной системе возникает известная проблема SCHED_RR
и SCHED_FIFO
заключается в том, что, поскольку они основаны на приоритетах задач, задачи с более высоким приоритетом, выполняемые дольше, чем ожидалось, могут произвольно и неконтролируемо задерживать задачи с более низким приоритетом.
С SCHED_DEADLINE
вместо этого задачи независимо объявляют свои требования к времени, с точки зрения времени выполнения для каждой задачи каждой задачи, необходимого для каждого периода для каждой задачи (и срока выполнения в пределах крайнего срока с момента начала каждого периода), и ядро принимает их в планировщике после планирования. тест. Теперь, если задача попытается выполнить дольше, чем назначенный ей бюджет, ядро приостановит эту задачу и отложит ее выполнение до следующего периода активации. Это не сохраняющее работу, свойство планировщика, позволяет ему обеспечить временную изоляцию задач. Это приводит к тому важному свойству, что в однопроцессорных системах или в многопроцессорных системах с разделами (где задачи распределены между доступными ЦП, поэтому каждая задача привязана к конкретному ЦП и не может мигрировать), все принимаются SCHED_DEADLINE
задачи гарантированно планируются на общее время, равное их бюджету, в каждом временном окне, соответствующем их периоду, если только сама задача не блокируется и ее не нужно запускать. Кроме того, особенностью алгоритма CBS является то, что он гарантирует временную изоляцию даже при наличии задач, блокирующих и возобновляющих выполнение: это делается путем сброса крайнего срока планирования задач на целый период, когда задача просыпается слишком поздно. В общем случае задачи свободно мигрируют на мультипроцессор, т.к. SCHED_DEADLINE
реализует глобальный EDF, применяется общее ограничение задержки для глобального EDF, как описано в разделе . [9]
Чтобы лучше понять, как работает планировщик, рассмотрим набор SCHED_DEADLINE
задачи с потенциально разными периодами, имеющие срок, равный периоду. Для каждой задачи, помимо настроенного времени выполнения и (относительного) периода, ядро отслеживает текущее время выполнения и текущий (абсолютный) крайний срок . Задачи планируются для процессоров на основе их текущих сроков с использованием глобального EDF. Если для политики планирования задач изначально установлено значение SCHED_DEADLINE
, текущий срок инициализируется текущим временем плюс настроенный период, а текущий бюджет устанавливается равным настроенному бюджету. Каждый раз, когда задача запланирована для выполнения на каком-либо процессоре, ядро позволяет ей выполняться в пределах доступного текущего бюджета, и всякий раз, когда задача отменяется из расписания, ее текущий бюджет уменьшается на количество времени, в течение которого она выполнялась. Как только текущий бюджет становится равным нулю, задача приостанавливается (регулируется) до следующего периода активации, после чего текущий бюджет снова пополняется до настроенного значения, а срок сдвигается вперед на значение, равное периоду задачи.
Этого недостаточно, чтобы гарантировать временную изоляцию . Задача, приостанавливающая себя вскоре после активации, а затем просыпающаяся ближе к текущему сроку или даже позже, просыпается почти со всем настроенным бюджетом, с текущим сроком, который очень близок к истечению, или даже в прошлом. . В таких условиях эта задача будет запланирована раньше любой другой, и в однопроцессорной системе она сможет отложить выполнение любой другой задачи с крайним сроком на срок, соответствующий ее бюджету. Чтобы избежать этой проблемы, SCHED_DEADLINE
принимает правило планирования пробуждения, определенное в алгоритме CBS. При пробуждении задачи, если с момента блокировки задачи прошло относительно небольшое время, предыдущий текущий срок и бюджет для задачи сохраняются неизменными. Однако если прошло слишком много времени, то ядро сбрасывает текущий крайний срок на текущее время плюс период резервирования, а текущий бюджет — на выделенный бюджет резервирования. Более подробное объяснение с примерами см. [9]
В многопроцессорной или многоядерной системе SCHED_DEADLINE
реализует глобальный EDF, поэтому задачи могут переноситься между доступными процессорами. В таком случае настроенный бюджет — это общее совокупное количество времени, в течение которого задаче разрешено выполняться на любом ЦП в течение каждого периода. Однако планировщик также учитывает маски сходства задач , поэтому можно легко создавать сценарии секционированного планирования, разбивать задачи на группы, где каждая группа ограничена определенным ЦП, или сценарии кластерного планирования, полученные также путем разделения ЦП и закрепления каждого раздела задач. вплоть до определенного раздела процессоров.
Для получения технических подробностей о SCHED_DEADLINE
обратитесь к документации, доступной в дереве исходного кода ядра. [9] Более подробную информацию о CBS и о том, как она обеспечивает временную изоляцию, можно найти в оригинальной статье CBS: [3] или раздел о CBS в этой статье [10] появился на lwn.net.
История
[ редактировать ]Первоначальная идея класса планирования Linux, основанного на алгоритме Earlyest Deadline First (EDF), родилась в небольшом контексте лаборатории систем реального времени (ReTiS) Scuola Superiore Sant'Anna. [11] и ее дочерняя компания Evidence Srl. [12] Затем Evidence Srl привлекла финансирование проекта ACTORS. [13] [14] при поддержке Европейской комиссии в рамках рамочной программы FP7 для финансирования и продвижения разработки первых версий патча.Оригинальную версию разработали Дарио Фаджиоли (контракт с Evidence Srl на разработку первых трех версий) и Юри Лелли (начиная с четвертой версии). [15] со спорадической помощью Майкла Тримарки и Фабио Чеккони. Йохан Экер отвечал за координацию в рамках ACTORS и поддержку со стороны Ericsson. Юри Лелли, Лука Абени и Клаудио Скордино сотрудничали в разработке программы восстановления (т.е. GRUB [16] ) и масштабирование частоты (т.е. GRUB-PA [17] ) функции.
Патч периодически выпускался для сообщества ядра через список рассылки ядра Linux (LKML). В каждом выпуске код приводился в соответствие с последней версией ядра и учитывались комментарии, полученные при предыдущей отправке.По мере того, как популярность планировщика росла, все больше разработчиков ядра начали оставлять свои отзывы и вносить свой вклад.
Первоначально проект назывался SCHED_EDF
и представлен сообществу ядра Linux в 2009 году. [18] Через несколько недель под этим названием он также был представлен на семинаре Real-Time Linux Workshop. [19] Затем имя было изменено на SCHED_DEADLINE по запросу сообщества ядра Linux. [20]
За прошедшие годы были выпущены следующие версии:
- Первая версия планировщика была представлена 22 сентября 2009 г. под названием
SCHED_EDF
. [18] - Первая версия планировщика после изменения названия на
SCHED_DEADLINE
был отправлен в LKML 16 октября 2009 г. [21] - Вторая версия планировщика была отправлена в LKML 28 февраля 2010 г. и впервые реализовала протокол наследования сроков. [22]
- Третья версия планировщика была отправлена в LKML 29 октября 2010 г., и в нее добавлена поддержка глобального/кластерного многопроцессорного планирования посредством динамической миграции задач. [23]
- Четвертая версия планировщика была отправлена в LKML 6 апреля 2012 г. и имеет улучшенную обработку выбора rq для динамической миграции задач и улучшенную интеграцию с PREEMPT_RT . [24]
- Пятая версия планировщика была отправлена в LKML 23 мая 2012 г. [25]
- Шестая версия планировщика была отправлена в LKML 24 октября 2012 г. [26]
- Седьмая версия планировщика была отправлена в LKML 11 февраля 2013 г. [27] Внутренние математические вычисления были ограничены разрешением в микросекундах (во избежание переполнения), а тег RFC был удален.
- Восьмая версия планировщика была отправлена в LKML 14 октября 2013 г. [28]
- Девятая версия планировщика была отправлена в LKML 7 ноября 2013 г. [29]
- Последняя версия была объединена с основным ядром Linux (номер фиксации a0fa1dd3cdbccec9597fe53b6177a9aa6e20f2f8). [30] ), и с тех пор является его постоянной частью.
Статьи о Linux Еженедельные новости [31] и Фороникс [32] веб-сайты утверждали, что SCHED_DEADLINE
может быть объединено с основным ядром в следующих выпусках. Наконец, спустя более четырех лет и представление девяти выпусков, патч был принят и включен в ядро Linux 3.14. [7] [8]
До SCHED_DEADLINE Лаборатория систем реального времени (ReTiS) [11] из Scuola Superiore Sant'Anna предоставила различные другие реализации CBS и ее вариантов с открытым исходным кодом в ядре Linux в контексте других европейских исследовательских проектов, включая OCERA, [33] архитектура AQuoSA в рамках проекта FRESCOR, [34] и ИРМОС. [35] Однако эти предыдущие усилия начинались с академического подхода, где основной целью был сбор экспериментальных результатов для исследовательских проектов, а не предоставление реализации, подходящей для интеграции в основное ядро. Благодаря IRMOS лаборатория получила первый серьезный контакт с разработчиками ядра Linux. [10]
Начиная с ядра 4.13, SCHED_DEADLINE завершен. [36] CBS с алгоритмом жадного восстановления неиспользованной полосы пропускания (GRUB). [37] Поддержка была разработана ReTiS Lab в сотрудничестве с Evidence Srl.
Начиная с ядра 4.16, SCHED_DEADLINE получил дальнейшее развитие для снижения энергопотребления на платформах ARM за счет реализации алгоритма GRUB-PA. [17] Работа выполнена компанией ARM Ltd. в сотрудничестве с Evidence Srl и Scuola Superiore Sant'Anna. [38]
Академическое образование
[ редактировать ]SCHED_DEADLINE
был представлен на некоторых академических семинарах, конференциях и в журналах:
- Дарио Фаджиоли, Фабио Чеккони, Майкл Тримарки, Клаудио Скордино, Класс планирования EDF для ядра Linux , 11-й семинар по Linux в реальном времени (RTLWS), Дрезден, Германия, сентябрь 2009 г. [19] [39]
- Никола Маника, Лука Абени, Луиджи Палополи, Дарио Фаджиоли, Клаудио Скордино, Планируемые драйверы устройств: реализация и результаты экспериментов , Международный семинар по платформам операционных систем для встраиваемых приложений реального времени (OSPERT), Брюссель, Бельгия, июль 2010 г. [40] [41]
- Юри Лелли, Джузеппе Липари, Дарио Фаджиоли, Томмазо Кучинотта, Эффективная и масштабируемая реализация глобального EDF в Linux , Международный семинар по платформам операционных систем для встраиваемых приложений реального времени (OSPERT), Порту (Португалия), июль 2011 г. [42] [43]
- Энрико Бини, Джорджио Бутаццо, Йохан Экер, Стефан Шорр, Рафаэль Герра, Герхард Фолер, Карл-Эрик Арцен, Ванесса Ромеро Сеговия, Клаудио Скордино, Управление ресурсами в многоядерных системах: подход ACTORS , IEEE Micro, vol. 31, нет. 3, стр. 72–81, май/июнь 2011 г. [14]
- Андреа Парри, Юри Лелли, Мауро Маринони, Джузеппе Липари, Проектирование и реализация протокола наследования пропускной способности мультипроцессора в Linux , 15-й семинар по Linux в реальном времени (RTLWS), Лугано-Манно, Швейцария, октябрь 2013 г. [44]
- Лука Абени, Юри Лелли, Клаудио Скордино, Луиджи Паолополи, Жадное восстановление ЦП для SCHED_DEADLINE , Материалы 16-го семинара по Linux в реальном времени (RTLWS), Дюссельдорф, Германия, октябрь 2014 г. [45]
- Юри Лелли, Клаудио Скордино, Лука Абени, Дарио Фаджиоли, Планирование сроков в ядре Linux , Программное обеспечение: практика и опыт, 46(6): 821–839, июнь 2016 г. [46]
- Клаудио Скордино, Лука Абени, Юри Лелли, Планирование реального времени с учетом энергопотребления в ядре Linux , 33-й симпозиум ACM/SIGAPP по прикладным вычислениям (SAC 2018), По, Франция, апрель 2018 г. [47]
- Клаудио Скордино, Лука Абени, Юри Лелли, Реальное время и энергоэффективность в Linux: теория и практика , Обзор прикладных вычислений ACM SIGAPP (ACR), Vol. 18 № 4, 2018. [48]
Проект также был представлен на Kernel Summit в 2010 году. [49] [50] на конференции Linux Plumbers Conference 2012, [51] [52] и на конференции Embedded Linux Conference 2013. [53]
Другая информация
[ редактировать ]У проекта есть официальная страница. [54] До основной интеграции код был общедоступен на веб-сайте GitHub. [55] который заменил предыдущий репозиторий на Gitorious. [56] После основной интеграции официальный код включен в дерево исходного кода ядра Linux.
появилось несколько статей В Linux Weekly News . [1] [57] Слэшдот , [58] ОСНовости [2] [59] и LinuxToday. [60] Видео было загружено на YouTube [61] также.
Перед интеграцией в основное ядро, SCHED_DEADLINE
уже был интегрирован в проект Yocto . [28] и был также некоторый интерес к включению в Линаро . проекты [62]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б [1] Еженедельные новости Linux, Планирование сроков для Linux
- ^ Перейти обратно: а б [2] OSNews, Планирование сроков в ядре Linux
- ^ Перейти обратно: а б [3] Л. Абени и Г. Бутаццо, «Интеграция мультимедийных приложений в системах жесткого реального времени», Proc. 19-го симпозиума IEEE по системам реального времени, Мадрид, 1998 г., стр. 4–13.
- ^ Перейти обратно: а б Бар, Моше. «Планировщик Linux» . Linux-журнал . Проверено 14 апреля 2012 г.
- ^ Мольнар, Инго (13 апреля 2007 г.). «[исправление] Модульное ядро планировщика и полностью честный планировщик [CFS]» . linux-kernel (список рассылки).
- ^ [4] Стандарт IEEE для информационных технологий - интерфейс портативной операционной системы, POSIX.1b, расширения реального времени (IEEE Std 1003.1b-1993)
- ^ Перейти обратно: а б «Ядро Linux 3.14, раздел 1.1. Класс планирования сроков для лучшего планирования в реальном времени» . kernelnewbies.org . 30 марта 2014 г. Проверено 2 апреля 2014 г.
- ^ Перейти обратно: а б [5] Phoronix, ядро Linux 3.14 уже имеет множество интересных функций.
- ^ Перейти обратно: а б с «Планирование сроков выполнения задач» .
- ^ Перейти обратно: а б «Планировщик реального времени IRMOS [LWN.net]» . lwn.net .
- ^ Перейти обратно: а б [6] Лаборатория ReTiS, Школа Супериоре Сант-Анна, Пиза, Италия.
- ^ [7] Evidence Srl, пресс-релиз для SCHED_DEADLINE v6.
- ^ [8] Проект ACTORS FP7
- ^ Перейти обратно: а б [9] Энрико Бини, Джорджио Бутаццо, Йохан Экер, Стефан Шорр, Рафаэль Герра, Герхард Фолер, Карл-Эрик Арцен, Ванесса Ромеро Сеговия, Клаудио Скордино, Управление ресурсами в многоядерных системах: подход ACTORS, IEEE Micro, vol. 31, нет. 3, стр. 72–81, май/июнь 2011 г.
- ^ [10] История проекта SCHED_DEADLINE .
- ^ «Освобождение ЦП для SCHED_DEADLINE [LWN.net]» . lwn.net . Проверено 24 октября 2018 г.
- ^ Перейти обратно: а б «ГРУБ-ПА» . git.kernel.org . Проверено 24 октября 2018 г.
- ^ Перейти обратно: а б [11] Первое представление SCHED_DEADLINE (все еще называемого SCHED_EDF)
- ^ Перейти обратно: а б [12] Дарио Фаджиоли, Фабио Чеккони, Майкл Тримарчи, Клаудио Скордино, Класс планирования EDF для ядра Linux, 11-й семинар по Linux в реальном времени (RTLW), Дрезден, Германия, сентябрь 2009 г.
- ^ [13] Запрос на изменение имени с SCHED_EDF на SCHED_DEADLINE.
- ^ [14] Первая версия SCHED_DEADLINE.
- ^ [15] Вторая версия SCHED_DEADLINE.
- ^ [16] Третья версия SCHED_DEADLINE.
- ^ [17] Четвертая версия SCHED_DEADLINE.
- ^ [18] Пятая версия SCHED_DEADLINE.
- ^ [19] Шестая версия SCHED_DEADLINE.
- ^ [20] Седьмая версия SCHED_DEADLINE.
- ^ Перейти обратно: а б [21] Восьмая версия SCHED_DEADLINE.
- ^ [22] Девятая версия SCHED_DEADLINE.
- ^ [23] Зафиксировать слияние SCHED_DEADLINE с основным ядром.
- ^ «Планирование сроков: скоро?» . lwn.net .
- ^ [24] Phoronix, SCHED_DEADLINE будет добавлен в Linux 3.14.
- ^ [25] Европейский исследовательский проект OCERA по CORDIS.
- ^ [26] Европейский исследовательский проект FRESCOR по CORDIS.
- ^ [27] Европейский исследовательский проект IRMOS по CORDIS.
- ^ «kernel/git/torvalds/linux.git — дерево исходного кода ядра Linux» . git.kernel.org . Проверено 5 сентября 2017 г.
- ^ [28] Алгоритм жадного восстановления неиспользуемой пропускной способности (GRUB)
- ^ «kernel/git/torvalds/linux.git — дерево исходного кода ядра Linux» . git.kernel.org . Проверено 4 января 2019 г.
- ^ [29] Семинар по Linux в реальном времени (RTLWS), 2009 г.
- ^ [30] Никола Маника, Лука Абени, Луиджи Палополи, Дарио Фаджиоли, Клаудио Скордино, Планируемые драйверы устройств: реализация и результаты экспериментов, Международный семинар по платформам операционных систем для встраиваемых приложений реального времени (OSPERT), Брюссель, Бельгия, июль 2010 г.
- ^ [31] Международные публикации ACTORS.
- ^ [32] Юри Лелли, Джузеппе Липари, Дарио Фаджиоли, Томмазо Кучинотта, Эффективная и масштабируемая реализация глобального EDF в Linux, Международный семинар по платформам операционных систем для встраиваемых приложений реального времени (OSPERT), Порту (Португалия), июль 2011 г. .
- ^ [33] Международный семинар по платформам операционных систем для встраиваемых приложений реального времени (OSPERT), Порту (Португалия), июль 2011 г.
- ^ [34] Семинар по Linux в реальном времени (RTLWS), 2013 г.
- ^ [35] Семинар по Linux в реальном времени (RTLWS), 2014 г.
- ^ Лелли, Юрий (2015). «Планирование сроков в ядре Linux». Программное обеспечение: практика и опыт . 46 (6): 821–839. дои : 10.1002/спе.2335 . S2CID 5527688 .
- ^ Скордино, Клаудио; Абени, Лука; Лелли, Юрий (9 апреля 2018 г.). Планирование в реальном времени с учетом энергопотребления в ядре Linux . АКМ. стр. 601–608. дои : 10.1145/3167132.3167198 . ISBN 9781450351911 . S2CID 49561532 .
- ^ «Обзор прикладных вычислений ACM SIGAPP (ACR), том 18, № 4, 2018 г.» (PDF) .
- ^ [36] SCHED_DEADLINE на Kernel Summit 2010 (KS2010)
- ^ [37] ReTiS Lab, SCHED_DEADLINE, представлено на Kernel Summit 2010.
- ^ [38] Конференция сантехников Linux, 2012 г.
- ^ [39] Проект SOOS, SCHED_DEADLINE на конференции Linux Plumbers Conference 2012.
- ^ [40] Конференция по встроенному Linux, Сан-Франциско, 2013. Обнаружение промахов по дедлайну с помощью SCHED_DEADLINE, Ёситаке Кобаяши, TOSHIBA Corporation
- ^ [41] Официальный сайт проекта SCHED_DEADLINE.
- ^ [42] Новый общедоступный репозиторий GitHub.
- ^ «SCHED_DEADLINE — Главная — Открыть вики — Gitorious» . Архивировано из оригинала 27 декабря 2010 г. Проверено 11 января 2011 г. Предыдущий репозиторий Gitorious
- ^ [43] Еженедельные новости Linux, Добавление периодов в SCHED_DEADLINE.
- ^ [44] Slashdot , Планирование сроков, предлагаемое для ядра Linux
- ^ [45] OSNews , Доступна новая версия SCHED_DEADLINE для Linux.
- ^ [46] LinuxToday, Добавление периодов в SCHED_DEADLINE.
- ^ [47] Видео SCHED_DEADLINE на YouTube.
- ^ [48] SCHED_DEADLINE на Линаро