Pengertian Deadlock

Deadlock adalah suatu kondisi dimana dua proses atau lebih tidak dapat meneruskan eksekusinya

Resources (1)

 Contoh resources sistem komputer
 printers
 tape drives
 Proses-proses membutuhkan akses ke resource secara teratur
 Contoh 1 : suatu proses memegang (hold) resource A dan meminta resource B
 pada saat yang sama proses lain sedang memegang resource B dan meminta resource A
 masing-masing proses melakukan block, dalam kondisi seperti ini terjadi deadlock

Resources (2)

 Contoh 2 :
 semaphores A dan B, di-inisialisasi 1
P0 P1
wait (A); wait(B)
wait (B); wait(A)
. .
. .
. .
signal(A) signal(B)
signal(B) signal(A)

Resources (3)

 Contoh 3 :
 Bridge Crossing
 Traffic hanya satu arah
 Masing-masing bagian jembatan dapat digambarkan sebagai resource.
 Jika deadlock terjadi, dapat diselesaikan dengan cara satu mobil mundur ke belakang.
 Beberapa mobil harus kembali jika terjadi deadlock
 Memungkinkan terjadinya starvation

Resources (4)

 Deadlock terjadi ketika…
 proses-proses diberikan hak akses secara eksklusif ke devices (resources)
 Preemptable resources
 dapat diambil dari proses tanpa menimbulkan efek yang buruk
 Nonpreemptable resources
 akan menyebabkan proses gagal jika diambil

4 Kondisi Terjadinya Deadlock

 Kondisi Mutual exclusion
 hanya satu proses dalam satu waktu yang dapat memegang (hold) resource
 Hold and wait condition
 suatu proses memegang satu resource dan me-request resource yang lain
 No preemption condition
 resource hanya dapat di-release setelah proses menyelesaikan task-nya pada resource tersebut
 Circular wait condition
 Masing-masing proses menunggu resource yang digunakan oleh proses lain secara berantai.
 Terdapat himpunan proses yang sedang menunggu {P0, P1, …, P0} sedemikian sehingga P0 menunggu resource yang dipegang oleh P1 , P1 sedang menunggu resource yang dipegang oleh P2, …, Pn–1 . Pn–1 menunggu resource yang dipegang oleh Pn . Dan Pn menunggu resource yang dipegang oleh P0 .

Metode-metode Penanganan Deadlocks

 Memastikan bahwa sistem tidak akan pernah masuk ke dalam kondisi (state) deadlock.
 Memungkinkan sistem untuk masuk ke dalam kondisi deadlock dan kemudian melakukan recovery (pemulihan).
 Mengabaikan masalah deadlock dan membuat deadlock tidak pernah terjadi dalam sistem; digunakan pada OS umumnya (Unix).

Metode Pencegahan Deadlock (1)

Cara pencegahan (Prevention) dari sisi permintaan (request) resources :
 Mutual Exclusion – tidak diperlukan untuk resource-resource yang di-share; harus dipegang (hold) untuk resource-resource yang tidak di-share (nonsharable resources).
 Hold and Wait – harus dijamin bahwa kapanpun suatu permintaan proses pada resource, proses tersebut tidak memegang resource yang lain.
 Membutuhkan proses untuk me-request dan mengalokasikan resources sebelum memulai eksekusi, atau membolehkan proses untuk me-request resource hanya ketika proses tidak sedang memegang resource.
 Utilisasi resource yang rendah memungkinkan terjadinya starvation.

Metode Pencegahan Deadlock (2)

 No Preemption
 Jika suatu proses yang memegang beberapa resource me-request resource yang lain yang tidak dapat secara langsung dialokasikan, maka semua resource yang sedang dipegang dibebaskan (released).
 Preempted resources ditambahkan ke list resources dimana proses sedang menunggu.
 Proses akan di-restart hanya jika dapat mengambil kembali (regain) resource, juga resource yang baru yang di-request.
 Circular Wait
 Membuat penomoran pada proses-proses yang mengakses resource. Suatu proses dimungkinkan untuk dapat meminta resource kapanpun, tetapi permintaannya harus dibuat terurut.

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

Metode Penghindaran Deadlock (1)

 Memberi kesempatan ke permintaan resource yang tidak mungkin menyebabkan deadlock.
 Jika pemberian akses tidak mungkin mengarah pada deadlock, maka resource akan diberikan pada proses yang meminta.
 Jika tidak aman, proses yang meminta akan di-suspend sampai suatu waktu permintaannya aman untuk diberikan.
 Kondisi aman (safe state)
 Jika tidak terjadi deadlock
 Kondisi tidak aman (unsafe state)
 Jika tidak terdapat cara untuk memenuhi semua permintaan

Metode Penghindaran Deadlock (2)

 Membutuhkan sistem yang memiliki informasi resource yang tersedia.
 Masing-masing proses memastikan jumlah maksimum resource yang diperlukan.
 Algoritma penghindaran (avoidence) deadlock memastikan tidak akan terjadi kondisi circular wait.
 Kondisi (state) alokasi resource didefinisikan sebagai jumlah dan alokasi resource yang tersedia dan maksimum permintaan resource oleh proses.

Basic Facts

 Jika sistem dalam kondisi aman (safe state) Þ tidak ada deadlock.
 Jika sistem dalam kondisi tidak aman (unsafe state) Þ kemungkinan dapat terjadi deadlock
 Pendekatan penghindaran (avoidence) memastikan bahwa sistem tidak akan pernah masuk ke dalam kondisi unsafe state.

Deteksi dan Pemulihan Deadlock

 Menentukan apakah deadlock sedang terjadi, kemudian proses-proses dan resource yang terlibat dalam deadlock tersebut.
 Setelah kondisi deadlock terdeteksi, maka langkah pemulihan deadlock dilakukan.

Cara Pemulihan Deadlock

 Ada beberapa cara untuk pemulihan deadlock :
 Menggagalkan semua proses yang deadlock
 Mem-backup semua proses yang deadlock dan me-restart semua proses tersebut
 Menggagalkan proses-proses yang deadlock secara berturut-turut hingga tidak ada deadlock.
 Menggagalkan pengalokasian resource-resource secara berturut-turut hingga tidak ada deadlock.
 Kriteria proses-proses yang akan disingkirkan :
 Memiliki waktu proses (yang telah berjalan) kecil.
 Jumlah keluaran sedikit
 Memiliki estimasi sisa waktu eksekusi terbesar.
 Jumlah total resource terkecil yang telah dialokasikan
 Memiliki prioritas terkecil