Apakah itu deadlock, dan bagaimana anda mencegah, mengelak, atau mengesannya?

Question

IT Interview Practice · Accepted Answer

Sebuah **deadlock** (kebuntuan) ialah keadaan di mana dua atau lebih thread masing-masing **tersekat selama-lamanya**, setiap satu menunggu sumber yang dipegang oleh yang lain. Tiada apa yang bergerak maju.

## Empat syarat perlu (Coffman)

Keempat-empatnya mesti berlaku serentak — buang mana-mana satu dan deadlock menjadi mustahil:

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

## Menangani deadlock

- **Pencegahan (prevention)** — reka bentuk supaya satu syarat tidak sesekali berlaku. Yang paling praktikal: bunuh **circular wait** dengan mengenakan **susunan lock global** (sentiasa peroleh A sebelum B). Atau serang **hold-and-wait** dengan merebut semua lock yang diperlukan sekali gus.
- **Pengelakan (avoidance)** — luluskan permintaan hanya jika sistem kekal dalam keadaan "selamat" di mana setiap thread masih boleh selesai (**algoritma Banker**). Ia memerlukan keperluan sumber maksimum setiap thread di awal, jadi ia jarang digunakan dalam praktik.
- **Pengesanan & pemulihan (detection & recovery)** — biarkan deadlock berlaku, imbas **wait-for graph** secara berkala untuk mencari kitaran, kemudian pulih dengan membunuh atau mengundur (rollback) satu mangsa. Pangkalan data melakukan tepat ini: ia mengesan deadlock dan membatalkan satu transaction dengan ralat "deadlock victim".
- **Abaikan ("algoritma burung unta")** — jika deadlock jarang berlaku, mulakan semula sahaja; banyak OS menerima cara ini bagi sesetengah sumber.

## Mengapa ia penting

Deadlock ialah topik temu duga klasik kerana rangka empat-syarat itu ialah alat diagnostik yang tepat: apabila menghadapi sesuatu yang tergantung, anda boleh bertanya "syarat mana boleh saya patahkan?" Dalam sistem sebenar jawapan pilihan ialah **susunan lock yang konsisten** (yang menghalang circular wait) — peraturan yang anda gunakan setiap kali anda mengambil lebih daripada satu lock. Menyedari bahawa pangkalan data anda melontarkan ralat deadlock-victim, dan tahu untuk sekadar retry transaction itu, ialah penerapan praktikal secara langsung.

Empat syarat perlu (Coffman)

Menangani deadlock

Mengapa ia penting

Soalan berkaitan