# Plánování procesů: kdo dostane procesor

Máš jeden procesor a dvě stě věcí, které chtějí běžet. Kompilace chce spoustu času a je jí jedno, kdy skončí. Přehrávač hudby chce času málo, ale každých pár milisekund, jinak zvuk cukne. Textový editor musí zareagovat do desítek milisekund, jinak psaní drhne.

Rozhodni pořadí. Za milisekundu ho rozhodni znovu. A pak zase, tisíckrát za vteřinu, dokud stroj běží.

A nikdy se nesmíš zeptat, co ty programy vlastně chtějí. Neřeknou ti to. Většina z nich to o sobě ani neví.

Tahle stránka jde od algoritmů na papíře po to, co běží v jádře tvého stroje. Předpokládá [procesy](Procesy) a [vlákna](Vlakna), protože plánovací jednotkou v Linuxu je vlákno. Cena přepnutí je na [přepínání kontextu](Prepinani-kontextu), čekání na zámky na [uváznutí](Uvaznuti).

## Plánovač nevidí do budoucnosti

Optimální rozvrh by šel spočítat. Stačilo by dopředu vědět, jak dlouho bude která úloha počítat a kdy se zablokuje na disku.

Tohle je nejdůležitější věc na celé stránce: **plánovač tuhle informaci nemá a nikdy ji mít nebude.**

Všechny plánovací algoritmy jsou proto odhady budoucího chování z minulého. Každý se dá popsat větou „čemu věří“ a z ní plyne, kde se rozpadne. Zbytek stránky je výčet těch vět a jejich cen.

## Pět kritérií, která se navzájem tlučou

| Kritérium | Co měří | Kdo to chce |
|---|---|---|
| Propustnost | dokončených úloh za vteřinu | dávky, kompilace |
| Doba obrátky | od zadání po dokončení | kdo čeká na výsledek |
| Doba odezvy | od zadání po první reakci | člověk u klávesnice |
| Spravedlnost | že nikdo nezůstane stát | stroj s víc uživateli |
| Využití procesoru | kolik času se doopravdy počítá | kdo ten stroj platil |

**Propustnost a odezva jdou přímo proti sobě.** Propustnosti pomůžeš tím, že necháš každou úlohu běžet dlouho: míň přepínání, teplejší cache. Odezvě pomůžeš přesně opačně.

Chceš odezvu 10 ms a běží osmdesát úloh? Musíš přepínat po 125 µs, a jedno přepnutí stojí jednotky mikrosekund. **Na desktopu i běžném serveru to zaplať:** tři procenta výkonu nepozná nikdo, cukající zvuk pozná každý.

## Kdo smí koho přerušit

**Nepreemptivní plánování** nechá úlohu běžet, dokud sama neskončí nebo se nezablokuje - typicky [systémovým voláním](Systemova-volani) čekajícím na disk. Jen tam se plánovač dostane ke slovu.

**Preemptivní plánování** znamená, že jádro může úloze odebrat procesor kdykoli. Nástrojem je časovač: hardware vyvolá [přerušení](Preruseni-a-vyjimky), jádro dostane řízení a rozhodne znovu.

**Časové kvantum** je doba, po kterou úloha smí běžet, než se plánovač zeptá podruhé. Určuje ho cena přepnutí (kvantum musí být řádově větší, jinak stroj počítá sám sebe), cílová odezva dělená počtem běhuschopných úloh a rozlišení časovače. Vychází to na jednotky milisekund.

## Co se dnes už nedělá: kooperativní multitasking

Windows 3.1 a klasický Mac OS až do roku 2001 preempci neměly. Úloha se procesoru vzdávala **dobrovolně** - na Windows tím, že si sáhla pro další zprávu z fronty, na Macu voláním `WaitNextEvent`.

Fungovalo to přesně tak dlouho, dokud se všechny programy chovaly slušně. Jeden zacyklený program položil celý systém: nešlo přepnout okno, nešla myš, nešlo ho ani zabít - i zabití procesu potřebuje, aby jádro dostalo procesor.

Kooperativní model nikdo neopustil kvůli eleganci, ale proto, že **spolehlivost nesmí záviset na slušnosti nejhoršího nainstalovaného programu**.

## Klasické algoritmy a čemu každý věří

### FCFS a konvojový efekt

První přišel, první běží. Nepreemptivní, jedna fronta, žádné rozhodování.

