DBMS Terdistribusi - Penanganan Kebuntuan

Bab ini mengulas mekanisme penanganan kebuntuan dalam sistem database. Kami akan mempelajari mekanisme penanganan kebuntuan di sistem database terpusat dan terdistribusi.

Apa itu Deadlocks?

Deadlock adalah keadaan sistem database yang memiliki dua atau lebih transaksi, ketika setiap transaksi menunggu item data yang dikunci oleh beberapa transaksi lainnya. Kebuntuan dapat diindikasikan dengan sebuah siklus dalam grafik tunggu. Ini adalah grafik berarah di mana simpul menunjukkan transaksi dan tepi menunjukkan menunggu item data.

Misalnya pada grafik tunggu berikut ini, transaksi T1 sedang menunggu data item X yang dikunci oleh T3. T3 menunggu Y yang dikunci oleh T2 dan T2 menunggu Z yang dikunci oleh T1. Karenanya, siklus tunggu terbentuk, dan tidak ada transaksi yang dapat dilanjutkan.

Penanganan Kebuntuan dalam Sistem Terpusat

Ada tiga pendekatan klasik untuk penanganan kebuntuan, yaitu -

Pencegahan kebuntuan.
Penghindaran kebuntuan.
Deteksi dan penghapusan deadlock.

Ketiga pendekatan tersebut dapat digabungkan dalam sistem database terpusat dan terdistribusi.

Pencegahan Kebuntuan

Pendekatan pencegahan kebuntuan tidak mengizinkan transaksi apa pun untuk memperoleh kunci yang akan menyebabkan kebuntuan. Ketentuannya adalah ketika lebih dari satu transaksi meminta penguncian item data yang sama, hanya satu dari mereka yang diberikan kunci.

Salah satu metode pencegahan kebuntuan yang paling populer adalah pra-akuisisi semua kunci. Dalam metode ini, transaksi memperoleh semua kunci sebelum mulai mengeksekusi dan mempertahankan kunci selama seluruh durasi transaksi. Jika transaksi lain memerlukan salah satu kunci yang sudah diperoleh, itu harus menunggu sampai semua kunci yang dibutuhkannya tersedia. Dengan menggunakan pendekatan ini, sistem dicegah dari kebuntuan karena tidak ada transaksi menunggu yang memiliki kunci.

Penghindaran Kebuntuan

Pendekatan penghindaran kebuntuan menangani kebuntuan sebelum terjadi. Ini menganalisis transaksi dan kunci untuk menentukan apakah menunggu mengarah ke kebuntuan atau tidak.

Metodenya dapat secara singkat dinyatakan sebagai berikut. Transaksi mulai dijalankan dan meminta item data yang perlu dikunci. Manajer kunci memeriksa apakah kunci tersedia. Jika tersedia, manajer kunci mengalokasikan item data dan transaksi memperoleh kunci. Namun, jika item dikunci oleh beberapa transaksi lain dalam mode yang tidak kompatibel, manajer kunci menjalankan algoritma untuk menguji apakah menjaga transaksi dalam status menunggu akan menyebabkan kebuntuan atau tidak. Karenanya, algoritme memutuskan apakah transaksi dapat menunggu atau salah satu transaksi harus dibatalkan.

Ada dua algoritma untuk tujuan ini, yaitu wait-die dan wound-wait. Mari kita asumsikan bahwa ada dua transaksi, T1 dan T2, di mana T1 mencoba mengunci item data yang sudah dikunci oleh T2. Algoritmanya adalah sebagai berikut -

Wait-Die- Jika T1 lebih tua dari T2, T1 diperbolehkan menunggu. Sebaliknya, jika T1 lebih muda dari T2, T1 dibatalkan dan kemudian dimulai ulang.
Wound-Wait- Jika T1 lebih tua dari T2, T2 dibatalkan dan kemudian dimulai ulang. Sebaliknya, jika T1 lebih muda dari T2, T1 diperbolehkan menunggu.

Deteksi dan Penghapusan Kebuntuan

Deteksi kebuntuan dan pendekatan penghapusan menjalankan algoritma deteksi kebuntuan secara berkala dan menghilangkan kebuntuan jika ada. Itu tidak memeriksa kebuntuan ketika transaksi menempatkan permintaan kunci. Ketika sebuah transaksi meminta kunci, manajer kunci memeriksa apakah itu tersedia. Jika tersedia, transaksi diperbolehkan untuk mengunci item data; jika tidak, transaksi dibiarkan menunggu.

