1. Pendahuluan: Masalah Filsuf Makan Malam dan Empat Kondisi Coffman (1971)

Pada tahun 1965, ilmuwan komputer Belanda Edsger W. Dijkstra merumuskan Masalah Filsuf Makan Malam (Dining Philosophers Problem) yang terkenal: lima filsuf $P_0 \dots P_4$ duduk mengelilingi meja bundar; di antara setiap piring spageti terdapat satu garpu ($F_0 \dots F_4$). Untuk makan, setiap filsuf harus memegang garpu kiri $F_i$ dan garpu kanan $F_{(i+1)\bmod 5}$ secara bersamaan. Jika kelima filsuf merasa lapar pada mikrodetik yang persis sama dan serentak mengambil garpu kiri $F_i$, masing-masing akan menunggu selamanya hingga tetangga kanannya melepaskan garpu kedua—seluruh sistem membeku abadi. Kondisi ini disebut kebuntuan (Deadlock).

Secara formal, himpunan bagian proses tak kosong $D \subseteq \mathcal{P}$ berada dalam status deadlock jika dan hanya jika setiap proses $P_i \in D$ terblokir menunggu suatu peristiwa (seperti pelepasan kunci) yang hanya dapat dipicu oleh proses lain $P_j \in D$ di dalam himpunan tunggu yang sama.

Pada tahun 1971, Edward G. Coffman Jr., M. J. Elphick, dan Arie Shoshani membuktikan bahwa deadlock sumber daya hanya dapat terjadi jika empat kondisi perlu terpenuhi secara bersamaan:

1. Eksklusi Bersama (Mutual Exclusion): Setidaknya satu sumber daya dipegang dalam mode eksklusif (tidak dapat dibagi).
2. Genggam dan Tunggu (Hold and Wait): Sebuah proses sedang memegang setidaknya satu sumber daya sambil menunggu terblokir untuk memperoleh sumber daya tambahan yang dipegang proses lain.
3. Tanpa Preempsi (No Preemption): Sumber daya yang telah dialokasikan tidak dapat direbut paksa; hanya dilepaskan secara sukarela oleh pemegangnya.
4. Tunggu Melingkar (Circular Wait): Terdapat rantai tertutup proses $\{P_0, P_1, \dots, P_{k-1}\}$ di mana setiap $P_i$ menunggu sumber daya yang dipegang oleh $P_{(i+1)\bmod k}$.

Karena keempat kondisi tersebut masing-masing merupakan syarat perlu, menegasikan secara logis satu saja dari empat kondisi Coffman membuat deadlock mustahil terjadi secara matematis ($0\,\%$).

2. Graf Alokasi Sumber Daya (RAG) dan Teorema Siklus (Holt, 1972)

Pada tahun 1972, Richard C. Holt memodelkan status sumber daya sebagai graf berarah bipartit yang disebut Graf Alokasi Sumber Daya (RAG) $G = (V, E)$, dengan himpunan simpul $V = \mathcal{P} \cup \mathcal{R}$ (proses $P_i$ dan tipe sumber daya $R_j$ yang memiliki $W_j \ge 1$ instans identik), sisi permintaan $P_i \to R_j$, serta sisi alokasi $R_j \to P_i$.

Tiga teorema fundamental menghubungkan siklus berarah pada $G$ dengan deadlock:

• Teorema 1 (Asiklisitas $\implies$ Bebas Deadlock): Jika $G$ tidak mengandung siklus berarah (berupa DAG), tidak ada proses yang mengalami deadlock.
• Teorema 2 (Syarat Perlu dan Cukup pada Instans Tunggal): Jika setiap tipe sumber daya hanya memiliki satu instans ($\forall j, W_j = 1$), maka siklus berarah pada $G \iff$ deadlock.
• Teorema 3 (Ketidakcukupan pada Multi-Instans): Jika suatu sumber daya memiliki banyak instans ($\exists j, W_j > 1$), keberadaan siklus berarah adalah syarat perlu, tetapi BUKAN syarat cukup untuk deadlock!

  flowchart TD
    subgraph RAG_Single["Kasus A: RAG Instans Tunggal (Siklus <==> Pasti Deadlock)"]
        PA1(("P1 (Terblokir)")) -->|"Meminta"| RA1["R1 (1 instans: ●)"]
        RA1 -->|"Dialokasikan ke"| PA2(("P2 (Terblokir)"))
        PA2 -->|"Meminta"| RA2["R2 (1 instans: ●)"]
        RA2 -->|"Dialokasikan ke"| PA1
    end

    subgraph RAG_Multi["Kasus B: RAG Multi-Instans (Ada siklus P1->R1->P3->R2->P1 tetapi NOL Deadlock!)"]
        PB1(("P1 (Terblokir)")) -->|"Meminta"| RB1["R1 (2 instans: ●●)"]
        RB1 -->|"Instans #1"| PB3(("P3 (Terblokir)"))
        PB3 -->|"Meminta"| RB2["R2 (2 instans: ●●)"]
        RB2 -->|"Instans #1"| PB1
        RB1 -->|"Instans #2"| PB2(("P2 (BERJALAN: Tanpa permintaan!)"))
        RB2 -->|"Instans #2"| PB4(("P4 (BERJALAN: Tanpa permintaan!)"))
    end

Pada Kasus B terdapat siklus $P_1 \to R_1 \to P_3 \to R_2 \to P_1$, namun $P_2$ dan $P_4$ memiliki derajat keluar $0$ (simpul muara aktif): begitu keduanya selesai dan melepas instans $R_1$ serta $R_2$, siklus tersebut langsung terurai!

