Latihan Kuis 2 - 3

Back to IF3140 Sistem Basis Data

Problem Set: Analisis Concurrency Control & Deadlock

Mata Pelajaran: Sistem Basis Data

Estimasi Waktu: 60 menit

Total Nilai: 100 poin

Tujuan Pembelajaran

Setelah menyelesaikan problem set ini, mahasiswa diharapkan dapat:

1. Menganalisis dan membedakan jadwal (schedule) yang mematuhi Two-Phase Locking (2PL) dan Strict 2PL.

2. Mengevaluasi dampak dari cascading rollback dalam sebuah skenario transaksi.

3. Membangun dan menginterpretasi Wait-for Graph (WFG) untuk mendeteksi adanya deadlock.

4. Mengaplikasikan skema deadlock avoidance (Wait-Die dan Wound-Wait) pada studi kasus yang diberikan.

5. Mensintesis dan merekomendasikan strategi penanganan deadlock (prevention, avoidance, detection) untuk sebuah skenario dunia nyata.

Petunjuk Umum

• Bacalah setiap studi kasus dan skenario dengan teliti.

• Jawablah setiap pertanyaan dengan jelas dan berikan justifikasi yang kuat berdasarkan konsep yang telah dipelajari.

• Untuk soal analisis jadwal, perhatikan setiap operasi (Read, Write, Lock, Unlock, Commit, Abort).

• Gunakan terminologi yang presisi (misal: lock point, timestamp, victim selection).

BAGIAN I: Analisis Skenario & Studi Kasus (75 poin)

Fokus: Application dan Analysis - Menerapkan konsep ke situasi baru.

Soal 1. Studi Kasus: Analisis Two-Phase Locking (2PL) (25 poin)

Kasus: Diberikan dua buah jadwal (S1 dan S2) yang melibatkan transaksi T1 dan T2. Data item yang diakses adalah E dan F.

Jadwal S1:

T1: XL(E); W(E); UL(E); T2: XL(E); W(E); XL(F); W(F); T1: Abort; T2: Commit; UL(E); UL(F);

Jadwal S2:

T1: XL(E); W(E); T2: XL(E); (Wait); T1: XL(F); W(F); T1: Commit; UL(E); UL(F); T2: (Grant); W(E); T2: Commit; UL(E);

Pertanyaan:

a. (10 poin) Analisislah S1. Apakah S1 mematuhi protokol 2PL? Apakah S1 mematuhi protokol Strict 2PL? Jelaskan justifikasi Anda.

b. (10 poin) Apa konsekuensi dari T1: Abort pada S1? Fenomena apa yang terjadi, dan mengapa ini merugikan?

c. (5 poin) Analisislah S2. Protokol apa yang dipatuhi oleh S2 (2PL, Strict 2PL, atau Rigorous 2PL)? Jelaskan mengapa S2 dapat mencegah masalah yang terjadi pada S1.

Soal 2. Analisis Deteksi: Wait-for Graph (WFG) (25 poin)

Kasus: Sebuah sistem basis data menggunakan Deadlock Detection dengan Wait-for Graph (WFG). Pada satu waktu (T), status sistem adalah sebagai berikut:

• T1: Sedang memegang lock-X pada item F dan sedang menunggu (request) lock-S pada item G.

• T2: Sedang memegang lock-S pada item G dan sedang menunggu (request) lock-X pada item H.

• T3: Sedang memegang lock-X pada item H dan sedang menunggu (request) lock-X pada item G.

• T4: Sedang memegang lock-S pada item I dan sedang menunggu (request) lock-X pada item F.

• T5: Sedang memegang lock-X pada item J.

Pertanyaan:

a. (10 poin) Gambarkan Wait-for Graph (WFG) berdasarkan status sistem di atas.

b. (10 poin) Analisislah WFG tersebut. Apakah terjadi deadlock di dalam sistem? Jika ya, sebutkan siklus (cycle) yang terbentuk dan transaksi mana saja yang terlibat.

c. (5 poin) Jika terjadi deadlock, dan sistem memutuskan T3 sebagai victim untuk di-rollback, jelaskan bagaimana recovery tersebut memutus siklus deadlock.

Soal 3. Studi Kasus: Analisis Deadlock Avoidance (25 poin)

Kasus: Sebuah sistem menggunakan skema Deadlock Avoidance berbasis timestamp (TS). Semakin kecil nilai TS, semakin tua transaksi tersebut. Diberikan tiga transaksi dengan timestamp berikut:

