Skip to content

Vymenne algoritmy

Jump to bottom
Martin Skalicky edited this page Aug 7, 2026 · 1 revision

Výměnné algoritmy, swap a thrashing

„Mám dost paměti, tak swap vypnu." Tuhle radu najdeš ve stovkách návodů a ve většině případů si tím uškodíš.

Swap není nouzová paměť pro případ, že ti dojde RAM. Je to místo, kam systém odkládá stránky, o které se roky nikdo nepřihlásil, aby paměť dal tam, kde je vidět. Vypnutím swapu nezískáš ani bajt - jen odebereš možnost se špatných stránek zbavit.

Stránka řeší, jak se vybírá, která stránka poletí ven, a co se stane, když se to udělá špatně. Mechaniku stránkování neřeší - to je na virtuální paměti a stránkování.

Otázka nezní, jestli je paměť plná

Přijde výpadek stránky, rámce jsou obsazené, jádro musí jeden uvolnit. Vypadá to jako otázka „kolik je volné paměti". Není.

Tohle je nejdůležitější věc na celé stránce: otázka nikdy nezní „je paměť plná", ale „která stránka se nejdéle nepoužije". Odpověď nikdo nezná, protože závisí na budoucnosti. Odhaduje se z minulosti a všechny výměnné algoritmy jsou jen různě dobré odhady téhle jedné věci.

Čtyři odhady té jedné otázky

Všechny na jedné referenční posloupnosti, tedy stránkách v pořadí, v jakém se na ně proces odkazuje:

1 2 3 4 1 2 5 1 2 3 4 5

Optimální algoritmus, který se nedá napsat

Bélády, 1966. Pravidlo je triviální: vyhoď stránku, která se bude potřebovat nejpozději.

Se třemi rámci zaberou první tři odkazy prázdné rámce. Čtvrtý musí něco vyhodit: jednička je na řadě v kroku 5, dvojka v kroku 6, trojka až v kroku 10, takže letí trojka. V kroku 7 jde ven čtyřka. Celkem sedm výpadků.

Sedmičku si zapamatuj, je to dolní mez. OPT se neimplementuje, ale je nejdůležitější z celé čtveřice: bez měřítka nevíš, jestli je devět výpadků dobrý výsledek.

FIFO a Beládyho anomálie

FIFO vyhazuje stránku, která je v paměti nejdéle. Jedna fronta, žádné bity, žádná režie. A chová se tak, jak by se čekat nemělo.

Tučně je stránka právě načtená, tedy výpadek. Nezměněný řádek je zásah:

Krok Stránka Tři rámce Čtyři rámce
1 1 1 . . 1 . . .
2 2 1 2 . 1 2 . .
3 3 1 2 3 1 2 3 .
4 4 4 2 3 1 2 3 4
5 1 4 1 3 1 2 3 4
6 2 4 1 2 1 2 3 4
7 5 5 1 2 5 2 3 4
8 1 5 1 2 5 1 3 4
9 2 5 1 2 5 1 2 4
10 3 5 3 2 5 1 2 3
11 4 5 3 4 4 1 2 3
12 5 5 3 4 4 5 2 3

Spočítej tučné položky: devět výpadků při třech rámcích, deset při čtyřech. O třetinu víc paměti a víc práce. Tomu se říká Beládyho anomálie (Bélády, Nelson, Shedler, 1969).

Příčina je v krocích 5 a 6. Se třemi rámci tam FIFO jedničku a dvojku znovu načte a tím je omladí. Se čtyřmi je najde v paměti a pořadí ve frontě nechá být - o krok později tedy letí ven ty dvě nejžhavější. FIFO netrestá nepoužívané stránky, trestá staré.

LRU: zrcadlení minulosti

LRU (least recently used) vyhodí tu, která se nejdéle nepoužila. Podíváš se do minulosti a doufáš, že se bude opakovat. U reálných programů se opakuje.

LRU patří do třídy zásobníkových algoritmů: obsah paměti při n rámcích je vždy podmnožinou obsahu při n+1 rámcích (Mattson a spol., 1970). Proto anomálii mít nemůže. Na naší posloupnosti udělá deset výpadků při třech rámcích a osm při čtyřech - je tu tedy horší než FIFO, protože jednotlivou posloupnost lze zkonstruovat proti čemukoliv.

Přesné LRU se ale nikde nedělá. Vyžadovalo by aktualizaci pořadí při každém přístupu do paměti, tedy každých 80 ns. Odhad by stál víc než chyba, kterou opravuje.

Clock, čili druhá šance

Z toho, co MMU umí zadarmo, zbývá jediný bit: bit „bylo přistoupeno", který hardware nastaví při dotyku stránky a jádro ho umí vynulovat.