3. Strategi 1 (Pencegahan): Bukti Kontradiksi Pengurutan Kunci Total

Di dalam kernel OS (seperti validator lockdep Linux) dan sistem multithread, kondisi 4 (tunggu melingkar) dihapuskan melalui Pengurutan Kunci Total (Total Lock Ordering): setiap mutex $L \in \mathcal{L}$ diberi peringkat global unik $\phi(L) \in \mathbb{N}$, dan setiap thread yang memegang himpunan kunci $\mathcal{H}$ hanya boleh meminta kunci baru $L_{\text{new}}$ jika peringkatnya строго lebih besar:

【Bukti dengan Kontradiksi】: Andaikan terbentuk siklus tunggu $\{P_0, P_1, \dots, P_{k-1}\}$ ($k \ge 2$), di mana $P_i$ memegang $L_i$ dan menunggu $L_{(i+1)\bmod k}$. Karena semua thread mematuhi aturan urutan naik ketat, perantaian pertidaksamaan sepanjang siklus menghasilkan:

Karena tidak ada bilangan asli yang lebih kecil dari dirinya sendiri, terjadi kontradiksi ($\bot$)! Baik pada transfer bank (selalu kunci rekening ber-ID lebih kecil dulu) maupun filsuf makan malam (membuat $P_4$ mengambil garpu kanan $F_0$ sebelum garpu kiri $F_4$, karena $0 < 4$), tunggu melingkar menjadi mustahil. $\blacksquare$

4. Strategi 2 (Penghindaran): Algoritma Bankir Dijkstra (Telusur Matriks 5×3)

Ketika urutan kunci bersifat dinamis, Algoritma Bankir Dijkstra (1965 / Habermann, 1969) mewajibkan deklarasi awal kebutuhan maksimum $\mathbf{Max}$ dan memeriksa dalam waktu $O(m \cdot n^2)$ sebelum setiap alokasi apakah status hasil tetap merupakan Status Aman (Safe State) yang memiliki setidaknya satu Urutan Aman (Safe Sequence) ($\text{Deadlock} \subsetneq \text{Status Tidak Aman}$).

Untuk $n=5$ proses $\{P_0 \dots P_4\}$ dan $m=3$ sumber daya dengan $\mathbf{Total} = (A=10, B=5, C=7)$ serta total teralokasi $(7,2,5)$, vektor tersedia awal adalah $\mathbf{Available} = (10,5,7) - (7,2,5) = \mathbf{(3, 3, 2)}$:

Urutan aman $\langle P_1, P_3, P_4, P_0, P_2 \rangle$ membuktikan bahwa $t_0$ Aman. Jika $P_1$ meminta $(1,0,2)$, alokasi sementara menyisakan $\mathbf{Available}=(2,3,0) \ge \mathbf{Need}_1=(0,2,0)$ (disetujui seketika). Namun jika tepat setelahnya $P_0$ meminta $(0,2,0)$, ketersediaan jatuh ke $(2,1,0)$ yang tidak dapat memenuhi $\mathbf{Need}$ proses mana pun (Status Tidak Aman): sang bankir menolak permintaan tersebut dan memblokir $P_0$!

5. Strategi 3 & 4 (Deteksi WFG, Wait-Die/Wound-Wait, Burung Unta) & Livelock vs. Starvation

RDBMS (PostgreSQL, MySQL InnoDB) membangun Graf Tunggu (Wait-For Graph, WFG) dan mencari siklus melalui DFS dalam $O(|V|+|E|)$, membatalkan (rollback) transaksi korban dengan log Undo terkecil (deteksi seketika di MySQL; setelah deadlock_timeout = 1s di PostgreSQL). Basis data terdistribusi (Google Spanner) memakai protokol berbasis stempel waktu $\text{TS}(T_i)$ dari Rosenkrantz et al. (1978): Wait-Die (non-preemptif) dan Wound-Wait (preemptif, lebih sedikit restart sia-sia), dengan wajib mempertahankan stempel waktu asli $\text{TS}(T_i)$ saat mencoba ulang demi mencegah kelaparan (starvation). Untuk kehabisan tabel sistem yang sangat langka pada OS umum, UNIX dan Windows menerapkan Algoritma Burung Unta (Ostrich Algorithm) dengan mengabaikan masalah agar panggilan sistem harian tetap cepat.

  flowchart TD
    Req["Transaksi terdistribusi Ti meminta kunci yang dipegang Tj"] --> Cmp{"Bandingkan stempel waktu mulai: TS(Ti) < TS(Tj) ?<br/>(Apakah peminta Ti LEBIH TUA daripada pemegang Tj?)"}
    Cmp -->|"Ya: Ti LEBIH TUA (Older)"| WD1["[Wait-Die (non-preemptif)]: Ti yang tua MENUNGGU Tj yang muda (Tua -> Muda)<br/>[Wound-Wait (preemptif)]: Ti yang tua MELUKAI (abort) Tj dan merebut kunci!"]
    Cmp -->|"Tidak: Ti LEBIH MUDA (Younger)"| WD2["[Wait-Die (non-preemptif)]: Ti yang muda MATI (abort & coba lagi dengan TS asli)<br/>[Wound-Wait (preemptif)]: Ti yang muda MENUNGGU dengan tenang Tj yang tua (Muda -> Tua)"]

Terakhir, mari bandingkan ketiga kegagalan keaktifan (Liveness):