Deadlock Detection - Single Instances & Multiple Instances

jika suatu sistem tidak menggunakan algoritma deadlock prevention atau deadlock avoidance, maka situasi deadlock dapat terjadi. Pada pembahasan ini, sistem akan dapat memberikan.

• Algoritma yang memeriksa satus sistem untuk menentukan apakah telah terjadi deadlock.
• Algoritma untuk memulihkan (recover) dari kondisi deadlock.

Kondisi deadlock dapat terjadi pada saat ketika proses meminta sumber daya tetapi tidak segera diberikan/dilayani. Sumber daya yang diperlukan oleh proses bisa hanya single instance atau multiple instances, oleh karna itu deadlock detection dapat diimplementasikan pada kedua hal ini.

Single Instance Dari Setiap Jenis Resource

Jika semua sumber daya hanya memiliki single instance, maka untuk mendeteksi deadlock dapat mengunakan variant dari resource-allocation graph, yang disebut wait-for graph. Untuk mendapatkan graf ini diperoleh dari resource-allocation graph, yaitu dengan cara menghapus resource nodes dan mengatur edge langsung ke setiap proses yang dituju atau tanpa resource nodes.

Gambar (a) Resource-Allocation Graph dan (b) Wait-For Graph.

Pada wait-for graph edge dari Pi ke Pj menyiaratkan bahwa proses Pi sedang menunggu proses Pj untuk melepaskan resource yang dibutuhkan Pi. Sebuah edge Pi ≥ Pj ada dalam wait-for graph seperti pada bagian gambar (b) diatas, jika dan hanya jika terdapat dua edge Pi ≥ Rq dan Rq ≥ Pj untuk beberapa resource Rq seperti pada bagian gambar (a) diatas. Contoh P2 ≥ R4 dan R4 ≥ P3.

Pada gambar diatas terlihat pembentukan wait-for graph dari resource-allocation graph, hanya jika terdapat single instance resource. Sperti yang telah dijelaskan sebelumnya deadlock dapat terjadi didalam sistem jika dan haya jika wait-for graph terdapat siklus/cicle. Untuk mendeteksi deadlock pada algoritma ini, sistem butuh mempertahankan wait-for graph secara periodik mencari cycle didalam graf itu sendiri. Algoritma ini juga memerlukan urutan operasi n², dimana n adalah jumlah simpul/vertice pada graf.

Multiple Instance Dari Setiap Jenis Resource

Skema wait-for graph tidak dapat diterapkan pada sistem multple instances setiap jenis sumber dayanya untuk mendeteksi deadlock. Sehingga diperlukan algoritma ini untuk menangani hal tersebut menggunakan beberapa struktur data dengan variasi waktu mirip dengan penggunaan alogritma Banker. Berikut struktur data yang dipergunakan.

• Struktur data Available. Vektor dengan panjang m – menunjukkan jumlah resource instance yang tersedia untuk setiap jenisnya.
• Sturktur data Allocation. Matriks n x m menentutukan jumlah resource dari setiap jenisnya yang sedang dialokasikan untuk setiap proses.
• Struktur data Request. Matriks n x m menunjukkan/mengindentifikasikan permintaan resource saat ini dari setiap proses. Jika Request[i][j] = k, maka proses Pi meminta k lebih banyak resource instance dari resource jenis Rj.

Sama halnya seperti algoritma Bankir, pada algoritma ini, setiap allocation/baris sebagai matris Allocation, dan Request sebagai vektor, tetapi dalam hal ini dirujuk sebagai Allocation_i dan Request_i. Algoritma deadlock-detection yang dijelaskan disini hanyalah menginvestigasi setiap kemungkinan urutan pengalokasian sumber daya yang tersisa agar dipenuhi/diselesaikan untuk proses. Berikut uraian algoritmanya, dan jika ingin mempertajam analisa dapat dibandingkan dengan algoritma Banker pada pembasahan sebelumnya.

• 1. Misal Work dan Finish masing-masing adalah vektor dengan panjang m dan n. Nilai alwal atau inisialisasi Work = Available. Untuk i = 0, 1, …, n-1, jika Allocation_i ≠ 0, maka Finish[i] = false Finish[i] = false, jika tidak Finish[i] = true.
• 2. Cari index i, sehingga keduanya (a dan b) menjadi.
  • a. Finish[i] == False
  • b. Request_i ≤ Work
  • Jika index i tidak ada yang menjadi poin (a) dan poin (b), lanjut ke langkah 4, dan jika ada lanjut ke langkah 3.
• 3. Defenisikan variabel berikut menjadi.
  • Work = Work + Allocation_i
  • Finish[i] = true
  • Kemudian kembali ke langka 2.
• 4. Jika Finish[i] == false untuk beberapa i, dimana 0 ≤ i < n, maka sistem dalam keadaan deadlock, serta jika Finish[i] == false, maka proses Pi juga akan deadlock.

Algorima ini memerlukan urutan operasi m x n² untuk mendeteksi apakah sistem dalam keadaan deadlock atau tidak. Mungkin ada pertanyaan mengapa mengklaim kembali resource dari proses Pi (langka 3) setelah menentukan Request_i ≤ Work (langka 2b)? hal ini sebenarnya karena telah mengetahui bahwa Pi saat ini tidak membutuhkan resource lainnya untuk menyelesaikan pekerjaannya, sehingga meskipun deadlock dapat terjadi nantinya, maka deadlock tersebut dapat di deteksi pada saat ketika algoritma deadlock-detection dipanggil berikutnya.

Untuk mengilustrasikan penggunaan algoritma ini, misal terdapat 5 proses yaitu P0, P1, P2, P3, P4; dan terdapat 3 tipe resource yaitu A, B, dan C. Setiap tipe resource memiliki resource instance, untuk resource tipe A memiliki 7 resource instance; untuk resource tipe B memiliki 2 resource instance, dan untuk resource tipe C memiliki 6 resource instance. Selanjutnya permisalkan pada T0 memiliki pengalokasian sumber daya sebagai berikut.

Gambar Algoritma Multiple Instances Deadlock Detection (No Deadlock).

Pada tabel ilustrasi penggunaan algoritma diatas, yang mereprenentasikan kondisi sistem, dapat diklaim bahwa sistem tidak dalam keadaan deadlock saat algoritma ini dijalankan, dengan sequence adalah <P0, P2, P3, P1, P4> menghasilkan Finish[i] == true untuk semua i. Misal sekarang proses P2 meminta 1 instance resource tambahan pada jenis C, maka matriks Request diubah sebagai berikut.

Gambar Algoritma Multiple Instances Deadlock Detection (Deadlock Occor).

Maka dari permintaan P0 tersebut sistem akan menjadi deadlock, meskipun dapat mengklaim kembali sumber daya yang dimiliki oleh proses P0, hal ini terjadi karena sumber daya yang tersedia tidak cukup untuk memenuhi permintaan proses lainnya, sehingga deadlock terjadi pada proses P1, P2, P3, dan P4.

Referensi

1. Operating Systems: Internals and Design Principles (8th Edition), William Stallings, 2014.
2. Operating System Concepts (9th Edition in Chinese) by Abraham Silberschatz et al.
3. The Linux Programming Interface: A Linux and UNIX System Programming Handbook, Michael Kerrisk.