Полностью честный планировщик - Википедия - Completely Fair Scheduler

Расположение «Completely Fair Scheduler» (планировщика процессов) в упрощенной структуре ядра Linux.

В Полностью честный планировщик (CFS) это планировщик процессов который был объединен с выпуском 2.6.23 (октябрь 2007 г.) Linux ядро и является планировщиком по умолчанию. Он обрабатывает ЦПУ выделение ресурсов для выполнения процессы, и направлен на максимальное использование ЦП в целом, а также на максимальную интерактивную производительность.

В отличие от предыдущего планировщика O (1), который использовался в старых ядрах Linux 2.6, реализация планировщика CFS не основана на запускать очереди. Вместо этого красно-черное дерево реализует «график» будущего выполнения задачи. Кроме того, планировщик использует наносекунда учет гранулярности - элементарные единицы, с помощью которых была выделена доля ЦП отдельного процесса (что делает излишним предыдущее понятие временных интервалов). Это точное знание также означает, что никаких конкретных эвристика требуются, например, для определения интерактивности процесса.^[1]

Как и старый планировщик O (1), CFS использует концепцию, называемую «равноправие спящего», которая рассматривает спящие или ожидающие задачи, эквивалентные задачам в очереди выполнения. Это означает, что интерактивные задачи, которые проводят большую часть своего времени в ожидании ввода пользователя или других событий, получают сопоставимую долю процессорного времени, когда им это нужно.

Алгоритм

Структура данных, используемая для алгоритма планирования, представляет собой красно-черное дерево в котором узлы зависят от планировщика sched_entity конструкции. Они получены из общего task_struct дескриптор процесса, с добавленными элементами планировщика.

Узлы индексируются процессором "время исполнения"в наносекундах.^[2]

А "максимальное время исполнения"также рассчитывается для каждого процесса, чтобы представить время, которое процесс ожидал бы для работы на" идеальном процессоре ". Это время, в течение которого процесс ожидал запуска, деленное на общее количество процессов.

Когда планировщик вызывается для запуска нового процесса:

1. Выбирается крайний левый узел дерева расписания (так как у него будут самые низкие затраты время исполнения), и отправлен на исполнение.
2. Если процесс просто завершает выполнение, он удаляется из системы и дерева планирования.
3. Если процесс достигнет своего максимальное время исполнения или иным образом остановлен (добровольно или через прерывание), он повторно вставляется в дерево планирования на основе его новых затрат время исполнения.
4. Затем новый крайний левый узел будет выбран из дерева, повторяя итерацию.

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

Планировщик CFS с справедливой очередью имеет сложность планирования O (бревно N), где N - количество задач в очередь. Выбор задачи может быть выполнен за постоянное время, но для повторной вставки задачи после ее выполнения требуется O (журнал N) операций, поскольку очередь выполнения реализована как красно-черное дерево.

История

Кон Коливас работа с расписанием, особенно его реализация "честный график "по имени Крайний срок для вращающейся лестницы, вдохновленный Инго Мольнар разработать его CFS, как замену ранее O (1) планировщик, ссылаясь на Коливаса в своем заявлении.^[3]CFS - это реализация хорошо изученного классического алгоритма планирования, называемого взвешенная справедливая очередь.^[4] Изначально изобретен для пакетные сети, справедливая организация очереди ранее применялась к планированию ЦП под именем планирование шага. CFS - первая реализация честной очереди. планировщик процессов широко используется в операционных системах общего назначения.^[4]

Ядро Linux получило исправление для CFS в ноябре 2010 года для ядра 2.6.38, которое сделало планировщик более справедливым для использования на настольных компьютерах и рабочих станциях. Разработан Майком Гэлбрейтом с использованием идей, предложенных Линус Торвальдс, патч реализует функцию автогруппировки, которая значительно повышает производительность интерактивного рабочего стола.^[5] Алгоритм помещает родительские процессы в ту же группу задач, что и дочерние процессы.^[6](Группы задач привязаны к сеансам, созданным через setsid () системный вызов.^[7]) Это решило проблему медленного интерактивного времени отклика на многоядерных и многопроцессорных (SMP ), когда они выполняли другие задачи, которые используют много потоков, интенсивно использующих ЦП в этих задачах. Простое объяснение заключается в том, что с применением этого патча можно будет по-прежнему смотреть видео, читать электронную почту и выполнять другие типичные действия на рабочем столе без сбоев или прерываний, пока, скажем, компилирует Ядро Linux или кодирование видео.

В 2016 году планировщик Linux был исправлен для повышения многоядерной производительности на основе предложений, изложенных в документе «Планировщик Linux: десятилетие потраченных впустую ядер».^[8]

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

• Планировщик Brain Fuck
• SCHED_DEADLINE

Рекомендации

внешняя ссылка

• Корбет, Джонатан (17 апреля 2007 г.). «Планировщики: сюжет становится более плотным». LWN.net. Архивировано из оригинал на 2017-09-06. Получено 2016-07-21.
• Корбет, Дж. (2007-07-02). «Планирование группы CFS». LWN.net. Архивировано из оригинал на 2017-09-06. Получено 2016-07-21.
• Корбет, Дж. (16 октября 2007 г.). "Справедливое планирование пользователей и другие исправления планировщика". LWN.net. Архивировано из оригинал на 2017-06-12. Получено 2016-11-24.
• Корбет, Дж. (17 ноября 2010 г.). "Групповое планирование на основе телетайпа". LWN.net. Архивировано из оригинал на 2018-05-21. Получено 2016-11-24.
• Корбет, Дж. (06.12.2010). «Групповое планирование и альтернативы». LWN.net. Архивировано из оригинал на 2017-06-11. Получено 2016-11-24.
• Сингх Пабла, Чандандип (01.08.2009). "Совершенно честный планировщик". linuxjournal.com. Архивировано из оригинал на 2018-03-18. Получено 2014-11-17.
• Джонс, Тим (15 декабря 2009 г.). «Внутри Linux 2.6 полностью честный планировщик». ibm.
• Лози, Жан-Пьер (2016-04-21). «Планировщик Linux: десятилетие потраченных зря ядер» (PDF). ACM. Архивировано из оригинал (PDF) на 2018-02-05. Получено 2016-11-24.