# 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 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č](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:

```c
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`:

| 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á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ří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í