Deadlock

Gambaran Mengenai Deadlock
Pada sistem multiprogramming, beberapa proses mungkin saja harus berkompetisi untuk menggunakan sumber daya yang jumlahnya terbatas. Jika sebuah proses me-request sumber daya dan sumber daya tersebut tidak tersedia pada saat itu (sedang dipegang oleh proses lain), maka proses tersebut akan memasuki status wait (proses diblok). Status proses yang sedang menunggu tersebut bisa saja tidak akan pernah berubah karena sumber daya yang di-request proses tersebut sedang dipegang oleh proses lain yang juga sedang menunggu. Situasi demikian dinamakan sebagai deadlock.
Berdasarkan uraian pada poin di atas, dapat disimpulkan bahwa deadlock terjadi saat dua atau lebih proses menunggu suatu kejadian selama tak terhingga karena kejadian tersebut hanya bisa disebabkan oleh sebuah proses yang sedang menunggu.
Dengan kata lain, deadlock terjadi saat himpunan proses yang masing-masing memegang sumber daya sedang diblok dan menunggu untuk mendapatkan sumber daya yang sedang dipegang oleh proses lain dalam himpunan proses tersebut.
Ilustrasi deadlock dapat digambarkan dengan masalah jembatan penyeberangan.

Model Sistem
Sebuah sistem terdiri dari sumber daya dengan jumlah terbatas yang didistribusikan kepada sejumlah proses yang berkompetisi untuk mendapatkan sumber daya.
Sumber daya terbagi menjadi beberapa tipe dan tiap tipe sumber daya dapat terdiri dari sejumlah instance yang identik. Contoh tipe sumber daya adalah space memory, siklus CPU, dan I/O devices (misalnya : printer dan tape drives). Jika sebuah sistem memiliki 2 printer maka sumber daya bertipe printer mempunyai 2 instance.
Status proses terhadap sumber daya yang perlu digunakannya adalah sebagai urutan berikut :
1.Request :
Jika request proses terhadap suatu sumber daya belum dipenuhi (misalnya : sumber daya yang di-request sedang digunakan oleh proses lain), maka proses yang me-request harus menunggu sampai sumber daya yang diperlukannya tersedia).
Use :
Proses dapat menggunakan sumber daya (misalnya : jika sumber daya-nya adalah printer, maka proses dapat melakukan pencetakan dengan printer).
Release:
Proses melepaskan sumber daya.
Status deadlock pada sebuah sistem dapat terjadi baik dengan melibatkan tipe sumber daya yang sama, maupun dengan melibatkan tipe sumber daya yang berbeda.

Karateristik Deadlock
Saat terjadi deadlock, proses-proses tidak pernah selesai diekseskusi.
Syarat perlu terjadinya deadlock yaitu :
Mutual exclusion :
Hanya satu proses pada suatu waktu yang dapat menggunakan sebuah sumber daya.
Hold and wait :
Suatu proses yang sedang memegang satu atau lebih sumber daya sedang menunggu sumber daya tambahan yang sedang dipegang oleh proses lain.
No preemption
Sumber daya hanya dapat lepas dari proses yang sedang memegangnya jika proses itu sendiri yang melepas sumber daya tersebut secara sukarela setelah proses itu menyelesaikan task-nya.
Circular Wait
Terdapat sebuah himpunan proses yang sedang menunggu yaitu : (P0, P1, ..., Pn), dimana P0 menunggu sumber daya yang sedang dipegang oleh P1, P1 menunggu sumber yang sedang dipegang oleh P2, ... , Pn-1 menunggu sumber daya yang sedang dipegang oleh Pn, dan Pn menunggu sumber daya yang sedang dipegang oleh P0.
Deadlock dapat dideskripsikan dengan menggunakan graph berarah bernama resource-allocation graph.

Jika resource-allocation graph tidak mengandung cycle, maka deadlock tidak akan terjadi.

Jika resource allocation graph mengandung cycle :
Jika tiap tipe sumber daya hanya memiliki 1 instance, maka terjadi deadlock.
Jika tiap tipe sumber daya memiliki beberapa instance, maka deadlock mungkin bisa terjadi (bisa juga tidak).

