Deadlock
Z Wikipedie, otevřené encyklopedie
Deadlock je odborný výraz pro situaci, kdy úspěšné dokončení nějaké akce je podmíněno předchozím dokončením jiné akce. Pokud tato jiná akce může být dokončena až po dokončení původní akce, vzniká paradox, často značovaný jako 'co je dříve? slepice nebo vejce'.
V počítači se jedná o zablokování procesů (případně vláken) způsobené čekáním na synchronizačních primitivech. Obvykle k němu dochází v důsledku chyby při jejich použití, někdy je ovšem možnost deadlocku ponechána v kódu úmyslně protože její odstranění by bylo příliš náročné. Vzniklý deadlock se potom nějakým způsobem řeší (například zrušením (rollback) transakce nebo zabíjením procesů) nebo se počítá s tím, že nastává zřídka a uživatel si pomůže sám.
Obsah |
[editovat] Podmínky deadlocku (Coffman)
Odstranění kterékoliv z těchto podmínek dostačuje pro zabránění deadlocku.
- Vzájemné vyloučení
- Prostředek může v jednom okamžiku používat jenom jeden proces (jinak dojde k chybě).
- Drž a čekej
- Proces může žádat o další prostředky, i když už má nějaké přiděleny.
- Neodnímatelnost
- Jakmile proces zmíněný prostředek vlastní, nelze mu ho bezpečně odejmout, musí ho sám vrátit.
- Čekání do kruhu
- 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.
[editovat] 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í
- Pro mnoho prostředků lze zabránit exkluzivitě používání předřazením spoolu, tedy fronty, do které posílají procesy úlohy. Takto je řešeno například používání tiskárny, ale i přístup k disku.
- Drž a čekej (Hold & wait)
- 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 (No preemption)
- 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 (Circular wait)
- 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 hiearchické zamykání, kdy se smí zamykat pouze směrem od kořene stromu dolů.
[editovat] Detekce deadlocku
Obecně je detekce deadlocku nemožná (je ekvivalentní s halting problémem) – nemůžeme zjistit na jaký prostředek proces čeká ani jestli ho proces který ho zrovna drží bude ochoten uvolnit před získáním prostředku, na jehož získání čeká. Pokud se ovšem omezíme na detekci deadlocku mezi procesy čekajícími na určité typy událostí – takové, u kterých obě zmíněné věci víme – jedná se o algoritmus hledání cyklu v grafu.
[editovat] Distribuovaný deadlock
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.
