Как работает планировщик задач Linux и почему идея виртуального времени изменила всё

Планировщик процессов - один из тех компонентов ядра, о котором думаешь только тогда, когда он начинает мешать. Лаги в интерфейсе при компиляции в фоне, неотзывчивый терминал при интенсивной записи на диск, голодание фоновых задач на многоядерной машине - всё это симптомы того, что планировщик принял не то решение. Понять, как он принимает решения, значит уметь объяснить поведение системы под нагрузкой и грамотно влиять на него.

Completely Fair Scheduler появился в ядре Linux в октябре 2007 года в версии 2.6.23. Его написал Инго Молнар, вдохновившись работой Кона Коливаса над алгоритмом Rotating Staircase Deadline. CFS заменил предыдущий O(1)-планировщик, у которого были серьёзные проблемы с интерактивностью на десктопных системах. Начиная с ядра 6.6, вышедшего в 2023 году, CFS постепенно уступает место EEVDF-планировщику, однако понимание CFS остаётся фундаментальным - EEVDF строится на тех же концепциях и расширяет их.

Идея идеального многозадачного процессора и виртуальное время

Документация ядра описывает философию CFS одним предложением: планировщик моделирует идеальный точный многозадачный процессор на реальном железе. Что это означает на практике? Если запущено N задач, каждая должна получать ровно 1/N процессорного времени одновременно. На воображаемом идеальном процессоре с бесконечным числом ядер это работало бы буквально - все задачи выполнялись бы параллельно с одинаковой скоростью. На реальном железе с одним ядром приходится чередовать, и возникает вопрос - как чередовать справедливо?

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

Красота этой идеи - в самоорганизации. Никаких сложных эвристик интерактивности, никаких специальных очередей для "важных" задач. Просто монотонно растущий счётчик и выбор минимума. Задача, которая спала полчаса, накопила маленький vruntime и получит приоритет сразу после пробуждения - естественным образом, без явного повышения приоритета.

Красно-чёрное дерево как сердце планировщика

Для того чтобы идея работала эффективно, нужна структура данных с тремя свойствами: отсортированность по vruntime, быстрое извлечение минимума и быстрые вставка с удалением. Обычная очередь с приоритетом (heap) не подходит - вставка в произвольное место занимает O(log N), но поиск элемента занимает O(N). Список не подходит - поиск минимума O(N). Выбор CFS - красно-чёрное дерево, самобалансирующееся бинарное дерево поиска.

CFS поддерживает упорядоченное по времени красно-чёрное дерево, где все запущенные задачи отсортированы по ключу vruntime. CFS выбирает самый левый узел этого дерева - задачу с наименьшим vruntime. По мере продвижения системы вперёд выполненные задачи помещаются всё правее в дереве, постепенно давая шанс каждой задаче стать "самым левым узлом" и попасть на CPU в детерминированный промежуток времени.

Вставка и удаление узлов из дерева выполняются за O(log N), где N - число задач. Выбор следующей задачи происходит за O(1), поскольку самый левый узел всегда кэширован в переменной min_vruntime.

Это элегантное решение: наиболее "голодная" по CPU задача всегда находится мгновенно, а поддержание порядка при вставке новых и удалении выполнившихся задач стоит логарифмического времени - приемлемая цена для планировщика, вызываемого тысячи раз в секунду.

# Посмотреть параметры планировщика для процесса
cat /proc/$$/sched

# Статистика планировщика по всем CPU
cat /proc/schedstat

# Информация о группах планировщика
cat /sys/fs/cgroup/cpu/cpu.stat

Nice-значения, веса и взвешенное справедливое планирование

Абсолютная справедливость - равные доли CPU для всех задач - не всегда то, что нужно. Фоновая задача резервного копирования не должна получать столько же процессорного времени, сколько интерактивная оболочка. Для управления приоритетами UNIX-системы исторически используют nice-значения от -20 (наивысший приоритет) до +19 (наинизший).

CFS не игнорирует nice-значения, но обращается с ними принципиально иначе, чем старые планировщики. Вместо отдельных очередей приоритетов nice-значение преобразуется в вес задачи. Для одного и того же времени на CPU vruntime задачи с более высоким приоритетом увеличивается меньше, чем у задачи с низким приоритетом. Медленный рост vruntime высокоприоритетных задач означает, что их узлы медленно перемещаются слева направо в красно-чёрном дереве, и эти задачи чаще оказываются в позиции для следующего выполнения.

Управлять nice-значением запущенного процесса можно через renice, а новый процесс запустить с нужным приоритетом через nice:

# Запустить задачу с низким приоритетом (nice +15)
nice -n 15 make -j$(nproc)

# Понизить приоритет уже запущенного процесса
renice +10 -p 1234

