Dead lock

Karakteristik Deadlock

Situasi deadlock dapat terjadi bila terdapat 4 kondisi yang berjalan serentak pada sistem.
Mutual Exclusion
Sebuah resource hanya dapat digunakan oleh sebuah proses pada suatu waktu tertentu. (resource yang non-shareable.)
Hold and Wait
terdapat proses yang sedang menunggu dan memegang resource.

Karakteristik Deadlock (cont.)

Non-preemption
Resource tidak dapat digunakan sebelum proses yang menggunakan telah selesai menggunakan dan kemudian melepaskannya.
Circular wait
Proses-proses berada dalam lingkaran. Terjadi saling menunggu resource yang sedang digunakan oleh proses berikutnya dalam lingkaran tersebut.

Pengendalian Deadlock
Mengabaikan, menganggap bahwa deadlock
tidak akan pernah terjadi.
Membiarkan terjadinya deadlock, lalu kemudian segera diperbaiki/recover.
Menggunakan protokol untuk meyakinkan bahwa sistem tidak akan pernahdeadlock.

Ostrich Algorithm

Algoritmapaling sederhana.
Mengabaikanterjadinyakondisideadlock.
Jadiapayang haruskitalakukanjikaterjadideadlock menurutOstrich algorithm?
Cukup di restart!

Mendeteksi dan memperbaiki

Mendeteksi apabiladalamsebuahproses
terjadi kondisiyang mengarahkecircular wait.
Apabila deadlock terjadi tentukan proses mana saja yang terlibat.
Setelah deadlock terdeteksi, biarkan proses yang mengalami deadlock selesai menggunakan resource, agar resource bisa digunakan. Atau stop semua proses yang terlibat deadlock.

Penggunaan Protokol

Deadlock Prevention
Menggunakan method supaya tidak terjadi salah
satu kondisi yang menyebabkan deadlock.
Deadlock Avoidance
Menghindari situasi yang dapat mengarah kepada terjadinya deadlock, sistem harus diberikan
informasi tambahan yang menyatakan resource
mana yang diminta proses, dan digunakan selama proses berjalan.

Deadlock prevention

Salah satu faktor-faktor penyebab deadlock
harus dapat dicegah.
Mutual Exclusion
Sifat alamiah sebuah resource (tidak bisa dicegah).Namun, ada beberapa resource yang dapat
di-spool.
Hold and Wait
Harus dipastikan bahwa ketika sebuah proses
merequest resource, proses itu tidak sedang memegang resource lain.

Deadlock prevention (cont.)

Non preemption
Mencegah supaya tidak ada proses dalam keadaan menunggu-mendapat-resource yang sedang digunakan oleh proses lain. (seluruh proses menjadi preemption).
Circular waiting
Mengatur agar setiap proses hanya dapat menggunakan sebuah sumber daya pada suatu waktu.
Melakukan penomoran resource.

Deadlock avoidance

Menyeleksi request resource dari proses-proses, apabila request itu ‘berbahaya’ maka requestnya akan ditunda dahulu hingga keadaan sudah aman.
Membutuhkan informasi tambahan mengenai aliran resource yang diminta.
Algoritma yang digunakan Algoritma Banker.

Deadlock detection

Jika tidak terdapat deadlock prevention atau avoidance dalam suatu sistem diperlukan suatu mekanisme untuk mengetahui terjadinya deadlock.
Menggunakan algoritmauntukmendeteksiadanyadeadlock.
Memeriksa penggunaan resource oleh proses-proses


Save vsUnsafe state

Ketika terjadi resource request, sistem harus memastikan proses berada dalam safe state
Safe state sistem dapat mengalokasikan resource untuk tiap-tiap proses dan mencegah terjadinya deadlock
Unsafe state sistem tidak dapat mengatur alokasi resource untuk tiap proses

Safe vs Unsafe state (cont.)

Jika sistem berada dalam kondisi safe state, berarti tidak terjadi deadlock.
Jika dalam kondisi unsafe state, kemungkinan bisa terjadi deadlock.


Banker’s algorithm

Setiap prosesharusmengklaimberapajumlahmaksimumresource yang akandigunakan.
Jikaresource tidaktersediamakapermintaanditunda.
Setiap prosesyang telahselesaiharusmengembalikanresource yang dipakai.

BANKER'S ALGORITHM

PROSES ALOKASI MAKS TERSEDIA
P1 2 5 2
P2 4 8
P3 2 3
P1 2 5 4
P2 4 8
P3 - -
P1 - - 6
P2 4 8
P3 - -

Kelemahan Banker’s algorithm

Proses kebanyakan belum mengetahui jumlah maksimum resource yang dibutuhkan.
Jumlah proses tidak tetap.
Beberapa resource dapat diambil dari sistem sewaktu-waktu.
Algoritma membuat sistem untuk memenuhi permintaan hingga waktu yang tidak terbatas.

Deadlock Recovery

Pemulihandeadlock dapatdilakukanmelalui:
Hapussemuaprosesyang terlibatdalamdeadlock.
Rollback danrestart proses.
Secarabertahaphapusproses-prosesyang terlibatdeadlock hinggatidakadadeadlock lagi.
Secaraberurutan, preempt resource-
resource sampaitidakadadeadlock.

Summary

Deadlock berpotensi terjadi pada sistem dengan multiproses akibat penggunaan resource bersama yang mengakibatkan konflik.
Ada beberapa cara untuk menghandle deadlock ini, namun tidak ada solusi umum mengenai deadlock.
Masing-masing teknik mempunyai kelemahan.