Deadlock

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
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 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í procesů (případně vláken) způsobené křížovým čekáním na synchronizačních primitivech. K uváznutí dochází v důsledku 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ází může jednu transakci zrušit (příkazem rollback).

Příklad uváznutí[editovat | editovat zdroj]

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í 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[editovat | editovat zdroj]

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.):

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[editovat | editovat zdroj]

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 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í 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[editovat | editovat zdroj]

Obecně je předvídání deadlocku nemožné (je ekvivalentní s 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í cyklu v grafu.

Distribuovaný deadlock[editovat | editovat zdroj]

Deadlock může být distribuovaný, tedy obsahovat proces čekající na událost nebo prostředek na jiném počítači. Detekce distribuovaného deadlocku je ještě složitější než detekce deadlocku na jednom počítači.

Související články[editovat | editovat zdroj]