Deadlock

Permasalahan deadlock terjadi karena sekumpulan proses-proses yang di-blok dimana setiap proses membawa sebuah sumber daya dan menunggu mendapatkan sumber daya yang dibawa oleh proses lain. Misalnya sistem mempunyai 2 tape drive dan terdapat dua proses P1 dan P2 yang masing masing membawa satu tape drive dan masing-masing memerlukan tape drive yang dibawa proses lain sehingga terjadi keadaan saling menunggu resource dan sistem di-blok.

Deadlock adalah efek samping dari sinkronisasi, dimana satu variabel digunakan oleh 2 proses. Keadaan dimana 2 atau lebih proses saling menunggu meminta resources untuk waktu yang tidak terbatas lamanya.

KARAKTERISTIK DEADLOCK

1. Kondisi yang Diperlukan, Deadlock terjadi bila terdapat empat kondisi berikut ini secara simultan.
2. Mutual Exclusion : hanya satu proses pada satu waktu yang dapat menggunakan sumber daya. Membuat file spool untuk resource yang digunakan bersama-sama
3. Genggam dan Tunggu (Hold and Wait) : : memaksa sebuah proses untuk melepaskan resource yang dimilikinya ketika meminta resource baru. Suatu proses membawa sedikitnya satu sumber daya menunggu mendapatkan tambahan sumber daya baru yang dibawa oleh proses
4. on-Preemption : membolehkan adanya preemption. sebuah sumber daya dapat dibebaskan dengan sukarela oleh proses yang memegangnya setelah proses menyelesaikan task.
5.  Menunggu Secara Sirkuler (Circular Wait) : memberikan penamaan resource berdasarkan urutan atau level. Terdapat sekumpulan proses {P0, P1, …, P0} yang menunggu sumber daya dimana P0 menunggu sumber daya yang dibawa P1, P1 menunggu sumber daya yang dibawa P2, dan seterusnya, Pn–1 menunggu sumber daya yang dibawa oleh Pn, dan Pn menunggu sumber daya yang dibawa P0.

MODEL DEADLOCK

Gambar 1.1 Model deadlock

Gambar 1.2 Model deadlock

METODE MENANGANI DEADLOCK

Terdapat tiga metode untuk menangani permasalahan deadlock yaitu :

Ø  Menggunakan protocol untuk menjamin bahwa sistem tidak pernah memasuki status deadlock

Ø  Mengijinkan sistem memasuki status deadlock dan kemudian memperbaikinya.

Ø  Mengabaikan permasalahan dan seakan-akan deadlock tidak pernah terjadi pada sistem.z                                  

Model ini yang banyak digunakan pada sistem operasi termasuk UNIX.

STRATEGI MENGATASI DEADLOCK 

• Prevention : memastikan paling sedikit satu penyebab Deadlock tidak berlaku
• Avoidance : sistem menolak request terhadap resource yang berpotensi deadlock, Algoritma Banker. Resource manager menolak proses yang meminta resource yang berpotensi deadlock. Jika ada permintaan resource yang maksimum digunakan, maka proses tersebut akan dipaksa untuk melepaskan resource yang sudah dimiliknya. Perlu adanya informasi tambahan.
• Detection and Recovery : membiarkan Deadlock terjadi, lalu mendeteksinya, kemudian melakukan recovery. Algoritma Ostrich . Membiarkan deadlock terjadi lalu mendeteksinya kemudian melakukan tindakan recovery seperlunya. Algoritma yang paling dikenal adalah algoritma Ostrich. Tindakan recovery yang dilakukan adalah :melakukan preemption, membuat checkpoint untuk rollback lalu membunuh proses yang prioritasnya kecil.

MENCEGAH DEADLOCK

Untuk mencegah deadlock dilakukan dengan meniadakan salah satu dari syarat perlu sebagai berikut

• Mencegah Mutual Exclusion. Hal ini dikarenakan tidak ada sumber daya yang dapat digunakan bersama-sama, jadi sistem harus membawa sumber daya yang tidak dapat digunakan bersama-sama.
• Mencegah Hold and Wait . Sistem harus menjamin bila suatu proses meminta sumber daya, maka proses tersebut tidak sedang memegang sumber daya yang lain. Proses harus meminta dan dialokasikan semua sumber daya yang diperlukan sebelum proses memulai eksekusi atau mengijinkan proses meminta sumber daya hanya jika proses tidak membawa sumber daya lain. Model ini mempunyai utilitas sumber daya yang rendah dan kemungkinan terjadi starvation jika proses membutuhkan sumber daya yang popular sehingga terjadi keadaan menunggu yang tidak terbatas karena setidaknya satu dari sumber daya yang dibutuhkannya dialokasikan untuk proses yang lain.
• Mencegah Non Preemption Peniadaan non preemption mencegah proses-proses lain harus menunggu. Seluruh proses menjadi preemption, sehingga tidak ada tunggu menunggu. Cara mencegah kondisi non preemption :

1. Jika suatu proses yang membawa beberapa sumber daya meminta sumber daya lain yang tidak dapat segera dipenuhi untuk dialokasikan pada proses tersebut, maka semua sumber daya yang sedang dibawa proses tersebut harus dibebaskan
2. Proses yang sedang dalam keadaan menunggu, sumber daya yang dibawanya ditunda dan ditambahkan pada daftar sumber daya.
3. Proses akan di restart hanya jika dapat memperoleh sumber daya yang lama dan sumber daya baru yang diminta.

• Mencegah Kondisi Menunggu Sirkular. Sistem mempunyai total permintaan global untuk semua tipe sumber daya. Proses dapat meminta proses kapanpun menginginkan, tapi permintaan harus dibuat terurut secara numerik. Setiap proses yang membutuhkan sumber daya dan memintanya maka nomor urut akan dinaikkan. Cara ini tidak akan menimbulkan siklus. Masalah yang timbul adalah tidak ada cara pengurutan nomor sumber daya yang memuaskan semua pihak.