====== Deadlock (Uváznutí) ======

**Deadlock** je situace v informatice, ke které dochází při souběžném běhu více [[thread|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.

----

====== Čtyři podmínky pro vznik (Coffmanovy podmínky) ======

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.



----

====== Praktický příklad: Klasický scénář ======

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.



----

====== Jak se s Deadlockem bojuje? ======

Existují tři hlavní strategie, jak tento problém řešit:

===== 1. Prevence a vyhýbání se =====
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.

===== 2. Detekce a zotavení =====
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).

===== 3. Ignorování (Pštrosí algoritmus) =====
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.

----

====== Rozdíl: Deadlock vs. Livelock ======

^ 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.//