• TS(T1) = 10

• TS(T2) = 20

• TS(T3) = 30

Perhatikan urutan kejadian berikut yang terjadi secara sekuensial:

1. T2 meminta dan mendapatkan lock-X pada item A.

2. T3 meminta dan mendapatkan lock-X pada item B.

3. T1 meminta lock-X pada item B (yang sedang dipegang T3).

4. T3 meminta lock-X pada item A (yang sedang dipegang T2).

Pertanyaan:

Analisislah apa yang akan terjadi pada Kejadian 3 dan Kejadian 4 jika sistem menerapkan:

a. (10 poin) Skema Wait-Die.

b. (10 poin) Skema Wound-Wait.

c. (5 poin) Skema mana yang cenderung menghasilkan lebih banyak rollback dalam skenario ini? Jelaskan.

BAGIAN II: Esai Sintesis (25 poin)

Fokus: Synthesis dan Evaluation - Integrasi konsep dan pemikiran kritis.

Soal 4. Esai Sintesis: Memilih Strategi Penanganan Deadlock (25 poin)

Skenario: Anda adalah seorang Arsitek Basis Data yang ditugaskan untuk merancang sistem core banking baru. Dua kebutuhan utama dari klien adalah:

1. Konsistensi Data Kritis: Transaksi (transfer, debit, kredit) tidak boleh gagal di tengah jalan atau menyebabkan data tidak konsisten.

2. Ketersediaan Tinggi (High Availability): Sistem tidak boleh “freeze” atau berhenti merespons, bahkan untuk beberapa detik.

Klien Anda khawatir tentang deadlock. Anda harus menjelaskan tiga pendekatan utama (Prevention, Avoidance, Detection) dan memberikan rekomendasi.

Instruksi:

Tuliskan esai analisis (sekitar 200-300 kata) yang membandingkan trade-off dari:

1. Deadlock Prevention (misal: menggunakan Total Order pada sumber daya)

2. Deadlock Avoidance (misal: menggunakan Wound-Wait)

3. Deadlock Detection (misal: menggunakan WFG dan victim selection)

Dalam esai Anda, fokuslah pada dampaknya terhadap kinerja, konkurensi, dan kompleksitas implementasi. Akhiri esai Anda dengan rekomendasi strategi mana (atau kombinasi strategi) yang paling cocok untuk sistem core banking tersebut, dan berikan justifikasi yang kuat untuk pilihan Anda.

Kunci Jawaban & Rubrik Penilaian

Bagian I

Soal 1:

• a. (10 poin) Analisis S1:

  • 2PL: S1 MEMATUHI 2PL.

    • T1: Growing phase (XL(E)), Shrinking phase (UL(E)). Lock point setelah XL(E).

    • T2: Growing phase (XL(E), XL(F)), Shrinking phase (UL(E), UL(F)). Lock point setelah XL(F).

    • Kedua transaksi memiliki fase growing dan shrinking yang terpisah. (5 poin)

  • Strict 2PL: S1 TIDAK MEMATUHI Strict 2PL.

    • Strict 2PL mengharuskan lock-X (Eksklusif) ditahan sampai transaksi commit atau abort.

    • T1 melepaskan lock-X pada E (UL(E)) sebelum ia Abort. Ini adalah pelanggaran Strict 2PL. (5 poin)

• b. (10 poin) Konsekuensi S1:

  • Ketika T1 Abort, operasinya (W(E)) harus dibatalkan (rollback).

  • Masalah: T2 telah membaca (XL(E) juga berarti R(E)) dan menulis (W(E)) data E yang “kotor” (dirty read/write) yang ditinggalkan oleh T1.

  • Fenomena: Ini menyebabkan Cascading Rollback. Karena T2 telah beroperasi pada data tidak valid dari T1, T2 juga WAJIB di-rollback untuk menjaga konsistensi, meskipun T2 sudah Commit. (10 poin)

• c. (5 poin) Analisis S2:

  • S2 mematuhi Strict 2PL (dan juga Rigorous 2PL karena semua lock ditahan).

  • T1 menahan semua lock-nya (XL(E), XL(F)) sampai ia Commit. T2 baru diizinkan mendapatkan lock pada E setelah T1 selesai.

  • Ini mencegah masalah dirty read yang terlihat di S1. Jika T1 Abort di S2, tidak ada transaksi lain yang terpengaruh. (5 poin)

Soal 2:

