Protokol Deadlock Prevention

Seperti yang telah dijelaskan sebelumnya, situasi deadlock dapat terjadi jika empat kondisi berlangsung secara bersamaan, sehingga dengan memastikan bahwa setidaknya salah satu dari kondisi tersebut tidak terjadi, maka deadlock dapat dicegah. Berikut uraian pencegahan dari keempat kondisi tersebut.

Kondisi Mutual Exclusion

Penggunaan mutex diperlukan pada resource yang bersifat non-shareable, contoh sumber dayanya adalah printer, langkah yang digunakan adalah melakukan spooling sumber daya tersebut yaitu dengan cara membuat antrian untuk setiap proses yang membutuhkannya. Pada resource yang bersifat sharable tidak membutuhkan mutex, contoh pada file, cukup merubah aksesnya menjadi read-only, sehingg beberapa proses dapat membacanya secara bersamaan tanpa perlu saling menunggu untuk selesai membaca. Meskipun syarat mutual exclusion telah ditanganin, namun tidak menjamin tidak akan terjadi deadlock, karena beberapa resource secara instrintik (terkandung didalamnya) memang bersifat non-shareable dan tidak dapat di spooling, contoh tabel proses, kemudian mutex_lock, yang keduanya tidak dapat dibagikan secara bersamaan oleh ke beberapa proses.

Kondisi Hold and Wait

Kondisi hold dan wait dapat menyebabkan deadlock. Alternatif pertama untuk memastikan kondisi hold and wait tidak terjadi, maka harus menjamin bahwa setiap kali proses meminta resource lainnya, maka proses tersebut tidak sedang menahan/menggunakan resource apapun. hal ini dapat dicapai dengan menerapkan ketentuan mengharuskan system calls meminta semua resource yang diperlukan oleh proses tersebut sebelum dieksekusi agar dapat didahulukan melalui system call pada proses lainnya.

Alternatif kedua untuk memastikan kondisi hold and wait tidak tidak terjadi, harus menjamin setiap kali proses meminta resource lainnya, maka terlebih dahulu harus melepas resource yang sedang ditahan/digunakannya. hal ini dapat dicapai dengan menerapkan ketentuan mengharuskan system calls meminta semua resource yang diperlukan agar dapat didahulukan melalui system call pada proses lainnya.

Untuk mengilustrasikan perbedaan antara dua alternatif tersebut permisalkan terdapat proses copy file gambar dari USB flask-disk ke dalam harddisk komputer kemudian mencetaknya ke sebuah printer. Jika dikaitkan dengan aturan alternatif pertama, maka sebelum dijalankan proses tersebut harus meminta seluruh resource yaitu USB flask-disk, harddisk, dan printer. Selanjutnya jika dikatikan dengan aturan alternatif ke dua, maka sebelum proses dieksekusi hanya meminta resource USB flask-disk dan harddisk, agar dapat melakukan proses penyalinan file gambar, dan setelah selesai menyalin maka proses melepaskan resource tersebut, kemudian proses meminta resource file gambar dan printer, dan setelelah selesai mencetak maka proses melepaskan resource tersebut.

Meskipun demikin, kedua alternatif ini memiliki dua kerugian/kelemahan utama. Kerugian alternatif pertama yaitu utilisasi/pemanfaatan sumber daya yang rendah karena terdapat sumber daya yang diambil oleh proses tetapi belum digunakan, sehingga sangat memungkinkan mengalokasikan sumber daya tersebut ke proses lainnya. Kerugian altertnatif kedua yaitu sangat memungkinkan terjadi kelaparan/starvation, karena setidaknya sebuah proses membutuhkan satu sumber daya, tetapi sumber daya tersebut selalu di alokasikan ke proses lainnya, sehingga proses tersebut harus menunggu tanpa batas waktu yang tidak diketahui.

Kondisi No Preemption

