Perbandingan algoritma obermarck dan chandy-misra dalam penanggulangan deadlock terdistribusi

Abstract

Deadlock adalah keadaan dimana sejumlah permintaan yang tidak bisa dijalankan oleh scheduler karena permintaan-permintaan tersebut saling tunggu menunggu. Deadlock adalah masalah utama dalam penggunaan data secara bersama-sama. Pada sistem basis data terdistribusi sering terjadi deadlock antar transaksi, terutama pada sistem yang menggunakan concurrency control berbasis locking. Ada berbagai cara untuk menangani deadlock, yaitu dengan pencegahan, penghindaran, dan pendeteksian. Masing-masing memiliki kelebihan dan kekurangan. Pencegahan dan penghindaran deadlock bersifat konservatif dan pesimistik, sehingga lebih banyak peneliti yang tertarik untuk menemukan algoritma pendeteksian deadlock. Pendeteksian deadlock ini dapat dilakukan secara terdistribusi. Algoritma Obermarck dan Chandy-Misra termasuk ke dalam algoritma pendeteksi deadlock terdistribusi yang bermodel AND. Informasi tentang transaksi yang sedang menunggu digambarkan dalam WFG(Wait For Graf). Performa kedua algoritma ini dibandingkan dengan menggunakan simulasi. Kriteria yang dibandingkan adalah lamanya deadlock (Deadlock Persistent Time/DPT) dalam sistem dan lamanya waktu komunikasi untuk memelihara WFG (WFG's Maintenance Time). Deadlock bertahan dalam sistem lebih lama pada algoritma Obermarck. Dengan adanya deadlock ini, performa sistem akan berkurang. Algoritma Obermarck lebih banyak melakukan komunikasi untuk memelihara WFG. Oleh karena itu, dilihat dari lamanya deadlock dalam sistem dan banyaknya komunikasi untuk memelihara WFG, dapat disimpulkan algoritma Chandy-Misra lebih baik daripada algoritma Obermarck.