Как Linux распределяет процессорное время между задачами

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

Объект планирования в Linux — задача, представленная структурой task_struct. Она может описывать отдельный процесс или поток выполнения. У каждого CPU есть собственная очередь выполнения, runqueue. Такая организация позволяет ядрам выбирать задачи независимо и снижает конкуренцию за общие структуры данных. Если на одном ядре накопилась нагрузка, а другое простаивает, балансировщик переносит задачи между очередями.

За десятилетия развития Linux подход к выбору следующей задачи изменился от быстрого перебора приоритетов к модели справедливого распределения времени и затем к снижению задержек. Для обычных пользовательских процессов ключевыми этапами стали O(1) Scheduler, CFS и EEVDF.

Классы планирования: сначала определяется приоритет

Планировщик Linux состоит из нескольких классов. Ядро проверяет их по порядку приоритета и берёт готовую задачу из первого подходящего класса.

• stop_sched_class обслуживает внутренние критические операции ядра, когда требуется временно остановить обычные задачи на одном или нескольких CPU.
• SCHED_DEADLINE предназначен для задач реального времени с жёсткими временными границами.
• SCHED_FIFO и SCHED_RR работают с задачами реального времени. В первом случае задача удерживает CPU до добровольной передачи, во втором между задачами одинакового приоритета используется квант времени.
• SCHED_NORMAL и SCHED_BATCH составляют Fair Scheduler — класс для большинства пользовательских процессов.
• SCHED_IDLE оставляет CPU фоновым задачам, когда более важной работы нет.

O(1), CFS и EEVDF относятся именно к Fair Scheduler. Они не заменяют всю подсистему планирования: задачи реального времени и служебные классы продолжают работать по собственным правилам.

O(1): быстрый выбор по очередям приоритетов

Ранние версии Linux использовали O(N) Scheduler. При переключении контекста он просматривал все готовые задачи и рассчитывал для каждой показатель goodness. В расчёт входили приоритет, оставшийся квант времени и привязка к процессору. При небольшом числе процессов это работало приемлемо, однако с ростом очереди сам планировщик стал заметно расходовать CPU.

O(1) Scheduler устранил полный обход. В нём были две очереди фиксированного размера: Active для готовых задач и Expired для задач, исчерпавших свой квант. Каждая очередь содержала списки процессов по уровням приоритета. Планировщик выбирал первую задачу с наивысшим доступным приоритетом, поэтому время выбора не зависело от общего числа процессов.

После завершения кванта задача попадала в Expired. Когда Active пустела, очереди менялись местами и цикл продолжался. Архитектура обеспечивала высокую скорость и хорошо масштабировалась для серверных нагрузок своего времени.

Проблема проявилась в правилах, которыми O(1) определял характер процесса. Алгоритм пытался отличить интерактивную задачу от вычислительной и изменить её приоритет. Эвристики накапливались, усложняли код и могли давать фоновым потокам необоснованные преимущества. Распределение времени между процессами также оставалось недостаточно предсказуемым.

CFS: справедливость через виртуальное время

В 2007 году в Linux появился Completely Fair Scheduler, CFS. Его основная идея — измерять, сколько процессорного времени задача уже получила с учётом своего приоритета. Для этого каждой задаче сопоставляется vruntime, виртуальное время выполнения.

Чем меньше vruntime, тем меньше задача успела поработать и тем раньше она должна получить CPU. Готовые задачи CFS хранит в красно-чёрном дереве, упорядоченном по виртуальному времени. Самый левый узел содержит задачу с минимальным vruntime; на него поддерживается прямой указатель. Добавление, удаление и перебалансировка дерева требуют O(log N).

CFS оперирует сущностью sched_entity, вложенной в task_struct. В ней находятся виртуальное время, вес, узел дерева и параметры, нужные планировщику. Эта модель подходит и для потоков, и для групп задач, например при использовании cgroups.

Скорость роста vruntime зависит от NICE. Значение NICE лежит в диапазоне от -20 до 19 и отражает вес задачи при распределении CPU. У задачи с большим весом виртуальное время растёт медленнее: она получает большую долю процессорного времени, сохраняя принцип справедливости относительно назначенного веса. Для ускорения ядро использует заранее вычисленную таблицу весов, а не вычисляет их на каждом шаге.

Модель виртуального времени сделала поведение Fair Scheduler понятнее: процесс, получивший меньше положенной доли CPU, оказывается ближе к следующему запуску. При этом у CFS проявилась особенность для сценариев, чувствительных к задержкам. Задаче, которой CPU нужен прямо сейчас — например, графической оболочке, мультимедийному приложению или игре, — иногда приходилось ждать дольше желаемого.

EEVDF: право на выполнение и виртуальный дедлайн

В Linux 6.6 для обычных процессов основным алгоритмом Fair Scheduler стал EEVDF — Earliest Eligible Virtual Deadline First. Он сохраняет красно-чёрное дерево и виртуальное время CFS, но меняет правило выбора следующей задачи.

EEVDF вводит два понятия: eligibility, право задачи быть выбранной, и виртуальный дедлайн. Сначала планировщик определяет задачи, которые имеют право на CPU. Затем среди них выбирает задачу с наиболее ранним виртуальным дедлайном.

Право на выполнение связано с величиной lag — отставанием задачи от её справедливой доли процессорного времени. Если lag положителен, задача получила меньше ресурсов, чем ей полагается. Такая задача считается eligible. Отрицательный lag означает, что задача уже использовала больше своей доли.

Виртуальный дедлайн вычисляется из текущего виртуального времени, кванта выполнения и веса задачи:

deadline = vruntime + slice / weight

Здесь slice — квант, выделяемый на выполнение, а weight определяется значением NICE. В результате EEVDF учитывает и накопленную долю CPU, и ожидаемый момент обслуживания задачи. Это уменьшает задержки для интерактивных нагрузок, сохраняя справедливое распределение ресурсов.

Что меняется для администратора и разработчика

Переход от O(1) к CFS, а затем к EEVDF показывает, почему загрузка CPU нельзя оценивать только средним процентом utilisation. Две задачи могут суммарно занимать одинаковую долю процессора, но по-разному влиять на задержки и ощущение отзывчивости системы.

Для серверов важны очереди выполнения на каждом CPU, балансировка нагрузки и веса задач. Для приложений с пользовательским интерфейсом, аудио, видео и короткими интерактивными операциями важен момент, когда задача получит следующий квант. EEVDF добавляет этот аспект в решение Fair Scheduler через eligibility и виртуальные дедлайны.

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