# Повысить приоритет (требует root для отрицательных значений)
renice -5 -p 1234

# Просмотреть nice-значения всех процессов
ps -eo pid,ni,comm | sort -k2 -n | head -20

Задачи организованы в очередь выполнения, реализованную как красно-чёрное дерево, отсортированное по возрастанию vruntime. Когда CPU ищет следующий поток для выполнения, он выбирает самый левый узел дерева - поток с наименьшим vruntime.

Целевая задержка, минимальная гранулярность и защита от деградации

CFS не переключает задачи непрерывно - это было бы неэффективно из-за overhead переключения контекста. Вместо этого существует понятие целевой задержки (target latency) - интервала времени, в течение которого каждая запущенная задача должна получить хотя бы один квант процессорного времени.

Если целевая задержка составляет 20 мс и запущено 5 задач, каждая получает по 4 мс. Если задач 10, каждая получила бы по 2 мс - но здесь вступает в игру параметр минимальной гранулярности. CFS никогда не устанавливает квант меньше минимальной гранулярности, обычно равной 4-6 мс, чтобы не тратить слишком много времени на переключение контекста.

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

# Целевая задержка планировщика в наносекундах
cat /proc/sys/kernel/sched_latency_ns

# Минимальная гранулярность
cat /proc/sys/kernel/sched_min_granularity_ns

# Период вытеснения для пробуждённых задач
cat /proc/sys/kernel/sched_wakeup_granularity_ns

# Настроить под интерактивные нагрузки (меньше задержка)
echo 4000000 > /proc/sys/kernel/sched_latency_ns
echo 500000 > /proc/sys/kernel/sched_min_granularity_ns

Спящие задачи, справедливость при пробуждении и I/O-нагрузки

Один из тонких аспектов CFS - обращение со спящими задачами. Пока процесс ждёт ввода-вывода или события, его vruntime не растёт. Когда он просыпается, его vruntime оказывается значительно меньше, чем у всех активных задач, - и он немедленно попадает на CPU. Это желаемое поведение для интерактивных задач: пользователь нажал клавишу, процесс получает процессор мгновенно.

Однако неограниченное снижение vruntime спящих задач создало бы проблему: процесс, проспавший час, получил бы час "кредита" CPU и забрал бы всё процессорное время на этот период. CFS решает это через cfs_rq::min_vruntime - минимальное виртуальное время среди всех задач в очереди, монотонно возрастающее значение. Когда спящая задача просыпается, её vruntime корректируется относительно текущего min_vruntime перед помещением в красно-чёрное дерево. Это гарантирует справедливое обращение без несправедливого преимущества из-за длительного сна.

Именно этот механизм объясняет, почему I/O-нагруженные задачи в Linux получают естественный приоритет без каких-либо явных настроек. Процесс, который постоянно читает данные с диска и ждёт завершения операций, накапливает маленький vruntime и всегда получает CPU быстро при пробуждении. CPU-нагруженный процесс, никогда не спящий, накапливает большой vruntime и вытесняется регулярно.

Групповое планирование и балансировка нагрузки на многоядерных системах

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

Но раздельные очереди порождают новую проблему - дисбаланс нагрузки. Одно ядро может быть перегружено, пока другое простаивает. CFS решает это через периодическую балансировку нагрузки между ядрами. Балансировщик мигрирует задачи между очередями, ориентируясь не просто на число задач, а на взвешенную нагрузку с учётом приоритетов.

Посмотреть статистику миграций и балансировки:

# Детальная статистика планировщика включая миграции
cat /proc/schedstat

# Привязать процесс к конкретным ядрам CPU
taskset -c 0,1 ./myapp

# Посмотреть текущую привязку процесса
taskset -p 1234

# Статистика переключений контекста для процесса
cat /proc/1234/status | grep ctxt

Групповое планирование (cgroup CPU) добавляет ещё один уровень справедливости. Без группового планирования процесс с большим числом потоков получил бы пропорционально больше CPU, чем процесс с одним потоком. Группировка задач через cgroup делит нагрузку по группам, обеспечивая справедливость между процессами, а не только между потоками.

# Ограничить процессорное время группы через cgroup v2
echo "50000 100000" > /sys/fs/cgroup/mygroup/cpu.max

# Задать вес группы относительно других
echo 200 > /sys/fs/cgroup/mygroup/cpu.weight

CFS - это планировщик, в котором сложность скрыта за элегантной идеей. Одна переменная на процесс, одно правило выбора, одна структура данных. Из этого минимализма вырастает поведение, которое кажется умным: интерактивные задачи получают приоритет сами по себе, голодание становится структурно невозможным, приоритеты работают без магии отдельных очередей. Понимание vruntime и красно-чёрного дерева даёт ответы на вопросы о поведении системы под нагрузкой без необходимости читать исходный код ядра.