Пропорциональное планирование и CFS

Другая постановка задачи

В главах про метрики и MLFQ планировщик гнался за оборотом и откликом. Теперь цель другая: поделить процессор в заданной пропорции. Например, на одной машине работают сервис A, сервис B и фоновые джобы C, и вы хотите, чтобы при полной загрузке A получал 50 % процессорного времени, B — 30 %, C — 20 %. Кто закончит первым, здесь вторично. Такой подход называют пропорциональным (proportional share) или справедливым (fair share) планированием.

Бэкендеру эта глава нужна ради одного практического вопроса: как Linux делит процессор между контейнерами и почему контейнер с лимитом «1 CPU» иногда отвечает с задержкой в сотню миллисекунд при полупустой ноде. Чтобы до него дойти, разберём три механизма от простого к реальному: lottery, stride и планировщик Linux.

Lottery: розыгрыш билетов

Каждой задаче выдаём билеты (tickets) пропорционально желаемой доле. На каждом тике планировщик вытягивает случайный билет, и его владелец работает этот квант.

  Всего 100 билетов:
  A: номера 0..49   (50 билетов)
  B: номера 50..79  (30 билетов)
  C: номера 80..99  (20 билетов)
 
  тик:     1   2   3   4   5   6   7   8   9   10
  случ.:   63  12  85  41  07  77  90  33  58  21
  победил: B   A   C   A   A   B   C   A   B   A

За 10 тиков A получила 5 квантов, B — 3, C — 2, ровно 50/30/20. Это повезло: на коротком отрезке вполне могло выйти 7/2/1. Чем длиннее интервал, тем ближе фактические доли к заданным (закон больших чисел), но на коротких интервалах разброс заметный.

Достоинства lottery: планировщик почти не хранит состояния (только число билетов), новую задачу добавить легко, а у любой задачи хотя бы с одним билетом есть шанс получить процессор. Недостаток — та самая случайность: за конкретную секунду задача с половиной билетов может получить и 35 %.

Stride: то же без случайности

Stride scheduling заменяет розыгрыш расчётом. Каждой задаче назначают шаг (stride), обратно пропорциональный числу билетов:

  stride = БОЛЬШОЕ_ЧИСЛО / tickets

У каждой задачи есть счётчик pass, сначала 0. На каждом тике:

1. выбрать задачу с минимальным pass (при равенстве — любую, здесь берём по алфавиту);
2. дать ей квант;
3. прибавить к её pass её stride.

Пусть у A 100 билетов, у B 50, у C 25, большое число 10 000. Тогда stride у A равен 100, у B 200, у C 400.

  тик │ выбрали │ pass A │ pass B │ pass C   (значения ПОСЛЕ тика)
  ────┼─────────┼────────┼────────┼────────
   0  │    A    │  100   │    0   │    0
   1  │    B    │  100   │  200   │    0
   2  │    C    │  100   │  200   │  400
   3  │    A    │  200   │  200   │  400
   4  │    A    │  300   │  200   │  400    (A и B по 200, взяли A)
   5  │    B    │  300   │  400   │  400
   6  │    A    │  400   │  400   │  400
  ────┴─────────┴────────┴────────┴────────
  За 7 тиков: A = 4, B = 2, C = 1, то есть 4 : 2 : 1 = 100 : 50 : 25

После тика 6 все pass снова равны, и цикл повторяется. Доли точные на каждом таком цикле, без всякой случайности.

У stride есть цена: глобальное состояние. Какой pass дать новой задаче? Если 0, она надолго монополизирует процессор, пока не догонит остальных. Поэтому новой задаче дают текущий минимальный pass в системе. Ровно эту идею использует планировщик Linux.

Планировщик Linux: vruntime

С 2007 по 2023 год в Linux по умолчанию работал CFS (Completely Fair Scheduler). В версии ядра 6.6 (конец 2023 года) его алгоритм выбора задачи заменили на EEVDF, о нём ниже. Учёт времени в обоих одинаковый, и начать проще с CFS.

Вместо pass у каждой задачи есть vruntime (виртуальное время выполнения): сколько процессорного времени она получила, пересчитанное с учётом её веса. Основное правило CFS:

  Запускай задачу с наименьшим vruntime.

Это прямой родственник stride: vruntime играет роль pass, «вес» играет роль билетов.

