Kritická sekce a zámky

Sdílená proměnná x je na začátku nula. Spustíš dvě vlákna, každé udělá tisíckrát x = x + 1. Na konci má být 2000.

Dostaneš 1873. Spustíš to znovu a dostaneš 1291. Potřetí 2000. Program je přitom napsaný správně podle všeho, co ses o programování naučil: proměnná je inicializovaná, smyčky mají správný počet iterací, přičítá se jednička.

Chyba je v tom, že x = x + 1 nejsou jedna operace, ale tři - načti, přičti, ulož. Mezi kterékoliv dvě z nich se vejde druhé vlákno a jeden přírůstek zmizí, protože ho přepíše hodnota načtená ještě před ním.

Tahle stránka vysvětluje, proč se to děje, co musí splňovat správné řešení a který zámek si vzít. Předpokládá vlákna a představu o tom, co stojí přepnutí kontextu. Neřeší semafory a monitory ani případ, kdy se dva zámky zaseknou navzájem, což je uváznutí.

Tři instrukce místo jedné

Přeložený x = x + 1 nad globální proměnnou vypadá na x86-64 takhle:

mov eax, DWORD PTR x[rip]    # načti hodnotu z paměti do registru
add eax, 1                   # přičti v registru
mov DWORD PTR x[rip], eax    # ulož registr zpátky do paměti

Mezi prvním a třetím řádkem je hodnota v paměti stará, ale vlákno už tu novou drží v registru. V tomhle okně smí plánovač vlákno odebrat z procesoru - nebo prostě běží druhé vlákno na jiném jádře.

Jedna instrukce ještě neznamená atomická. S -O2 z toho gcc často udělá jediné add DWORD PTR x[rip], 1. Nedělitelné to není: procesor ji uvnitř provede jako čtení, úpravu a zápis.

Co je atomická operace a co jí není

Atomická operace je taková, u které jiné vlákno nemůže pozorovat mezistav. Buď se nestala, nebo se stala celá. Sečtení v registru to nesplňuje - má tři pozorovatelné kroky.

Tabulka níž je nejužitečnější věc na stránce - proložení dvou vláken, která obě přičítají jedničku k hodnotě 41:

Dvě přičtení, výsledek 42 místo 43. Vlákno B zapsalo hodnotu spočítanou z čísla, které mezitím zestaralo. Tomu se říká souběh (race condition), tenhle tvar ztracená aktualizace.

Chyba není v kódu, je v předpokladu

Tohle je nejdůležitější věc na celé stránce: souběh není chyba v kódu, kterou by šlo najít čtením. Je to chyba v předpokladu, že tvoje operace proběhne celá.

Řešením proto není opatrnější kód - posloupnost neatomických instrukcí se nestane atomickou tím, že ji napíšeš pečlivěji. Řešením je vynucená vzájemná výlučnost: mechanismus, který zvenku zaručí, že daný úsek provádí nejvýš jedno vlákno.

Úsek, který sahá na sdílená data a musí proběhnout bez proložení, je kritická sekce.

Čtyři podmínky, které musí správné řešení splnit

Každé řešení vzájemného vyloučení musí splnit čtyři podmínky naráz. Když vypadne kterákoliv, je vadné, i kdyby na testech procházelo.

Vzájemné vyloučení. V kritické sekci je v jednom okamžiku nejvýš jedno vlákno. Zjevná podmínka a jediná, na kterou lidé myslí.

Vlákno mimo kritickou sekci nesmí blokovat ostatní. Kdo o vstup nestojí, nemluví do rozhodování.

Konečné čekání. Kdo o vstup požádá, dostane se dovnitř v konečném čase. Bez toho vzniká vyhladovění (starvation): program běží, nezasekl se, jen jedno vlákno se nikdy nedostane ke slovu.

Žádné předpoklady o rychlosti a počtu procesorů. Řešení nesmí stát na tom, že je jedno vlákno rychlejší, že je jader zrovna osm nebo že mezi dvěma příkazy uplyne dost času. Tuhle podmínku porušují naivní pokusy nejčastěji.

Jak se vzájemné vyloučení doopravdy vynutí

Proč softwarová řešení dnes nestačí

Vzájemné vyloučení jde postavit z obyčejného čtení a zápisu, bez podpory procesoru. Nejznámější je Petersonův algoritmus z roku 1981:

