Hva er en deadlock, og hvordan hindrer, unngår eller oppdager du den?

Question

IT Interview Practice · Accepted Answer

En **deadlock** er en tilstand der to eller flere tråder hver er **blokkert for alltid**, der hver venter på en ressurs som en annen holder. Ingenting gjør framgang.

## De fire nødvendige (Coffman-)betingelsene

Alle fire må gjelde samtidig — fjern én av dem og deadlock er umulig:

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

## Å håndtere deadlock

- **Forebygging (prevention)** — design slik at én betingelse aldri kan gjelde. Mest praktisk: drep **circular wait** ved å påtvinge en **global lock-rekkefølge** (skaff alltid A før B). Eller angrip **hold-and-wait** ved å ta alle nødvendige locks på én gang.
- **Unngåelse (avoidance)** — innvilg en forespørsel bare hvis systemet forblir i en "trygg" tilstand der hver tråd fortsatt kan fullføre (**Bankers algoritme**). Den trenger hver tråds maksimale ressursbehov på forhånd, så den brukes sjelden i praksis.
- **Oppdagelse og gjenoppretting (detection & recovery)** — la deadlocks skje, skann jevnlig **wait-for-grafen** for en sykel, og gjenopprett så ved å drepe eller rulle tilbake et offer. Databaser gjør nettopp dette: de oppdager deadlocks og avbryter én transaksjon med en "deadlock victim"-feil.
- **Ignorer ("strutsealgoritmen")** — hvis deadlocks er sjeldne, bare start på nytt; mange OS-er godtar dette for enkelte ressurser.

## Hvorfor det er viktig

Deadlock er et klassisk intervjutema fordi rammeverket med fire betingelser er et presist diagnoseverktøy: gitt en henging, kan du spørre "hvilken betingelse kan jeg bryte?" I ekte systemer er standardsvaret **konsistent lock-rekkefølge** (som hindrer circular wait) — en regel du bruker hver gang du tar mer enn én lock. Å kjenne igjen at databasen din kaster deadlock-victim-feil, og å vite at man bare skal prøve den transaksjonen på nytt, er en direkte praktisk anvendelse.

De fire nødvendige (Coffman-)betingelsene

Å håndtere deadlock

Hvorfor det er viktig

Relaterte spørsmål