Deadlock

Pada pembahasan di atas telah dikenal suatu istilah yang populer pada bagian semaphores, yaitu deadlock. Secara sederhana deadlock dapat terjadi dan menjadi hal yang merugikan, jika pada suatu saat ada suatu proses yang memakai sumber daya dan ada proses lain yang menunggunya. Bagaimanakah deadlock itu yang sebenarnya? Bagaimanakah cara penanggulangannya?

Latar Belakang

Misalkan pada suatu komputer terdapat dua buah program, sebuah tape drive dan sebuah printer. Program A mengontrol tape drive, sementara program B mengontrol printer. Setelah beberapa saat, program A meminta printer, tapi printer masih digunakan. Berikutnya, B meminta tape drive, sedangkan A masih mengontrol tape drive. Dua program tersebut memegang kontrol terhadap sumber daya yang dibutuhkan oleh program yang lain. Tidak ada yang dapat melanjutkan proses masing-masing sampai program yang lain memberikan sumber dayanya, tetapi tidak ada yang mengalah. Kondisi inilah yang disebut Deadlock atau pada beberapa buku disebut Deadly Embrace

Deadlock yang mungkin dapat terjadi pada suatu proses disebabkan proses itu menunggu suatu kejadian tertentu yang tidak akan pernah terjadi. Dua atau lebih proses dikatakan berada dalam kondisi deadlock, bila setiap proses yang ada menunggu suatu kejadian yang hanya dapat dilakukan oleh proses lain dalam himpunan tersebut.

Terdapat kaitan antara overhead dari mekanisme koreksi dan manfaat dari koreksi deadlock itu sendiri. Pada beberapa kasus, overhead atau ongkos yang harus dibayar untuk membuat sistem bebas deadlock menjadi hal yang terlalu mahal dibandingkan jika mengabaikannya. Sementara pada kasus lain, seperti pada real-time process control, mengizinkan deadlock akan membuat sistem menjadi kacau dan membuat sistem tersebut tidak berguna.

Contoh berikut ini terjadi pada sebuah persimpangan jalan. Beberapa hal yang dapat membuat deadlock pada suatu persimpangan, yaitu:

Strategi menghadapi Deadlock

Strategi untuk menghadapi deadlock dapat dibagi menjadi tiga pendekatan, yaitu:

  1. Mengabaikan adanya deadlock.
  2. Memastikan bahwa deadlock tidak akan pernah ada, baik dengan metode Pencegahan, dengan mencegah empat kondisi deadlock agar tidak akan pernah terjadi. Metode Menghindari deadlock, yaitu mengizinkan empat kondisi deadlock, tetapi menghentikan setiap proses yang kemungkinan mencapai deadlock.
  3. Membiarkan deadlock untuk terjadi, pendekatan ini membutuhkan dua metode yang saling mendukung, yaitu:

Dari penjabaran pendekatan diatas, terdapat empat metode untuk mengatasi deadlock yang akan terjadi, yaitu:

Mencegah Deadlock

Metode ini merupakan metode yang paling sering digunakan. Metode Pencegahan dianggap sebagai solusi yang bersih dipandang dari sudut tercegahnya deadlock. Tetapi pencgahan akan mengakibatkan kinerja utilisasi sumber daya yang buruk.

Metode pencegahan menggunakan pendekatan dengan cara meniadakan empat syarat yang dapat menyebabkan deadlock terjadi pada saat eksekusi Coffman (1971).

Syarat pertama yang akan dapat ditiadakan adalah Mutual Exclusion, jika tidak ada sumber daya yang secara khusus diperuntukkan bagi suatu proses maka tidak akan pernah terjadi deadlock. Namun jika membiarkan ada dua atau lebih proses mengakses sebuah sumber daya yang sama akan menyebabkan chaos. Langkah yang digunakan adalah dengan spooling sumber daya, yaitu dengan mengantrikan job-job pada antrian dan akan dilayani satu-satu.

Beberapa masalah yang mungkin terjadi adalah:

  1. Tidak semua dapat di-spool, tabel proses sendiri tidak mungkin untuk di-spool
  2. Kompetisi pada ruang disk untuk spooling sendiri dapat mengarah pada deadlock

Hal inilah yang menyebabkan mengapa syarat pertama tidak dapat ditiadakan, jadi mutual exclusion benar-benar tidak dapat dihilangkan.

Cara kedua dengan meniadakan kondisi hold and wait terlihat lebih menjanjikan. Jika suatu proses yang sedang menggunakan sumber daya dapat dicegah agar tidak dapat menunggu sumber daya yang lain, maka deadlock dapat dicegah. Langkah yang digunakan adalah dengan membuat proses agar meminta sumber daya yang mereka butuhkan pada awal proses sehingga dapat dialokasikan sumber daya yang dibutuhkan. Namun jika terdapat sumber daya yang sedang terpakai maka proses tersebut tidak dapat memulai prosesnya.

