Completely Fair Scheduler ( CFS ) был планировщиком процессов , который был объединен с выпуском 2.6.23 (октябрь 2007 г.) ядра Linux . Он был планировщиком по умолчанию для задач класса (т. е. задач, не имеющих ограничений на выполнение в реальном времени) и управлял распределением ресурсов ЦП для выполнения процессов , стремясь максимизировать общее использование ЦП, а также максимизировать интерактивную производительность.SCHED_NORMAL
В отличие от предыдущего планировщика O(1) , использовавшегося в старых ядрах Linux 2.6, который поддерживал и переключал очереди выполнения активных и просроченных задач, реализация планировщика CFS основана на очередях выполнения по ЦП, узлы которых являются упорядоченными по времени планируемыми сущностями, которые хранятся отсортированными по красно-черным деревьям . CFS устраняет старое понятие фиксированных временных срезов по приоритетам и вместо этого стремится отдать справедливую долю времени ЦП задачам (или, лучше, планируемым сущностям). [1] [2]
Начиная с версии 6.6 ядра Linux его заменил планировщик EEVDF .
Задача (т. е. синоним потока) — это минимальная сущность, которую Linux может планировать. Однако он также может управлять группами потоков, целыми многопоточными процессами и даже всеми процессами данного пользователя. Такая конструкция приводит к концепции планируемых сущностей, где задачи группируются и управляются планировщиком как единое целое. Чтобы эта конструкция работала, каждый task_structдескриптор задачи встраивает поле типа sched_entity, представляющее набор сущностей, к которым принадлежит задача.
Каждая очередь выполнения по ЦП типа cfs_rqсортирует sched_entityструктуры в упорядоченном по времени виде в красно-черное дерево (или 'rbtree' на жаргоне Linux), где самый левый узел занят сущностью, которая получила наименьший отрезок времени выполнения (который сохраняется в поле vruntimeсущности). Узлы индексируются по " времени выполнения " процессора в наносекундах. [3]
Для каждого процесса также рассчитывается " максимальное время выполнения ", представляющее время, которое процесс ожидал бы для выполнения на "идеальном процессоре". Это время, которое процесс ожидал выполнения, деленное на общее количество процессов.
Когда планировщик вызывается для запуска нового процесса:
Если процесс проводит много времени в состоянии сна, то его затраченное время невелико, и он автоматически получает повышение приоритета, когда оно ему наконец понадобится. Следовательно, такие задачи не получают меньше процессорного времени, чем задачи, которые постоянно выполняются.
Сложность алгоритма, который вставляет узлы в cfs_rqочередь выполнения планировщика CFS, составляет O ( log N ), где N — общее количество сущностей. Выбор следующей сущности для выполнения выполняется за постоянное время, поскольку самый левый узел всегда кэшируется.
Работа Кона Коливаса с планированием, наиболее значительная из его реализации « справедливого планирования » под названием Rotating Staircase Deadline , вдохновила Инго Молнара на разработку своего CFS в качестве замены более раннего планировщика O(1) , в объявлении которого он упомянул Коливаса. [4] CFS — это реализация хорошо изученного классического алгоритма планирования, называемого взвешенной справедливой очередью . [5] Первоначально изобретенная для пакетных сетей , справедливая очередь ранее применялась к планированию ЦП под названием stride scheduling . CFS — это первая реализация планировщика процесса справедливой очереди , широко используемая в операционной системе общего назначения. [5]
Ядро Linux получило патч для CFS в ноябре 2010 года для ядра 2.6.38, который сделал планировщик «более справедливым» для использования на настольных компьютерах и рабочих станциях. Разработанный Майком Гэлбрейтом с использованием идей, предложенных Линусом Торвальдсом , патч реализует функцию, называемую автоматической группировкой, которая значительно повышает производительность интерактивного рабочего стола. [6] Алгоритм помещает родительские процессы в ту же группу задач, что и дочерние процессы. [7] (Группы задач привязаны к сеансам, созданным с помощью системного вызова setsid(). [8] ) Это решило проблему медленного времени интерактивного отклика в многоядерных и многопроцессорных ( SMP ) системах, когда они выполняли другие задачи, использующие много потоков, интенсивно использующих процессор. Простое объяснение заключается в том, что с применением этого патча можно по-прежнему смотреть видео, читать электронную почту и выполнять другие типичные действия на рабочем столе без сбоев или прерываний, например, при компиляции ядра Linux или кодировании видео.
В 2016 году планировщик Linux был исправлен для улучшения многоядерной производительности на основе предложений, изложенных в статье «Планировщик Linux: десятилетие бесполезной траты ядер» [9] .
В 2023 году новый планировщик, основанный на раннем подходящем виртуальном крайнем сроке первого планирования (EEVDF), был подготовлен для замены CFS. [10] Мотивацией было устранение необходимости в исправлениях CFS «latency nice». [11]