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?“. Vreálném životě se uváznutí řeší např. couváním (vdopravě).
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. Kuváznutí dochází vdůsledku chyby programu nebo není uváznutí vprogramu úmyslně řešeno, protože řešení by bylo příliš náročné. Pokud vtakovém případě dojde kuváznutí, je nutný zásah uživatele, který může násilně ukončit jeden zprocesů nebo vpřípadě práce sdatabází může jednu transakci zrušit (příkazem rollback).
Při práci sdatabázemi procesy A aB provádějí složitější operace nad tabulkami X aY. Kvůli vyloučení souběhu jsou tabulky během transakce uzamčeny. Proces A bude aktualizovat tabulku X, aproto si ji zamkne. Proces B bude aktualizovat tabulku Y aproto 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 vnekoneč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).
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 zroku 1971 poprvé popsal Edward G.Coffman, Jr.):[1][2]
Vzájemné vyloučení (Mutual exclusion)
Každý prostředek může vjednom okamžiku používat nejvýše jeden proces (aby nedošlo k porušení konzistence dat).
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 odejmout, musí ho sám vrátit.
Cyklické čekání (Circular wait)
Dojde k uzavření cyklu, ve kterém je dva nebo více procesů, znichž každý čeká na prostředek, který je přidělen dalšímu procesu v cyklu.
Předcházení (prevence) – napadení jedné z Coffmanových podmínek
Vyhýbání se – Operační systém vyhoví žádosti o přidělení prostředku pouze pokud zůstane v bezpečném stavu (tj. existuje cesta, jak uspokojit všechny požadavky na prostředky jejich přidělováním v určitém pořadí) – viz bankéřův algoritmus. Procesy musí předem specifikovat všechny prostředky, které budou potřebovat; v současných operačních systémech k tomu obvykle nejsou nástroje.
Detekce a zotavení – Hledá kružnici v orientovaném grafu (hrany vedou od procesu, který čeká, k procesu, který prostředek vlastní), pokud tam je kružnice, nastalo zablokování a je třeba ho řešit:
Odebrání prostředku – může být na přechodnou dobu
Zabíjení procesů z cyklu (případně i mimo cyklus, procesů vlastnících identický prostředek)
Rollback (OS ukládá stav procesů, při zablokování se některé procesy vrátí do předchozího stavu, může způsobit ztrátu dat nebo práce; často používané u databází)
Ignorování problému (pštrosí algoritmus) – Mnoho operačních systémů se sice snaží snižovat nebezpečí vzniku deadlocku (použitím spoolingu, umožněním současného zamykání více prostředků, apod.), ale protože by důsledné zabraňování deadlocku vedlo k nepřijatelnému snížení efektivity systému, toto nebezpečí úplně neodstraňují. Detekce zablokování a jeho řešení zůstává na uživateli (typicky násilným ukončením jednoho nebo více procesů a uvolněním přidělených prostředků). Tento přístup nespotřebovává prostředky OS proto bývá velmi častý (Unix, Windows).
Odstranění deadlocku napadením Coffmanových podmínek
Odstranění deadlocku napadením jedné zCoffmanových podmínek je naprosto spolehlivé, ale obvykle obtížné aněkdy nemožné.
Vzájemné vyloučení
U mnoha prostředků není nutné mít přístup ksamotnému prostředku, ale lze používat virtualizovaný prostředek (stiskárnou nemusí komunikovat jednotlivé programy, mohou pouze ukládat data pro tisk do souborů, odkud je čte ana 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ů vjazyku 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 apozději obnovit. Typickým příkladem je procesor avnitřní paměť.
Cyklické čekání
Vznik cyklu lze vyloučit například pokud existuje jednoznačné pořadí, vjaké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ů.
Bankéřův algoritmus
Bankéřův algoritmus se používá hlavně u prostředků, kterých se přiděluje určité množství (jednotky s výměnnými médii, jako jsou magnetopáskové jednotky, diskové jednotky u sálových počítačů, paměť, odkládací prostor). Bankéř (operační systém) má klienty (procesy) a těm slíbil jistou výšku úvěru (maximální množství prostředků). Bankéř ví, že ne všichni klienti potřebují plnou výši úvěru najednou. Klienti občas navštíví banku a žádají postupně o prostředky až do maximální výše úvěru. Klient v konečném čase obchod dokončí a bance vypůjčené prostředky vrátí. Bankéř peníze půjčí pouze tehdy, zůstane-li banka v bezpečném stavu. To znamená, že existuje cesta, jak v každém okamžiku přidělit alespoň jednomu z klientů předem uvedené maximální množství prostředků, a poté, co všechny své prostředky vrátí, postupně uspokojovat další klienty.[3]
Detekce deadlocku
Obecně je předvídání deadlocku nemožné (je ekvivalentní sproblé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 vgrafu.
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.
DIJKSTRA, E. W., 1968. Co-operating sequential processes. In: Programming languages: NATO Advanced Study Institute: lectures given at a three weeks Summer School held in Villard-le-Lans. [s.l.]: Academic Press Inc. Dostupné online. S.43–112.
TANENBAUM, Andrew S., 2009. Modern Operating Systems. 3. vyd. London: Pearson Education International.