Clock srovná rámce do kruhu a nechá po nich obíhat ručičku. Nula pod ručičkou znamená, že stránka od poslední obrátky nikoho nezajímala, a letí ven. Jednička se vynuluje a ručička jde dál - to je ta druhá šance. Často používaná stránka si jedničku stihne nastavit dřív, než se ručička vrátí.

Vylepšení používá dva bity: přistoupeno a změněno. Čistou stránku stačí zahodit, obsah je pořád na disku. Změněná se musí nejdřív zapsat, a proto se vyhazuje nerada; clock ji ve prospěch čisté přeskočí.

Tohle skutečně běží na tvém stroji. Linux má dva seznamy, aktivní a neaktivní, a přesouvá mezi nimi stránky podle přístupů - clock s pamětí navíc. Od jádra 6.1 (rok 2022) je k dispozici i vícegenerační MGLRU, zapínaná přes /sys/kernel/mm/lru_gen/enabled.

Který z nich chceš

Algoritmus Kvalita odhadu Cena Beládyho anomálie Používá se dnes
OPT dokonalá nelze implementovat ne jen jako měřítko
FIFO mizerná nulová ano ne
LRU přesné výborná neúnosná ne ne
Clock, jeden bit dobrá bit na rámec ano ojediněle
Clock, dva bity a dva seznamy velmi dobrá nízká prakticky ne ano, a nemáš co vybírat

Vítěz není nejlepší odhad, ale nejlepší poměr odhadu k ceně.

Kolik rámců komu

Peter Denning, 1968: pracovní soubor (working set) je množina stránek, na které proces sáhl za poslední časový úsek. Je měřitelný a je to správná jednotka přidělování.

Plyne z toho pravidlo, které vypadá krutě a je správné: proces má dostat tolik rámců, kolik jich aktivně používá, jinak nemá cenu mu dávat žádné. Proces s pracovním souborem 400 MiB, kterému dáš 200 MiB, nepoběží poloviční rychlostí. Bude pořád načítat to, co před chvílí vyhodil.

Celé to stojí na lokalitě. V čase: na co jsi sáhl teď, budeš potřebovat zase za chvíli. V prostoru: sáhl-li jsi na adresu, sáhneš brzy i na sousední. Bez ní by žádný odhad nefungoval.

Thrashing: nic nespadlo a nic nejde

Součet pracovních souborů překročí počet rámců. Každý proces vyhodí stránku, kterou za okamžik potřebuje jiný. Systém stráví víc času stránkováním než prací.

Zvenku to vypadá takhle: procesor je téměř nevytížený, disk na sto procentech, systém nereaguje na nic - a přitom nic nespadlo a žádná chyba se nevypsala.

Samo se to nespraví, protože zpětná vazba míří špatným směrem. Plánovač vidí nevyužitý procesor, vyhodnotí to jako volnou kapacitu a pustí dovnitř další proces, který si vyžádá další rámce.

Přístup do RAM je zhruba 80 ns, tvrdý výpadek z NVMe 100 µs a z plotnového disku 10 ms, tedy stotisíckrát dýl.

Podíl tvrdých výpadků Efektivní přístup, NVMe Efektivní přístup, plotna
0,01 % 90 ns 1 080 ns
0,1 % 180 ns 10 080 ns
1 % 1 080 ns 100 080 ns

Desetina procenta výpadků na plotně znamená stotřicetkrát pomalejší paměť. Průměr určuje ta drobná menšina přístupů, která čeká na disk.

Facebook 2018: jádro si toho všimne pozdě

Provozovatelé velkých flotil narazili na to, že jádro považuje thrashující stroj za zdravý. OOM killer se spustí, teprve když není co uvolnit - jenže stroj, který dvacet minut přehazuje stránky, je z pohledu uživatele mrtvý dávno předtím.

Odpovědí byly dvě věci z roku 2018: PSI (pressure stall information), měření času stráveného čekáním na paměť, které se dostalo do jádra 4.20, a oomd, démon zabíjející podle PSI dřív než jádro. Poučení: livelock není chybový stav a systém ho sám nepozná.

Swap v praxi

swapon --show                  # co je swap a kolik z toho je použité
free -h                        # řádek Swap a sloupec available na řádku Mem
sysctl vm.swappiness           # na Debianu výchozích 60

vm.swappiness neznamená „jak moc se má swapovat". Znamená poměr, v jakém jádro sahá na anonymní stránky proti souborovým. Anonymní stránka (halda, zásobník - viz správa paměti) nemá kde jinde být a musí do swapu. Souborová je kopie něčeho na disku a stačí ji zahodit; patří tam i page cache a kód běžících programů.

Odtud plyne, proč je vypnutý swap horší, než čekáš: bez swapu jsou anonymní stránky nevyhoditelné a celý tlak spadne na souborové. Systém začne zahazovat spustitelný kód a číst ho znovu z disku.