Tři úlohy přijdou naráz: `P1` potřebuje 24 ms procesoru, `P2` 3 ms, `P3` 3 ms. V pořadí `P1, P2, P3` čeká `P1` nula, `P2` 24 ms a `P3` 27 ms, tedy průměrně **17 ms**. Otoč pořadí na `P2, P3, P1` a čekání je 0, 3 a 6 ms, průměr **3 ms**. Stejné úlohy, stejná práce, pětinásobný rozdíl jen podle toho, kdo se postavil první.

To je **konvojový efekt**: dlouhá výpočetní úloha nasbírá za sebou zástup krátkých. Ty krátké bývají diskové, a dokud stojí ve frontě na procesor, disk nedělá nic. Propustnost se propadne i tam, kde se o procesor nehraje.

### SJF a SRTF: optimum, které nemáš

Shortest Job First bere nejkratší čekající úlohu. Shortest Remaining Time First je jeho preemptivní verze: přijde-li úloha kratší než zbytek běžící, běžící o procesor přijde.

SJF dává **dokazatelně nejmenší průměrnou dobu čekání** ze všech rozvrhů - výš je to právě to druhé pořadí s průměrem 3 ms. A je to k ničemu, protože **délku úlohy dopředu nikdo nezná**. Reálné plánovače ji odhadují z minulých běhů, což je jiné jméno pro „věřím, že to bude jako minule“.

Druhá potíž je **vyhladovění**: kam pořád přicházejí krátké úlohy, tam se dlouhá nedostane ke slovu nikdy. Léčí se **stárnutím** - kdo čeká, tomu priorita roste, až se prosadí. To najdeš skoro v každém reálném plánovači.

### Round Robin: celý spor je o kvantum

Fronta jako u FCFS, ale úloha běží nejvýš jedno kvantum a pak jde na její konec.

Ty samé tři úlohy s kvantem 4 ms: `P1` běží 0-4, `P2` 4-7 a končí, `P3` 7-10 a končí, `P1` dobíhá do 30 ms. Doby čekání 6, 4 a 7 ms, průměr **5,67 ms**. Horší než SJF, třikrát lepší než FCFS - a hlavně `P3` dostal procesor po 7 ms místo po 27 ms.

**Round Robin nekupuje průměr, kupuje odezvu.** Doba obrátky se mu obvykle zhorší, protože každou úlohu roztrhá na kusy.

Volba kvanta je celý ten algoritmus. **Příliš krátké** znamená, že větší část času jde na [přepínání kontextu](Prepinani-kontextu) než na práci. **Příliš dlouhé** znamená, že se každá úloha dopočítá v jednom kuse a z Round Robinu se stane FCFS i s konvojem.

### Priority a víceúrovňové fronty se zpětnou vazbou

Prioritní plánování dá každé úloze číslo a bere nejvyšší. Potíž je, že to číslo musí někdo napsat, a statické priority vedou přímo k vyhladovění.

MLFQ (Multi-Level Feedback Queue) si prioritu **spočítá sám z chování úlohy**. Pravidla:

1. Má-li `A` vyšší prioritu než `B`, běží `A`.
2. Mají-li stejnou, střídají se Round Robinem.
3. Nová úloha nastupuje na **nejvyšší** prioritu.
4. Vyčerpá-li úloha celé kvantum, klesne o patro níž.
5. Vzdá-li se procesoru sama dřív, prioritu si **udrží**.
6. Po uplynutí periody `S` se všechny úlohy vrátí nahoru.

Trik jsou pravidla 4 a 5. Kdo se zablokuje na klávesnici nebo na disku, je interaktivní, zůstává nahoře a reaguje rychle. Kdo sežere celé kvantum, klesá dolů a dostává kvanta delší, ale řidší. **Plánovač se nikoho neptal, co je zač. Odvodil si to.**

Pravidlo 6 brání vyhladovění i podvádění: naivní pravidlo 4 se dá obejít tím, že se program vzdá procesoru těsně před koncem kvanta. Reálné implementace proto účtují **celkový čas spotřebovaný na úrovni**, ne jednotlivá kvanta.

| Algoritmus | Čemu věří | Kde se to zlomí |
|---|---|---|
| FCFS | pořadí příchodu je spravedlivé | dlouhá úloha zablokuje všechny |
| SJF a SRTF | délku úlohy znáš dopředu | neznáš ji |
| Round Robin | všichni jsou si rovni | kvantum je kompromis, ne řešení |
| Statické priority | důležitost jde napsat číslem | nikdo ji nenapíše správně |
| MLFQ | chování z minulé vteřiny vydrží | úloha, která změní povahu |

## Co z toho zbylo v Linuxu

### nice a váhy

Každý běžný proces má `nice` v rozsahu **-20 až 19**, výchozí 0. Vyšší číslo znamená nižší prioritu. Kladnou hodnotu si smí nastavit kdokoli, zápornou jen root nebo proces s `CAP_SYS_NICE`.