• a. (10 poin) Wait-for Graph:

  • (Wajib ada gambar/deskripsi node dan panah)

  • Nodes: T1, T2, T3, T4, T5

  • Edges (Panah):

    • T1 -> T2 (T1 menunggu G yang dipegang T2)

    • T2 -> T3 (T2 menunggu H yang dipegang T3)

    • T3 -> T2 (T3 menunggu G yang dipegang T2)

    • T4 -> T1 (T4 menunggu F yang dipegang T1)

• b. (10 poin) Analisis Deadlock:

  • YA, terjadi deadlock.

  • Terdapat siklus yang melibatkan T1, T2, T3, dan T4.

  • Siklus utamanya adalah T1 -> T2 -> T3 -> T2 (ini adalah siklus, T2 dan T3 saling tunggu) dan T4 -> T1 -> T2 -> ....

  • Self-correction: Mari kita lihat lebih dekat.

    • T1 → T2 (karena G)

    • T2 → T3 (karena H)

    • T3 → T2 (karena G)

    • T4 → T1 (karena F)

  • Siklus yang paling jelas adalah T2 -> T3 -> T2. Ini adalah deadlock antara T2 dan T3. (5 poin)

  • Ada juga siklus yang lebih besar: T1 -> T2 -> T3 -> T2 (redundan) dan T4 -> T1 -> T2 -> T3 -> T2 (redundan).

  • Fokus pada siklus T2 -> T3 -> T2 sudah cukup untuk membuktikan deadlock. (5 poin)

• c. (5 poin) Recovery (T3 Victim):

  • Jika T3 dipilih sebagai victim, T3 akan di-abort dan di-rollback.

  • Akibatnya, T3 melepaskan semua lock yang dipegangnya (termasuk lock-X pada H).

  • Ini memutus panah T2 -> T3 (karena T2 akan mendapatkan lock H).

  • Ini juga memutus panah T3 -> T2 (karena T3 tidak lagi menunggu G).

  • Siklus T2 -> T3 -> T2 terputus, dan deadlock teratasi. (5 poin)

Soal 3:

• a. (10 poin) Skema Wait-Die (Non-preemptive):

  • Aturan: Ti (minta) vs Tj (pegang). Jika TS(Ti) < TS(Tj) (Tua minta ke Muda), Ti MENUNGGU. Jika TS(Ti) > TS(Tj) (Muda minta ke Tua), Ti MATI (rollback).

  • Kejadian 3: T1 (TS=10) meminta B yang dipegang T3 (TS=30).

    • TS(T1) < TS(T3). Tua minta ke Muda.

    • Hasil: T1 MENUNGGU.

  • Kejadian 4: T3 (TS=30) meminta A yang dipegang T2 (TS=20).

    • TS(T3) > TS(T2). Muda minta ke Tua.

    • Hasil: T3 MATI (di-rollback).

• b. (10 poin) Skema Wound-Wait (Preemptive):

  • Aturan: Ti (minta) vs Tj (pegang). Jika TS(Ti) < TS(Tj) (Tua minta ke Muda), Ti MELUKAI (wound) Tj (Tj rollback). Jika TS(Ti) > TS(Tj) (Muda minta ke Tua), Ti MENUNGGU.

  • Kejadian 3: T1 (TS=10) meminta B yang dipegang T3 (TS=30).

    • TS(T1) < TS(T3). Tua minta ke Muda.

    • Hasil: T1 MELUKAI T3. T3 di-rollback dan melepaskan lock B. T1 mendapatkan lock B.

  • Kejadian 4: T3 (TS=30) meminta A yang dipegang T2 (TS=20).

    • TS(T3) > TS(T2). Muda minta ke Tua.

    • Hasil: T3 MENUNGGU. (Namun, jika Kejadian 3 terjadi lebih dulu, T3 sudah di-rollback dan tidak akan sampai ke Kejadian 4).

• c. (5 poin) Perbandingan:

  • Dalam skenario ini, Wait-Die menghasilkan 1 rollback (T3 mati) dan 1 wait (T1 menunggu).

  • Wound-Wait juga menghasilkan 1 rollback (T3 dilukai).

  • Secara umum, Wait-Die sering dianggap menghasilkan lebih banyak rollback karena transaksi “Muda” yang aktif meminta akan langsung “Mati”, sementara di Wound-Wait, transaksi “Muda” diizinkan menunggu yang “Tua”.

Bagian II

Soal 4:

