Wat is een deadlock, en hoe voorkom, vermijd of detecteer je hem?

Question

IT Interview Practice · Accepted Answer

Een **deadlock** is een toestand waarin twee of meer threads elk **voor altijd geblokkeerd** zijn, elk wachtend op een resource die een ander vasthoudt. Niets maakt vooruitgang.

## De vier noodzakelijke (Coffman-)voorwaarden

Alle vier moeten tegelijk gelden — verwijder er één en deadlock is onmogelijk:

```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
```

## Omgaan met deadlock

- **Preventie** — ontwerp zo dat één voorwaarde nooit kan gelden. Het meest praktisch: dood **circular wait** door een **globale lock-volgorde** op te leggen (verkrijg altijd A vóór B). Of val **hold-and-wait** aan door alle benodigde locks in één keer te pakken.
- **Vermijding** — sta een verzoek alleen toe als het systeem in een "veilige" toestand blijft waarin elke thread nog kan afronden (het **Banker's algorithm**). Het heeft de maximale resourcebehoefte van elke thread vooraf nodig, dus het wordt in de praktijk zelden gebruikt.
- **Detectie & herstel** — laat deadlocks gebeuren, scan periodiek de **wait-for graph** op een cyclus, en herstel dan door een slachtoffer te killen of terug te rollen. Databases doen precies dit: ze detecteren deadlocks en breken één transactie af met een "deadlock victim"-fout.
- **Negeren (het "struisvogelalgoritme")** — als deadlocks zeldzaam zijn, herstart gewoon; veel OS'en accepteren dit voor sommige resources.

## Waarom het belangrijk is

Deadlock is een klassiek interviewonderwerp omdat het vier-voorwaardenraamwerk een precies diagnostisch gereedschap is: bij een hang kun je vragen "welke voorwaarde kan ik breken?" In echte systemen is het standaardantwoord **consistente lock-volgorde** (die circular wait voorkomt) — een regel die je toepast elke keer dat je meer dan één lock neemt. Herkennen dat je database deadlock-victim-fouten gooit, en weten dat je die transactie simpelweg opnieuw moet proberen, is een directe praktische toepassing.

De vier noodzakelijke (Coffman-)voorwaarden

Omgaan met deadlock

Waarom het belangrijk is

Gerelateerde vragen