DEADLOCK

DEADLOCK

 Proses disebut deadlock, jika proses menunggu suatu kejadian tertentu yang tak akan pernah terjadi atau kondisi dimana 2 proses atau lebih tidak dapat meneruskan eksekusinya.

Sekumpulan proses berkondisi dedlock, jika setiap proses yang ada dikumpulan itu menunggu sesuatu kejadian yang hanya dapat dilakukan proses lain yang juga berada di kumpulan itu. Proses menunggu kejadian yang tak akan pernah terjadi.

Contoh :

P0                                           P1

Wait (S)                                Wait (Q)

Wait (Q)                               Wait (S)

 

Pada langkah pertama, kedua proses masih berjalan dengan baik. Pada langkah kedua, proses P0 meminta Q yang ternyata masih dibawa oleh P1 dan baru akan dilepas setelah signal (Q), demikian pula P1 meminta S yang masih dibawa oleh P0 dan baru akan dilepas setelah signal (S). Sehingga kondisi ini akan menimbulkan deadlock.

Deadlock terjadi ketika proses-proses mengakses secara eksklusif sumber daya. Semua deadlock yang terjadi melibatkan persaingan memperoleh sumber daya eksklusif oleh dua proses atau lebih. Adanya deadlock akan mengakibatkan sistem menjadi kacau.

 

Ilustrasi deadlock, misalnya :

• Terdapat dua proses, yaitu P1 dan P2 dan dua sumber daya kritis, yaitu R1 dan R2
• Proses P1 dan P2 harus mengakses kedua sumber daya tersebut, dengan kondisi ini terjadi : R1 diberikan ke P1 , sedangkan R2 diberikan ke P2.

Karena untuk melanjutkan eksekusi memerlukan kedua sumber daya sekaligus maka kedua proses akan saling menunggu sumber daya lain selamanya. Tak ada proses yang dapat melepaskan sumber daya yang telah dipegangnya karena menunggu sumber daya lain yang tak pernah diperolehnya. Kedua proses dalam kondisi deadlock, yang tidak dapat membuat kemajuan apapun dan deadlock merupakan kondisi terparah karena dapat melibatkan banyak proses dan semuanya tidak dapat mengakhiri prosesnya secara benar.

 

Model Deadlock :

Urutan kejadian pengoperasian perangkat I/O adalah :

• Meminta / request : meminta pelayanan I/O
• Memakai / Use : memakai perangkat I/O
• Melepaskan / release : melepaskan pemakaian perangkat I/O

 

Deadlock tidak hanya terjadi pada dua proses dan dua sumber daya, deadlock dapat terjadi dengan melibatkan lebih dari dua proses dan dua sumber daya.

Syarat-syarat terjadinya deadlock :

1. Mutual exclution condition

Tiap sumber daya saat itu diberikan pada tepat satu proses/ proses mengklaim kontrol eksklusif terhadap sumber daya yang dibutuhkannya.

2. Hold and wait condition / kondisi genggam dan tunggu

Proses-proses yang sedang menggenggam sumber daya yang telah diaalokasikan untuknya sementara menunggu sumber daya-sumber daya tambahan yang baru.

3. Non-preemption condition / kondisi non-preemption

Sumber daya-sumber daya yang sebelumnya diberikan tidak dapat diambil paksa dari proses sampai sumber daya tersebut digunakan sampai selesai. Sumber daya-sumber daya harus secara eksplisit dilepaskan dari proses yang menggenggamnya.

4. Circular wait condition / kondisi menunggu secara sirkularl

Harus terdapat rantai sirkuler / satu lingkaran proses dari dua proses atau lebih dimana setiap proses memegang satu atau lebih sumber daya yang diminta oleh proses berikutnya pada lingkaran tersebut, masing-masing menunggu sumber daya yang digenggam oleh anggota berikutnya pada rantai itu.

 

Ketiga syarat pertama merupakan syarat perlu bagi terjadinya deadlock. Keberadaan deadlock selalu berarti terpenuhi kondisi-kondisi diatas, tidak mungkin terjadi deadlock bila tidak ada ketiga kondisi itu. Deadlock terjadi berarti terdapat ketiga kondisi itu, tetapi adanya ketiga kondisi itu belum berarti terjadi deadlock.

Deadlock baru benar-benar terjadi bila syaarat keempat terpenuhi. Kondisi keempat merupakan keharusan bagi terjadinya peristiwa deadlock. Bila salah satu dari kondisi tidak terpenuhi, maka deadlock tidak terjadi.

 

