Jak funguje plánování CPU (scheduling) a jaké jsou běžné algoritmy?

Question

IT Interview Practice · Accepted Answer

**Plánování CPU (CPU scheduling)** je rozhodnutí kernelu o tom, *které* připravené vlákno dostane CPU *jako další* a na *jak dlouho*. Protože obvykle je víc spustitelných vláken než jader, **scheduler** je multiplexuje a snaží se vyvážit protichůdné cíle — **throughput**, **nízkou latenci / dobu odezvy** a **spravedlnost (fairness)** — a přitom se vyhnout **starvation** (vyhladovění).

## Běžné algoritmy

```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** ilustruje hlavní řídicí prvek — **quantum**:

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

## Skutečné schedulery

Dlouholetým výchozím schedulerem Linuxu byl **CFS (Completely Fair Scheduler)**: místo pevných časových kvant sleduje **virtual runtime (vruntime)** každé úlohy a vždy spouští vlákno, které dosud dostalo nejméně CPU, vážené jeho hodnotou **nice** — přibližuje se principu „každý dostane spravedlivý díl“. Klíčuje červeno-černý strom (red-black tree) podle vruntime, takže výběr další úlohy je O(log n). (Novější kernely používají EEVDF, zjemnění se stejným cílem spravedlnosti plus těsnějšími mezemi latence.)

**Preemptive vs cooperative:** moderní OS jsou **preemptivní** — timer interrupt umožňuje scheduleru násilně převzít CPU zpět, takže jedno vlákno nemůže monopolizovat jádro.

## Proč je to důležité

Plánování přímo utváří latenci a throughput, které uživatelé pociťují. Tazatelé ho zkoumají, aby zjistili, zda rozumíte kompromisům — proč interaktivní zátěž chce krátká quanta nebo zvýšení priority, proč prioritní plánování potřebuje **aging**, aby se předešlo starvation, a jak MLFQ/CFS dosahují dobrého interaktivního chování, aniž by předem znaly délky úloh. Je to také mentální model za laděním `nice`, real-time priorit a diagnostikou vyhladovělé nebo trhané služby.

Běžné algoritmy

Skutečné schedulery

Proč je to důležité

Související otázky