Kriticka-sekce-a-zamky.md

# 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](Vlakna) a představu o tom, co stojí [přepnutí kontextu](Prepinani-kontextu). Neřeší [semafory a monitory](Semafory-a-monitory) ani případ, kdy se dva zámky zaseknou navzájem, což je [uváznutí](Uvaznuti). ## 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 registruadd eax, 1                   # přičti v registrumov 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č](Planovani-procesu) 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: | Vlákno A | Vlákno B | Hodnota x v paměti ||---|---|---|| načti x → 41 | | 41 || | načti x → 41 | 41 || přičti → 42 | | 41 || | přičti → 42 | 41 || ulož 42 | | 42 || | ulož 42 | **42** | 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: ```cint flag[2] = {0, 0};   // kdo má zájem vstoupitint turn;               // kdo dává přednost tomu druhému // kód procesu i, ten druhý je jflag[i] = 1;                        // hlásím zájemturn = j;                           // ale pouštím druhého napředwhile (flag[j] && turn == j)    ;                               // aktivně čekám// kritická sekceflag[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`: | Instrukce | Co dělá | K čemu je ||---|---|---|| `lock xchg` | vymění registr a paměť | test-and-set, nejjednodušší zámek || `lock cmpxchg` | zapíše, jen když je tam očekávaná hodnota | **compare-and-swap, základ všeho ostatního** || `lock xadd` | přičte a vrátí původní | atomické čítače | 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í](Systemova-volani) a [přepnutí kontextu](Prepinani-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í](Preruseni-a-vyjimky), 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í](Uvaznuti). **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](Meziprocesova-komunikace), 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. ```bash# ThreadSanitizer - nejlepší poměr užitku a práce, zpomalí zhruba 5-15krátgcc -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ádrastrace -f -c -e trace=futex ./pocitadlo # spor o zámky v jádře, ne ve tvém programusudo 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říznak | Kde je problém ||---|---|| Výsledek se mění mezi spuštěními | neatomická úprava sdílených dat || Chyba zmizí po přidání výpisu | výpis zamyká a mění časování, souběh trvá || Funguje na jednom jádře, padá na osmi | spoléhá se na to, že se vlákna nepotkají || Padá jen v optimalizovaném překladu | chybí bariéra, překladač přesunul přístup || Běží, ale je pomalejší než jednovláknový | rvačka o zámek, nebo falešné sdílení || Občas se zasekne napořád | dva zámky v opačném pořadí, [uváznutí](Uvaznuti) | **„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](Semafory-a-monitory)** - co postavit nad zámkem, když jde o čekání na podmínku- **[Uváznutí](Uvaznuti)** - co se stane, když zamykáš na dvou místech ve špatném pořadí- **[Vlákna](Vlakna)** - co je sdílené a co ne, tedy kde vůbec může souběh vzniknout- **[Meziprocesová komunikace](Meziprocesova-komunikace)** - jak se sdílenému stavu vyhnout úplně- **[Nástroje a diagnostika](Nastroje-a-diagnostika)** - čím dalším se do běžícího programu vidí