Алгоритмы планирования — от round-robin до CFS
Когда у вас 5 голодных детей и одна шоколадка, нужно делить честно. Алгоритм деления — это и есть scheduling algorithm. На системе с 1500 потоков и 8 CPU задача та же, только дети голодные, шоколадка одна, и kernel решает несколько тысяч раз в секунду.
В этом уроке разберём четыре классических алгоритма: round-robin (всем поровну по очереди), priority-based (важным больше), MLFQ (multilevel feedback queue — умный гибрид), и CFS (Completely Fair Scheduler — то, что было в Linux 18 лет, до конца 2023). Для junior data engineer важно понимать, как именно Linux принимает решение «кому дать CPU следующему» — это объясняет, почему nice работает именно так, почему long-running batch job получает меньше CPU чем интерактивный shell, и почему CPU usage в htop иногда выглядит странно.
Round-robin: простейший fair scheduler
Round-robin — крутая первая модель. Все процессы в одной очереди, scheduler берёт первого, даёт ему фиксированный time slice (например, 10 мс), потом перемещает его в конец очереди и берёт следующего.
Плюсы round-robin:
- Очень просто реализовать.
- Идеально fair: все получают одинаково.
- Гарантированный максимум ожидания:
N * time_slice.
Минусы:
- Нет приоритетов: критичный процесс ждёт наравне с фоновым batch job.
- Нет адаптации: I/O-bound процесс получает свой 10 мс, проспит 9.5 мс на read’е, потом снова 10 мс ждёт следующего хода.
- Время slice — компромисс: длинный slice (=меньше переключений overhead, но плохо для интерактивности), короткий (хорошо для отзывчивости, но дорого).
Round-robin живёт в Linux как SCHED_RR — real-time класс политики (рассмотрим в уроке 04). Для обычных процессов он был оставлен в 90-х из-за минусов.
Priority-based: важные процессы получают больше
Идея простая: каждому процессу присваивается priority (число от 0 до N). Scheduler всегда выбирает процесс с самым высоким приоритетом. При равном приоритете — round-robin внутри уровня.
Главная проблема — starvation: если высокоприоритетный процесс не отпускает CPU, низкоприоритетные ждут вечно. Решается aging — автоматическим повышением приоритета процессов, которые долго ждут. Чем дольше ждёшь — тем выше приоритет, в какой-то момент догонишь любой busy процесс.
Static vs dynamic priority:
- Static — приоритет задаётся при старте, не меняется. Для real-time правильно.
- Dynamic — приоритет меняется в runtime (например, повышается из-за aging, снижается из-за расхода CPU). Для обычных процессов умнее.
Linux традиционно использует комбинацию: real-time классы (SCHED_FIFO, SCHED_RR) с static priority, плюс normal классы (SCHED_OTHER, SCHED_BATCH) с dynamic priority. Подробно — в уроке 03.
MLFQ — multilevel feedback queue
MLFQ — умный алгоритм 70-х: несколько очередей разных приоритетов, плюс автоматическое перемещение между ними на основе поведения.
Логика:
- Новый процесс — в очередь высокого приоритета.
- Использовал весь slice — CPU-bound, demote в очередь ниже.
- Заблокировался на I/O — остаётся в высокой (интерактивный).
- Долго ждёт — promote обратно (anti-starvation).
Результат: интерактивные процессы (shell, текстовый редактор) автоматически в верхних очередях, batch jobs (компиляция, расчёты) — в нижних. Никто специально не настраивает.
MLFQ использовался в коммерческих Unix (Solaris, AIX). В Linux был похожий O(1) scheduler с 2003 по 2007, потом заменён на CFS.
CFS — Completely Fair Scheduler
CFS появился в Linux 2.6.23 (2007), от Ingo Molnar. Основная идея: вместо очередей и эвристик — математически точная справедливость через virtual runtime (vruntime).
Идея в одном предложении: процессы получают CPU пропорционально весу, и CFS всегда даёт CPU тому, кто получил меньше всех.
Как nice влияет на CFS:
nice — значение от -20 (highest) до +19 (lowest). Внутри kernel это превращается в weight — множитель, который входит в формулу:
vruntime_delta = actual_runtime * (NICE_0_WEIGHT / weight)Где NICE_0_WEIGHT = 1024. Веса для nice’ов:
- nice -20 -> weight 88761 (CPU в ~86x больше чем nice 0)
- nice 0 -> weight 1024 (стандарт)
- nice 19 -> weight 15 (CPU в ~68x меньше чем nice 0)
Это значит: процесс с nice -5 получает примерно в 3-4 раза больше CPU чем nice 0, при равной конкуренции. nice работает мультипликативно, а не аддитивно.
# Запустим два CPU-bound процесса -- один nice 0, другой nice 10:
yes > /dev/null &
PID1=$!
nice -n 10 yes > /dev/null &
PID2=$!
sleep 2
# Сравним CPU usage:
ps -p $PID1,$PID2 -o pid,ni,%cpu
# PID 12345 NI 0 %CPU 90
# PID 12346 NI 10 %CPU 10
# nice 10 получает ~10% CPU вместо 50/50
kill $PID1 $PID2Что делает CFS хорошим:
- Никаких эвристик типа “если slice не использовал — хороший, demote”. Чистая математика.
- Идеальный fair-share при равных приоритетах. Каждый получит ровно
1/NCPU. - Никаких magic threshold. Раньше O(1) scheduler имел эвристики «sleep_avg > X -> bonus», их трудно настраивать. CFS просто.
- O(log N) операции через RB-tree. Масштабируется до тысяч runnable tasks.
Что у CFS не идеально:
- Latency-sensitive workloads страдают. Если вам нужна предсказуемая задержка (видео-стриминг, real-time control), CFS усредняет.
- Group scheduling сложный. При большом числе cgroups эффективность падает.
- Cache locality. CFS не очень умно учитывает, что процесс на CPU 0 имеет тёплый кэш — может перенести его на CPU 5 ради баланса.
EEVDF — следующий шаг (Linux 6.6+)
В Linux 6.6 (октябрь 2023) CFS заменили на EEVDF (Earliest Eligible Virtual Deadline First). Это эволюция, не революция. Идея: каждой задаче даётся deadline — желаемое время, к которому она должна получить свой fair share. Scheduler выбирает задачу с наименьшим deadline (то есть кто срочнее).
Для практического junior data engineer-а ничего не меняется: nice, chrt, cgroups работают так же. Изменения внутри. Если у вас kernel 6.6+ (Ubuntu 24.04, Debian 13) — у вас EEVDF.
# Проверьте версию kernel:
uname -r
# 6.8.0-... -- EEVDF
# 5.15.0-... -- CFS
# Текущий scheduler класс не меняется:
chrt -p 1
# SCHED_OTHER -- normal class (CFS/EEVDF под капотом)Сравнительная таблица
Практика: посмотрим scheduler в действии
# 1. Проверим scheduler класс процессов:
chrt -p 1
# pid 1's current scheduling policy: SCHED_OTHER
# pid 1's current scheduling priority: 0
# (SCHED_OTHER = CFS/EEVDF default)
chrt -p $(pgrep -f kworker | head -1)
# Тоже SCHED_OTHER
# 2. Запустим 3 CPU-bound с разными nice:
yes > /dev/null &
A=$!
nice -n 5 yes > /dev/null &
B=$!
nice -n 10 yes > /dev/null &
C=$!
sleep 3
ps -p $A,$B,$C -o pid,ni,%cpu,comm
# Распределение CPU будет ~70/20/10 -- nice работает мультипликативно через CFS weights
kill $A $B $C
# 3. Посмотреть CFS schedstats:
cat /proc/$$/sched | head -20
# se.vruntime -- virtual runtime данного процесса
# se.sum_exec_runtime -- общее CPU время
# nr_switches -- сколько раз переключали
# 4. Per-CPU runqueue stats:
cat /proc/schedstat
# Несколько строк, по одной на CPU
# Параметры: yields, context switches, load среднееКooперативный scheduler в userspace (Go runtime)
В userspace часто реализуется свой scheduler внутри runtime. Go scheduler — классический пример.
Go использует work-stealing + cooperative scheduling:
Это пример того, как принципы scheduler’ов применимы не только в kernel. Похожие идеи в Tokio (Rust async), JVM ForkJoinPool, Erlang BEAM.
kube-scheduler: распределение Pod'ов по нодам по тем же принципамПопробуй сам
# 1. Сравните CPU-распределение по nice:
for n in 0 5 10 15 19; do
nice -n $n yes > /dev/null &
echo "Started nice $n, PID $!"
done
sleep 5
ps -eo pid,ni,%cpu,comm | grep -E '^.{0,30}(yes|^PID)'
killall yes
# nice -19 получит большую часть CPU; nice 19 -- крохи
# 2. Посмотрите детальные scheduler stats для процесса:
sleep 60 &
PID=$!
sleep 3
cat /proc/$PID/sched
# nr_switches, nr_voluntary_switches -- разное
# se.vruntime -- virtual runtime CFS
kill $PID
# 3. SCHED_RR vs SCHED_OTHER:
# Запустить процесс в RR классе (нужно root или CAP_SYS_NICE):
sudo chrt -r -p 50 $$ # current shell -> SCHED_RR prio 50
# (НЕ запускайте бесконечный цикл в SCHED_RR -- будет блокировать систему!)
sudo chrt -o -p 0 $$ # вернуть SCHED_OTHER
# 4. Замерьте, сколько процессов переключений в секунду:
vmstat 1 5
# Колонка cs -- context switches/sec
# Запустите параллельно много yes и сравните: cs скакнёт
# 5. Если есть Go установлен -- запустите программу с миллионом goroutines:
cat > /tmp/many.go << 'EOF'
package main
import "fmt"; import "runtime"; import "time"
func main() {
for i := 0; i < 1000000; i++ {
go func() { for { runtime.Gosched() } }()
}
fmt.Println(runtime.NumGoroutine())
time.Sleep(time.Hour)
}
EOF
# go run /tmp/many.go &
# top -- увидите, что process использует все GOMAXPROCS cores