Co je deadlock a jak mu předcházet, vyhnout se mu nebo ho detekovat?

Question

IT Interview Practice · Accepted Answer

**Deadlock** (uváznutí) je stav, kdy jsou dvě nebo více vláken **navždy zablokovaná**, každé čeká na prostředek, který drží jiné. Nic se neposouvá dál.

## Čtyři nutné (Coffmanovy) podmínky

Všechny čtyři musí platit najednou — odstraňte kteroukoli a deadlock je nemožný:

```text
1. Mutual exclusion   → a resource is held exclusively (only one holder at a time)
2. Hold and wait      → a thread holds one resource while waiting to acquire another
3. No preemption      → resources can't be forcibly taken; only released voluntarily
4. Circular wait      → a cycle: T1 waits for R2 (held by T2), T2 waits for R1 (held by T1)
```

```text
   T1 ──holds──▶ R1        T1 wants R2 ──▶ (held by T2)
   T2 ──holds──▶ R2        T2 wants R1 ──▶ (held by T1)   ← cycle = deadlock
```

## Zvládání deadlocku

- **Prevence** — navrhněte to tak, aby jedna podmínka nikdy nemohla platit. Nejpraktičtější: zlikvidujte **circular wait** zavedením **globálního pořadí zámků** (vždy získat A před B). Nebo napadněte **hold-and-wait** tím, že získáte všechny potřebné zámky najednou.
- **Vyhýbání (avoidance)** — vyhovte požadavku jen tehdy, když systém zůstane v „bezpečném“ stavu, kde každé vlákno může stále dokončit (**Bankéřův algoritmus**). Potřebuje předem znát maximální nároky každého vlákna na prostředky, takže se v praxi používá zřídka.
- **Detekce a zotavení** — nechte deadlocky nastat, pravidelně skenujte **wait-for graph** kvůli cyklu a pak se zotavte zabitím nebo rollbackem oběti. Databáze dělají přesně tohle: detekují deadlocky a přeruší jednu transakci s chybou „deadlock victim“.
- **Ignorování („pštrosí algoritmus“)** — pokud jsou deadlocky vzácné, prostě restartujte; mnoho OS to pro některé prostředky akceptuje.

## Proč je to důležité

Deadlock je klasické téma pohovorů, protože rámec čtyř podmínek je přesný diagnostický nástroj: při zaseknutí se můžete zeptat „kterou podmínku mohu porušit?“ V reálných systémech je oblíbenou odpovědí **konzistentní pořadí zámků** (které zabraňuje circular wait) — pravidlo, které aplikujete pokaždé, když berete víc než jeden zámek. Rozpoznání, že vaše databáze vyhazuje chyby deadlock-victim, a vědomí, že stačí danou transakci zopakovat (retry), je přímá praktická aplikace.

Čtyři nutné (Coffmanovy) podmínky

Zvládání deadlocku

Proč je to důležité

Související otázky