Czym jest zakleszczenie? Jakie są cztery warunki i jak mu zapobiegać?

Question

IT Interview Practice · Accepted Answer

**Zakleszczenie to stan, w którym dwa lub więcej wątków czeka w nieskończoność na zasób trzymany przez pozostałe, więc żaden nie może się posunąć naprzód.** Wymaga jednoczesnego spełnienia czterech warunków (warunki Coffmana).

## Cztery warunki

1. **Wzajemne wykluczanie** — zasób jest trzymany na wyłączność.
2. **Trzymaj i czekaj** — wątek trzyma jeden zasób, czekając na kolejny.
3. **Brak wywłaszczania** — zasobów nie da się odebrać siłą.
4. **Cykliczne oczekiwanie** — cykl wątków, z których każdy czeka na następny.

Przełam którykolwiek jeden, a zakleszczenie staje się niemożliwe.

```text
Thread 1 holds A, wants B ─┐
                           ├─ circular wait → deadlock
Thread 2 holds B, wants A ─┘
```

## Przykład i poprawka

```python
# DEADLOCK: threads lock in opposite orders
def t1():
    with lockA:
        with lockB: ...     # T1: A then B
def t2():
    with lockB:
        with lockA: ...     # T2: B then A  ← cycle!

# FIX: impose a global lock ordering (always A before B)
def safe():
    with lockA:
        with lockB: ...     # everyone acquires in the same order
```

## Zapobieganie i wykrywanie

- **Kolejność blokowania**: zawsze zajmuj blokady w spójnej, globalnej kolejności — przełamuje cykliczne oczekiwanie.
- **Limity czasu / try-lock**: `tryAcquire(timeout)`, wycofaj się i ponów — przełamuje trzymaj-i-czekaj.
- **Pojedyncza gruboziarnista blokada** lub struktury bez blokad (lock-free) całkowicie omijają problem.
- **Wykrywanie**: watchdog buduje graf oczekiwania (wait-for graph) i szuka cykli, po czym zabija/restartuje ofiarę.

## Dlaczego to ważne

Zakleszczenia zamrażają systemy po cichu — bez awarii, jedynie zawieszone żądania. Nazwanie czterech warunków pokazuje, że potrafisz rozumować o tym, *dlaczego* do niego dochodzi, i dobrać celowaną prewencję (zwykle spójną kolejność blokowania), zamiast rozsypywać blokady i liczyć na szczęście.

Cztery warunki

Przykład i poprawka

Zapobieganie i wykrywanie

Dlaczego to ważne

Powiązane pytania