Czym jest deadlock i jak mu zapobiegać, unikać go lub go wykrywać?

Question

IT Interview Practice · Accepted Answer

**Deadlock (zakleszczenie)** to stan, w którym dwa lub więcej wątków są każdy **zablokowane na zawsze**, każdy czekając na zasób, który trzyma inny. Nic nie posuwa się naprzód.

## Cztery warunki konieczne (Coffmana)

Wszystkie cztery muszą zachodzić naraz — usuń którykolwiek, a deadlock jest niemożliwy:

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

## Radzenie sobie z deadlockiem

- **Zapobieganie (prevention)** — zaprojektuj tak, by jeden warunek nigdy nie mógł zachodzić. Najbardziej praktyczne: zabij **circular wait**, narzucając **globalną kolejność locków** (zawsze zdobywaj A przed B). Albo zaatakuj **hold-and-wait**, zdobywając wszystkie potrzebne locki naraz.
- **Unikanie (avoidance)** — przyznaj żądanie tylko, jeśli system pozostaje w stanie „bezpiecznym", w którym każdy wątek nadal może się zakończyć (**algorytm bankiera**). Wymaga z góry maksymalnych potrzeb zasobowych każdego wątku, więc rzadko jest używany w praktyce.
- **Wykrywanie i odzyskiwanie (detection & recovery)** — pozwól deadlockom się zdarzać, okresowo skanuj **wait-for graph** w poszukiwaniu cyklu, a potem odzyskaj, zabijając lub wycofując (rollback) ofiarę. Bazy danych robią dokładnie to: wykrywają deadlocki i przerywają jedną transakcję z błędem „deadlock victim".
- **Ignorowanie („algorytm strusia")** — jeśli deadlocki są rzadkie, po prostu zrestartuj; wiele systemów operacyjnych akceptuje to dla niektórych zasobów.

## Dlaczego to ważne

Deadlock to klasyczny temat rozmów rekrutacyjnych, bo ramy czterech warunków to precyzyjne narzędzie diagnostyczne: mając zawieszenie, możesz zapytać „który warunek mogę złamać?". W prawdziwych systemach standardową odpowiedzią jest **spójna kolejność locków** (która zapobiega circular wait) — reguła, którą stosujesz za każdym razem, gdy bierzesz więcej niż jeden lock. Rozpoznanie, że Twoja baza danych rzuca błędy deadlock-victim, i wiedza, że wystarczy ponowić (retry) tę transakcję, to bezpośrednie zastosowanie praktyczne.

Cztery warunki konieczne (Coffmana)

Radzenie sobie z deadlockiem

Dlaczego to ważne

Powiązane pytania