Deadlock Avoidance: Algoritma Safe State

Algoritma Safe State

Dalam algoritma ini, suatu kedaan/state dikatakan aman/safe jika sistem dapat mengalokasikan berbagai sumber daya ke setiap proses (hingga mencapai kapasitas maksimalnya) dalam beberapa urutan dan masih menghindari terjadinya deadlock, atau dengan kata lain sistem berada pada safe sate hanya jika terdapat urutan yang aman (safe sequence).

Misalkan urutan proses <P1, P2, …, Pn> adalah safe sequence untuk status alokasi saat ini jika, ketika setiap Pi pada saat meminta sumber daya, dapat dipenuhi oleh sumber daya yang tersedia saat ini ditambah sumber daya yang ditahan/digunakan oleh semua proses Pj, dengan j < i, yaitu jika sumber daya yang dibutuhkan Pi tidak segera tersedia, maka Pi dapat menunggu hingga semua proses Pj selesai menggunakan sumber dayanya dan melepaskannya. Selanjunya setelah proses Pj selesai, maka proses Pi dapat menggunakan seluruh sumber daya yang dibutuhkannya untuk menyelesaikan tugasnya, kemudian melepas/mengalokasikan serta menghentikan (terminate) sumber daya yang digunakannya, hanya jika telah menyelesaikan tugasnya. Saat Pi dihentikan (terminate), P_i + 1 dapat mengambil sumber daya yang dibutuhkan, dan begitu seterusnya. Sehingga jika tidak terdapat urutan (sequence) seperti ini, maka status sistem dapat dikatakan tidak aman (unsafe).

Kondisi proses safe state bukan kondisi deadlock state, sebaliknya deadlock state adalah proses unsafe state. Namun tidak semua proses unsafe state adalah deadlock (lihat Gambar Safe, Unsafe, dan Deadlock state spaces dibawah). Kondisi proses unsafe state dapat menyebabkan terjadinya deadlock, yaitu ketika sistem operasi tidak dapat mencegah proses meminta sumber daya yang dapat menyebabkan deadlock. Tetapi selama kondisi proses adalah safe state, sistem operasi dapat menghindari unsafe state atau deadlock.

State sistem adalah kondisi sumber daya yang tersedia saat ini untuk dialokasikan ke proses. Kemudian safe state adalah kondisi setidaknya ada satu urutan pengalokasian sumber daya ke proses yang tidak menimbulkan deadlock, yaitu semua proses dapat berjalan hingga selesai. Tentu saja unsfe state adalah kondisi yang tidak aman sehingga memungkinkan terjadinya kondisi deadlock.

Untuk mengilustrasikannya, misal pada sistem terdapat 12 harddisk sebagai sumber daya dan 3 proses yaitu: P0, P1, dan P2. Proses P0 membutuhkan 10 harddisk, proses P1 membutuhkan 4 harddisk, dan proses P3 membutuhkan hingga 9 harddisk. Misal pada waktu t0, proses P0 sedang menahan 5 harddisk, proses P1 sedang menahan 2 harddisk, dan proses P2 sedang menahan 2 harddisk, sehingga jika dijumlahkan terdapat 9 harddisk yang sedang digunakan dan menyisakan 3 harddisk yang tidak sedang digunakan.

Gambar Safe, Unsafe, Deadlock State Spaces.

Gambar Observasi Safe State Sistem.

Pada saat t0, sistem dalam safe state, dengan safe sequence <P1, P0, P2> memenuhi kondisi yang aman (safe). Proses P1 dapat segera dialokasikan semua harddisk yang dibutuhkannya dan kemudian mengembalikannya jika telah selesai menggunakannya, sehingga sistem akan memiliki 5 harddik yang tersedia/tidak sedang digunakan. Kemudian proses P0 bisa mendapatkan semua harddik yang dibutuhkannya dan kemudian mengembalikannya jika telah selesai menggunakannya, sehingga sistem akan memiliki 12 harddik yang tersedia/tidak sedang digunakan.

Available: A <  Number of resource not allocated to any process.
Claim: Cij  < Max needs of proccess i for resource j.
Allocation: Aij  < Current needs of process i for resource j.

Safe state = Cij ≤ current available of resource for all j + Aij.

Suatu sistem dapat berubah dari kondisinya dari safe state menjadi unsafe state. Misal pada waktu t1, proses P2 meminta untuk dialokasikan 1 harddisk lagi. Maka hal ini menjadikan sistem menjadi unsafe state. Pada titik ini, hanya proses P1 yang dapat dialokasikan semua harddisk-nya. Ketika P1 mengembalikan harddisk tersebut, sistem hanya akan memiliki 4 harddisk yang tersedia. Sejak proses P0 dialokasikan 5 harddisk tetapi memiliki maksimal 10 harddisk, sehingga mungkin akan meminta 5 harddisk lagi, jika demikian maka proses P0 harus menunggu, karena belum tersedia satupun harddisk yang diiginkan. Demikian halnya dengan proses P2, mungkin meminta 6 harddisk tambahan, dan tentunya harus menunggu terlebih dahulu, sehingga hal ini mengakibatkan terjadinya deadlock. Kesalahan ini terjadi karena mengijinkan permintaan dari proses P2 untuk diberikan satu harddisk lagi, akan tetapi jika dapat membuat proses P2 menunggu sampai salah satu dari proses lainnya selesai dan melepaskan sumber daya yang dibutuhkan oleh P2, maka sebaliknya kondisi deadlock dapat dihindari.

Dengan konsep safe state, kita dapat mendefenisikan avoidance-algorithm yang dapat memastikan sistem tidak akan pernah mengalami deadlock, dengan ide yang sederhana yaitu memastikan sistem akan selalu dalam keadaan aman (safe state) yang dimulai pada saat inisialisasinya (awalanya). Sehingga setiap kali suatu proses meminta sumber daya yang saat ini tersedia, maka sistem harus memutuskan apakah sumber daya yang dapat sergera dialokasikan segera mungkin apa harus menunggu terlebih dahlulu. Permintaan ini dapat diberika hanya jika pada saat selesai mengalokasikan sumber daya, kemudian meninggalkan/melepaskannya dalam keadaan safe state pada sistem.

Pada penggunaan sekema ini juga memiliki kekurangan, seperti jika suatu proses meminta sumber daya yang saat ini tersedia, namun harus menunggu terlebih dahulu, sehingga penggunaan/utilisasi sumber daya dapat dikatakan rendah daripada yang seharusnya.

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.