Deteksi dan Pemulihan dari Deadlock

Back to: IF2130 Sistem Operasi

Topic

Questions/Cues

• Prinsip deteksi (detection)?
• Deteksi dengan graf Wait-For (1 instance)?
• Deteksi untuk multi-instance?
• Kapan deteksi dijalankan?
• Dua metode pemulihan (recovery)?
• Opsi terminasi proses/thread?
• Isu dalam pemilihan korban?
• Opsi preemption sumber daya?
• Tiga masalah dalam preemption?

Reference Points

Apa ya

Prinsip Deadlock Detection

• Ini adalah pendekatan reaktif. Sistem tidak mencoba mencegah atau menghindari deadlock. Sebaliknya, sistem membiarkan deadlock terjadi.
• Sistem menyediakan dua komponen:

1. Sebuah algoritma untuk memeriksa apakah keadaan deadlock sedang terjadi.
2. Sebuah algoritma untuk memulihkan sistem dari deadlock tersebut.

Algoritma Deteksi (Single Instance per Resource Type)

• Menggunakan varian dari RAG yang disebut Wait-For Graph.
• Graf ini hanya berisi node untuk thread (proses) dan menghilangkan node sumber daya.
• Sebuah panah dari Ti​→Tj​ ada di graf ini jika thread Ti​ sedang menunggu thread Tj​ untuk melepaskan sumber daya yang dibutuhkan Ti​.
• Aturan: Deadlock ada jika dan hanya jika terdapat siklus dalam wait-for graph.
• Sistem perlu memelihara graf ini dan secara berkala menjalankan algoritma pencari siklus (kompleksitas O(n²), dengan n adalah jumlah thread).

Algoritma Deteksi (Multiple Instances per Resource Type)

• Wait-for graph tidak berlaku di sini. Algoritma yang digunakan mirip dengan Safety Algorithm pada Algoritma Banker, tetapi dengan beberapa perbedaan.
• Struktur Data: Available, Allocation, dan Request (matriks permintaan saat ini, bukan Need).
• Cara Kerja: Algoritma ini secara optimis mencoba mencari urutan penyelesaian thread. Ia memeriksa apakah ada thread yang permintaannya (Request) bisa dipenuhi oleh sumber daya yang ada (Available). Jika ya, thread itu diasumsikan selesai dan sumber dayanya (Allocation) ditambahkan ke Available. Proses ini diulang.
• Hasil: Jika setelah algoritma selesai ada thread yang tidak bisa “menyelesaikan” (ditandai Finish[i] == false), maka thread tersebut dipastikan mengalami deadlock.

Penggunaan Algoritma Deteksi

• Kapan dijalankan? Ini adalah sebuah trade-off.
  • Opsi 1: Setiap ada permintaan yang gagal. Keuntungan: langsung mengetahui thread mana yang “menyebabkan” deadlock. Kerugian: overhead komputasi yang sangat tinggi.
• Opsi 2: Secara periodik (misal, setiap jam) atau saat utilisasi CPU turun drastis (gejala deadlock). Keuntungan: overhead lebih rendah. Kerugian: saat terdeteksi, mungkin sudah banyak thread yang terlibat dalam siklus

Metode Pemulihan dari Deadlock

• Setelah deadlock terdeteksi, sistem harus memutus siklus tunggu. Ada dua cara utama:
  • Process/Thread Termination (Menghentikan Proses): Membatalkan satu atau lebih proses/thread yang terlibat.
• Resource Preemption (Mengambil Paksa Sumber Daya): Mengambil sumber daya dari satu atau lebih proses dan memberikannya ke proses lain.

Opsi Process Termination:

• Batalkan Semua Thread yang Deadlock: Cara paling brutal namun efektif untuk memutus siklus. Kerugiannya sangat besar karena semua hasil komputasi parsial dari thread-thread tersebut hilang.
• Batalkan Satu per Satu: Lebih ringan, tetapi butuh overhead tambahan karena algoritma deteksi harus dijalankan lagi setelah setiap pembatalan untuk memeriksa apakah siklus sudah putus.
• Isu Pemilihan Korban (Victim Selection): Memilih thread mana yang akan dibatalkan adalah keputusan kebijakan yang sulit. Faktor yang dipertimbangkan antara lain:
• Prioritas thread.
• Berapa lama thread sudah berjalan.
• Sumber daya apa dan berapa banyak yang telah digunakan.
• Apakah thread bersifat interaktif atau batch.

Opsi Resource Preemption:

• Sistem secara bertahap mengambil sumber daya dari thread korban dan memberikannya ke thread lain dalam siklus sampai siklus terputus.
• Tiga Masalah yang Harus Diatasi:

