Recovery Dari Deadlock

Ketika algoritma deadlock-detection menemukan adanya deadlock, maka terdapat beberapa alternatif yang dapat diambil. Salah satu alternatif kemungkinan yang diambil adalah memberi tahu operator bahwa telah terjadi deadlock, dan memberikan operator tersebut menangani hal tersebut secara manual. Kemungkinan alternatif lainnya adalah memberikan sistem memulihkan/recovery dari deadlock secara otomatis, menggunakan dua opsi. Pilihan atau opsi sederhana pertama adalah membatalkan proses menyebabkan circular wait, disebut sebagai process termination; opsi kedua adalah memberitahukan kepada proses lainnya untuk menyela/mendahului beberapa sumber daya dari satu atau lebih proses yang mengalami deadlock, disebut sebagai resource preemption.

Process Termination

Untuk mengeliminasi deadlock dengan cara membatalkan/aborting proses, dapat menggunakan salah satu dari dua metode berikut. Meskipun demikian, dari kedua metode tersebut sistem mengambil kembali semua sumber daya yang dialokasikan ke proses yang dihentikan, dan kedua metode ini menimbulkan overhead (penggunaan resource diluar dari pekerjaan utamanya) yang cukup besar.

• Abort all deadlocked processes – metode ini sangat jelas yakni memutuskan semua proses yang mengalami deadlock, tetapi memerlukan waktu yang lebih lama.
• Abort one process at a time until the deadlock cycle is eliminated – membatalkan proses satu persatu (parsial) hingga siklus deadlock hilang. Menggunakan metode ini mengharuskan memangil algoritma deadlock-detection tentunya untuk menentukan apakah ada proses yang masih mengalami deadlock, setiap kali proses dibatalkan.

Membatalkan atau menghentikan proses mungkin tidaklah mudah. Misal jika proses sedang memperbaharui file, ketika menghentikannya sebelum menyelesaikan pekerjaan semana mestinya, maka kemungkinan besar akan membuat file tersebut berada dalam status yang salah. Contoh lainnya pada proses mencetak dokumen melalui printer, jika proses tersebut dihentikan pada saat ditengah-tengah proses pencetakan, maka sistem harus dapat mereset printer ke dalam keadaan yang benar sebelum mencetak pekerjaan berikutnya.

Untuk meminimalisir overhead penghentian proses jika menggunakan metode parsial, penghentiannya dapat ditentukan dengan kebijakan urutan berikut. Penentuan kebijakan ini mirip dengan mengambil keputusan pada penjadwalan CPU, berikut urutannya dari overhead minim ke maksimum.

1. Hal apa yang menjadikan proses tersebut diprioritaskan.
2. Berapa lama proses tersebut sudah berlangsung, dan masih berapa lama lagi agar dapat menyelesaikan pekerjaanya.
3. Berapa banyak dan jenis penggunaan resource yang dilah digunakan oleh proses tersebut, misal apakah resource yang digunakan tersebut dapat disela.
4. Berapa banyak lagi jumlah resource yang dibutuhkan oleh proses tersebut agar dapat menyelesaikan pekerjaanya.
5. Berapa banyak proses yang harus dihentikan agar proses tersebut dapat menyelesaikan pekerjaannya.
6. Apakah proses interaktif (agar dapat dijalankan memerlukan interaksi, misal membutuhkan inputan dari pengguna) atau batch (menjalankan semuanya sekaligus, misal tanpa adanya inputan dari pengguna).

Resource Preemption

Menghilangkan deadlock dengan cara memperbolehkan proses lainnya untuk menyela secara berturut-turut dari resource yang digunakan oleh proses yang mengalami deadlock. Jika penyelaan/preemption diperlukan untuk menangani deadlock maka tiga masalah ini perlu ditangani juga, yaitu.

1. Selecting a victim – sumber daya dan proses mana saja yang harus disela? Hal ini dapat tentukan dengan mengurutkannya seperti pada urutan process termination.
2. Rollback – jika menyela sumber daya dari suatu proses, maka proses tersebut tidak akan dapat mengeksekusi pekerjaan berikutnya hingga selesai, sehingga proses yang telah disela tersebut harus dikembalikan menjadi safe state dan memuat ulang atau restart. Karena sulitnya untuk menentukan safe state dari proses yang telah disela tersebut, solusi paling sederhana adalah melakukan rollback total, yaitu membatalkan proses tersebut, dan kemudian memuat ulang. Tentunya agar solusi ini dapat dihandalkan maka memerlukan sistem untuk menyimpan lebih banyak informasi mengenai status dari proses tersebut sebelum di batalkan.
3. Starvation – bagaimana memastikan bahwa tidak ada proses yang mengunggu lama sampai waktu yang tidak terbatas untuk mendapatkan sumber daya yang diperlukan. Artinya bagaimana menjamin bahwa sumber daya yang dibutuhkan oleh proses tersebut tidak selalu disela/no-preemtion oleh proses yang sama. Solusi paling umum biasanya menggunakan rollback, sepeti penjelasan poin ke dua.

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.