Планирование процессов в Linux через Completely Fair Scheduler

Содержание

1. 1. Эволюция планировщиков Linux3
2. 2. Виртуальное время и справедливость6
3. 3. Красно-черные деревья в CFS8
4. 4. Влияние CFS на производительность10
5. Список литературы12

1. Эволюция планировщиков Linux

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

В ядре 2.4 появился планировщик O(n), названный так по сложности поиска следующего процесса. При каждом переключении он пробегал по всему списку задач, вычислял приоритет каждой и выбирал лучшую. Проблема была не только в линейной сложности. Приоритет пересчитывался один раз в секунду, поэтому задачи с одинаковым приоритетом могли голодать: планировщик не запоминал, кому сколько времени уже выделил. Интерактивные приложения вроде текстового редактора начинали тормозить под нагрузкой, потому что их кванты тратились впустую на фоновые процессы. Для эпохи настольных систем это было терпимо, но масштабирование на симметричные многопроцессорные конфигурации давалось с большим скрипом: общая блокировка очереди задач сводила на нет выигрыш от нескольких ядер.

Инго Мольнар, один из ключевых разработчиков того времени, взялся за радикальную переработку. Результат его работы, планировщик O(1), вошёл в ядро 2.6 в 2003 году. Алгоритм хранил два массива очередей: активный и истёкший. Выбор следующей задачи занимал константное время, независимо от их числа. Каждый процесс получал приоритет, зависящий от того, насколько он интерактивен: короткие всплески активности повышали ранг, длительные вычисления понижали. На бумаге

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

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

Выход предложил тот же Инго Мольнар. В апреле 2007 года он опубликовал патч, реализующий Completely Fair Scheduler, CFS. Идея была до гениальности проста: вместо сложной системы приоритетов и квантов, планировщик моделирует идеально справедливый мультиплексированный процессор. Если в системе N задач, каждая должна получать ровно 1/N времени процессора. CFS отслеживает, сколько времени фактически получила каждая задача, и выбирает ту, которая отстала от идеала больше всех. Никаких догадок об интерактивности: задача, которая спит и ждёт ввода, автоматически накапливает право на большее время, когда проснётся. Это решило проблему отзывчивости без единой эвристики.

Мольнар сформулировал две цели, которые легли в основу разработки. Первая: сделать планировщик настолько простым, насколько это

возможно, чтобы его поведение было предсказуемым и поддавалось анализу. Вторая: гарантировать, что в любой момент времени разница между фактическим и идеальным распределением процессорного времени для каждой задачи не превысит одного кванта. Последнее достигалось за счёт того, что все задачи хранились в красно-чёрном дереве, отсортированном по накопленному виртуальному времени выполнения. Вставка и удаление занимали логарифмическое время, а выбор следующей задачи сводился к взятию крайнего левого узла. CFS был принят в основную ветку ядра 2.6.23 в октябре 2007 года, и с тех пор его преемники, включая EEVDF, остаются основой планирования в Linux.

2. Виртуальное время и справедливость

Справедливость в планировании процессов упирается в фундаментальный вопрос: как разделить процессор между задачами разной важности, не ущемляя ни одну из них? CFS отвечает на него через понятие виртуального времени. Это не таймер в привычном смысле. Реальное время измеряет длительность физических процессов, а виртуальное отражает, сколько процессорного времени «заслужил» процесс относительно других.

Механика расчета прозрачна. Ядро ведет для каждого процесса переменную `vruntime`, которая увеличивается по формуле: `vruntime += real_runtime * NICE_0_LOAD / weight`. Здесь `real_runtime` это фактическое время работы процесса на CPU, `weight`, его вес, а `NICE_0_LOAD`, константа, вес процесса с приоритетом nice 0. Смысл в том, что при одинаковом реальном времени работы процессы с разным весом накапливают разное виртуальное время.

Вес процесса напрямую связан со значением nice. Чем меньше nice (в диапазоне от -20 до 19), тем больше weight и тем медленнее растет vruntime. Например, процесс с nice 0 имеет вес 1024. Процесс с nice -5 получит вес около 3355, а с nice 5, всего 335. Это означает, что при равном реальном времени выполнения vruntime высокоприоритетного процесса увеличится примерно в три раза медленнее, чем у низкоприоритетного. Такая асимметрия и есть механизм реализации приоритетов.

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

Идея CFS восходит к концепции «идеального мультиплексирования». В теории, если бы существовал процессор бесконечной мощности, каждый процесс мог бы выполняться одновременно со скоростью, пропорциональной его весу. В реальности CPU один, поэтому приходится приближаться к этому идеалу. CFS делает это через виртуальное время: вместо того чтобы точно рассчитывать доли, он стремится уравнять vruntime всех процессов. Чем меньше разброс значений vruntime в системе, тем ближе реальное распределение к идеальному. На практике это означает, что за длительный период каждый процесс получит ровно столько процессорного времени, сколько предписывает его вес.

3. Красно-черные деревья в CFS

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

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

В CFS каждый процесс представлен узлом дерева, а ключом для вставки служит значение vruntime. Процесс с меньшим виртуальным временем находится левее, с большим правее. Тот процесс, который должен исполняться следующим, всегда расположен в крайнем левом узле дерева. Извлечь его просто: нужно спуститься от корня, каждый раз выбирая левого потомка, пока не достигнем узла без левой ветви. Эта операция имеет сложность O(log n), но благодаря тому, что крайний левый узел кэшируется планировщиком, в большинстве случаев она выполняется за константное время.

