Как работает kernel scheduler в Linux (CFS) и как он влияет на latency

Планировщик задач (scheduler) в Linux — это компонент ядра, который решает, какой процесс и когда получит CPU. От его работы напрямую зависит latency: насколько быстро приложение получит процессорное время после того, как оно готово к выполнению.

В современных ядрах Linux используется CFS (Completely Fair Scheduler) — планировщик, ориентированный на «справедливое» распределение CPU между процессами.

Базовая идея CFS

Вместо сложных очередей с фиксированными приоритетами CFS моделирует идеальную систему, в которой каждый процесс получает равную долю CPU (с учётом веса).

Основные принципы:

• каждый процесс получает CPU пропорционально своему весу
• никто не должен «голодать» (starvation)
• система стремится к равномерному распределению времени

Для этого используется ключевое понятие — virtual runtime.

Что такое vruntime

vruntime — это «виртуальное время», которое показывает, сколько CPU уже получил процесс.

Как это работает:

• чем дольше процесс выполняется, тем быстрее растёт его vruntime
• планировщик выбирает процесс с минимальным vruntime
• процессы с более низким приоритетом (higher nice) накапливают vruntime быстрее

Это создаёт эффект справедливости: тот, кто меньше работал, получает CPU раньше.

Структура данных: red-black tree

Все runnable-процессы хранятся в сбалансированном дереве (red-black tree), отсортированном по vruntime.

Это позволяет:

• быстро находить процесс с минимальным vruntime
• эффективно вставлять и удалять процессы

Алгоритм выбора процесса выглядит так:

1. выбрать процесс с минимальным vruntime
2. дать ему CPU
3. обновить его vruntime
4. вернуть обратно в дерево

Как работает распределение CPU

В CFS нет жёстко фиксированного time slice, как в старых планировщиках.

Вместо этого используются параметры:

• target latency — время, за которое все процессы должны получить CPU
• min granularity — минимальный квант выполнения

Если процессов мало:

• каждый получает более длинный кусок CPU

Если процессов много:

• CPU делится на более мелкие интервалы

Таким образом система адаптируется под нагрузку.

Влияние nice и веса

Каждый процесс имеет значение nice, которое влияет на его вес.

• меньший nice (например, -10) → больше CPU
• больший nice (например, +10) → меньше CPU

Важно: это не абсолютный приоритет, а относительный.

CFS делит CPU пропорционально весам процессов.

Как CFS влияет на latency

Теперь самое важное — влияние на задержки.

1. Очередь выполнения

Если много runnable-процессов:

• каждый ждёт своей очереди
• latency растёт

Это особенно заметно на перегруженных системах.

2. Granularity

Если min granularity слишком большой:

• процессы дольше ждут переключения
• увеличивается latency

Если слишком маленький:

• растёт количество context switch
• увеличивается overhead CPU

3. CPU-bound vs IO-bound

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

• CPU-bound процессы могут «забивать» очередь
• IO-bound процессы (часто просыпаются) обычно получают CPU быстрее

Это помогает интерактивным приложениям.

4. Wakeup latency

Когда процесс просыпается (например, после I/O), важно, как быстро он получит CPU.

CFS старается давать преимущество таким процессам:

• их vruntime меньше
• они быстрее попадают в выполнение

Это снижает perceived latency.

NUMA и многопроцессорные системы

На системах с несколькими CPU ситуация усложняется:

• есть отдельные runqueue для каждого CPU
• используется load balancing

Проблемы:

• миграция процессов между CPU
• cache misses

Это тоже влияет на latency, особенно для чувствительных приложений. В нашем блоге также есть статья про NUMA-aware разработку.

Практические параметры

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

• sched_latency_ns
• sched_min_granularity_ns
• sched_wakeup_granularity_ns

Их можно смотреть и менять через /proc/sys/kernel/.

Но трогать их без понимания — плохая идея.

Когда CFS становится проблемой

Хотя CFS универсален, есть кейсы, где он не идеален:

• real-time приложения
• low-latency trading
• аудио/видео обработка

В таких случаях используют:

• real-time scheduler (SCHED_FIFO, SCHED_RR)
• изоляцию CPU (cpuset)

Практические советы

1. Следите за load average
   • высокий load = рост latency
2. Используйте nice и cgroups
   • ограничивайте фоновые задачи
3. Изолируйте критичные сервисы
   • выделяйте CPU
4. Мониторьте context switches
   • слишком много → overhead
5. Анализируйте perf и sched trace
   • помогает понять поведение планировщика

Итог

CFS — это планировщик, который стремится к справедливому распределению CPU.

Он использует vruntime и сбалансированное дерево, чтобы выбирать процесс, который меньше всего получил CPU.

С точки зрения latency:

• больше процессов → выше задержки
• неправильные настройки → деградация
• тип нагрузки сильно влияет на поведение

Понимание работы scheduler позволяет лучше настраивать систему и снижать latency критичных приложений.