int flag[2] = {0, 0};   // kdo má zájem vstoupit
int turn;               // kdo dává přednost tomu druhému

// kód procesu i, ten druhý je j
flag[i] = 1;                        // hlásím zájem
turn = j;                           // ale pouštím druhého napřed
while (flag[j] && turn == j)
    ;                               // aktivně čekám
// kritická sekce
flag[i] = 0;                        // odcházím

Trik je v turn. Když oba nahlásí zájem naráz, přežije jen jeden zápis do ní - a ten prohrávající pustí druhého dovnitř.

V praxi ho nepoužiješ. Platí pro dva procesy a hlavně: procesory i překladače přeuspořádávají instrukce. Překladač si může flag[j] podržet v registru, x86-64 smí odložit zápis do turn až za čtení flag[j] - a oba se ocitnou uvnitř. Bez bariéry paměti (atomic_thread_fence, prakticky mfence) nefunguje.

V návodech pořád je, protože názorně ukazuje ty čtyři podmínky - a přesně tohle se dnes nedělá.

Na čem to stojí doopravdy: atomické instrukce procesoru

Skutečné zámky stojí na instrukcích, kterým atomicitu zaručuje hardware. Na x86-64 to zajistí prefix lock:

Nejdůležitější je compare-and-swap (CAS): „zapiš novou hodnotu, ale jen pokud je tam pořád ta, kterou jsem četl.“ Když se mezitím změnila, CAS neuspěje a zkusíš to znovu:

opakuj {
    stara = x                     # přečti aktuální hodnotu
    nova  = stara + 1             # spočítej novou
} dokud CAS(&x, stara, nova) neuspěje

Všechny zámky ve všech knihovnách - mutex v pthreads, std::mutex, zámky v Javě, v Go i v Rustu - stojí na těchhle instrukcích. Nad nimi je jen správa čekajících vláken.

Který zámek si vzít

Spinlock vs. mutex

Spinlock aktivně čeká. V cyklu zkouší CAS a nikdy se nevzdá procesoru. Když ho někdo drží déle než pár desítek nanosekund, spálíš celé jádro na nic. Na jednom jádře čekáš na vlákno, kterému tím bereš procesor.

Mutex vlákno uspí. Zařadí ho do fronty a plánovač mu odebere procesor. Cenou je systémové volání a přepnutí kontextu, dohromady jednotky mikrosekund.

Doporučení: v uživatelském programu ber mutex. Spinlock má smysl jen tam, kde se nesmí spát a kde je čekání řádově kratší než přepnutí kontextu - tedy v jádře a v obsluze přerušení, kde není koho uspat.

Dnešní mutex je levný, dokud není spor. V Linuxu stojí na futexu (fast userspace mutex): nesporný zámek se vezme a vrátí jediným atomickým zápisem, bez cesty do jádra. Volání futex() přijde na řadu, teprve když je obsazeno.

Zrnitost zámku

Hrubý zámek chrání celou datovou strukturu naráz. Je snadný, těžko se rozbije a je pomalý - všechna vlákna se u něj seřadí do fronty.

Jemný zámek chrání každý prvek zvlášť - jeden na přihrádku hešovací tabulky. Je rychlejší, a jakmile potřebuješ držet dva naráz, otevřel sis dveře k uváznutí.

Doporučení: začni s jedním hrubým zámkem a zjemňuj až podle měření. Odhady, kde je spor, bývají chybné a jemné zamykání se ladí mnohem hůř.

Co ještě existuje a kdy po tom sáhnout

Čtenářsko-zapisovatelský zámek pustí dovnitř libovolně mnoho čtenářů, zapisovatele jen samotného. Zní to jako výhra zdarma a bývá pomalejší, než čekáš: příchod i odchod čtenáře je atomický zápis do společného čítače a cache-line se přehazuje mezi jádry stejně jako u mutexu. Ber ho až u dlouhých čtení.

Atomické typy bez zámku (_Atomic v C11, std::atomic) jsou správná volba pro čítače, příznaky a ukazatele. Jednu proměnnou ošetří levně a spolehlivě, invariant přes dvě jimi neuhlídáš.