Когда процесс получает процессор, его vruntime начинает расти. Рано или поздно он перестает быть минимальным, и его место в дереве перестает соответствовать его новому ключу. Тогда планировщик удаляет узел из дерева и вставляет его заново с обновленным значением.

Удаление узла из красно-черного дерева сложнее, чем вставка: если узел черный, нужно восстановить баланс, перекрашивая соседние узлы и выполняя повороты. Но в среднем обе операции остаются логарифмическими. В ядре Linux для этого используются функции rb_insert_color и rb_erase_color из файла lib/rbtree.c, которые реализуют классические алгоритмы, описанные в книге Кормена и соавторов «Алгоритмы: построение и анализ».

Интересная деталь: CFS не хранит в дереве все процессы системы. Спящие или заблокированные задачи, которые не готовы к исполнению, из дерева исключаются. Дерево содержит только активные процессы из очереди готовности. Когда процесс просыпается, он вставляется обратно. Такая экономия позволяет держать дерево компактным даже в системах с тысячами запущенных приложений.

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

В условиях высокой нагрузки, когда десятки процессов конкурируют за процессор, красно-черное дерево ведет себя предсказуемо. Число поворотов при балансировке ограничено, а глубина дерева растет логарифмически. Это позволяет CFS сохранять стабильное время принятия решения даже при существенном росте числа задач. Именно сочетание гарантированной логарифмической сложности и простоты реализации сделало красно-черное дерево стандартом для планировщиков в современных ядрах Linux.

4. Влияние CFS на производительность

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

Однако идеальная справедливость имеет обратную сторону. CFS оптимизирован для общего случая и плохо подходит для задач с жесткими требованиями реального времени. Планировщик не дает никаких гарантий, что процесс получит процессорное время к конкретному дедлайну. Он лишь обещает пропорциональное разделение ресурсов в долгосрочной перспективе. Для аудио- или видеозахвата, где потеря пакета данных из-за задержки критична, это может стать проблемой. В таких сценариях Linux полагается на механизмы реального времени (SCHED_FIFO, SCHED_RR), которые обходят CFS и работают по принципу строгих приоритетов. CFS, в свою очередь, остается для обычных задач, и его попытка быть «справедливым» к высокоприоритетному процессу реального времени привела бы к катастрофе.

Синтетические бенчмарки, проведенные вскоре после выхода ядра 2.6.23, показали, что CFS не только решил проблему интерактивности, но и не потерял в общей пропускной способности. Тесты, такие как развертка ядра Linux или компиляция больших проектов, не выявили значительного регресса по сравнению с O(1). В некоторых сценариях, особенно с большим количеством конкурирующих за процессор задач, CFS даже выигрывал за счет более предсказуемого распределения квантов. Ключевое отличие было в поведении: старый планировщик мог «забыть» о процессе, CFS же обеспечивал плавный, без рывков, прогресс для всех участников.

Эволюция не остановилась. В ядре 6.6, вышедшем в 2023 году, CFS уступил место новому алгоритму EEVDF (Earliest Eligible Virtual Deadline First). Это не революция, а развитие той же идеи. EEVDF добавляет к виртуальному времени понятие «дедлайна», что позволяет более точно контролировать задержки для отдельных задач. Если CFS просто выбирал процесс с наименьшим vruntime, то EEVDF учитывает, сколько времени процесс уже ждал и сколько он должен получить, чтобы выдерживать заданный темп. Это улучшает латентность для чувствительных рабочих нагрузок и упрощает управление приоритетами, делая поведение планировщика еще более предсказуемым. Переход на EEVDF не отменяет заслуг CFS: именно он доказал, что модель справедливого распределения времени работает в масштабах от однокристальных систем до серверов с сотнями ядер. CFS стал фундаментом, на котором строится современное планирование в Linux, а его принципы остаются основой для новых разработок.

СПИСОК ЛИТЕРАТУРЫ

1. CFS Scheduler - The Linux Kernel documentation — https://docs.kernel.org/scheduler/sched-design-CFS.html

2. sched - обзор планирования работы ЦП - Ubuntu Manpage — https://manpages.ubuntu.com/manpages/resolute/ru/man7/sched.7.html

3. Многопроцессорность с Completely Fair Scheduler — https://www.linux.org.ru/news/doc/2518964

4. Принцип работы планировщика задач в Linux — https://habr.com/ru/companies/ruvds/articles/578788/

5. CFS vs O(1) scheduler — https://habr.com/ru/articles/13014/

6. Планировщик задач CFS будет включен в состав Linux ядра 2.6.23 — https://www.opennet.ru/opennews/art.shtml?num=11356

7. Планировщик задач в Linux и виртуальное время — https://fileenergy.com/linux/kak-rabotaet-planirovshchik-zadach-linux-i-pochemu-ideya-virtualnogo-vremeni-izmenila-vsjo

8. Презентация PowerPoint — https://csc.sibsutis.ru/sites/csc.sibsutis.ru/files/courses/os/Lecture_06.pdf