Metode Untuk Menangani Deadlocks
Menggunakan protokol yang menjamin sistem tidak akan pernah memasuki status deadlock
Membolehkan sistem memasuki status deadlock, lalu dilakukan recover.
Menganggap bahwa deadlocks tidak pernah terjadi dalam sistem (metode ini digunakan oleh sebagian besar sistem operasi termasuk UNIX).


Pencegahan Deadlock
Dengan memastikan bahwa setidaknya satu dari syarat perlu deadlock tidak terpenuhi, maka terjadinya deadlock dapat dicegah.Oleh karena itu, untuk mencegah deadlock diupayakan agar salah satu dari mutual exclusion, hold and wait, no preemption atau circular wait tidak terpenuhi.


Menghindari Deadlock
Menghindari deadlock berarti menghindari jangan sampai sistem berada pada status tidak aman.
Sistem dikatakan berada pada status aman bila sistem dapat mengalokasikan sumber daya ke masing-masing proses dengan urutan tertentu dan masih bisa menghindari deadlock
Jika sistem berada pada status aman maka deadlock tidak akan terjadi.
Jika sistem berada pada status tidak aman maka deadlock mungkin terjadi.
Beberapa algoritma untuk menghindari deadlock :
Resource allocation graph algorithm
Banker's algorithm


Pendeteksian Deadlock

Jika deadlock dapat terjadi pada sebuah sistem maka sistem tersebut harus menyediakan allgoritma untuk mendeteksi apakah deadlock telah terjadi dan algoritma untuk memulihkan sistem dari deadlock.

Pemulihan Dari Deadlock
Terminasi proses
Sumber daya preemption


1.Apakah perbedaan antara mencegah deadlock dan menghindari deadlock ?
Jawaban :
Mencegah deadlock : Memastikan agar minimal 1 dari syarat perlu deadlock tidak terpenuhi.
Menghindari deadlock : Menghindari agar jangan sampai sistem berada dalam status tidak aman.
2.Apakah perbedaan antara resource allocation graph algorithm dengan banker's algorithm ?
Resource allocation graph algorithm : tidak bisa digunakan untuk sistem yang masing-masing tipe sumber dayanya memiliki banyak instance.
Banker's algorithm : dapat digunakan untuk sistem yang masing-masing tipe sumber dayanya memiliki banyak instance.
3.Diketahui :
Terdapat 5 proses bernama P0, P1, P2, P3, dan P4 dan terdapat 3 tipe sumber daya yaitu tipe sumber daya A, B, dan C.
Sumber daya A memiliki 10 instance.
Sumber daya B memiliki 5 instance.
Sumber daya C memiliki 7 instance.
Snapshot sistem :
 
Allocation
Max
Available

A B C
A B C
A B C
P0
0 1 0
7 5 3
3 3 2
P1
2 0 0
3 2 2
 
P2
3 0 2
9 0 2
 
P3
2 1 1
2 2 2
 
P4
0 0 2
4 3 3
 

Ditanyakan :
a. Tunjukkan isi matriks Need!
b. Apakah sistem berada dalam status aman ?

Jawaban :
a. Need = Max - Allocation
Maka isi matriks Need yaitu :
 
Allocation

A B C
P0
7 4 3
P1
1 2 2
P2
6 0 0
P3
0 1 1
P4
4 3 1

b. Sistem berada dalam status aman karena urutan memenuhi kriteria aman.

4.Deadlock ialah suatu kondisi dimana proses dalam sistem operasi tidak berjalan lagi ataupun tidak ada komunikasi lagi antar proses.
Deadlock adalah suatu kondisi dimana dua proses atau lebih saling menunggu proses yang lain untuk melepaskan resource yang sedang dipakai. Karena beberapa proses itu saling menunggu, maka tidak terjadi kemajuan dalam kerja proses-proses tersebut. Deadlock adalah masalah yang biasa terjadi ketika banyak proses yang membagi sebuah resource yang hanya boleh dirubah oleh satu proses saja dalam satu waktu.
contoh :
Misal ada proses A mempunyai resource X, proses B mempunyai resource Y. Kemudian kedua proses ini dijalankan bersama, proses A memerlukan resource Y dan proses B memerlukan resource X, tetapi kedua proses tidak akan memberikan resource yang dimiliki sebelum proses dirinya sendiri selesai dilakukan.