Deadlock je situace v informatice, ke které dochází při souběžném běhu více vláken. Lze ho přirovnat k situaci na křižovatce, kde do středu vjedou čtyři auta ze čtyř směrů a vzájemně si zablokují cestu – nikdo nemůže jet dál, dokud někdo jiný necouvne, ale couvnout není kam.
Aby mohl Deadlock nastat, musí být současně splněny tyto čtyři podmínky:
1. **Vzájemné vyloučení (Mutual Exclusion):** Prostředek (např. tiskárna nebo proměnná) může v jeden okamžik používat pouze jedno vlákno. 2. **Držení a čekání (Hold and Wait):** Vlákno již drží alespoň jeden prostředek a zároveň žádá o další, který momentálně drží někdo jiný. 3. **Nemožnost odnětí (No Preemption):** Operační systém nemůže vláknu prostředek násilím sebrat; vlákno ho musí uvolnit dobrovolně. 4. **Kruhové čekání (Circular Wait):** Existuje uzavřený řetězec vláken, kde každé čeká na prostředek držený dalším článkem v řetězci.
Představme si dvě vlákna (A a B) a dva zámky k datům (Zámek 1 a Zámek 2):
Obě vlákna nyní navždy stojí. Vlákno A neustoupí, dokud nedostane Zámek 2, a Vlákno B neustoupí, dokud nedostane Zámek 1.
Existují tři hlavní strategie, jak tento problém řešit:
Systém je navržen tak, aby jedna z Coffmanových podmínek nikdy nenastala.
Systém nechá Deadlock nastat, ale pravidelně kontroluje grafy závislostí. Pokud najde kruh, zasáhne:
Většina běžných operačních systémů (Windows, Linux) Deadlocky u uživatelských aplikací ignoruje. Předpokládá se, že k nim dochází zřídka a je levnější nechat uživatele aplikaci restartovat, než neustále monitorovat všechny prostředky.
| Stav | Popis |
|---|---|
| Deadlock | Vlákna stojí a nedělají nic (jsou zablokovaná). |
| Livelock | Vlákna stále něco dělají (mění svůj stav), ale nikam se neposouvají (jako když se dva lidé v úzké chodbě snaží vyhnout a oba úskakují stále na stejnou stranu). |
Související pojmy: Vlákno (Thread), Proces, Multitasking, Synchronizace, Mutex, Race Condition.