Вес и nice

Приоритет обычного процесса в Linux задаётся числом nice от −20 до +19. Чем меньше nice, тем процесс «наглее» и тем больше процессора получает. Ядро переводит nice в вес по фиксированной таблице. Несколько значений:

Соседние значения nice отличаются по весу примерно в 1,25 раза. Пока задача работает, её vruntime растёт так:

  Δvruntime = Δреальное_время × 1024 / вес

У задачи с nice 0 vruntime растёт со скоростью реального времени. У задачи с большим весом медленнее, поэтому она чаще оказывается минимальной и чаще запускается.

Пример. На одном ядре CPU две вычислительные задачи: A с nice 0 (вес 1024) и B с nice 5 (вес 335). Доли процессора пропорциональны весам:

  A: 1024 / (1024 + 335) ≈ 75 %
  B:  335 / (1024 + 335) ≈ 25 %

Проверим через vruntime. За 30 мс работы vruntime A вырастет на 30 мс. Задаче B, чтобы её vruntime вырос на те же 30 мс, хватит 30 × 335 / 1024 ≈ 9,8 мс реального времени. Планировщик держит vruntime обеих примерно равными, значит, на каждые 30 мс работы A приходится около 10 мс работы B: те же 75 на 25.

Для эксперимента на Linux: nice -n 5 ./worker запускает процесс с nice 5, renice меняет nice работающего процесса, а top показывает значение в колонке NI.

Как выбирается задача с минимумом

Задачи, готовые к запуску, CFS хранит в красно-чёрном дереве (сбалансированном дереве поиска), упорядоченном по vruntime. Самый левый узел — минимум.

              (150)
             /     \
         (145)     (210)
         /
     (120)   ← самый левый: запустить следующим

Вставка и удаление стоят O(log n), а самый левый узел ядро держит в кэше. Задача поработала, её vruntime вырос, её вставляют обратно правее, а левым становится кто-то другой. Так vruntime всех задач держатся рядом, отсюда «completely fair».

Задача, которая долго спала (ждала сеть), не должна потом монополизировать процессор из-за маленького vruntime. Поэтому при пробуждении её vruntime подтягивают к текущему минимуму в дереве: та же идея, что со стартовым pass в stride.

EEVDF: что изменилось в Linux 6.6

CFS хорошо делил процессор, но плохо управлял задержкой: задача, которой нужно поработать 1 мс, но как можно скорее (обработчик звука, сетевой обработчик), не могла об этом сообщить. Её «наказывали» эвристиками и ручными настройками.

EEVDF (Earliest Eligible Virtual Deadline First) сохраняет vruntime и веса, а выбор задачи делает в два шага:

1. Право на запуск (eligible). Ядро считает средневзвешенный vruntime всех готовых задач. Задача имеет право работать, если она недополучила процессор, то есть её vruntime не больше среднего. Задача, которая уже обогнала остальных, ждёт.
2. Виртуальный дедлайн. Каждая задача просит квант (slice), по умолчанию несколько миллисекунд. Дедлайн = vruntime + slice × 1024 / вес. Из задач с правом на запуск выбирается та, у которой дедлайн самый ранний.

Задача с коротким slice получает ранний дедлайн и запускается раньше, но работает меньше за раз, поэтому её долю в целом это не увеличивает. Доли по-прежнему определяют веса, а задержкой теперь можно управлять отдельно. С ядра 6.12 задача может запросить свой slice через системный вызов sched_setattr.

Код этого планировщика в ядре по-прежнему называется fair scheduler, и на собеседованиях почти всегда говорят «CFS». Отвечайте про vruntime и веса, а затем уточните, что в ядрах с 6.6 выбор задачи делает EEVDF. Это показывает, что вы знаете актуальное состояние.

Связь с многоядерностью

На машине с несколькими ядрами CPU у каждого ядра своя очередь (своё дерево), и задачи между ними время от времени перекладываются. Почему так и как это делают, разберём в главе планирование на многоядерных.

Контейнеры: вес и квота

Контейнеры в Docker и Kubernetes ограничивают процессор через cgroups (control groups) — механизм ядра, который объединяет процессы в группу и управляет её ресурсами. Для процессора два независимых рычага. Имена файлов зависят от версии cgroups; почти все современные дистрибутивы используют cgroup v2.