Nula znamená „sahej na anonymní stránky až v nouzi", 60 je vyvážený stav a od jádra 5.8 (rok 2020) jde nastavit až 200, tedy „radši swapuj, než abys zahazoval cache".

Doporučení: swap nech zapnutý na desktopu i na serveru a swappiness dej mezi 10 a 60. Nižší konec pro stroje s jednou hlavní službou, vyšší tam, kde běží hodně věcí.

echo 'vm.swappiness = 20' | sudo tee /etc/sysctl.d/99-swap.conf   # trvale
sudo sysctl --system                                              # načte hned

Kde je disk pomalý, sáhni po zramu - na Debianu balík zram-tools. Swapuje se do komprimovaného bloku v RAM, takže odložená stránka zůstane v paměti a zabírá zhruba třetinu.

Pravidlo „swap má být dvojnásobek RAM" pochází z doby, kdy měly stroje 64 MiB, a v návodech přežívá setrvačností. Se 16 GB RAM stačí pár gigabajtů; větší swap řeší leda hibernaci.

Kdy swap skutečně vypnout

U databáze s pevným rozpočtem paměti. Když má stroj 16 GB, databáze cache na 12 GB a víc se neděje, odložený blok cache je jen pomalejší varianta téhož.

U latenčně kritických úloh. Obchodní systémy, zpracování zvuku, real-time řízení - tam je předvídatelnost důležitější než přežití.

V obou případech vypínáš swap spolu s pevným limitem a hlídáním paměti. Vypnout swap a doufat je nejhorší varianta.

OOM killer

Když už není co odložit, jádro spočítá každému procesu skóre podle spotřeby paměti a ten s nejvyšším dostane SIGKILL.

cat /proc/1234/oom_score        # čím vyšší, tím dřív proces padne
sudo choom -n -500 -p 1234      # posune oom_score_adj, rozsah -1000 až 1000
dmesg -T | grep -i -E 'oom|killed process'

Skóre je zhruba úměrné spotřebě paměti, takže OOM killer zabije ten největší proces - tedy přesně tu databázi, kvůli které stroj existuje. Proto se oom_score_adj na kritické službě posouvá dolů a na nahraditelném nahoru; -1000 proces vyřadí úplně. Že tenhle stav nastane, je důsledek přeprodávání paměti, které rozebírá správa paměti.

V kontejneru to vypadá jinak a mate to. Limit vynucují cgroups, takže proces zemře při dosažení memory.max kontejneru, i když má stroj paměti dost. dmesg mluví o memory-cgroup out of memory a kontejner končí s kódem 137; proč, řeší virtualizace a kontejnery.

Diagnostika

vmstat 1                        # si a so jsou stránkování, b a wa jeho následky
cat /proc/pressure/memory       # PSI, od jádra 4.20 (rok 2018)

PSI je dnes nejlepší ukazatel tlaku na paměť, protože měří to, co tě zajímá: kolik času procesy prostojí čekáním na paměť. some je podíl času, kdy stál aspoň jeden proces, full kdy stáli všichni. Stroj s plnou pamětí a nulovým full je zdravý.

Příznak Kde je problém
swpd velké, si a so nula žádný, swap dělá svou práci
so trvale nenulové paměť dochází, stránky odcházejí ven
si i so trvale nenulové thrashing, odkládá se a hned zase čte
wa vysoké, us a sy nízké procesor čeká na disk
b trvale nenulové procesy uvízlé v čekání na stránku
full v /proc/pressure/memory roste někdo úplně stojí kvůli paměti
Killed process v dmesg OOM killer už zasáhl
Kontejner končí s kódem 137 limit cgroups, ne paměť stroje

Zbytek nástrojů je na stránce o nástrojích a diagnostice.

Co si odnést

Otázka nezní „je paměť plná", ale „která stránka se nejdéle nepoužije". Zbytek jsou odhady téhle věty.

OPT se nedá implementovat a přesto je nejdůležitější. Je to měřítko pro ostatní.

FIFO může při větší paměti udělat víc výpadků. Devět proti deseti na 1 2 3 4 1 2 5 1 2 3 4 5.

LRU je zásobníkový algoritmus, a proto anomálii nemá. Přesné se nedělá, stálo by víc než chyba, kterou opravuje.

Skutečně se používá clock se dvěma bity. V Linuxu jako seznamy aktivní a neaktivní.

Thrashing je stav, kdy nic nespadlo a nic nejde. Procesor prázdný, disk plný, plánovač to zhoršuje.

Swap je odkladiště pro nepoužívané, ne nouzová RAM. Vypnutý přesune tlak na kód programů.

PSI měří čekání, ne obsazenost. Proto pozná problém dřív než cokoliv jiného.

Kam dál

Našel jsi chybu nebo něco chybí? Založ issue nebo pošli pull request.

Úvod

Základy

Procesy

Souběh

Paměť

Soubory a zařízení

Systém v provozu

Praxe

Clone this wiki locally