Planovani procesu

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 a vlákna, protože plánovací jednotkou v Linuxu je vlákno. Cena přepnutí je na přepínání kontextu, čekání na zámky na uváznutí.

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 č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í, 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 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.

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.

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 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.

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í.

Diagnostika

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, 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. Zbytek nástrojů kolem perf a /proc má vlastní stránku o nástrojích a diagnostice.

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 - co se stane v okamžiku rozhodnutí a kolik to stojí
• Procesy - stavy, mezi kterými plánovač úlohy přesouvá
• Uváznutí - inverze priorit celá, i s dědičností priorit z Pathfinderu
• Vlákna - co je vlastně tou jednotkou, která se plánuje
• Virtualizace a kontejnery - cpu.max a tvrdé stropy místo poměrů