Masalah yang mungkin terjadi:

  1. Sulitnya mengetahui berapa sumber daya yang dibutuhkan pada awal proses
  2. Tidak optimalnya pengunaan sumber daya jika ada sumber daya yang digunakan hanya beberapa waktu dan tidak digunakan tapi tetap dimiliki oleh suatu proses yang telah memintanya dari awal.

Meniadakan syarat ketiga non preemptive ternyata tidak lebih menjanjikan dari meniadakan syarat kedua, karena dengan meniadakan syarat ketiga maka suatu proses dapat dihentikan ditengah jalan. Hal ini tidak dimungkinkan karena hasil dari suatu proses yang dihentikan menjadi tidak baik.

Cara terakhir adalah dengan meniadakan syarat keempat circular wait. Terdapat dua pendekatan, yaitu:

  1. Mengatur agar setiap proses hanya dapat menggunakan sebuah sumber daya pada suatu waktu, jika menginginkan sumber daya lain maka sumber daya yang dimiliki harus dilepas.
  2. Membuat penomoran pada proses-proses yang mengakses sumber daya. Suatu proses dimungkinkan untuk dapat meminta sumber daya kapan pun, tetapi permintaannya harus dibuat terurut.

Masalah yang mungkin terjadi dengan mengatur bahwa setiap proses hanya dapat memiliki satu proses adalah bahwa tidak semua proses hanya membutuhkan satu sumber daya, untuk suatu proses yang kompleks dibutuhkan banyak sumber daya pada saat yang bersamaan. Sedangkan dengan penomoran masalah yang dihadapi adalah tidak terdapatnya suatu penomoran yang dapat memuaskan semua pihak.

Secara ringkas pendekatan yang digunakan pada metode pencegahan deadlock dan masalah-masalah yang menghambatnya, terangkum dalam tabel dibawah ini.

Tabel 3-1. Tabel Deadlock

Syarat Langkah Kelemahan
Mutual Exclusion Spooling sumber daya Dapat menyebabkan chaos
Hold and Wait Meminta sumber daya di awal Sulit memperkirakan di awal dan tidak optimal
No Pre-emptive Mengambil sumber daya di tengah proses Hasil proses tidak akan baik
Circular Wait Penomoran permintaan sumber daya Tidak ada penomoran yang memuaskan semua pihak

Mendeteksi Deadlock dan Memulihkan Deadlock

Metode ini mengunakan pendekatan dengan teknik untuk menentukan apakah deadlock sedang terjadi serta proses-proses dan sumber daya yang terlibat dalam deadlock tersebut. Setelah kondisi deadlock dapat dideteksi, maka langkah pemulihan dari kondisi deadlock dapat segera dilakukan. Langkah pemulihan tersebut adalah dengan memperoleh sumber daya yang diperlukan oleh proses-proses yang membutuhkannya. Beberapa cara digunakan untuk mendapatkan sumber daya yang diperlukan, yaitu dengan terminasi proses dan pre-emption (mundur) suatu proses. Metode ini banyak digunakan pada komputer mainframe berukuran besar.

Resources Preemption

Metode ini lebih menekankan kepada bagaimana menghambat suatu proses dan sumber daya, agar tidak terjebak pada unsafe condition.

Beberapa langkahnya, yaitu:

Kesimpulan

Untuk mengatasi problem critical section dapat digunakan berbagai solusi software. Namun masalah yang akan timbul dengan solusi software adalah solusi software tidak mampu menangani masalah yang lebih berat dari critical section. Tetapi Semaphores mampu menanganinya, terlebih jika hardware yang digunakan mendukung maka akan memudahkan dalam menghadapi problem sinkronisasi.

Berbagai contoh klasik problem sinkronisasi berguna untuk mengecek setiap skema baru sinkronisasi. Monitor termasuk ke dalam level tertinggi mekanisme sinkronisasi yang berguna untuk mengkoordinir aktivitas dari banyak thread ketika mengakses data melalui pernyataan yang telah disinkronisasi

Kondisi deadlock akan dapat terjadi jika terdapat dua atau lebih proses yang akan mengakses sumber daya yang sedang dipakai oleh proses yang lainnya. Pendekatan untuk mengatasi deadlock dipakai tiga buah pendekatan, yaitu:

Dari ketiga pendekatan diatas, dapat diturunkan menjadi empat buah metode untuk mengatasi deadlock, yaitu:

Namun pada sebagian besar Sistem Operasi dewasa ini mereka lebih condong menggunakan pendekatan untuk mengabaikan semua deadlock yang terjadi

Silberschatz (1994) merumuskan sebuah strategi penanggulangan deadlock terpadu yang dapat disesuaikan dengan kondisi dan situasi yang berbeda, strateginya sendiri berbunyi:

  1. Kelompokkan sumber daya kedalam kelas yang berbeda
  2. Gunakan strategi pengurutan linear untuk mencegah kondisi circular waityang nantinya akan mencegah deadlock diantara kelas sumber daya
  3. Gunakan algoritma yang paling cocok untuk suatu kelas sumber daya yang berbeda satu dengan yang lain