Как работает планирование CPU, и какие есть распространённые алгоритмы?

Question

IT Interview Practice · Accepted Answer

**Планирование CPU (CPU scheduling)** — это решение ядра о том, *какой* готовый поток получит CPU *следующим* и на *какое время*. Поскольку запускаемых потоков обычно больше, чем ядер, **scheduler** мультиплексирует их, стремясь сбалансировать конкурирующие цели — **throughput**, **низкую задержку / время отклика** и **справедливость** — избегая при этом **starvation** (голодания).

## Распространённые алгоритмы

```text
FCFS (first-come, first-served) → simple, but one long job blocks everyone (convoy effect)
SJF  (shortest job first)       → optimal avg wait, but needs to know job length; can starve long jobs
Round-robin (RR)                → each job a fixed TIME SLICE (quantum), cycle through → fair, good latency
Priority                        → highest priority first → can STARVE low priority (fix: aging)
MLFQ (multi-level feedback)     → several priority queues; jobs that use a full quantum sink,
                                  interactive jobs that yield stay high → approximates SJF without knowing lengths
```

**Round-robin** иллюстрирует ключевую «ручку настройки» — **quantum**:

```text
quantum too SMALL → fair & responsive, but lots of context-switch overhead
quantum too LARGE → less overhead, but degrades toward FCFS (poor responsiveness)
```

## Реальные планировщики

Давним значением по умолчанию в Linux был **CFS (Completely Fair Scheduler)**: вместо фиксированных квантов он отслеживает **virtual runtime (vruntime)** каждой задачи и всегда запускает поток, получивший меньше всего CPU до сих пор, с весом по значению **nice** — приближая идею «каждый получает справедливую долю». Он индексирует красно-чёрное дерево (red-black tree) по vruntime, поэтому выбор следующей задачи — O(log n). (Новые ядра используют EEVDF — уточнение с той же целью справедливости плюс более жёсткими границами задержки.)

**Preemptive vs cooperative:** современные ОС **вытесняющие (preemptive)** — прерывание таймера позволяет планировщику принудительно забрать CPU обратно, так что один поток не может монополизировать ядро.

## Почему это важно

Планирование напрямую формирует задержку и throughput, которые ощущают пользователи. Интервьюеры зондируют эту тему, чтобы понять, разбираетесь ли вы в компромиссах — почему интерактивной нагрузке нужны короткие кванты или повышение приоритета, почему приоритетному планированию нужен **aging** для предотвращения starvation, и как MLFQ/CFS обеспечивают хорошее интерактивное поведение, не зная заранее длину задач. Это также ментальная модель, стоящая за настройкой `nice`, real-time-приоритетами и диагностикой заголодавшего или тормозящего сервиса.

Распространённые алгоритмы

Реальные планировщики

Почему это важно

Похожие вопросы