Вес — это те же билеты, только для группы процессов. Если ядра CPU свободны, группа с маленьким весом берёт сколько хочет. Если не хватает всем, группы делят процессор пропорционально весам. Kubernetes выставляет вес из requests.cpu.

Квота — жёсткий потолок: за каждый период группа может потратить не больше квоты процессорного времени, суммарно по всем ядрам. cpu.max = 150000 100000 значит «150 мс процессора на каждые 100 мс», то есть 1,5 ядра. Kubernetes выставляет квоту из limits.cpu. Когда группа выбрала квоту до конца периода, все её потоки замораживаются до начала следующего. Это троттлинг (throttling).

Троттлинг на числах

Контейнер с лимитом 1 CPU: квота 100 мс на период 100 мс. Нода на 8 ядер, сервис на Go до версии 1.25, поэтому GOMAXPROCS = 8: рантайм готов исполнять код на 8 потоках одновременно.

Приходит запрос, который параллельно обрабатывает 8 горутин, каждой нужно 15 мс процессора.

  период 100 мс
  0 мс          12,5 мс                                    100 мс
  |█ 8 потоков █|░░░░░░░░░░ троттлинг, все потоки стоят ░░░░|█ ...
  квота 100 мс выбрана за 12,5 мс (8 × 12,5 = 100)

За первые 12,5 мс восемь потоков потратили 8 × 12,5 = 100 мс процессора, то есть всю квоту. До конца периода группа стоит, хотя на ноде свободны другие ядра. Каждой горутине осталось досчитать 2,5 мс, они сделают это в начале следующего периода. Запрос, которому нужно 15 мс работы, ответил примерно через 103 мс. В метриках это выглядит как «пила» на p99 при низкой средней загрузке.

Проверить, что дело в троттлинге, можно по файлу cpu.stat группы: поля nr_throttled (сколько периодов закончились троттлингом) и throttled_usec (сколько времени группа стояла).

Лекарства: согласовать параллелизм с квотой (GOMAXPROCS не больше лимита), поднять лимит или убрать его, оставив только вес. С Go 1.25 рантайм на Linux делает первое сам: по умолчанию GOMAXPROCS равен меньшему из числа доступных ядер и квоты cgroup, округлённой вверх (но не меньше 2), и пересчитывается, если лимит поменяли. Это работает, если в go.mod указана версия Go 1.25 или новее и GOMAXPROCS не задан вручную.

Сравнение механизмов

Частые ошибки

• Путать вес и квоту. Вес (cpu.weight, requests) работает только при нехватке процессора, квота (cpu.max, limits) режет всегда.
• Считать, что лимит 2 CPU значит «процесс может использовать 2 ядра». Он значит «200 мс процессора за 100 мс», и эти 200 мс можно выбрать восемью потоками за 25 мс, после чего стоять.
• Думать, что nice 19 полностью останавливает процесс. Он получает мало (вес 15 против 1024), но не ноль.
• Говорить, что Linux «в любом ядре» использует CFS: с 6.6 выбор делает EEVDF.

Проверьте себя

1. Lottery, у A 75 билетов, у B 25. Какую долю процессора получит A в среднем?
2. Stride: у A 200 билетов, у B 100, большое число 1000. Найдите stride и последовательность первых трёх запусков (при равенстве берём A).
3. Две задачи с nice 0 и nice 1. Какие доли процессора они получат?
4. cpu.max = 50000 100000. Сколько это ядер? Сколько миллисекунд в каждом периоде группа простоит, если её 4 потока непрерывно хотят считать?
5. Go 1.25, нода на 16 ядер, cpu.max = 250000 100000. Каким будет GOMAXPROCS по умолчанию?

Что спрашивают на собесе

• Чем пропорциональное планирование отличается от SJF и MLFQ.
• Lottery против stride: одинаковые средние доли, но разная точность на коротком интервале и разное состояние.
• Что такое vruntime, как nice превращается в вес и как вес влияет на рост vruntime.
• Почему CFS хранит задачи в красно-чёрном дереве.
• Что изменил EEVDF в Linux 6.6 и зачем.
• cpu.weight/cpu.shares против cpu.max/квоты; что такое троттлинг и как его увидеть и устранить; что поменялось в Go 1.25 с GOMAXPROCS.