• (25 poin) Rubrik Esai Sintesis:

  • Perbandingan Prevention (5 poin): Menjelaskan Prevention (misal: Total Order) dengan benar. Menyebutkan keunggulannya (jaminan tidak ada deadlock) dan kelemahannya (kaku, sangat mengurangi konkurensi, tidak praktis untuk skenario dinamis).

  • Perbandingan Avoidance (5 poin): Menjelaskan Avoidance (misal: Wait-Die/Wound-Wait) dengan benar. Menyebutkan keunggulannya (lebih dinamis dari prevention) dan kelemahannya (overhead tinggi karena setiap request dicek, starvation).

  • Perbandingan Detection (5 poin): Menjelaskan Detection (WFG) dengan benar. Menyebutkan keunggulannya (konkurensi tertinggi, optimis) dan kelemahannya (membiarkan deadlock terjadi, biaya rollback/victim selection).

  • Rekomendasi & Justifikasi (10 poin):

    • Rekomendasi yang baik: Mengusulkan kombinasi dari Strict 2PL (untuk Konsistensi Kritis / mencegah cascading rollback) DENGAN Deadlock Detection (untuk Ketersediaan Tinggi).

    • Justifikasi:

      • Strict 2PL adalah wajib untuk sistem banking untuk memastikan data tidak “kotor” dan commit bersifat atomik.

      • Detection dipilih di atas Prevention/Avoidance karena: (1) Deadlock dalam sistem yang dirancang baik (seperti banking yang transaksinya singkat) sebenarnya jarang terjadi. (2) Overhead dari Avoidance pada setiap lock request akan membunuh kinerja (Ketersediaan Tinggi), sementara Detection (dijalankan periodik) lebih murah. (3) Sistem “freeze” karena deadlock (masalah detection) lebih baik ditangani dengan rollback korban yang cepat daripada “freeze” karena overhead avoidance yang konstan.

Tips Pengerjaan untuk Peserta

Strategi Umum:

1. Baca semua soal terlebih dahulu - Alokasikan waktu Anda. Soal 1, 2, dan 3 adalah analisis skenario, sementara soal 4 adalah sintesis.

2. Pahami instruksi - Perhatikan kata kunci: “analisis”, “gambarkan WFG”, “apa yang terjadi (Wait-Die vs Wound-Wait)”, “bandingkan trade-off”.

3. Kelola waktu:

   • Bagian I (3 Soal): ~45 menit (~15 menit per soal)

   • Bagian II (1 Esai): ~15 menit

   • Review: (Waktu sisa)

Strategi Per Bagian:

• Bagian I:

  • Soal 1: Buat tabel atau garis waktu untuk melacak status lock (Growing/Shrinking) dan status commit (kapan lock-X dilepas).

  • Soal 2: Gunakan pendekatan sistematis. Buat daftar semua node (transaksi). Lalu, untuk setiap transaksi yang waiting, gambarkan panah DARI dia KE transaksi yang memegang lock. Cari siklus tertutup.

  • Soal 3: Tuliskan aturan Wait-Die dan Wound-Wait di kertas coretan Anda. Aplikasikan aturan (TS(Minta) vs TS(Pegang)) secara ketat untuk setiap kejadian.

• Bagian II (Esai):

  • Struktur esai Anda: (1) Intro singkat. (2) Paragraf Prevention (Pro/Con). (3) Paragraf Avoidance (Pro/Con). (4) Paragraf Detection (Pro/Con). (5) Paragraf Rekomendasi (Pilihan + Justifikasi Kuat).

Red Flags untuk Dihindari:

• ❌ Tertukar antara 2PL dan Strict 2PL. Ingat: Strict 2PL = Tahan lock-X sampai commit/abort.

• ❌ Tertukar antara Wait-Die dan Wound-Wait. Ingat: Wound-Wait = Tua “melukai” Muda. Wait-Die = Muda “mati” saat bertemu Tua.

• ❌ Menggambar WFG secara tidak akurat. Panah SELALU dari (yang Menunggu) → (yang Memegang).

• ❌ Memberikan rekomendasi di Soal 4 tanpa justifikasi yang mengaitkannya kembali ke kebutuhan klien (Konsistensi vs Ketersediaan).

Sumber Belajar yang Direkomendasikan

• Catatan “Pengantar Concurrency Control dan Jenis Kunci.md”

• Catatan “Two-Phase Locking.md”

• Catatan “Konsep dan Deadlock Prevention.md”

• Catatan “Deadlock Avoidance.md”

• Catatan “Deteksi dan Deadlock Recovery.md”