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

В главе про метрики мы гнались за оборотом (как быстро задача завершится) и откликом (как быстро она впервые получит CPU). А в MLFQ — пытались угадать, кто интерактивный, кто счётный, и раздавать приоритеты.

Теперь сменим вопрос. Допустим, нам не так важно, кто закончит первым. Важно справедливо поделить CPU в нужной пропорции. Например: «сервису A дать 50% процессора, сервису B — 30%, фоновым джобам C — 20%». Это и есть пропорциональное планирование (proportional-share, оно же fair-share).

Бытовая аналогия: вы делите интернет-канал в квартире. Не «кто первый качает, тому всё», а «геймеру 50% скорости, рабочему ноуту 30%, телефону 20%». Кто сколько заплатил долей — столько в среднем и получает.

  Обычный планировщик          Пропорциональный планировщик
  (scheduling / mlfq)          (lottery / stride / CFS)
 
  «кто закончит быстрее?»       «кто какую ДОЛЮ CPU получит?»
  цель: turnaround / response   цель: A=50%, B=30%, C=20%
  угадываем длину/тип           явно задаём вес/билеты

Что нарисовано: слева — привычная цель (быстрее завершить/ответить), справа — новая цель (поделить ресурс по заданным долям). Дальше разберём три способа это сделать: lottery, stride и CFS (то, что реально крутится в Linux).

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

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

Чем больше у тебя билетов, тем выше шанс, что вытянут именно твой → тем больше CPU в среднем достанется. «В среднем» — ключевое слово: это вероятностный механизм.

  Раздали билеты (всего 100):
 
  A: ███████████████████████████████████████████████████  тикеты 0..49   (50)
  B: ██████████████████████████████                        тикеты 50..79  (30)
  C: ████████████████████                                  тикеты 80..99  (20)
 
  Розыгрыш тиков (random 0..99):
 
  тик: 1   2   3   4   5   6   7   8   9   10
  rnd: 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. На коротком интервале возможен перекос, на длинном доли сходятся к заданным (закон больших чисел).

Плюсы lottery:

• Простота. Весь планировщик — это «сгенерируй random, найди владельца».
• Нет голодания. У каждого, у кого хоть 1 билет, есть ненулевой шанс.
• Легко менять доли: просто выдай/забери билеты.

Минус — дисперсия (разброс). На коротких отрезках реальная доля скачет: не повезло с рандомом — и за секунду ты получил не 50%, а 35%. Для строгого SLA это плохо. Хочется детерминизма — и тут приходит stride.

Stride: детерминированная версия

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

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

Чем больше билетов — тем меньше шаг. У каждого процесса есть счётчик pass (накопленный «виртуальный пробег»), стартует с 0. Алгоритм на каждом тике:

1. Выбрать процесс с минимальным pass (он «меньше всех пробежал» → его очередь).
2. Запустить его на квант.
3. Прибавить к его pass его же stride.

Возьмём билеты A=100, B=50, C=25 и большое число 10000. Тогда strideA=100, strideB=200, strideC=400. Тот, у кого больше билетов, имеет меньший шаг → его pass растёт медленно → его выбирают чаще.

  stride:  A=100   B=200   C=400
 
  тик │ выбрали │ pass.A │ pass.B │ pass.C
  ────┼─────────┼────────┼────────┼────────
   0  │   A     │  100   │   0    │   0     (все по 0, берём A)
   1  │   B     │  100   │  200   │   0
   2  │   C     │  100   │  200   │  400
   3  │   A     │  200   │  200   │  400
   4  │   A     │  300   │  200   │  400
   5  │   B     │  300   │  400   │  400
   6  │   A     │  400   │  400   │  400
   7  │   A     │  500   │  400   │  400
  ────┴─────────┴────────┴────────┴────────
  Итог за 8 тиков: A=4, B=2, C=2  → ~ 4:2:2 = 100:50:25 ✓

Что нарисовано: на каждом шаге берём строку с минимальным pass, запускаем этот процесс и увеличиваем его pass на stride. У A шаг маленький, поэтому его pass догоняет остальных медленно — и A выбирают вдвое чаще, чем B, и вчетверо чаще, чем C. Ровно как требовали билеты. Никакого рандома — результат точный и повторяемый.

Сравним два подхода:

Тонкость stride: какой pass дать новому процессу? Если поставить 0 — он монополизирует CPU, пока не догонит остальных. Поэтому новичку обычно присваивают текущий минимальный pass в системе. Именно эту проблему изящно решает CFS.

CFS: как это сделано в Linux

CFS (Completely Fair Scheduler) — планировщик, много лет работавший по умолчанию в Linux. Идея — та же пропорциональность, но через понятие vruntime (virtual runtime, виртуальное время выполнения).

vruntime — это «сколько процессор уже накрутил для данной задачи», но взвешенное по приоритету. Правило одно:

  Всегда запускай задачу с НАИМЕНЬШИМ vruntime.

Это прямой родственник stride: vruntime ≈ pass, «выбрать минимальный» — то же самое. Когда задача бежит, её vruntime растёт. У низкоприоритетных он растёт быстрее (они быстрее «наедаются»), у высокоприоритетных — медленнее, так что их выбирают чаще.

