Deadlock

Deadlock adalah jalan buntu yang dapat terjadi ketika dua atau lebih transaksi masing-masing menunggu lock yang sedang dipegang oleh transaksi lainnya untuk dilepas. Hanya ada satu cara untuk menghancurkan deadlock, yaitu abort satu atau lebih transaksi. Ada tiga cara untuk menangani deadlock, yaitu timeout, deadlock prevention dan deadlock detection and recovery.

Timeout

Pendekatan sederhana pada pencegahan deadlock adalah berdasarkan lock timeout. Dengan pendekatan ini, sebuah transaksi yang meminta sebuah lock akan menunggu hanya sampai periode waktu tertentu yang didefinisikan sistem.

Deadlock Prevention

Pendekatan lain untuk mencegah deadlock adalah untuk memesan transaksi menggunakan timestamp transaksi. Dua algoritma telah ditemukan oleh Rosenkrantz. Algoritma pertama, Wait-Die, mengijinkan hanya transaksi yang lebih tua untuk menunggu yang lebih muda, jika tidak transaksi dibatalkan (die/mati) dan restart dengan timestamp yang sama, sehingga lama kelamaan transaksi tersebut akan menjadi transaksi aktif tertua dan tidak akan mati. Algoritma kedua, Wound-Wait, menggunakan pendekatan simetrikal. Hanya transaksi yang lebih muda yang dapat menunggu untuk yang lebih tua. Jika transaksi yang lebih tua meminta lock yang dipegang oleh transaksi yang lebih muda, transaksi yang lebih muda digagalkan.

 

Deadlock Detection

Deadlock detection biasanya ditangani oleh konstruksi wait-for graph (WFG) yang menunjukkan ketergantungan transaksi, yaitu transaksi Ti tergantung pada Tj jika transaksi Tj memegang lock pada sebuah item data yang ditunggu oleh Ti.

WFG adalah sebuah directed graph G = (N, E ) yang terdiri dari satu set node N dan satu set directed edge E, yang dikonstruksi sebagai berikut

  • Buat sebuah node untuk setiap transaksi.
  • Buat sebuah directed edge Ti → Tj , jika transaksi Ti menunggu untuk melakukan lock sebuah item yang sedang di-lock oleh Tj.

Deadlock terjadi jika dan hanya jika WFG mengandung sebuah cycle. Gambar di atas menunjukkan WFG yang menunjukkan deadlock antara dua transaksi.

Referensi :

Connolly T dan Begg C. (2005). Database Systems: A Practical Approach in Design, Implementation, and Management. Fourth Edition. Addison Wesley. Longman Inc., USA.