IF Notes

Konsep dan Deadlock Prevention

4 min read

Back to IF3140 Sistem Basis Data

2.1: Konsep & Pencegahan Deadlock

Questions/Cues

  • Apa itu Deadlock?

  • Apa 4 kondisi perlu Deadlock?

    1. Mutual Exclusion
    1. Hold and Wait
    1. No Preemption
    1. Circular Wait

  • Apa itu Deadlock Prevention?

  • Bagaimana cara mencegah Hold and Wait?

  • Apa itu Pre-declaration?

  • Bagaimana cara mencegah Circular Wait?

  • Apa itu Total Order?

Reference Points

  • Slides “11 - Concurrency Control - 2.pdf” (Hal 17-20)

Apa itu Deadlock?

Deadlock (kebuntuan) adalah sebuah kondisi di mana dua atau lebih transaksi saling menunggu selamanya untuk melepaskan lock yang mereka butuhkan.

Skenario Klasik:

  1. T1: lock-X(A).

  2. T2: lock-X(B).

  3. T1: request-X(B). (T1 Menunggu T2).

  4. T2: request-X(A). (T2 Menunggu T1).

Hasil: T1 menunggu T2, dan T2 menunggu T1. Keduanya akan menunggu selamanya dan tidak ada yang bisa lanjut.

Empat Kondisi Perlu (Necessary Conditions)

Sebuah deadlock bisa terjadi jika dan hanya jika keempat kondisi berikut terpenuhi secara bersamaan:

  1. Mutual Exclusion (Mutex):

    • Hanya satu transaksi yang boleh memegang lock pada suatu item data pada satu waktu (setidaknya untuk lock yang tidak kompatibel seperti lock-X).

    • Ini adalah kondisi yang inheren dari mekanisme locking dan tidak bisa dihilangkan.

  2. Hold and Wait (Tahan dan Tunggu):

  • Sebuah transaksi yang sudah memegang setidaknya satu lock (misal T1 pegang A) diizinkan untuk meminta dan menunggu lock baru (misal T1 minta B).

  1. No Preemption (Tidak Ada Paksaan):

  • Lock yang sudah diberikan kepada sebuah transaksi tidak dapat diambil paksa (preempted) oleh sistem.

  • Lock hanya bisa dilepaskan secara sukarela oleh transaksi yang memegangnya.

  1. Circular Wait (Tunggu Melingkar):

    • Terdapat sebuah rantai (siklus) dari transaksi yang saling menunggu.

    • Contoh: T1 -> T2 -> ... -> Tn -> T1, di mana Ti -> Tj berarti Ti sedang menunggu lock yang dipegang oleh Tj.

Deadlock Prevention (Pencegahan)

Strategi prevention (pencegahan) adalah memastikan agar sistem tidak akan pernah masuk ke kondisi deadlock. Caranya adalah dengan “menyerang” (menghilangkan) setidaknya salah satu dari empat kondisi perlu tersebut (biasanya Hold-and-Wait atau Circular-Wait).

1. Menyerang “Hold and Wait”

  • Metode: Pre-declaration (Deklarasi di Awal)

    • Aturan: Setiap transaksi harus meminta SEMUA lock yang ia butuhkan di awal eksekusinya. Jika semua lock bisa didapat, transaksi boleh berjalan. Jika ada satu saja yang tidak bisa didapat, transaksi tidak boleh memegang lock apapun dan harus menunggu.

  • Kelemahan:

    • Sulit: Seringkali transaksi tidak tahu lock apa saja yang ia butuhkan di masa depan (tergantung kondisi data).

    • Boros: Transaksi akan memegang lock (misal di akhir operasi) jauh lebih lama dari yang diperlukan.

    • Konkurensi Rendah: Mengurangi tingkat konkurensi secara drastis.

2. Menyerang “Circular Wait”

  • Metode: Impose Total Order (Paksakan Urutan Total)

    • Aturan: Berikan nomor unik (urutan) pada semua item data (misal A=1, B=2, C=3, …).

    • Paksakan semua transaksi untuk meminta lock hanya dalam urutan yang menaik.

    • Contoh: Jika T butuh lock A dan B, ia harus minta lock(A) dulu, baru lock(B). Ia dilarang minta lock(B) lalu lock(A).

    • Mengapa ini berhasil? Situasi Circular Wait T1(pegang A, minta B) dan T2(pegang B, minta A) menjadi tidak mungkin. T2 akan dipaksa minta A dulu sebelum B.

  • Kelemahan:

    • Tidak Fleksibel: Urutan akses data tidak selalu sesuai dengan urutan yang dipaksakan.

    • Graph-Based Protocol (Catatan 1.4) adalah salah satu implementasi dari metode ini (menggunakan pohon sebagai urutan).

Summary

Deadlock adalah kondisi di mana dua atau lebih transaksi saling menunggu lock dalam sebuah siklus, sehingga berhenti selamanya. Ini bisa terjadi jika empat kondisi terpenuhi: Mutual Exclusion, Hold and Wait (pegang 1, tunggu 1), No Preemption (tidak bisa diambil paksa), dan Circular Wait (siklus tunggu). Deadlock Prevention (Pencegahan) bertujuan menghilangkan salah satu kondisi ini. Cara utamanya adalah menyerang Hold and Wait dengan Pre-declaration (minta semua lock di awal) atau menyerang Circular Wait dengan Total Order (memaksa urutan permintaan lock), meskipun keduanya memiliki kelemahan pada fleksibilitas dan konkurensi.

Graph View

Backlinks