Definisi Dedlock
Deadlock
dapat terjadi karena dua prosees yang saling menunggu resource yang digunakan
proses lainnya dalam waktu yang tidak terbatas lamanya, deadlock dalam arti
lainnya adalah kebuntuan dalam system operasi atau kebuntuan beberapa proses.
Jadi deadlock ialah suatu kondisi dimana proses tidak berjalan lagi ataupun
tidak ada komunikasi antara proses.
Deadlock dapat dianalogikan Kemacetan total di jalan raya
Penyebab terjadinya deadlock
Bebrapa
penyebab terjadinya deadlock adalah:
·
Mutual Exlution
Adalah
system memanage resource sehingga satu resource hanya boleh di pakai oleh satu
proses dan jika adal proses lain yang akan menggunakan resource yang sama harus
merequest dan menunggu proses yang memakainya melepaskan resource tersebut.
·
Hold and Wait
Adalah
suatu proses yang meminta sumberdaya lagi tanpa melepaskan sumberdaya yang
telah di pakainya, halini dapat mengakibatkan proses lain menunggu resource
yang telah dipainya.
·
Circular Waiting
Adalah
keadaaan dimana suatu proses yang saling menunggu resource dalam satu rangkaian
yang proses. Hal seperti ini akan menjadikan system tidak melakukan proses
manapun.
·
No Preemtion
Adalah
dimana resource yang dipakai oleh suatu proses tidak boleh di pakai oleh
prosees lainya sebelun proses tersebut selesai menggunakan resource tersebut, maka
proses yang lain menunggu untuk mendapat giliran menggunakan resource.
Pencegahan deadlock
Abaikan, dan pura-pura tidak tahu lalu restar system
Prevention (Pencegahan)
·
Merancangkan sistem sedemikian sehingga deadlock
tidak mungkin terjadi
·
Menidakan satu dari sekumpulan proses yang
berpotensi deadlocdk
·
Mencegah kondisi Mutual Exlusion
·
Penggunaan resorce secara ekslusif
·
Efesiensi alokasi sumberdaya
·
Meminimisasi penggunaan sumberdaya pada suatu proses
·
Mencegah kondisi Hold and Wait
·
Pengalokasian semua sumberdaya sebelum mulai
proses
·
Masalah :
·
Resource yang akan digunakan tidak diketahui
dengan pasti
·
Mengikat resource yang mungkin akan digunakan
juga oleh proses lain
·
Alternative :
·
Jika proses membutuhkan resource maka dia harus
melepas terlebih dulu semua resource yang telah digunakannya kemudian request
kembali resource yang diperlukan.
·
Mencegah kondisi No Preemtion
·
Jika terjadi pending dari request resource yang
dibutuhkan maka lepaskan semua resource yang sudah digunakan pada proses
tersebut
·
Resource yang di-preemted ditambahkan
kesumberdaya yang ditunggu
·
Proses akan kembali dimulai setelah semua
resource didapatkan
·
Mencegah kondisi Circular Waiting
·
Lepaskan resource yang telah dipakai jika memninta
rtesource baru
·
Pengurutan resource secara global
·
Request harus dilakukan secara berurutan
Penghindaran (Avoidance)
§
Sistem harus mengenali proses mana yang akan
membawa ke kondisi dadlock.
·
Jangan memulai proses apapun jika langkah
tersebut dapat membawa kekondisi deadlock
§
Jangan alaokasikan resource pada proses yang
membawa kekondisi deadlock
Algoritma ostrich
Algoritma
paling simple menurut saya, karena algoritma ini benar-benear mengabaikan
kondisi deadlock.
Ostrich : benamkan
kepala ke pasair, pura-pura tidak ada masalah sama sekali, jika terjadi
deadlock jangan lakukan apapun cukup lakukan re-start sistem
Algoritma banker
Algoritma
yang melakukan penghindaran ternhadap deadlock, algoritma ini meniru dari
sistem bank, dengan ilustrasi seorang bankir yang melayani sekelompok orang
yang meminta pinjaman, jadi kepada siapa dia memberikan pinjamannya, dan setiap
pelanggan memberikan batasan pinjaman maksimum kepada setiap peminjaman dana.
Algoritma
banker mempertimbangkan apakahpermintaan mereka itu sesuai dengan jumlah dana
yang ia miliki, sekaligus memperkirakan jumlah maksimal dari peminjamaan dana
tersebut.
Struktur data Algoritma Bangker:
1. Tersedia: jumlah sumber daya/dana yang tersedia
2. Maksimum: jumlah sumber daya maksimum yang diminta oleh setiap
proses
3. Alokasi: jumlah sumber daya yang dibutuhkan oleh setiap
proses
4. Kebutuhan: sumber daya yang sedang dibutuhkan oleh setiap
proses
Contoh Algoritma Banker.
Diketahui:
– maxc[i, j] = maksimum klaim utk Rj oleh pi
– alloc[i, j] = banyak unit Rj yg dialokasikan ke
pi
• Dapat menghitung banyaknya unit Rj yg
tersedia:
avail[j] = cj - Σ0≤i<n alloc[i,j]
• Menentukan jika state aman/tidak
berdasarkan informasi ini
Salin tabel alloc[i,j] ke alloc’[i,j]
• Jika diketahui C, maxc, and alloc’, hitung
vektor sumber daya yg tersedia
• Hitung pi: maxc[i,j] – alloc’[i,j] ≤ avail[j]
untuk 0 ≤ j < m and 0 ≤ i < n
– Jika pi tidak ada, unsafe state
– Jika alloc’[i,j]=0 untuk semua i dan j, safe state
• Set alloc’[i,j] ke 0; dealokasi semua sumber
daya yg dimiliki pi; kembali ke
langkah 2
contoh Algoritma banker (2)
Proses
|
Alokasi
|
Maks
|
Sisa
|
P1
|
2
|
5
|
2
|
P2
|
4
|
8
|
P3
|
2
|
3
|
P1
|
2
|
8
|
4
|
P2
|
4
|
8
|
P3
|
-
|
-
|
P1
|
-
|
-
|
6
|
P2
|
4
|
8
|
P3
|
-
|
-
|
Algoritma safety
Algoritma
ini menentukan apakah kondisi si safe state atau unsafe state.
Contoh
