Планировщик CFS¶

Планировщик CFS (Completely Fair Scheduler, полностью справедливый планировщик) — это алгоритм планирования процессов в операционной системе Linux, используемый по умолчанию для задач общего назначения (SCHED_NORMAL). Он был разработан австралийским программистом Инго Мольнаром и внедрён в ядро Linux версии 2.6.23 в 2007 году, заменив предыдущий планировщик O(1). Основная цель CFS — обеспечить максимально справедливое распределение процессорного времени между всеми выполняющимися процессами, моделируя идеальное мультизадачное окружение.

¶История

До появления CFS в ядре Linux использовался планировщик O(1), разработанный в 2002 году. Несмотря на свою эффективность при большом количестве процессов, он имел ряд недостатков, включая сложность настройки и неоптимальное поведение в интерактивных сценариях. В 2007 году Инго Мольнар представил CFS как часть набора патчей для ядра 2.6.23. Алгоритм был основан на концепции «красного-чёрного дерева» (red-black tree) и модели идеального мультизадачного процессора. CFS быстро стал стандартным планировщиком и с тех пор постоянно совершенствовался, включая оптимизации для многоядерных систем, энергосбережения и поддержку контейнеров.

¶Принцип работы

Основная идея CFS заключается в том, чтобы каждому процессу предоставлять долю процессорного времени, пропорциональную его приоритету. Вместо традиционных очередей с фиксированными квантами времени CFS использует модель «виртуального времени» (vruntime). Каждому процессу присваивается значение vruntime, которое увеличивается по мере его выполнения. Чем выше приоритет процесса (ниже значение nice), тем медленнее растёт его vruntime, что позволяет ему получать больше процессорного времени.

¶Красное-чёрное дерево

CFS хранит все готовые к выполнению процессы в структуре данных — красно-чёрном дереве, где ключом является значение vruntime. Процесс с наименьшим vruntime (то есть тот, который получил меньше всего процессорного времени относительно других) находится в крайнем левом узле дерева и выбирается для выполнения следующим. После выполнения процесса его vruntime увеличивается, и он может быть перемещён вправо по дереву, уступая место другим процессам. Это обеспечивает постоянное выравнивание времени выполнения между всеми процессами.

¶Квант времени

В отличие от классических планировщиков, CFS не использует фиксированный квант времени. Вместо этого он определяет целевой период планирования (targeted latency), в течение которого каждый процесс должен получить хотя бы один шанс на выполнение. Квант времени для каждого процесса вычисляется как отношение его веса к общему весу всех процессов, умноженное на целевой период. Если количество процессов велико, квант может стать слишком маленьким, что приведёт к большим накладным расходам на переключение контекста. Для предотвращения этого вводится минимальная гранулярность (min_granularity) — минимальный квант времени, который может быть выделен процессу.

¶Приоритеты и веса

В CFS приоритет процесса задаётся через значение nice, которое может варьироваться от -20 (наивысший приоритет) до +19 (наинизший приоритет). Каждому значению nice соответствует определённый вес, который определяет долю процессорного времени, выделяемую процессу. Чем ниже значение nice (выше приоритет), тем больше вес и тем больше процессорного времени получает процесс. Значение vruntime процесса корректируется с учётом его веса: для процесса с высоким приоритетом vruntime растёт медленнее, что позволяет ему дольше оставаться в левой части дерева и чаще получать процессор.

¶Таблица соответствия приоритетов и весов (примерные значения)

¶Поддержка многоядерных систем

CFS включает механизмы для эффективной работы на многоядерных процессорах. Каждый центральный процессор (CPU) имеет свою собственную очередь готовых к выполнению процессов (runqueue), что позволяет избежать глобальных блокировок. Для балансировки нагрузки между ядрами используется механизм load balancing, который периодически оценивает загрузку каждого ядра и перемещает процессы с перегруженных ядер на менее загруженные. При этом учитывается кэш-аффинность процессов — стремление не перемещать процесс на другое ядро, если он уже имеет горячий кэш на текущем.

¶Групповое планирование

CFS поддерживает групповое планирование (group scheduling), которое позволяет объединять процессы в группы (например, по пользователям или контейнерам) и распределять процессорное время между группами, а не между отдельными процессами. Это особенно важно для серверных сред и систем, использующих контейнеризацию (например, Docker), где необходимо гарантировать, что каждый пользователь или контейнер получит справедливую долю ресурсов независимо от количества запущенных внутри процессов.

¶Интерактивность и энергосбережение

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

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

¶Сравнение с другими планировщиками

CFS значительно отличается от планировщика O(1), который использовал фиксированные очереди приоритетов и сложные эвристики для определения интерактивности. CFS проще в реализации и более предсказуем в поведении. В реальном времени (RT) используются другие планировщики, такие как SCHED_FIFO и SCHED_RR, которые не являются справедливыми и предназначены для задач с жёсткими временными ограничениями. Для мультимедийных приложений иногда применяется планировщик BFS, который ориентирован на максимальную интерактивность на десктопах, но не масштабируется на большие серверы.

¶Критика и ограничения

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

¶Применение

CFS используется по умолчанию в большинстве дистрибутивов Linux, включая Ubuntu, Debian, Fedora, CentOS, Arch Linux и многие другие. Он применяется как на десктопах, так и на серверах, в облачных средах и встраиваемых системах. Благодаря своей справедливости и предсказуемости, CFS является основой для многих современных систем управления ресурсами, включая cgroups и контейнерные платформы.

¶Интересные факты

• Название «Completely Fair Scheduler» (полностью справедливый планировщик) было выбрано с иронией, так как полная справедливость в компьютерных системах недостижима.
• CFS был одним из первых крупных компонентов ядра Linux, полностью переписанных после перехода на модель разработки с использованием Git.
• Инго Мольнар, создатель CFS, также известен своей работой над планировщиком реального времени и вкладом в разработку ядра Linux в целом.

¶Источники

• Документация ядра Linux: «sched-design-CFS.txt»
• Статья Инго Мольнара «CFS: Completely Fair Scheduler» в списке рассылки ядра Linux (2007)
• Книга «Linux Kernel Development» (3-е издание), Роберт Лав
• Документация по планировщику CFS на сайте kernel.org
• Статья «Inside the Linux 2.6 Completely Fair Scheduler» на IBM DeveloperWorks (2009)