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

• Vlákno A získá Zámek 1 a chce získat Zámek 2.
• Vlákno B získá Zámek 2 a chce získat Zámek 1.

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.

• Řazení prostředků: Všechna vlákna musí žádat o prostředky vždy ve stejném pořadí (např. vždy nejdřív Zámek 1, pak Zámek 2). Tím se eliminuje kruhové čekání.
• Bankéřův algoritmus: Systém předem vypočítá, zda přidělení prostředku nemůže vést k nebezpečnému stavu.

Systém nechá Deadlock nastat, ale pravidelně kontroluje grafy závislostí. Pokud najde kruh, zasáhne:

• Ukončení procesu: Jedno ze zablokovaných vláken je násilně ukončeno (kill), čímž se uvolní jeho prostředky.
• Rollback: Systém vrátí proces do dřívějšího uloženého bodu (checkpointu).

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.

Související pojmy: Vlákno (Thread), Proces, Multitasking, Synchronizace, Mutex, Race Condition.