Protokol Deadlock Avoidance

Secara garis besar mekanisme deadlock-prevention yang telah dibahas sebelumnya yaitu mencegah terjadinya deadlock (mutualexclusion, hold dan wait, no preemption) atau secara langsung mencegah terjadinya circular-wait. Mekanisme tersebut dilakukan dengan cara membatasi bagaimana permintaan dapat dibuat. Batasan tersebut memastikan bahwa setidaknya satu dari kondisi yang diperlukan untuk terjadinya deadlock tidak terjadi. Namun kemungkinan besar dampak dari penggunaan metode ini sama halnya dengan metode sebelumnya yaitu utilisasi sumber daya yang renda, serta dapat mereduksi throughput (kecepatan komunikasi) sistem.

Sebagai alternatif yang dapat digunakan untuk menghindari/avoiding deadlock adalah dengan meminta informasi tambahan tentang bagaimana berbagai sumber daya harus diminta. Misal, dalam sistem dengan satu flask-disk dan satu printer, sistem mungkin perlu mengehtaui bahwa proses P akan meminta flask-disk terlebih dahulu kemudian printer sebelum melepas kedua resource tersebut, sedangkan proses Q akan meminta printer terlebih dahulu dan kemudian flask-disk. Dengan pengetahuan tentang urutan lengkap permintaan dan pelepasan sumber daya dari setiap proses, sistem dapat memutuskan untuk setiap permintaan apakah proses tersebut harus menunggu atau tidak untuk menghindari kemungkinan terjadinya deadlock dimasa mendatang. Untuk memutuskan apakah permintaan saat ini dapat dipenuhi atau harus ditunda, maka sistem harus mempertimbangkan sumber daya yang tersedia saat ini, kemudian jumlah sumber daya saat ini yang dialokasikan untuk setiap proses, serta permintaan dan melepas sumber daya selanjutnya untuk setiap proses.

Berbagai algoritma yang menggunakan pendekatan ini memiliki perbedaan pada jumlah dan jenis informasi yang dibutuhkan. Model yang paling sederhana dan paling berguna mengharuskan setiap proses mendeklarasikan jumlah maksimum sumber daya dari setiap tipe/jenis yang mungkin diperlukan. Algoritma deadlock-avoidence secara dinamis memeriksa status alokasi sumber daya untuk memastikan bahwa kondisi circular-wait tidak akan pernah terjadi. Status pengalokasian sumber daya ditentukan/didefenisikan oleh jumlah sumber daya yang tersedia, kemudian sumber daya yang telah dialokasikan, serta dengan jumlah maksimal sumber daya yang dibutuhkan oleh setiap proses. Dalam hal ini akan menggunakan dua algoritma deadlock-avoidence, yaitu algoritma safe-state dan algoritma resource-allocation-graph pada sistem single-instace untuk setiap jenis resource, serta alogritma Banker untuk sistem multiple-instances untuk setiap jenis resourse.

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.