```bash
nice -n 19 make -j8     # kompilace, která nesmí zaseknout práci u klávesnice
renice -n 5 -p 1234     # nastaví nice běžícímu procesu, absolutní hodnota
```

Nice se nepřevádí na pořadí ve frontě, ale na **váhu**. Nice 0 má váhu 1024, každý stupeň znamená zhruba 1,25násobek, takže nice 19 má váhu 15. Dva výpočetní procesy na jednom jádře, jeden s nice 0 a druhý s nice 19, si čas rozdělí zhruba **98,5 % ku 1,5 %**.

`nice -n 19` tedy neznamená „běž pomalu“, ale „ber si zbytky, když má někdo jiný co počítat“. Když nepočítá nikdo jiný, doběhne to plnou rychlostí.

### CFS a EEVDF

CFS (Completely Fair Scheduler, od jádra 2.6.23 z roku 2007) opustil kvanta. Každé úloze počítá **virtuální běhový čas** - odběhnutý čas dělený vahou - a vybírá vždycky tu s **nejmenším**.

Věří tomuhle: spravedlivé je, aby všichni měli stejný podíl procesoru, přepočtený vahami. Úloha, která hodně spí, má malý virtuální čas, a tak se po probuzení dostane na procesor skoro okamžitě. Interaktivita je vedlejší efekt spravedlnosti, ne zvláštní pravidlo.

**Od jádra 6.6 (rok 2023) je výchozí EEVDF** (Earliest Eligible Virtual Deadline First). Váhy i virtuální čas drží, ale přidává každé úloze **virtuální termín** odvozený z délky plátku, který si úloha přeje, a vybírá nejbližší termín mezi těmi, kdo na svůj podíl mají nárok. Čemu věří navíc: **spravedlnost sama nerozliší úlohu, která chce hodně času občas, od úlohy, která chce málo času hned.**

### Real-time třídy: SCHED_FIFO a SCHED_RR

Vedle běžné třídy jsou dvě real-time politiky se statickými prioritami **1-99**, které mají přednost před vším ostatním. **SCHED_FIFO** běží, dokud sám neskončí, nezablokuje se nebo ho nevytlačí vyšší real-time priorita; kvantum nemá. **SCHED_RR** je totéž se střídáním po kvantu mezi stejnými prioritami.

```bash
chrt -p 1234                               # jakou politiku a prioritu proces má
sudo chrt -f 50 ./program                  # spustí pod SCHED_FIFO s prioritou 50
cat /proc/sys/kernel/sched_rt_runtime_us   # 950000, tedy 95 % periody
```

Poctivé varování: **real-time úloha ve smyčce, která se neuspí, zablokuje jádro natvrdo.** Nedostaneš shell, nedostaneš myš, dostaneš tvrdý restart. Jádro se brání škrcením - real-time úlohy smějí zabrat nejvýš 950 000 z každých 1 000 000 mikrosekund. Těch zbylých 5 % je jediný důvod, proč se stroj dá zachránit.

A hlavně: **„real-time“ neznamená „rychlý“.** Znamená zaručený horní odhad. Taková úloha může mít horší průměrnou odezvu než běžná a přesto být naplánovaná správně - nejde o průměr, ale o mez, kterou nepřekročí nikdy.

## Osm jader, osm front

Na osmijádrovém stroji má plánovač **běhovou frontu na každém jádře**. Jedna sdílená by znamenala jeden zámek, o který se perou všechna jádra při každém rozhodnutí, tedy [kritickou sekci](Kriticka-sekce-a-zamky) na nejteplejším místě systému.

Cenou je nerovnoměrnost, kterou dorovnává **vyvažování zátěže**: jádro s prázdnou frontou si přetáhne úlohu od přetíženého souseda. Migrace není zadarmo - úloha přijde o obsah cache i TLB a chvíli po přesunu běží pomaleji. Proto se jí plánovač brání a raději nechá jádro stát.

```bash
nproc                     # kolik jader plánovač reálně vidí
taskset -c 2,3 ./program  # připne program na jádra 2 a 3
taskset -pc 1234          # vypíše afinitu běžícího procesu
```

Připínat všechno je běžný omyl. Ruční afinita vypne vyvažování, a když se spleteš, máš jedno jádro na 100 % a sedm nečinných.

## Mars, 1997: úloha, která čekala na tu nejnižší