Metode-metode mengatasi deadlock :

1. Deadlock prevention/ metode pencegahan terjadinya deadlock

Pengkondisian sistem agar menghilangkan kemungkinan terjadinya deadlock. Pencegahan merupakan solusi yang bersih dipandang dari sudut tercegahnya deadlock. Jika mulainya satu atau lebih proses akan menyebabkan terjadinya deadlock, proses tersebut tidak akan dimulai sama sekali.

• Tiap proses harus meminta resource yang dibutuhkan sekaligus dan tidak bisa berjalan sampai semua didapat (untuk “wait for”)
• Jika ada resource tidak terpenuhi , yang lainnya harus dilepas (untuk no preemption)
• Urutkan tipe-tipe resource secara linier / linier ordering ( untuk “circular wait”)

2. Deadlock avoidance / metode penghindaran terjadinya deadlock

Menghindarkan kondisi yang paling mungkin menimbulkan deadlock agar memperoleh sumber daya lebih baik. Penghindaran bukan berarti menghilangkan semua kemungkinan terjadinya deadlock. Jika sistem operasi mengetahui bahwa alokasi sumber daya menimbulkan resiko deadlock, sistem menolak / menghindari pengaksesan itu. Dengan demikian menghindari terjadinya deadlock. Contohnya dengan menggunakan algoritma banker yang diciptakan oleh Dijkstra.

3. Deadlock detection and recovery / metode deteksi dan pemulihan dari deadlock

Deteksi digunakan pada sistem yang mengijinkan terjadinya deadlock, dengan memeriksa apakah terjadi deadlock dan menentukan proses dan sumber daya yang terlibat deadlock secara presisi. Begitu telah dapat ditentukan, sistem dipulihkan dari deadlock dengan metode pemulihan. Metode pemulihan dari deadlock sistem sehingga beroperasi kembali, bebas dari deadlock. Proses yang terlibat deadlock mungkin dapat menyelesaikan eksekusi dan membebaskan sumber dayanya.

 

Pencegahan deadlock :

1. Tiap proses harus meminta semua sumber daya yang diperlukan sekaligus dan tidak berlanjut sampai semuanya diberikan
2. Jika proses telah sedang memegang sumber daya tertentu, untuk permintaan berikutnya proses harus melepas dulu sumber daya yang dipegangnya. Jika diperlukan, proses meminta kembali sekaligus dengan sumber daya yang baru
3. Beri pengurutan linier terhadap tipe-tipe sumber dya pada semua proses, yaitu jika proses telah dialokasikan suatu tipe sumber daya, proses hanya boleh berikutnya meminta sumber daya tipe pada urutan yang berikutnya.

 

Contoh kasus deadlock dikehidupan sehari-hari :

Kasus 1

Deadlock dapat dianalogikan dalam kondisi ketika sedang mengerjakan tugas dimana terdapat 1 orang berperan sebagai notulis dan dua orang bertugas mendiktekan hasil diskusi yang sudah selesai dikerjakan dan harus diketik. Ketika dua orang pendikte secara bersamaan mendiktekan sesuatu kepada notulis, maka notulis akan kesulitan untuk memilih yang mana yang harus dituliskan terlebih dahulu. Dalam kondisi “bingung” tersebut yang disebut keadaan deadlock.

Kasus 2

Deadlock dapat dianalogikan lagi seperti ketika di UNY ada konser Raisha dan RAN di GOR UNY. Ketika konser selesai dan semua penonton ingin keluar dari GOR dan hanya terdapat satu buah pintu yang terbuka. Semua akan berdesak-desakan berebut keluar melewati pintu tersebut. Sehingga akhirnya malah tidak ada yang keluar karena tidak ada yang mau mengalah dan mendahulukan orang lain.

Kasus 3

Deadlock dapat dianalogikan lagi seperti ketika dikelas PTI E sebanyak 40 orang sedang melaksanakan UTS mata kuliah Sistem Operasi. Soal berupa esai yang harus ditulis tangan. Namun ternyata di kelas tersebut hanya terdapat satu buah pulpen. Ketika seluruh mahasiswa berebut ingin menggunakan pulpen tersebut terlebih dahulu dibanding yang lain untuk mengerjakan soal dan tidak ada yang mau mengalah atau memberi kesempatan kepada orang lain untuk menggunakan pulpen terlebih dahulu.