Mikä on deadlock, ja miten sen ehkäiset, vältät tai havaitset?

Question

IT Interview Practice · Accepted Answer

**Deadlock** on tila, jossa kaksi tai useampi thread on kukin **estetty ikuisesti**, ja jokainen odottaa resurssia, jota toinen pitää. Mikään ei etene.

## Neljä välttämätöntä (Coffman) ehtoa

Kaikkien neljän on oltava voimassa yhtä aikaa — poista mikä tahansa niistä, ja deadlock on mahdoton:

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

## Deadlockin käsittely

- **Ehkäisy (prevention)** — suunnittele niin, ettei jokin ehto voi koskaan päteä. Käytännöllisin: tapa **circular wait** asettamalla **globaali lukkojärjestys** (hanki aina A ennen B:tä). Tai hyökkää **hold-and-waitia** vastaan hankkimalla kaikki tarvittavat lukot kerralla.
- **Välttäminen (avoidance)** — myönnä pyyntö vain, jos järjestelmä pysyy "turvallisessa" tilassa, jossa jokainen thread voi silti valmistua (**Bankerin algoritmi**). Se tarvitsee kunkin threadin maksimiresurssitarpeet etukäteen, joten sitä käytetään käytännössä harvoin.
- **Havaitseminen ja toipuminen (detection & recovery)** — anna deadlockien tapahtua, skannaa säännöllisesti **wait-for-graafi** sykliä etsien ja toivu tappamalla tai rollbackaamalla uhrin. Tietokannat tekevät juuri näin: ne havaitsevat deadlockit ja keskeyttävät yhden transaktion "deadlock victim" -virheellä.
- **Sivuuttaminen ("strutsialgoritmi")** — jos deadlockit ovat harvinaisia, käynnistä vain uudelleen; monet OS:t hyväksyvät tämän joillekin resursseille.

## Miksi se on tärkeää

Deadlock on klassinen haastatteluaihe, koska neljän ehdon kehys on tarkka diagnostinen työkalu: jumitusta kohdatessasi voit kysyä "minkä ehdon voin rikkoa?" Todellisissa järjestelmissä vakiovastaus on **johdonmukainen lukkojärjestys** (joka estää circular waitin) — sääntö, jota sovellat joka kerta kun otat useamman kuin yhden lukon. Sen tunnistaminen, että tietokantasi heittää deadlock-victim-virheitä, ja sen tietäminen, että kyseinen transaktio pitää vain uudelleenyrittää, on suora käytännön sovellus.

Neljä välttämätöntä (Coffman) ehtoa

Deadlockin käsittely

Miksi se on tärkeää

Aiheeseen liittyvät kysymykset