Uvaznuti.md

# Uváznutí, čili když se dva slušně vychovaní programy nedomluví Vlákno A drží zámek 1 a potřebuje k práci ještě zámek 2. Vlákno B ve stejnou chvíli drží zámek 2 a potřebuje zámek 1. Obě čekají na to druhé a ani jedno se nedočká. Ani jedno přitom neudělalo chybu, kterou bys mohl ukázat prstem. Obě zamykají poctivě, obě po sobě uklízejí a nikde není souběh. Chyba je v **pořadí**, ve kterém ty dva kusy kódu zámky berou - a to pořadí nikdo nenapsal. Stránka řeší, kdy tenhle stav nastane, jak ho vyloučit a proč na něj narazíš jinde, než čekáš. Neřeší, jak zámky fungují uvnitř - to je na stránce o [kritické sekci a zámcích](Kriticka-sekce-a-zamky), bez které tady nic nedává smysl. Předpokládá i znalost [vláken](Vlakna). ## Uváznutí není chyba, je to shoda čtyř okolností Tohle je nejdůležitější věc na celé stránce: **uváznutí nastane jedině tehdy, když platí čtyři podmínky současně.** Zařiď, aby jedna z nich neplatila nikdy, a uváznutí není nepravděpodobné - je nemožné. Nehledáš tedy chybu, ale čtyři vlastnosti systému, ze kterých jednu odstraníš. To je celá obrana proti uváznutí; zbytek stránky ji jen rozvádí. ### Čtyři Coffmanovy podmínky Pojmenoval je Edward Coffman se spoluautory v roce 1971. **Vzájemné vyloučení.** Zdroj drží v jednu chvíli jen jeden proces - jinak by to nebyl zámek. **Držení a čekání.** Proces drží jeden zdroj a přitom čeká na další, místo aby čekal s prázdnou. **Nepřipustitelnost odebrání.** Zdroj nejde držiteli sebrat, musí ho vrátit sám. **Kruhové čekání.** Existuje kruh procesů, ve kterém každý čeká na zdroj držený tím následujícím. ### Kterou z těch čtyř se vyplatí rušit Vzájemné vyloučení zrušit nejde, aniž bys zrušil smysl zámku. Odebrání jde jen tam, kde umíš vrátit stav zpět - databáze díky `ROLLBACK` umí, mutex nad pamětí nikdy. Držení a čekání zrušit lze, ale platíš horším využitím zdrojů. **Kruhové čekání je jediná ze čtyř podmínek, která se ruší zadarmo.** Nestojí výkon ani paměť, jen dohodu o pořadí. Proto ji v praxi uvidíš rušit jako jedinou. ### Jak se kruh pozná v grafu přidělení zdrojů Nakresli si to jako orientovaný graf: hrana od procesu ke zdroji je „čeká na něj", od zdroje k procesu „drží ho". ```mermaidflowchart LR    A[Vlákno A] -->|čeká na| Z2[Zámek 2]    Z2 -->|drží| B[Vlákno B]    B -->|čeká na| Z1[Zámek 1]    Z1 -->|drží| A``` Uváznutí je v grafu vidět jako cyklus. Má-li každý zdroj jedinou instanci, platí cyklus = uváznutí. Má-li jich víc, je cyklus jen nutná podmínka. ## Čtyři postoje, které k tomu jde zaujmout | Postoj | Co to stojí | Kde se používá ||---|---|---|| **Ignorovat** | občasný restart | Linux, Windows, běžné aplikace || Prevence | disciplínu v celém kódu | jádra, ovladače, knihovny || Vyhýbání se | znát maxima dopředu | prakticky nikde || Detekce a zotavení | průběžnou kontrolu a zabitou práci | databáze | ### Pštrosí algoritmus, který používá Linux i Windows Pštrosí algoritmus znamená strčit hlavu do písku a nedělat nic. V obecném operačním systému je to správná volba a obě velká jádra ji dělají: prevence by musela platit pro každý cizí ovladač a průběžná detekce by stála výkon při každém zamčení. Uváznutí v jádře je vzácné a uživatel ho vyřeší restartem. Není to úplná rezignace. Linux má zapnutelný validátor pořadí zámků (`CONFIG_PROVE_LOCKING`, lockdep), který nebezpečné pořadí hlásí i tehdy, když k uváznutí nedošlo. Detekce se dělá při vývoji, ne v produkci. ## Prevence v praxi ### Globální pořadí zámků **Zaveď globální pořadí zámků a ber je vždycky v něm.** Kruh pak nemůže vzniknout, protože by vyžadoval, aby někdo šel proti pořadí. To je nejdůležitější praktické pravidlo stránky. Modelový příklad je převod peněz mezi dvěma účty. Zamykat „nejdřív svůj, pak cizí" je ta chyba z úvodu: ```c// špatně: pořadí závisí na směru převodulock(&z->zamek); lock(&na->zamek); // správně: rozhoduje číslo účtu, ne směrif (z->cislo < na->cislo) { lock(&z->zamek);  lock(&na->zamek); }else                      { lock(&na->zamek); lock(&z->zamek);  }``` Při `z->cislo == na->cislo` jde o převod na sebe sama a zamkneš jen jednou. Kde není přirozený klíč, použij adresu struktury. **Zámky s časovým limitem.** `pthread_mutex_trylock` při neúspěchu hned vrátí `EBUSY` místo čekání. Pak **pusť všechny zámky, které držíš**, náhodně počkej a začni znovu - jinak sis vyrobil livelock. Záchranná brzda, ne náhrada za pořadí. **Vezmi všechno naráz, nebo nic.** Ruší podmínku držení a čekání. Funguje, když dopředu víš, co budeš potřebovat. ## Bankéřův algoritmus a bezpečný stav Bankéřův algoritmus kruh nezakazuje. Před každým přidělením ověří, jestli systém zůstane v **bezpečném stavu** - tedy jestli existuje pořadí procesů, ve kterém se všechny dokončí, i když si každý řekne o maximum. Fond má 12 spojení. Tři procesy předem hlásí, kolik jich nanejvýš budou chtít. | Proces | Max | Alokace | Potřeba ||---|---|---|---|| P0 | 10 | 5 | 5 || P1 | 4 | 2 | 2 || P2 | 9 | 2 | 7 | Dostupné = 12 - 9 = **3**. P1 potřebuje 2, projde a vrátí 4 - dostupné je 7. P0 potřebuje 5, projde a vrátí 10. P2 pak potřebuje 7 a projde taky. Posloupnost P1, P0, P2 existuje, stav je bezpečný. Teď si P2 řekne o spojení navíc. Dostupné klesne na 2, potřeba P2 stoupne na 6. Projde jen P1, po něm jsou dostupné 4, ale P0 chce 5 a P2 šest. Bezpečná posloupnost neexistuje a **bankéř požadavek odmítne, přestože dvě spojení volná jsou**. V operačních systémech to nenajdeš: vyžaduje předem znát maximální nárok každého procesu na každý typ zdroje. To nikdo neví a procesy navíc vznikají za běhu. V návodech přežívá proto, že se hezky počítá. ## Detekce se doopravdy dělá v databázích Databáze mají obě věci, které jádro nemá: přehled o tom, kdo drží který zámek, a možnost vzít práci zpět. Proto smějí nechat uváznutí vzniknout a pak ho uklidit. PostgreSQL po vypršení `deadlock_timeout` (výchozí 1 s) prohledá graf čekání, a najde-li cyklus, zruší jednu transakci s chybou `deadlock detected` a stavem `40P01`. MySQL s InnoDB dělá totéž a vrátí chybu 1213, `Deadlock found when trying to get lock`. **Tohle je nejčastější místo, kde uváznutí reálně potkáš** - ne v jádře, ale v logu aplikace. Nezvyšuj časové limity, transakci zopakuj a srovnej pořadí, ve kterém zamykáš řádky. ## Inverze priorit a Mars Pathfinder 1997 Sonda Mars Pathfinder přistála 4. července 1997 a v prvních dnech se opakovaně sama restartovala. Nízkopriotní úloha sbírající meteorologická data držela zámek nad sdílenou informační sběrnicí. Vysokopriotní úloha, která sběrnici obsluhuje, na ten zámek čekala. Mezitím běžela dlouhá středněpriotní komunikační úloha a nízkopriotní vůbec nepustila k procesoru. Zámek se neuvolnil, hlídací obvod usoudil, že se sběrnice zasekla, a restartoval systém. Formálně to nebylo uváznutí - kruh nikde nebyl - ale chovalo se to stejně. Opraveno bylo vzdáleně, nahráním změny, která na zámku zapnula **dědění priorit**: držitel dočasně převezme prioritu toho, kdo čeká. Priority samotné jsou v [plánování procesů](Planovani-procesu). **Poučení: chyba se objevila už při pozemních testech, ale protože nešla spolehlivě zopakovat, uzavřela se jako nedůležitá.** Uváznutí, které nastane jednou za sto běhů, není náhoda. Je to deterministická chyba, jejíž podmínku jsi zatím nenašel. ## Livelock a vyhladovění nejsou totéž | Jev | Co dělá procesor | Koho postihne | Odejde samo ||---|---|---|---|| Uváznutí | nic, procesy stojí | uzavřenou skupinu | ne || Livelock | běží naplno | uzavřenou skupinu | jen s náhodným čekáním || Vyhladovění | práce postupuje | jednoho, ostatní jedou | až se změní zátěž | Livelock je stav, kdy se procesy hýbou, reagují na sebe a nepostupují - dva lidé uhýbající si na chodbě donekonečna na stejnou stranu. Vzniká z naivního `trylock` bez náhodné prodlevy. Vyhladovění nikoho neblokuje, jen jeden proces nepřijde na řadu. ## Uváznutí, ve kterém není ani jeden zámek Zámek není podmínka, stačí čekání na sebe navzájem. Dva procesy propojené dvěma rourami ([IPC](Meziprocesova-komunikace)) se zaseknou, jakmile oba zapisují víc, než se vejde do vyrovnávací paměti roury (na Linuxu 64 KiB), a ani jeden zatím nečte. Oba visí ve `write()`. Stejně se chová plná fronta zpráv. **Nejčastější reálné uváznutí v běžné aplikaci je vyčerpaný fond spojení k databázi.** Fond má deset spojení, každý požadavek si jedno vezme a v půlce práce si řekne o druhé. Jakmile deset požadavků drží po jednom, aplikace stojí a databáze se nudí. ## Diagnostika ```bashsudo gdb -p 12345 -batch -ex 'thread apply all bt'   # zásobníky všech vláken narázsudo cat /proc/12345/stack        # kde v jádře vlákno spí; jen u stavu Dps -eLo pid,tid,stat,wchan:24,comm | awk '$3 ~ /^D/'  # kdo spí neukončitelně a kde``` ```bashsudo sysctl -w kernel.sysrq=1          # Debian má výchozích 438, výpisy zakázanéecho w | sudo tee /proc/sysrq-trigger  # do logu vypíše zásobníky blokovaných úlohsudo dmesg -T | grep -A20 'blocked for more than'``` U MySQL vypíše poslední cyklus `SHOW ENGINE INNODB STATUS\G` v sekci `LATEST DETECTED DEADLOCK`, u PostgreSQL zapni `log_lock_waits = on`. Zbytek nářadí je v [nástrojích a diagnostice](Nastroje-a-diagnostika). | Příznak | Kde je problém ||---|---|| Nulové vytížení procesoru, aplikace neodpovídá | klasické uváznutí na zámcích || Vytížení 100 % a nic se nedokončuje | livelock nebo cyklení nad spinlockem || Všechna vlákna v `bt` stojí v `pthread_mutex_lock` | uváznutí v uživatelském kódu, srovnej pořadí || Aplikace stojí, databáze je nečinná | vyčerpaný fond spojení || `Deadlock found when trying to get lock` v logu | InnoDB našel cyklus a transakci zrušil || `INFO: task ... blocked for more than 120 seconds` | vlákno spí v jádře, typicky I/O nebo zámek jádra | ## Co si odnést **Uváznutí vyžaduje čtyři podmínky současně.** Stačí trvale zrušit jednu. **Globální pořadí zámků je celá prevence.** Ruší kruhové čekání, jedinou ze čtyř podmínek, která je zadarmo. **Pštrosí algoritmus je v obecném operačním systému správná odpověď.** Linux i Windows uváznutí neřeší a mají pravdu. **Bankéřův algoritmus se nepoužívá.** Potřebuje maxima, která nikdo dopředu nezná. **Detekci dělají databáze, ne jádro.** Mají přehled o zámcích a umí vzít práci zpět. **Nejčastější uváznutí v aplikaci nemá mutex.** Je to fond spojení, ze kterého si jeden požadavek bere dvě. ## Kam dál - **[Kritická sekce a zámky](Kriticka-sekce-a-zamky)** - co je mutex a proč se bez něj neobejdeš- **[Semafory a monitory](Semafory-a-monitory)** - klasické úlohy, kde uváznutí číhá- **[Plánování procesů](Planovani-procesu)** - priority a jejich dědění- **[Meziprocesová komunikace](Meziprocesova-komunikace)** - roury a fronty, kde se zasekneš beze zámku