Kondisi berikut ini yang dapat menyebabkan terjadinya deadlock adalah tidak dapat menyela sumber daya yang telah dialokasikan. Untuk memastikan kondisi ini tidak berlaku, maka dapat menerapkan aturan jika sebuah proses sedang menahan beberapa resource, kemudian meminta resource lainnya yang tidak dapat segera dialokasikan untuk proses ini, maka proses ini harus menunggu, tetapi seluruh resource yang sedang ditahan/digunakan harus dapat di disela atau secara implisit (tidak langsung) harus di lepas. Kemudian resource yang telah dilepas tersebut/sudah menjadi preemption ditambahkan ke dalam daftar resource agar dapat digunakan oleh proses yang sedang menunggu. Selanjutnya karena proses ini sudah memasuki state waitting juga, maka proses ini akan dimuat ulang, hanya jika proses ini dapat memperoleh kembali resource lama yang telah dilepas (melalui daftar resource) ditambah dengan resource baru yang diminta.

Alur sederhananya seperti ini, pertama, membebaskan semua resource (dari no-preemption menjadi preemtion) yang dipegang suatu proses apabila proses ingin mengakses suatu resource lain, dan tidak dapat langsung dipenuhi. Kedua, resource yang telah menjadi preemption tersebut ditambahkan kedalam daftar resource biasanya kedalam register, sehingga dapat digunakan oleh proses lain yang membutuhkannya. Ketiga, proses awal yang melepaskan resource tersebut dapat dimulai kembali apabila sudah mendapatkan kembali semua resource yang dilepaskan termasuk resource tambahan yang ingin diakses.

Mekanisme ini sering diterapkan pada resource yang statusnya dapat dengan mudah disimpan dan kemudian dipulihkan nantinya, contoh resource-nya adalah register CPU dan ruang memori, tetapi mekanisme ini umumnya tidak dapat diterapkan pada resource seperti mutex locks dan semafor.

Kondisi Circular Wait

Kondisi terakhir berikut ini dapat menyebabkan terjadinya deadlock. Salah satu cara yang memungkinkan untuk memastikan bahwa kondisi ini tidak akan pernah terjadi adalah memberikan nomor urut setiap resource dan mengharuskan setiap proses jika ingin mengakses/menggunakan resource dilakukan secara berurutan dari rendah ke tinggi.

Sebagai ilustrasi, misal R = {R1, R2, …, Rm} yang merupakan himpunan jenis/tipe sumber daya. Kemudian defenisikan setiap jenis sumber daya menjadi sebuah bilangan bulat yang unik (tidak ada yg sama). Hal ini dilakukan agar dapat membandingkan dua sumber daya dan untuk menentukan apakah satu proses mendahului proses yang lain. Selanjutnya hal tesebut didefenisikan kedalam fungsi one-to-one dengan persamaan F:R → N, dimana N adalah bilangan asli. Sebagai contoh himpunan resource dari tipe R adalah flask-disk, harddisk, dan printer, maka fungsi F dapat didefenisikan sebagai berikut.

F(flask-disk) = 1
F(harddisk) = 3
F(printer) = 6

Untuk menghindari deadlock dari fungsi diatas, sebagai alternatif pertama setiap proses hanya dapat meminta resource dalam urutan enumerasi yang meningkat, artinya awalan sebuah proses dapat meminta resource instance nomor berapapun dari sebuah tipe, misal Rj. Kemudian proses tersebut dapat meminta resource instance lainnya dari tipe Rj jika dan hanya jika F(Rj) > F(Ri). Misal dari contoh sebelumnya proses ingin menggunkan flask-disk dan printer, maka harus meminta flask-disk terlebih dahulu, kemudian meminta printer. Selanjutnya alternatif kedua, dapat mensyaratkan kepada proses yang meminta resource instance dari tipe Rj tersebut untuk terlebih dahulu melepaskan resource yang sedang ia tahan/gunakan (Ri), sehingga diperoleh F(Ri) ≥ F(Rj). Hal ini berlaku jika beberapa resource instance dari tipe yang sama dibutuhkan/diminta oleh suatu proses, maka semua request resource tersebut harus dikeluarkan/dilepaskan terlebih dahulu.

Contoh terdapat resource R1, R2, R3, R4, R5. Jika P0 sedang mengakss R2, maka P0 hanya boleh meminta resource instance R3, R4, R5. Jika P1 sedang mengakses R3, maka P1 hanya boleh meminta R4 atau R5. Sehingga jika alternatif ini digunakan, makan kondisi circular-wait tidak akan terjadi.

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.