Vad är en deadlock, och hur förhindrar, undviker eller upptäcker du den?

Question

IT Interview Practice · Accepted Answer

En **deadlock** är ett tillstånd där två eller fler threads var och en är **blockerade för alltid**, där var och en väntar på en resurs som en annan håller. Ingenting gör framsteg.

## De fyra nödvändiga (Coffman-)villkoren

Alla fyra måste gälla samtidigt — ta bort något av dem och deadlock är omöjlig:

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

## Hantera deadlock

- **Prevention** — designa så att ett villkor aldrig kan gälla. Det mest praktiska: döda **circular wait** genom att införa en **global lock ordering** (skaffa alltid A före B). Eller angrip **hold-and-wait** genom att ta alla behövda locks på en gång.
- **Avoidance** — bevilja en begäran bara om systemet förblir i ett "safe" tillstånd där varje thread fortfarande kan slutföra (**Banker's algorithm**). Den behöver varje threads maximala resursbehov i förväg, så den används sällan i praktiken.
- **Detection & recovery** — låt deadlocks hända, skanna periodiskt **wait-for-grafen** efter en cykel, och återhämta sedan genom att döda eller rulla tillbaka ett offer. Databaser gör precis detta: de upptäcker deadlocks och avbryter en transaction med ett "deadlock victim"-fel.
- **Ignorera ("the ostrich algorithm")** — om deadlocks är sällsynta, starta bara om; många OS accepterar detta för vissa resurser.

## Varför det är viktigt

Deadlock är ett klassiskt intervjuämne eftersom ramverket med fyra villkor är ett precist diagnostiskt verktyg: givet en hängning kan du fråga "vilket villkor kan jag bryta?" I verkliga system är standardsvaret **konsekvent lock ordering** (som förhindrar circular wait) — en regel du tillämpar varje gång du tar mer än ett lock. Att inse att din databas kastar deadlock-victim-fel, och veta att du bara ska försöka igen med den transaction:en, är en direkt praktisk tillämpning.

De fyra nödvändiga (Coffman-)villkoren

Hantera deadlock

Varför det är viktigt

Relaterade frågor