BAB IV
DEADLOCK
A.
Definisi
Deadlock dalam
arti sebenarnya adalah kebuntuan. Kebuntuan yang dimaksud dalam sistem operasi adalah
kebuntuan proses. Jadi Deadlock ialah suatu kondisi dimana proses tidak
berjalan lagi atau pun tidak ada komunikasi lagi antar proses. Deadlock disebabkan
karena proses yang satu menunggu sumber daya yang sedang dipegang oleh proses
lain yang sedang menunggu sumber daya yang dipegang oleh proses tersebut. Dengan kata lain, Deadlock terjadi ketika
proses menunggu sumber daya untuk melakukan suatu kejadian tertentu yang tidak
akan pernah terjadi.
Deadlock terjadi jika
memenuhi 4 syarat berikut :
1.
Mutual
Exclusion Condition
Sumber daya yang harus diberikan hanya pada satu proses.
2.
Hold
and Wait Condition
Proses yang sedang memegang sumberdaya, menunggu sumber daya
yang baru.
3.
Non-Preemption
Condition
Sumber daya yang diberikan sebelumnya tidak dapat diambil
paksa dari proses yang sedang menggenggamnya. Harus terlebih dahulu dilepaskan
oleh proses yang menggenggamnya.
4.
Circular
Wait Condition
Harus terdapat rantai
sirkuler dari dua proses atau lebih, dan masing-masing proses menunggu sumber
daya yang digenggam oleh proses berikutnya.
B.
Metode-metode
Mengatasi Deadlock
1.
Metode
Pencegahan Deadlock (Deadlock Prevention)
a.
Meniadakan Mutual Exclusion
Melakukan
spooling perangkat-perangkat yang harus didedikasikan ke suatu proses. Dengan
spooling, permintaan-permintaan diantrikan di harddisk. Setiap job di antrian
spooler akan dilayani satu per satu.
b.
Meniadakan Hold and Wait
1)
Mengalokasikan semua sumber daya atau tidak sama sekali
2)
Hold and release
c.
Meniadakan Non-preemption
d.
Meniadakan Menunggu Sirkular
1)
Proses hanya diperbolehkan menggenggam satu sumber daya.
2)
Penomoran global semua sumber daya.
2.
Metode
Penghindaran Deadlock (Deadlock Avoidance)
a.
Proses harus menyatakan seluruh sumber daya maksimum yang
dibutuhkan sebelum eksekusi.
b.
Ketika eksekusi berlangsung, proses meminta sumber daya yang
diperlukan hingga batas maksimum yang dinyatakan di awal.
c.
Proses yang menyatakan kebutuhan melewati kapasitas sistem,
tidak akan dieksekusi.
Safe State
State dinyatakan safe state
jika tidak deadlock dan terdapat cara untuk memenuhi seluruh permintaan tanpa
menghasilkan deadlock.
Unsafe State
State dinyatakan unsafe state
jika tidak terdapat cara untuk memenuhi semua permintaan yang tertunda dengan
menjalankan proses-proses sesuai suatu urutan.
3.
Metode
Deteksi (Deadlock Detection)
Untuk
mengetahui ada atau tidaknya deadlock dalam suatu graf dapat dilihat dari
perputaran dan resource yang dimilikinya, yaitu:
1.
Jika tidak ada perputaran berarti tidak deadlock.
2.
Jika ada perputaran, ada potensi terjadi deadlock.
3.
Resource dengan instan tunggal dan perputaran mengakibatkan deadlock.
(a)
Graf dengan deadlock (b) Graf tanpa deadlock
Pada gambar "Graf
dengan deadlock", terlihat bahwa ada perputaran yang memungkinkan
tejadinya deadlock dan semua sumber daya memiliki satu instans kecuali sumber
daya R2. Graf tersebut memiliki minimal dua perputaran, yaitu:
1. R2
-> P0 -> R0 -> P1 -> R1 -> P2 -> R2
2. R2 -> P1 -> R1 -> P2 -> R2
Gambar di atas menunjukkan beberapa hal sebagai berikut:
1. P0 meminta sumber
daya R0.
2. R0 mengalokasikan
sumber dayanya pada P1.
3. P1 meminta sumber
daya R1.
4. R1 mengalokasikan sumber dayanya pada P2.
5. P2 meminta sumber
daya R2.
6. R2 mengalokasikan sumber dayanya pada P0 dan
P1.
7. R3 mengalokasikan
sumber dayanya pada P2.
Hal-hal tersebut dapat
mengakibatkan deadlock sebab P0 memerlukan sumber daya R0 untuk menyelesaikan
prosesnya, sedangkan R0 dialokasikan untuk P1. Di lain pihak P1 memerlukan sumber
daya R1 sedangkan R1 dialokasikan untuk P2. P2 memerlukan sumber daya R2 akan
tetapi R2 mengalokasikan sumber dayanya pada R3.
Gambar “Graf Tanpa deadlock” memiliki
perputaran tetapi deadlock tidak terjadi. Pada gambar di atas, graf
memiliki 1 perputaran yaitu: P0 –> R1 –> P2 –> R0 –> P3 –> R2
–> P0.
Graf di atas menunjukkan beberapa hal:
1. P0 meminta sumber daya R1.
2. R1 mengalokasikan sumber dayanya pada P2.
3. P2 meminta sumber daya R0.
4. R0 mengalokasikan sumber dayanya pada P3.
5. P3 meminta sumber daya R2.
6. R0 mengalokasikan sumber dayanya pada P3.
7. R1 mengalokasikan sumber dayanya pada P1.
Hal ini tidak menyebabkan deadlock
walaupun ada perputaran sebab semua sumber-daya yang diperlukan P1 dapat
terpenuhi sehingga P1 dapat melepaskan semua sumber-dayanya, yang kemudian
dapat digunakan oleh proses lain.
4.
Pemulihan
Deadlock (Deadlock Recovery)
Hal-hal
yang terjadi dalam mendeteksi adanya Deadlock adalah:
1.
Permintaan sumber daya dikabulkan
selama memungkinkan.
2.
Sistem operasi memeriksa adakah kondisi
circular wait secara periodik.
3.
Pemeriksaan adanya Deadlock dapat
dilakukan setiap ada sumber daya yang hendak digunakan oleh sebuah proses.
4.
Memeriksa dengan algoritma tertentu.
Ada
beberapa jalan untuk kembali dari Deadlock.
Preemption
Untuk
sementara waktu menjauhkan sumber daya dari pemakainya, dan memberikannya pada
proses yang lain. Ide untuk memberi pada proses lain tanpa diketahui oleh pemilik
dari sumber daya tersebut tergantung dari sifat sumber daya itu sendiri.
Perbaikan dengan cara ini sangat sulit atau dapat dikatakan tidak mungkin. Cara
ini dapat dilakukan dengan memilih korban yang akan dikorbankan atau diambil
sumber dayanya utuk sementara, tentu saja harus dengan perhitungan yang cukup
agar waktu yang dikorbankan seminimal mungkin. Setelah kita melakukan
preemption dilakukan pengkondisian proses tersebut dalam kondisi aman. Setelah
itu proses dilakukan lagi dalam kondisi aman tersebut.
Melacak
Kembali
Setelah
melakukan beberapa langkah preemption, maka proses utama yang diambil
sumber dayanya akan berhenti dan tidak dapat melanjutkan kegiatannya, oleh
karena itu dibutuhkan langkah untuk kembali pada keadaan aman dimana proses
masih berjalan dan memulai proses lagi dari situ. Beberapa sistem mencoba
dengan cara mengadakan pengecekan beberapa kali secara periodik dan menandai
tempat terakhir kali menulis ke disk, sehingga saat terjadi Deadlock dapat
mulai dari tempat terakhir penandaannya berada.
Lewat
membunuh proses yang menyebabkan Deadlock
Cara
yang paling umum ialah membunuh semua proses yang mengalami Deadlock.
Cara ini paling umum dilakukan dan dilakukan oleh hampir semua sistem operasi.
Namun, untuk beberapa sistem, kita juga dapat membunuh beberapa proses saja
dalam siklus Deadlock untuk menghindari Deadlock dan
mempersilahkan proses lainnya kembali berjalan. Atau dipilih salah satu korban untuk
melepaskan sumber dayanya, dengan cara ini maka masalah pemilihan korban
menjadi lebih selektif, sebab telah diperhitungkan beberapa kemungkinan jika si
proses harus melepaskan sumber dayanya.
Kriteria
seleksi korban ialah:
1.
Yang paling jarang memakai prosesor
2.
Yang paling sedikit hasil programnya
3.
Yang paling banyak memakai sumber daya
sampai saat ini
4.
Yang alokasi sumber daya totalnya
tersedkit
5. Yang memiliki
prioritas terkecil
Thanks for reading & sharing Kamar Pekick
0 komentar:
Post a Comment