Linux CFS

CFS (Completely Fair Scheduler) — это планировщик задач (процессов) ядра операционной системы Linux, реализующий алгоритм полностью справедливого распределения процессорного времени. CFS является планировщиком по умолчанию для обычных (не реального времени) процессов в ядре Linux начиная с версии 2.6.23 (выпущена в октябре 2007 года). Разработан австралийским программистом Коном Коливасом (Con Kolivas) и впоследствии доработан и внедрён разработчиками ядра Linux, в первую очередь Ингваром Молнаром (Ingo Molnár). Основная цель CFS — обеспечить максимально справедливое распределение процессорного времени между всеми запущенными процессами, минимизируя при этом накладные расходы на переключение контекста и задержки.

История и предпосылки создания

До появления CFS в ядре Linux использовался планировщик O(1) (сложность O(1), то есть константная), также разработанный Ингваром Молнаром и внедрённый в ядре 2.6. Планировщик O(1) был значительным улучшением по сравнению с предыдущим планировщиком O(n), но обладал рядом недостатков, особенно на десктопных системах. Он был оптимизирован для серверных нагрузок и многопроцессорных систем, но плохо справлялся с интерактивными задачами (например, с графическим интерфейсом пользователя), что приводило к «залипаниям» и неотзывчивости системы.

В середине 2000-х годов Кон Коливас, не будучи штатным разработчиком ядра, создал альтернативный планировщик — Staircase Scheduler, а затем его улучшенную версию — Rotating Staircase Deadline Scheduler (RSDL). Эти планировщики демонстрировали превосходную интерактивность и справедливость, что вызвало большой интерес сообщества. Линус Торвальдс, главный архитектор Linux, признал необходимость изменений. Ингвар Молнар взял идеи Коливаса (в частности, концепцию «виртуального времени» и «красного-чёрного дерева») и реализовал их в виде CFS, который был принят в основную ветку ядра в версии 2.6.23. Сам Кон Коливас, разочарованный бюрократическими процессами разработки ядра, впоследствии создал альтернативную операционную систему MuQSS (Multiple Queue Skiplist Scheduler) для ядра Linux, но CFS остаётся стандартом.

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

В основе CFS лежит модель «идеального, полностью справедливого мультиплексирования». Теоретически, если в системе работает N процессов, каждый из них должен получать 1/N процессорного времени. На практике, из-за квантов времени (минимальных интервалов, на которые процесс запускается), точное соблюдение этой пропорции невозможно, поэтому CFS стремится к ней асимптотически.

Виртуальное время (vruntime)

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

Красно-чёрное дерево (Red-Black Tree)

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

Квант времени и целевая задержка (targeted latency)

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

Приоритеты и nice-значения

Хотя CFS стремится к равенству, он поддерживает приоритеты процессов через стандартный механизм nice-значений (от -20 до +19). Процесс с более низким nice-значением (высокий приоритет) получает больший вес при расчёте vruntime. Формула расчёта vruntime учитывает вес процесса: vruntime += (реальное время * 1024) / вес. Вес процесса экспоненциально зависит от nice: например, процесс с nice=0 имеет вес 1024, с nice=-20 — около 88761, с nice=+19 — около 15. Таким образом, высокоприоритетный процесс будет накапливать vruntime медленнее и, следовательно, получать больше процессорного времени.

Классификация и типы процессов в контексте CFS

В рамках CFS процессы делятся на два основных класса:

• SCHED_NORMAL (SCHED_OTHER) — стандартный класс для обычных процессов (включая интерактивные и фоновые). Именно для них предназначен CFS.
• SCHED_BATCH — класс для пакетных (batch) процессов, которые не являются интерактивными. CFS даёт таким процессам более крупные кванты времени и реже их переключает, что снижает накладные расходы, но увеличивает задержки. Это полезно для длительных вычислительных задач.
• SCHED_IDLE — класс для фоновых задач с очень низким приоритетом. Процессы этого класса получают процессорное время только тогда, когда в системе нет других готовых к выполнению процессов.

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

Особенности и критика

Преимущества

• Справедливость: Обеспечивает равномерное распределение процессорного времени, что особенно заметно в многозадачных средах.
• Интерактивность: Благодаря динамическому расчёту квантов и быстрому переключению, CFS хорошо подходит для десктопных систем, обеспечивая плавную работу интерфейса.
• Масштабируемость: Красно-чёрное дерево эффективно работает при большом количестве процессов (сотни и тысячи).
• Простота модели: Концепция vruntime интуитивно понятна и легко реализуема.

Недостатки и критика

• Неоптимальность для специфических нагрузок: CFS не идеален для систем с жёсткими требованиями к задержкам (например, аудио- и видеопроизводство в реальном времени). Для таких задач часто используют ядра с поддержкой PREEMPT_RT (реального времени).
• Проблемы с «групповым планированием»: В ранних версиях CFS были сложности с обеспечением справедливости между группами процессов (например, между разными пользователями или контейнерами). Позднее была добавлена поддержка CFS Group Scheduling через контрольные группы (cgroups), которая решает эту проблему.
• Чувствительность к параметрам: Настройка параметров (целевая задержка, минимальная гранулярность) требует понимания рабочей нагрузки. Неправильные настройки могут ухудшить производительность.
• Энергопотребление: На мобильных устройствах CFS может быть менее энергоэффективен, чем специализированные планировщики (например, Energy-Aware Scheduling — EAS), так как он не всегда оптимально распределяет нагрузку между ядрами разной производительности (big.LITTLE).

Применение

CFS используется в подавляющем большинстве дистрибутивов Linux (Debian, Ubuntu, Fedora, CentOS, Arch Linux и др.) для всех обычных процессов. Он является стандартным планировщиком для:

• Серверов (веб-серверы, базы данных, файловые серверы).
• Десктопов и рабочих станций.
• Встраиваемых систем (при условии отсутствия жёстких требований реального времени).
• Контейнерных сред (Docker, LXC) — через cgroups.

Альтернативами CFS являются планировщики реального времени (PREEMPT_RT), Brain Fuck Scheduler (BFS) и его преемник MuQSS (используются в некоторых нестандартных ядрах, например, в Linux-ck), а также Energy-Aware Scheduling (EAS) для ARM-устройств.

Источники

• Documentation/scheduler/sched-design-CFS.txt — документация ядра Linux.
• Understanding the Linux Kernel (3rd Edition) — Daniel P. Bovet, Marco Cesati.
• Linux Kernel Development (3rd Edition) — Robert Love.
• Патч-сет CFS Ингвара Молнара (2007) — обсуждение в списке рассылки ядра Linux.
• Работы Кона Коливаса — Staircase Scheduler и RSDL.