IF Notes

Deteksi dan Deadlock Recovery

4 min read

Back to IF3140 Sistem Basis Data

2.3: Deteksi & Pemulihan Deadlock

Questions/Cues

  • Apa itu Deadlock Detection?

  • Apa itu Wait-for Graph (WFG)?

  • Kapan deadlock terjadi di WFG?

  • Kapan deteksi dijalankan?

  • Apa itu Deadlock Recovery?

  • Langkah 1: Victim Selection?

  • Faktor pemilihan korban?

  • Langkah 2: Rollback?

  • Apa itu Total Rollback?

  • Apa itu Partial Rollback?

  • Apa itu Starvation?

Reference Points

  • Slides “11 - Concurrency Control - 2.pdf” (Hal 23-24)

Deadlock Detection (Deteksi)

Ini adalah pendekatan “paling optimis”: biarkan deadlock terjadi, lalu deteksi, dan terakhir pulihkan.

  • Keuntungan: Tidak ada overhead dari prevention atau avoidance pada setiap permintaan lock.

  • Kekurangan: Deadlock bisa terjadi dan “menggantung” sistem untuk sementara waktu sampai terdeteksi.

Metode: Wait-for Graph (WFG)

Metode deteksi yang paling umum adalah dengan membangun Wait-for Graph (Graf Tunggu).

  1. Node (Simpul): Setiap node adalah satu transaksi yang sedang aktif.

  2. Edge (Panah): Sebuah panah Ti -> Tj dibuat jika transaksi Ti sedang menunggu lock yang saat ini dipegang oleh transaksi Tj.

Kondisi Deadlock:

Sistem berada dalam kondisi deadlock jika dan hanya jika terdapat siklus (cycle) di dalam Wait-for Graph.

Contoh:

  • T1 menunggu T2 (T1 -> T2)

  • T2 menunggu T3 (T2 -> T3)

  • T3 menunggu T1 (T3 → T1)

    Ini adalah siklus, yang berarti T1, T2, dan T3 sedang deadlock.

Kapan Deteksi Dijalankan?

Algoritma pencarian siklus di WFG harus dijalankan:

  1. Secara Periodik: Misal, setiap 1 menit atau setiap 5 detik. Jika terlalu sering, overhead tinggi. Jika terlalu jarang, deadlock akan “menggantung” sistem terlalu lama.

  2. Setiap Ada Tunggu: Setiap kali sebuah transaksi terpaksa menunggu, cek WFG. Ini mendeteksi deadlock secara instan, tetapi overhead-nya sangat tinggi.

Deadlock Recovery (Pemulihan)

Setelah siklus (deadlock) terdeteksi, sistem harus “memutus” siklus tersebut. Ini dilakukan dengan me-rollback (membatalkan) satu atau lebih transaksi di dalam siklus.

Langkah 1: Victim Selection (Pemilihan Korban)

Transaksi mana di dalam siklus yang harus di-rollback?

Faktor-faktor Penentu:

  • Prioritas: Apakah ada transaksi yang lebih penting? (JANGAN rollback transaksi batch penting).

  • Biaya Rollback: Pilih yang paling “murah” untuk di-rollback.

  • Berapa lama transaksi telah berjalan?

  • Berapa banyak lock yang dipegang?

  • Berapa banyak data yang telah diubah?

  • Berapa banyak transaksi lain yang harus ikut di-rollback (jika tidak pakai Strict 2PL)?

Langkah 2: Rollback (Pembatalan)

  • Total Rollback: Abort seluruh transaksi korban dari awal dan mulai ulang. Ini adalah cara paling sederhana.

  • Partial Rollback: Rollback transaksi korban hanya sejauh yang diperlukan untuk membebaskan lock yang menyebabkan siklus. Lebih efisien, tetapi jauh lebih kompleks untuk diimplementasikan (perlu savepoint).

Masalah: Starvation (Kelaparan)

  • Definisi: Situasi di mana sebuah transaksi yang sama terus-menerus dipilih sebagai “korban” rollback setiap kali ia mencoba berjalan.

  • Solusi: Sistem harus melacak “jumlah rollback” dari setiap transaksi dan memasukkannya sebagai faktor dalam Victim Selection. Jangan pilih transaksi yang sudah terlalu sering jadi korban.

Summary

Deadlock Detection adalah strategi yang membiarkan deadlock terjadi dan mendeteksinya menggunakan Wait-for Graph (WFG), di mana node adalah transaksi dan panah adalah relasi tunggu. Sebuah siklus (cycle) di WFG menandakan adanya deadlock. Setelah terdeteksi (biasanya secara periodik), sistem melakukan Recovery (Pemulihan) dengan memilih korban (Victim Selection) berdasarkan biaya rollback atau prioritas. Korban tersebut kemudian di-Rollback (bisa Total atau Partial) untuk memutus siklus. Sistem harus waspada terhadap Starvation, di mana transaksi yang sama selalu dipilih sebagai korban.

Graph View

Backlinks