Back to IF3140 Sistem Basis Data
2.2: Penghindaran Deadlock (Avoidance)
Questions/Cues
Apa itu Deadlock Avoidance?
Apa beda Prevention vs Avoidance?
Apa asumsi yang dipakai?
Apa itu Timestamp Transaksi?
Apa itu skema Wait-Die?
Apa itu skema Wound-Wait?
Kapan transaksi MENUNGGU di Wait-Die?
Kapan transaksi MATI di Wait-Die?
Kapan transaksi MENUNGGU di Wound-Wait?
Kapan transaksi MELUKAI di Wound-Wait?
Mana yang preemptive?
Reference Points
- Slides “11 - Concurrency Control - 2.pdf” (Hal 21-22)
Definisi: Deadlock Avoidance
Deadlock Avoidance (Penghindaran) adalah pendekatan dinamis untuk menangani deadlock.
Berbeda dengan Prevention (Pencegahan) yang menerapkan aturan kaku di awal, Avoidance mengecek setiap permintaan lock saat runtime.
Sistem akan memutuskan apakah “aman” untuk memberikan lock tersebut. Jika permintaan lock berpotensi menciptakan deadlock di masa depan, sistem akan menundanya atau me-rollback salah satu transaksi.
Asumsi: Timestamp
Metode avoidance yang paling umum menggunakan Timestamp (TS).
Setiap transaksi (Ti) diberi timestamp unik saat ia dimulai.
Sistem menggunakan urutan timestamp ini untuk memutuskan siapa yang harus menunggu atau siapa yang harus rollback.
Asumsi: TS(Ti) < TS(Tj) berarti Ti lebih tua dari Tj.
Skema 1: Wait-Die (Tunggu-Mati)
Ini adalah skema non-preemptive (tidak bisa mengambil paksa).
Aturan: Asumsikan Ti meminta lock yang sedang dipegang oleh Tj.
Jika TS(Ti) < TS(Tj) — (Ti lebih TUA dari Tj):
Ti MENUNGGU (WAIT).
Logika: Transaksi yang lebih tua diizinkan menunggu transaksi yang lebih muda.
Jika TS(Ti) > TS(Tj) — (Ti lebih MUDA dari Tj):
- Ti MATI (DIE) / Rollback.
- Logika: Transaksi yang lebih muda tidak boleh menunggu transaksi yang lebih tua (karena ini bisa jadi awal dari siklus). Ti akan di-rollback dan dimulai ulang nanti (dengan timestamp yang sama).
Skema 2: Wound-Wait (Lukai-Tunggu)
Ini adalah skema preemptive (bisa mengambil paksa).
Aturan: Asumsikan Ti meminta lock yang sedang dipegang oleh Tj.
Jika TS(Ti) < TS(Tj) — (Ti lebih TUA dari Tj):
Ti MELUKAI (WOUND) Tj.
Logika: Transaksi yang lebih tua “melukai” transaksi yang lebih muda. Tj dipaksa rollback (preempted) dan melepaskan lock-nya. Lock kemudian diberikan kepada Ti.
Jika TS(Ti) > TS(Tj) — (Ti lebih MUDA dari Tj):
Ti MENUNGGU (WAIT).
Logika: Transaksi yang lebih muda diizinkan menunggu transaksi yang lebih tua.
Perbandingan Wait-Die vs Wound-Wait
Skenario (Ti minta lock Tj) Wait-Die (Non-preemptive) Wound-Wait (Preemptive) Ti lebih TUA (TS(Ti) < TS(Tj)) Ti MENUNGGU Ti MELUKAI Tj (Tj rollback) Ti lebih MUDA (TS(Ti) > TS(Tj)) Ti MATI (Ti rollback) Ti MENUNGGU
Wait-Die: Transaksi yang rollback adalah transaksi yang meminta lock (Ti yang lebih muda).
Wound-Wait: Transaksi yang rollback adalah transaksi yang memegang lock (Tj yang lebih muda).
Kedua skema ini menjamin bebas deadlock karena mereka memutus potensi circular wait menggunakan urutan timestamp.
Deadlock Avoidance adalah pendekatan dinamis yang memeriksa setiap permintaan lock saat runtime untuk mencegah deadlock. Ini sering menggunakan Timestamp (TS) untuk menentukan prioritas. Ada dua skema utama: (1) Wait-Die (Non-preemptive), di mana jika Ti lebih TUA dari Tj, Ti MENUNGGU, tetapi jika Ti lebih MUDA, Ti MATI (rollback). (2) Wound-Wait (Preemptive), di mana jika Ti lebih TUA dari Tj, Ti MELUKAI Tj (Tj rollback), tetapi jika Ti lebih MUDA, Ti MENUNGGU. Kedua skema ini efektif mencegah deadlock.
Additional Information
Pendalaman: Masalah Starvation
Kedua skema ini bisa menyebabkan starvation (kelaparan), di mana sebuah transaksi tidak pernah selesai karena terus-menerus di-rollback.
Wait-Die: Transaksi yang “muda” (TS besar) bisa berulang kali “mati” (rollback) setiap kali ia mencoba mengakses lock yang dipegang oleh transaksi yang lebih “tua”. Jika ini terjadi terus-menerus, ia bisa mengalami starvation.
Wound-Wait: Transaksi yang “muda” (TS besar) bisa berulang kali “dilukai” (rollback) oleh transaksi “tua” yang datang belakangan dan membutuhkan lock yang sama.
Solusi: Saat sebuah transaksi di-rollback dan dimulai ulang, sistem harus tetap menggunakan timestamp aslinya (yang lama). Ini memastikan bahwa seiring berjalannya waktu, transaksi tersebut akan menjadi transaksi “paling tua” di sistem dan akhirnya akan mendapatkan semua lock yang dibutuhkannya tanpa “mati” atau “dilukai”.
Pro & Kontra
Wait-Die: Cenderung menghasilkan lebih banyak rollback karena transaksi yang lebih muda yang meminta langsung di-rollback.
Wound-Wait: Cenderung menghasilkan lebih sedikit rollback karena rollback hanya terjadi jika transaksi yang lebih tua datang dan membutuhkan lock yang dipegang oleh yang lebih muda (sebuah preemption).