Deadlock Avoidance: Algoritma Resource-Allocation-Graph

Seperti pada pembahasan sebelumnya mengenai resource allocation graph (RAG) terdapat request dan assigment edge untuk mendeskripsikan terjadinya deadlock secara graf. Pada pembahasan ini akan memperkenalkan notasi baru dari jenis edge (arah/petunjuk) yaitu disebut sebagai claim edge, contoh penggunaan notasinya P0 ⇢ R1, yang menunjukkan bahwa proses Pi dapat meminta resource Rj suatu saat nanti (dalam algoritma ini hanya berlaku untuk satu sumber daya saja). Pada dasarnya graf claim edge menyerupai request edge dalam pentunjuk arahnya, tetapi diwaliki dalam bentuk grafis dengan garis terputus-putus. Ketika proses Pi meminta resource Rj, claim edge Pi ⇢ Rj diubah menjadi request edge Pi → Rj. Demikian halnya ketika resource Rj tersebut dilepas/release oleh proses Pi yaitu assigment edge Ri → Pj diubah menjadi claim edge Pi ⇢ Rj.

Sebagai catatan sumber daya harus di klaim secara apriori dalam sistem. Artinya, sebelum proses Pi mulai dieksekusi, semua claim-edge harus sudah terlihat pada resource-allocation graph. Untuk melonggarkan kondisi ini dilakukan dengan cara memperbolehkan claim edge Pi ⇢ Rj untuk ditambahkan ke graf hanya jika semua edge yang terkait dengan proses Pi adalah claim edge.

Gambar RAG Deadlock Avoidance dan Unsafe State.

Permisalkan proses Pi meminta resource Rj. Permintaan tersebut dapat dikabulkan hanya jika mengubah request edge Pi ≥ Rj menjadi assigmen edge Rj ≥ Pi tidak menghasilkan pembentukan siklus/cycle dalam resource-allocation graph seperti pada pembahasan sebelumnya mengenai RAG ini. Untuk memeriksa keamanan/safety siklus pada graf ini dapat menggunakan algoritma cycle-detection yang memerlukan urutan operasi n², dimana n adalah jumlah proses pada sistem, dan akan dibahan pada pembahasan berikutnya pada deadlock detection.

Pada gambar (a) diatas tidak terdapat cycle karena request edge menggunakan claim edge yang artinya meskipun kedua proses tersebut membutuhkan sumber daya yang sama, namun tidak harus segera dipenuhi, sehingga pengalokasian sumber daya pada sistem ini dalam keadaan aman (safe state). Sebaliknya jika ditemukan cycle / pada gambar (b), maka akan membuat sistem ini dalam keadaan tidak aman (unsafe state), maka Pi harus menunggu permintaannya dipenuhi.

Ilustrasi algoritma ini pada gambar resource allocation graph yaitu pada bagian (a), misal proses P2 meminta sumber daya R2, meskipun sumber daya R2 saat ini tidak sedang digunakan oleh proses manapun (release), alokasi sumber daya R2 tidak dapat dilakukan, karena tindakan ini akan membuat siklus/cycle pada graf, yaitu pada bagian gambar (b) diatas menjadi tidak aman (unsafe state). Perlu diingat kembali pada pembahasan algoritma safe state, kondisi unsafe state adalah adanya cycle dan bukan berarti kondisi deadlock, tetapi kondisi deadlock adalalah unsafe state. Maka dari gambar pada bagian (b) diatas, deadlock terjadi jika P1 request edge R2, dan P2 request edge R1.

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.