Karena tidak ada tindakan pencegahan saat memberikan permintaan kunci, beberapa transaksi mungkin menemui jalan buntu. Untuk mendeteksi kebuntuan, manajer kunci secara berkala memeriksa apakah wait-forgraph memiliki siklus. Jika sistem mengalami kebuntuan, pengelola kunci memilih transaksi korban dari setiap siklus. Korban diaborsi dan digulingkan; dan kemudian memulai kembali nanti. Beberapa metode yang digunakan untuk pemilihan korban adalah -

Pilih transaksi termuda.
Pilih transaksi dengan item data paling sedikit.
Pilih transaksi yang telah melakukan pembaruan paling sedikit.
Pilih transaksi yang memiliki overhead restart paling sedikit.
Pilih transaksi yang umum untuk dua atau lebih siklus.

Pendekatan ini terutama cocok untuk sistem yang transaksinya rendah dan di mana respons cepat terhadap permintaan kunci diperlukan.

Penanganan Kebuntuan dalam Sistem Terdistribusi

Pemrosesan transaksi dalam sistem basis data terdistribusi juga didistribusikan, yaitu transaksi yang sama dapat diproses di lebih dari satu situs. Dua masalah penanganan kebuntuan utama dalam sistem database terdistribusi yang tidak ada dalam sistem terpusat adalahtransaction location dan transaction control. Setelah masalah ini ditangani, kebuntuan ditangani melalui pencegahan kebuntuan, penghindaran kebuntuan atau deteksi dan penghapusan kebuntuan.

Lokasi Transaksi

Transaksi dalam sistem database terdistribusi diproses di beberapa situs dan menggunakan item data di beberapa situs. Jumlah pemrosesan data tidak merata di antara situs-situs ini. Jangka waktu pemrosesan juga bervariasi. Dengan demikian, transaksi yang sama mungkin aktif di beberapa situs dan tidak aktif di situs lain. Ketika dua transaksi yang bentrok berada di sebuah situs, mungkin terjadi salah satunya dalam keadaan tidak aktif. Kondisi ini tidak muncul dalam sistem yang terpusat. Kekhawatiran ini disebut masalah lokasi transaksi.

Kekhawatiran ini dapat diatasi dengan model Rantai Daisy. Dalam model ini, transaksi membawa detail tertentu ketika berpindah dari satu situs ke situs lain. Beberapa rincian tersebut adalah daftar tabel yang diperlukan, daftar situs yang diperlukan, daftar tabel dan situs yang dikunjungi, daftar tabel dan situs yang belum dikunjungi dan daftar kunci yang diperoleh beserta tipenya. Setelah transaksi diakhiri dengan melakukan atau membatalkan, informasi tersebut harus dikirim ke semua situs terkait.

Kontrol Transaksi

Kontrol transaksi berkaitan dengan penunjukan dan pengendalian situs yang diperlukan untuk memproses transaksi dalam sistem database terdistribusi. Ada banyak pilihan terkait pilihan tempat memproses transaksi dan cara menentukan pusat kendali, seperti -

Satu server dapat dipilih sebagai pusat kendali.
Pusat kendali dapat berpindah dari satu server ke server lainnya.
Tanggung jawab pengendalian dapat dibagi oleh sejumlah server.

Pencegahan Kebuntuan Terdistribusi

Sama seperti pencegahan kebuntuan terpusat, dalam pendekatan pencegahan kebuntuan terdistribusi, transaksi harus memperoleh semua kunci sebelum mulai dieksekusi. Ini mencegah kebuntuan.

Situs tempat transaksi masuk ditetapkan sebagai situs pengendali. Situs pengontrol mengirimkan pesan ke situs tempat item data berada untuk mengunci item. Kemudian menunggu konfirmasi. Ketika semua situs telah mengkonfirmasi bahwa mereka telah mengunci item data, transaksi dimulai. Jika ada situs atau tautan komunikasi yang gagal, transaksi harus menunggu hingga diperbaiki.

Meskipun implementasinya sederhana, pendekatan ini memiliki beberapa kekurangan -