RCU je technika z jádra Linuxu, kde čtenáři nečekají vůbec a zapisovatel data zkopíruje, upraví kopii, přehodí ukazatel a starou verzi uvolní, až doběhnou všichni čtenáři.

Nejlepší zámek je ten, který nepotřebuješ. Když data vlastní jedno vlákno a ostatní mu posílají zprávy, kritická sekce nevznikne - proto se hodně souběžných systémů staví na meziprocesové komunikaci, ne na sdílené paměti.

Co doopravdy selhává

Therac-25, 1985-87

Kanadský ozařovací přístroj Therac-25 se v šesti známých případech přepnul do stavu, kdy pacient dostal řádově stonásobek zamýšlené dávky. Nejméně tři pacienti na následky zemřeli.

Příčinou byl souběh mezi úlohou obsluhující klávesnici a úlohou, která nastavovala magnety a polohu terče. Když operátor přepsal parametry a potvrdil je dost rychle, přístroj přijal nové nastavení energie, ale mechanická část zůstala v předchozí poloze. Svazek plné energie tak šel na pacienta bez rozptylového terče.

Rychle psali až zkušení operátoři. Při testech tak rychle nikdo nepsal, takže testy nenašly nic - a výrobce po prvních hlášeních tvrdil, že taková chyba není možná.

Poučení: souběh se neprojeví, dokud nezměníš časování. Zelené testy o souběhu neříkají nic.

Diagnostika: čím se souběh chytí

Souběh se nehledá čtením ani opakovaným spouštěním, ale nástroji, které sledují, kdo na která data sahá a s jakým zámkem.

# ThreadSanitizer - nejlepší poměr užitku a práce, zpomalí zhruba 5-15krát
gcc -fsanitize=thread -g -O1 -pthread pocitadlo.c -o pocitadlo && ./pocitadlo

# Helgrind - bez instrumentace při překladu, ale výrazně pomalejší
valgrind --tool=helgrind ./pocitadlo

# kolikrát se kvůli spornému zámku šlo do jádra
strace -f -c -e trace=futex ./pocitadlo

# spor o zámky v jádře, ne ve tvém programu
sudo perf lock contention -ab -- sleep 5

ThreadSanitizer i Helgrind hlásí souběh, i když v daném běhu k žádné škodě nedošlo - stačí jim, že dva přístupy k témuž místu nebyly seřazené zámkem. Přesně to potřebuješ.

„Přidal jsem výpis a je to v pořádku“ je nejnebezpečnější výsledek ze všech. Výpis sám zamyká a trvá desítky mikrosekund, takže rozhodí časování a okno pro proložení zavře. Nic jsi neopravil, jen chybu odsunul k zákazníkovi s jiným počtem jader.

Falešné sdílení je jediná položka tabulky, kde jsou zámky v pořádku: dvě vlákna sahají na různé proměnné ve stejné 64bajtové cache-line a jádra si tu řádku přehazují při každém zápisu. Pomůže odsadit je na vlastní cache-line.

Co si odnést

x = x + 1 jsou tři operace. Načti, přičti, ulož - a mezi kterékoliv dvě se vejde jiné vlákno.

Souběh není chyba v kódu, ale v předpokladu, že tvoje operace proběhne celá. Čtením se nenajde.

Správné řešení musí splnit čtyři podmínky naráz. Vzájemné vyloučení, žádné blokování zvenku, konečné čekání, žádné předpoklady o rychlosti a počtu jader.

Všechno reálné stojí na CAS. Compare-and-swap je základ každého zámku, který použiješ - Peterson je pěkný a nepoužitelný.

V uživatelském programu ber mutex, ne spinlock. Spinlock patří do jádra a do obsluhy přerušení.

Začni hrubým zámkem a zjemňuj podle měření. Jemné zamykání je rychlé a vede k uváznutí.

Zelené testy o souběhu nedokazují nic. Pusť ThreadSanitizer.

Kam dál

• Semafory a monitory - co postavit nad zámkem, když jde o čekání na podmínku
• Uváznutí - co se stane, když zamykáš na dvou místech ve špatném pořadí
• Vlákna - co je sdílené a co ne, tedy kde vůbec může souběh vzniknout
• Meziprocesová komunikace - jak se sdílenému stavu vyhnout úplně
• Nástroje a diagnostika - čím dalším se do běžícího programu vidí