Hvad er en deadlock, og hvordan forhindrer, undgår eller opdager du den?

Question

IT Interview Practice · Accepted Answer

En **deadlock** er en tilstand, hvor to eller flere tråde hver især er **blokeret for altid**, hver ventende på en ressource, som en anden holder. Intet gør fremskridt.

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

Alle fire skal gælde på én gang — fjern bare én, 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åndtering af deadlock

- **Forebyggelse (prevention)** — design, så én betingelse aldrig kan gælde. Det mest praktiske: dræb **circular wait** ved at påtvinge en **global lock-rækkefølge** (tag altid A før B). Eller angrib **hold-and-wait** ved at tage alle nødvendige locks på én gang.
- **Undgåelse (avoidance)** — imødekom kun en anmodning, hvis systemet forbliver i en "sikker" tilstand, hvor hver tråd stadig kan færdiggøre (**Banker's algorithm**). Den kræver hver tråds maksimale ressourcebehov på forhånd, så den bruges sjældent i praksis.
- **Opdagelse og genopretning (detection & recovery)** — lad deadlocks ske, scan med jævne mellemrum **wait-for-graph'en** for en cyklus, og genopret så ved at dræbe eller rulle et offer tilbage. Databaser gør præcis dette: de opdager deadlocks og afbryder én transaktion med en "deadlock victim"-fejl.
- **Ignorér ("strudsealgoritmen")** — hvis deadlocks er sjældne, så genstart bare; mange styresystemer accepterer dette for visse ressourcer.

## Hvorfor det betyder noget

Deadlock er et klassisk interviewemne, fordi rammen med de fire betingelser er et præcist diagnostisk værktøj: givet et hæng kan du spørge "hvilken betingelse kan jeg bryde?" I rigtige systemer er standardsvaret **konsistent lock-rækkefølge** (som forhindrer circular wait) — en regel, du anvender hver gang, du tager mere end én lock. At genkende, at din database kaster deadlock-victim-fejl, og at vide, at man blot skal prøve den transaktion igen, er en direkte praktisk anvendelse.

De fire nødvendige (Coffman-)betingelser

Håndtering af deadlock

Hvorfor det betyder noget

Relaterede spørgsmål