|
[[Soubor:Process deadlock.svg|thumb|right|Cyklické čekání: Proces P1 vyžaduje prostředek R1, který je přidělen procesu P2; proces P2 vyžaduje prostředek R2, který je přidělen procesu P1]]
'''Deadlock''' (česky také '''uváznutí''', '''vzájemné čekání''') je odborný výraz pro situaci, kdy úspěšné dokončení první akce je podmíněno předchozím dokončením druhé akce, přičemž druhá akce může být dokončena až po dokončení první akce. Vzniká [[paradox]], často označovaný jako 'Co‚Co bylo dříve? Slepice nebo vejce?'‘. V reálném životě se uváznutí řeší např. couváním (v dopravě).
V počítači se jedná o zablokování [[Počítačový program|procesů]] (případně [[Vlákno (program)|vláken]]) způsobené křížovým čekáním na [[synchronizační primitivum|synchronizačních primitivech]]. K uváznutí dochází v důsledku [[programátorská chyba|chyby]] programu nebo není uváznutí v programu úmyslně řešeno, protože řešení by bylo příliš náročné. Pokud v takovém případě dojde k uváznutí, je nutný zásah uživatele, který může násilně ukončit jeden z procesů nebo v případě práce s [[Databáze|databází]] může jednu [[transakce|transakci]] zrušit (příkazem [[rollback]]).
== Příklad uváznutí ==
Při práci s databázemi procesy A a B provádějí složitější operace nad tabulkami X a Y. Kvůli vyloučení [[Race condition|souběhu]] jsou tabulky během transakce uzamčeny. Proces A aktualizuje tabulku X, a proto si ji zamkne. Proces B aktualizuje tabulku Y a proto si ji také zamkne. Proces A čeká se zamčenou tabulkou X na uvolnění zámku na tabulce Y, aby mohl operaci dokončit. Zároveň proces B čeká na uvolnění zámku na tabulce X, aby mohl dokončit svoji operaci. Oba procesy uvíznou v nekonečném čekání (první čeká na dokončení operace druhého, která nemůže proběhnout, protože se čeká na dokončení operace prvního). ▼
▲Při práci s databázemi procesy A a B provádějí složitější operace nad tabulkami X a Y. Kvůli vyloučení [[Race condition|souběhu]] jsou tabulky během transakce uzamčeny. Proces A aktualizuje tabulku X, a proto si ji zamkne. Proces B aktualizuje tabulku Y a proto si ji také zamkne. Proces A čeká se zamčenou tabulkou X na uvolnění zámku na tabulce Y, aby mohl operaci dokončit. Zároveň proces B čeká na uvolnění zámku na tabulce X, aby mohl dokončit svoji operaci. Oba procesy uvíznou v nekonečném čekání (první čeká na dokončení operace druhého, která nemůže proběhnout, protože se čeká na dokončení operace prvního).
== Podmínky deadlocku ==
K uváznutí dojde jen při splnění všech následujících podmínek, které se označují jako ''Coffmanovy podmínky'' (protože je v článku z roku 1971 poprvé popsal [[Edward G. Coffman, Jr.|Edward G. Coffman, Jr.]]):
;Vzájemné vyloučení (Mutual exclusion):Prostředek může v jednom okamžiku používat jenom jeden proces (jinak dojde k chybě).
;Drž a čekej (Hold & wait):Proces může žádat o další prostředky, i když už má nějaké přiděleny.
;Neodnímatelnost (No preemption):Jakmile proces zmíněný prostředek vlastní, nelze mu ho bezpečně odejmout, musí ho sám vrátit.
;Čekání do kruhu (Circular wait):Je možné uzavřít cyklus z procesů čekající každý na svého předchůdce – respektive k deadlocku dojde, jakmile je tento cyklus uzavřen.
=== Odstranění deadlocku napadením Coffmanových podmínek ===
Odstranění deadlocku napadením jedné z Coffmanových podmínek je naprosto spolehlivé, ale obvykle obtížné a někdy nemožné.
;Vzájemné vyloučení:U mnoha prostředků není nutné mít přístup k samotnému prostředku, ale lze používat virtualizovaný prostředek (s [[počítačová tiskárna|tiskárnou]] nemusí komunikovat jednotlivé programy, mohou pouze ukládat data pro tisk do souborů, odkud je čte a na tiskárnu posílá specializovaný proces; podobně lze virtualizovat i prostředky sloužící pouze pro vstup). Toto předřazení [[fronta (datová struktura)|fronty]] fyzickému zařízení se nazývá ''spooling''.
;Drž a čekej:Proces musí o všechny prostředky, které potřebuje, zažádat najednou. Buď je všechny dostane, nebo nedostane ani jeden. Takto postupují [[databáze]] při použití zámků v jazyku [[SQL]] – musí všechny tabulky, které chtějí mít zamčené, zamknout najednou.
;Neodnímatelnost:Odejmutí lze provádět u prostředků, jejichž stav lze uložit a později obnovit. Typickým příkladem je procesor a vnitřní paměť. Napadení podmínky neodnímatelnosti vede k chaosu. Střídání procesů na procesoru sice na první pohled vypadá jako napadení této podmínky při správě prostředku ''čas procesoru'', ale je možné jen díky tomu, že existují okamžiky kdy změnu procesu provést nelze.
;Čekání do kruhu:Vznik cyklu lze vyloučit například pokud existuje jednoznačné pořadí, v jakém se o prostředky žádá. Na tomto principu je postaveno i hierarchické zamykání, kdy se smí zamykat pouze směrem od kořene stromu dolů.
== Detekce deadlocku ==
Obecně je předvídání deadlocku nemožné (je ekvivalentní s [[Problém zastavení|problémem zastavení]]) – nemůžeme zjistit, na jaký prostředek bude proces čekat, ani jestli ho proces, který ho zrovna drží, bude ochoten včas uvolnit. Pokud se ovšem omezíme na detekci uváznutí mezi procesy čekajícími na určité typy událostí – např. [[operační systém]] sleduje alokované prostředky – jedná se o [[algoritmus]] hledání [[Kružnice (graf)|cyklu]] v [[Graf (teorie grafů)|grafu]].
== Distribuovaný deadlock ==
| 