Kas yra deadlock ir kaip jį užkirsti, išvengti ar aptikti?

Question

IT Interview Practice · Accepted Answer

**Deadlock** (aklavietė) yra būsena, kai dvi ar daugiau gijų kiekviena yra **blokuota amžinai**, kiekviena laukia ištekliaus, kurį laiko kita. Niekas nejuda į priekį.

## Keturios būtinos (Coffman) sąlygos

Visos keturios turi galioti vienu metu — pašalink bet kurią vieną ir deadlock neįmanomas:

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

## Kaip elgtis su deadlock

- **Prevencija (prevention)** — projektuok taip, kad viena sąlyga niekada negalėtų galioti. Praktiškiausia: sunaikink **circular wait** primesdamas **globalų lock eiliškumą** (visada įsigyk A prieš B). Arba pulk **hold-and-wait** įsigydamas visus reikalingus lock iš karto.
- **Vengimas (avoidance)** — patenkink užklausą tik jei sistema lieka „saugioje“ būsenoje, kur kiekviena gija dar gali baigti (**Banker's algorithm**). Jam reikia iš anksto žinoti kiekvienos gijos maksimalius išteklių poreikius, todėl praktikoje retai naudojamas.
- **Aptikimas ir atkūrimas (detection & recovery)** — leisk deadlock įvykti, periodiškai skenuok **wait-for graph** ieškodamas ciklo, tada atkurk nužudydamas ar atsukdamas (rollback) auką. Duomenų bazės daro būtent tai: jos aptinka deadlock ir nutraukia vieną transakciją su „deadlock victim“ klaida.
- **Ignoravimas („stručio algoritmas“)** — jei deadlock reti, tiesiog paleisk iš naujo; daug OS priima tai kai kuriems ištekliams.

## Kodėl tai svarbu

Deadlock yra klasikinė interviu tema, nes keturių sąlygų karkasas yra tikslus diagnostikos įrankis: gavęs pakibimą (hang), gali klausti „kurią sąlygą galiu sulaužyti?“ Realiose sistemose įprastas atsakymas yra **nuoseklus lock eiliškumas** (kuris užkerta circular wait) — taisyklė, kurią taikai kaskart, kai imi daugiau nei vieną lock. Suvokimas, kad tavo duomenų bazė meta deadlock-victim klaidas, ir žinojimas, kad tereikia iš naujo bandyti (retry) tą transakciją, yra tiesioginis praktinis pritaikymas.

Keturios būtinos (Coffman) sąlygos

Kaip elgtis su deadlock

Kodėl tai svarbu

Susiję klausimai