Deadlock

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í

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 bude aktualizovat tabulku X, a proto si ji zamkne. Proces B bude aktualizovat 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.):

Vzájemné vyloučení (Mutual exclusion)

Každý prostředek může v jednom 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ů, z nichž každý čeká na prostředek, který je přidělen dalšímu procesu v cyklu.

Řešení zablokování

• 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é 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ěť.

Cyklické čekání

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ů.

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.

Detekce deadlocku

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

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.

Odkazy

Literatura

• 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. 
• COFFMAN, Edward G., Jr.; ELPHICK, Michael J.; SHOSHANI, Arie, 1971. System Deadlocks. ACM Computing Surveys. Roč. 3, čís. 2, s. 67–78. Dostupné online [cit. 2021-03-12]. Dostupné také na: [1]. DOI 10.1145/356586.356588. S2CID 15975305.  Archivováno 6. 5. 2021 na Wayback Machine.

Související články

• Nekonečný cyklus
• Livelock
• Efekt hrdla lahve
• Petriho síť
• Transakční paměť