Kunci pra-akuisisi membutuhkan waktu lama untuk keterlambatan komunikasi. Ini menambah waktu yang dibutuhkan untuk bertransaksi.
Jika situs atau tautan gagal, transaksi harus menunggu lama agar situs pulih. Sementara itu, di situs yang sedang berjalan, item dikunci. Ini dapat mencegah transaksi lain dijalankan.
Jika situs pengendali gagal, ia tidak dapat berkomunikasi dengan situs lain. Situs-situs ini terus menyimpan item data yang terkunci dalam keadaan terkunci, sehingga mengakibatkan pemblokiran.

Distribusikan Penghindaran Kebuntuan

Seperti pada sistem terpusat, penghindaran kebuntuan terdistribusi menangani kebuntuan sebelum terjadi. Selain itu, dalam sistem terdistribusi, masalah lokasi transaksi dan kontrol transaksi perlu ditangani. Karena sifat transaksi yang didistribusikan, konflik berikut mungkin terjadi -

Bentrok antara dua transaksi di situs yang sama.
Bentrok antara dua transaksi di situs berbeda.

Jika terjadi konflik, salah satu transaksi dapat dibatalkan atau dibiarkan menunggu sesuai algoritme tunggu-mati yang didistribusikan atau menunggu giliran yang didistribusikan.

Mari kita asumsikan bahwa ada dua transaksi, T1 dan T2. T1 tiba di Situs P dan mencoba mengunci item data yang sudah dikunci oleh T2 di situs itu. Oleh karena itu, ada konflik di Situs P. Algoritmanya adalah sebagai berikut -

Distributed Wound-Die
- Jika T1 lebih tua dari T2, T1 diperbolehkan menunggu. T1 dapat melanjutkan eksekusi setelah Situs P menerima pesan bahwa T2 telah berhasil dilakukan atau dibatalkan di semua situs.
- Jika T1 lebih muda dari T2, T1 dibatalkan. Kontrol konkurensi di Situs P mengirimkan pesan ke semua situs tempat T1 telah dikunjungi untuk membatalkan T1. Situs pengontrol memberi tahu pengguna ketika T1 telah berhasil dibatalkan di semua situs.
Distributed Wait-Wait
- Jika T1 lebih tua dari T2, T2 perlu dibatalkan. Jika T2 aktif di Situs P, Situs P membatalkan dan memutar kembali T2 dan kemudian menyiarkan pesan ini ke situs relevan lainnya. Jika T2 telah meninggalkan Situs P tetapi aktif di Situs Q, Situs P menyiarkan bahwa T2 telah dibatalkan; Situs L kemudian membatalkan dan memutar kembali T2 dan mengirimkan pesan ini ke semua situs.
- Jika T1 lebih muda dari T1, T1 diperbolehkan menunggu. T1 dapat melanjutkan eksekusi setelah Situs P menerima pesan bahwa T2 telah menyelesaikan pemrosesan.

Deteksi Kebuntuan Terdistribusi

Sama seperti pendekatan deteksi kebuntuan terpusat, kebuntuan dibiarkan terjadi dan dihapus jika terdeteksi. Sistem tidak melakukan pemeriksaan apa pun saat transaksi menempatkan permintaan kunci. Untuk implementasi, grafik tunggu global dibuat. Adanya siklus dalam grafik tunggu global menunjukkan kebuntuan. Namun, sulit untuk menemukan kebuntuan karena transaksi menunggu sumber daya di seluruh jaringan.

Alternatifnya, algoritma pendeteksian kebuntuan dapat menggunakan pengatur waktu. Setiap transaksi dikaitkan dengan pengatur waktu yang diatur ke periode waktu di mana transaksi diharapkan selesai. Jika transaksi tidak selesai dalam jangka waktu ini, timer akan mati, menunjukkan kemungkinan kebuntuan.

Alat lain yang digunakan untuk penanganan kebuntuan adalah detektor kebuntuan. Dalam sistem terpusat, ada satu detektor kebuntuan. Dalam sistem terdistribusi, mungkin ada lebih dari satu detektor kebuntuan. Detektor kebuntuan dapat menemukan kebuntuan untuk situs yang berada di bawah kendalinya. Ada tiga alternatif pendeteksian kebuntuan pada sistem terdistribusi, yaitu.

Centralized Deadlock Detector - Satu situs ditetapkan sebagai detektor kebuntuan pusat.
Hierarchical Deadlock Detector - Sejumlah detektor kebuntuan diatur dalam hierarki.
Distributed Deadlock Detector - Semua situs berpartisipasi dalam mendeteksi kebuntuan dan menghapusnya.