1. Selecting a Victim: Memilih sumber daya dan thread mana yang akan menjadi korban untuk meminimalkan “kerugian”.
2. Rollback: Thread yang sumber dayanya diambil paksa tidak dapat melanjutkan eksekusi begitu saja. Ia harus dikembalikan (rollback) ke suatu keadaan aman (safe state) sebelum sumber daya tersebut dialokasikan. Solusi paling umum adalah total rollback, yaitu membatalkan dan memulai ulang thread tersebut sepenuhnya.
3. Starvation: Perlu ada jaminan bahwa thread yang sama tidak selalu dipilih menjadi korban berulang kali. Solusinya adalah dengan memasukkan “jumlah rollback yang sudah dialami” sebagai salah satu faktor biaya dalam pemilihan korban.

Summary

Deteksi dan Pemulihan adalah strategi reaktif di mana sistem membiarkan deadlock terjadi, lalu secara periodik mendeteksinya dengan mencari siklus pada wait-for graph atau menggunakan algoritma deteksi. Setelah terdeteksi, sistem harus memutus siklus tersebut melalui dua cara utama: terminasi proses atau preemption sumber daya, di mana keduanya memerlukan keputusan sulit dalam memilih “korban” untuk meminimalkan dampak negatif dan risiko starvation.

Additional Information (Optional)

Aspek Teknis Lanjutan:

• Ekonomi Penanganan Deadlock: Pilihan antara mengabaikan, mencegah, menghindari, atau mendeteksi deadlock pada dasarnya adalah masalah ekonomi.
  • Mengabaikan: Paling murah jika deadlock sangat jarang terjadi (kasus di OS umum).
  • Pencegahan/Penghindaran: Memiliki overhead berkelanjutan (kinerja lebih lambat, utilisasi sumber daya rendah). Biayanya tinggi jika deadlock sebenarnya jarang.
  • Deteksi/Pemulihan: Overhead hanya muncul saat algoritma dijalankan dan saat pemulihan. Ini menjadi pilihan yang masuk akal untuk sistem di mana deadlock tidak dapat diabaikan (karena konsekuensi fatal) tetapi juga tidak cukup sering untuk membenarkan biaya pencegahan/penghindaran yang konstan. Ini adalah kasus tipikal untuk sistem database
  • Rollback Transaksi di Database: Alasan utama mengapa deteksi dan pemulihan sangat cocok untuk sistem database adalah konsep transaksi ACID (Atomicity, Consistency, Isolation, Durability). Sifat Atomicity menjamin bahwa sebuah transaksi adalah unit “semua atau tidak sama sekali”. Jika transaksi gagal atau dibatalkan (menjadi korban deadlock), sistem database secara inheren sudah memiliki mekanisme untuk melakukan rollback, yaitu mengembalikan semua perubahan yang dibuat oleh transaksi tersebut seolah-olah tidak pernah terjadi. Ini membuat proses pemulihan menjadi bersih dan aman bagi integritas data.

Tools & Software untuk Analisis Deadlock:

• Java jstack: Saat JVM mendeteksi deadlock, output dari jstack akan secara eksplisit menyatakan: Found one Java-level deadlock, lalu menampilkan detail thread yang terlibat, kunci mana yang dipegang, dan kunci mana yang ditunggu, sehingga sangat mudah untuk dianalisis.
• MySQL SHOW ENGINE INNODB STATUS: Perintah ini menghasilkan laporan teks yang panjang. Di dalamnya, jika ada deadlock yang baru saja terjadi, akan ada bagian LATEST DETECTED DEADLOCK yang secara detail memaparkan transaksi-transaksi yang terlibat, pernyataan SQL yang mereka jalankan, dan transaksi mana yang dipilih sebagai korban dan di-rollback.

Eksplorasi Mandiri:

• Simulasi Deadlock di Database (Praktis):

1. Buka dua koneksi ke server database (misalnya, dua jendela terminal yang terhubung ke MySQL atau PostgreSQL).
2. Jendela 1: START TRANSACTION; UPDATE produk SET stok = stok - 1 WHERE id = 101;
3. Jendela 2: START TRANSACTION; UPDATE produk SET stok = stok - 1 WHERE id = 102;
4. Jendela 1: UPDATE produk SET stok = stok - 1 WHERE id = 102; (Akan menunggu karena baris ini dikunci oleh Jendela 2).
5. Jendela 2: UPDATE produk SET stok = stok - 1 WHERE id = 101; (Ini akan menciptakan deadlock).
6. Amati hasilnya. Salah satu jendela akan segera melaporkan kesalahan (deadlock found… try restarting transaction), karena engine database mendeteksi siklus dan langsung memilih satu transaksi sebagai korban untuk di-rollback. Analisis log atau status engine setelahnya untuk melihat laporan deadlock tersebut.