Sonda Mars Pathfinder přistála v červenci 1997 a po pár dnech se začala sama restartovat. Příčinou byla **inverze priorit**: vysokopriotní úloha obsluhující datovou sběrnici čekala na zámek držený nízkopriotní meteorologickou úlohou, a té mezitím braly procesor úlohy střední priority. Hlídací obvod to vyhodnotil jako zatuhnutí a stroj restartoval.

Opravila to vzdálená aktualizace, která u zámku zapnula **dědění priorit** - držitel zámku dočasně převezme prioritu toho, kdo na něj čeká. Poučení: **plánovač neplánuje podle toho, na co úloha čeká, jen podle jejího čísla.** Celá je inverze priorit na stránce o [uváznutí](Uvaznuti).

## Diagnostika

```bash
top                    # sloupce PR a NI, v řádku %Cpu(s) hodnoty wa a si
pidstat 1              # využití procesoru po procesech, každou vteřinu
vmstat 1               # r = běhuschopné úlohy, b = blokované, cs = přepnutí
cat /proc/1234/sched   # virtuální čas, počty přepnutí, statistiky čekání
```

V `top` je `PR` skutečná priorita jádra (u real-time úloh se vypíše `rt`), `NI` hodnota nice. `wa` je podíl času, kdy procesor stál a čekal na [vstup a výstup](Vstup-a-vystup), `si` je čas v softwarových přerušeních, typicky při síťové zátěži. Ve výpisu `/proc/1234/sched` znamená vysoké `nr_involuntary_switches` úlohu, které pořád dochází kvantum, vysoké `nr_voluntary_switches` naopak úlohu, která pořád na něco čeká.

| Příznak | Kde je problém |
|---|---|
| Při plné zátěži to cuká, ale všechno doběhne | propustnost dobrá, latence ne - sniž prioritu dávky |
| Jeden proces „ukradl“ celý stroj | běží pod SCHED_FIFO a neuspává se, ověř `chrt -p` |
| `nice -n 19` nepomohl | úloha nečeká na procesor, ale na disk |
| Vysoké `wa`, nízké využití procesoru | hrdlo je I/O, plánovač s tím nesvede nic |
| `r` ve `vmstat` trvale mnohonásobek `nproc` | úloh je víc než jader, priority přerozdělí jen bídu |
| Proces stojí, i když má nejvyšší prioritu | čeká na zámek držený někým níž, tedy inverze priorit |

## Kde plánovač přestává pomáhat

**Nejčastější omyl kolem `nice` je, že řeší pomalost.** Neřeší. Nice přerozděluje **jen čas procesoru**. Čeká-li proces na disk, na síť nebo na zámek, nice s ním nepohne ani o procento - poznáš to tak, že ho v `top` sotva vidíš mezi spotřebiteli procesoru, zatímco `wa` je vysoké. Pro I/O je `ionice`, ale jeho třídy respektuje jen plánovač bloků BFQ; u NVMe s nastavením `none` nedělá vůbec nic.

**Potřebuješ-li tvrdý strop, a ne poměr, po nice nesahej.** Váhy garantují podíl při souběhu, ne maximum. Strop se dělá přes cgroups v2 a `cpu.max`, což patří k [virtualizaci a kontejnerům](Virtualizace-a-kontejnery). Zbytek nástrojů kolem `perf` a `/proc` má vlastní stránku o [nástrojích a diagnostice](Nastroje-a-diagnostika).

## Co si odnést

**Plánovač nezná budoucnost.** Všechno ostatní je odhad z minulého chování.

**Každý algoritmus se dá popsat větou „čemu věří“.** Znáš-li ji, víš i to, kde selže.

**Propustnost a odezva se nedají mít obě.** Kvantum je ciferník mezi nimi.

**FCFS umí být pětkrát horší než jiné pořadí týchž úloh.** Konvoj navíc uspí i disk.

**SJF je optimální a nepoužitelný**, protože délku úlohy dopředu nikdo nezná.

**Linux plánuje váhami, ne kvanty.** Nice 0 proti nice 19 je zhruba 98,5 ku 1,5.

**Real-time znamená zaručenou mez, ne rychlost.** Jedna zacyklená FIFO úloha ti položí stroj.

## Kam dál

- **[Přepínání kontextu](Prepinani-kontextu)** - co se stane v okamžiku rozhodnutí a kolik to stojí
- **[Procesy](Procesy)** - stavy, mezi kterými plánovač úlohy přesouvá
- **[Uváznutí](Uvaznuti)** - inverze priorit celá, i s dědičností priorit z Pathfinderu
- **[Vlákna](Vlakna)** - co je vlastně tou jednotkou, která se plánuje
- **[Virtualizace a kontejnery](Virtualizace-a-kontejnery)** - `cpu.max` a tvrdé stropy místo poměrů