Приоритет в Linux задаётся через nice — число от −20 (самый «жадный», высокий приоритет) до +19 (самый «вежливый», уступает другим). nice превращается в вес (weight). Прирост vruntime считается так:

  Δvruntime = Δreal_time * (вес_базовый / вес_задачи)
 
  nice = 0   → вес ~1024  → vruntime растёт «нормально»
  nice < 0   → вес больше → vruntime растёт медленнее → CPU больше
  nice > 0   → вес меньше → vruntime растёт быстрее  → CPU меньше

То есть «реальную» секунду CPU система пересчитывает в «виртуальные» секунды по весу. У жадной задачи секунда CPU стоит дёшево (мало виртуального времени), у вежливой — дорого.

  Кто следующий? Берём минимальный vruntime:
 
   задача │ vruntime
   ───────┼─────────
     P1   │   120     ← минимум, запускаем его
     P2   │   145
     P3   │   210
     P4   │   145
 
  P1 отбегал квант, его vruntime подрос до 150:
 
   задача │ vruntime
   ───────┼─────────
     P2   │   145     ← теперь минимум он
     P4   │   145
     P1   │   150
     P3   │   210

Что нарисовано: CFS всегда хватает задачу с самым маленьким vruntime, даёт ей CPU, после чего её vruntime растёт и она «отодвигается» назад. Так все задачи держатся примерно на одном виртуальном времени — отсюда «completely fair».

Чтобы находить минимум быстро, CFS хранит задачи не в списке, а в красно-чёрном дереве (red-black tree) — самобалансирующемся бинарном дереве поиска, упорядоченном по vruntime. Самый левый узел — минимум.

  Красно-чёрное дерево по vruntime:
 
              (150)
             /     \
         (145)     (210)
         /
     (120) ← самый левый = минимум = запустить следующим
 
  Вставка/удаление/поиск минимума — O(log n).

Что нарисовано: дерево упорядочено по vruntime, минимум всегда «крайний слева». Поэтому «выбрать следующего» и «вернуть отработавшего обратно» стоят O(log n) — дёшево даже при тысячах задач. Сравните с MLFQ, где были отдельные очереди на каждый приоритет.

Новый процесс в CFS получает vruntime около текущего минимума в дереве — тот самый трюк, что мы вручную делали в stride, тут встроен.

Связь с многоядерностью и проддействительностью

На многоядерной машине (см. multiprocessor scheduling) у каждого ядра — своя очередь (свой runqueue, своё дерево). Это даёт affinity (задача чаще остаётся на том же ядре → горячий кеш) и убирает борьбу за один общий замок. Периодически работает load balancing — перетаскивание задач между ядрами, чтобы они не простаивали.

А теперь то, ради чего бэкендеру это всё нужно: cgroups (control groups) — механизм Linux, которым контейнеры (Docker, Kubernetes) ограничивают CPU. Под капотом — тот же CFS. Два рычага:

• cpu.shares (вес) — относительная доля при конкуренции. Это буквально билеты/вес из CFS. Если процессор свободен, шарой ты не ограничен.
• cpu.cfs_quota_us / cpu.cfs_period_us — жёсткий потолок. «За каждый период period тебе дают не больше quota процессорного времени». Это и есть «дать контейнеру 1.5 ядра».

  Контейнеру дали 1.5 CPU:  quota=150ms, period=100ms
 
  Реальное время →
  период 1: |■■■■■■■■■■ ■■■■■|.....|   потратил 150ms CPU (по 2 ядрам)
            0ms       100ms (за период бюджет 150ms)
                            ↑ бюджет кончился раньше конца периода?
                              → THROTTLING: задачи замораживают до
                                нового периода
 
  cpu.shares = 512 vs 1024  → при драке за ядро доли 1:2
  свободно   → бери сколько хочешь (shares не режет в простое)

Что нарисовано: quota/period — это бюджет CPU на окно времени. Выбрал бюджет раньше — тебя throttle (приостанавливают) до следующего периода, даже если ядра простаивают. Отсюда классическая боль: latency-сервису поставили слишком маленькую quota — он упирается в потолок, появляются «пилообразные» задержки, хотя CPU на ноде свободен. shares же режут только при реальной конкуренции.

Финальное сравнение трёх механизмов:

(*) наивные реализации; их тоже можно ускорить структурами данных.

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

• Чем пропорциональное планирование отличается от SJF/MLFQ? SJF/MLFQ оптимизируют оборот/отклик и угадывают тип задачи; proportional-share явно делит CPU в заданных долях (по билетам/весу), справедливость важнее скорости.
• Lottery vs stride. Оба дают одинаковые средние доли. Lottery — случайный, простой, но с дисперсией на коротких интервалах; stride — детерминированный (min pass), точный, но нужно состояние pass и аккуратный старт нового процесса.
• Что такое vruntime и как работает CFS. vruntime — взвешенное по приоритету накопленное время CPU; CFS всегда запускает задачу с минимальным vruntime, хранит их в красно-чёрном дереве (выбор минимума за O(log n)). Это «stride» с весами и быстрой структурой.
• Как nice влияет на CPU. nice задаёт вес: чем меньше nice (ближе к −20), тем больше вес, тем медленнее растёт vruntime, тем больше доля CPU.
• cpu.shares vs cpu.quota в cgroups. shares — относительный вес, режет только при конкуренции; quota/period — жёсткий потолок; при исчерпании бюджета наступает throttling даже на простаивающих ядрах. Частая причина «непонятных» задержек у контейнеров.
• Почему у CFS per-core runqueue. Чтобы не драться за общий замок и сохранять affinity (горячий кеш); баланс между ядрами делает периодический load balancing (см. multiprocessor scheduling).