Mencegah Deadlock

1. Definisi Deadlock

suatu kondisi di mana sekumpulan proses tidak dapat berjalan kembali atau tidak adanya komunikasi antar proses
sekumpulan proses yang terblok yang tiap proses tersebut memegang sumber daya dan menunggu untuk mendapatkan sumber daya yang dipegang oleh proses di dalam kumpulan tersebut.

2. Model Deadlock

3. Penyebab Deadlock / Syarat Terjadi Deadlock

• Mutual Exclusion :

- Suatu kondisi dimana setiap sumber daya diberikan tepat pada satu proses pada suatu waktu.

• Hold and Wait

- Kondisi yang menyatakan proses-proses yang sedang memakai suatu sumber daya dapat meminta sumber daya yang lain.

• Non-pre-emptive

- Kondisi dimana suatu sumber daya yang sedang berada pada suatu proses tidak dapat diambil secara paksa dari proses tersebut,sampai proses itu melepaskannya.

• Circular Wait

- Kondisi yang menyatakan bahwa adanya rantai saling meminta sumber daya yang dimiliki oleh suatu proses oleh proses lainnya.

4. Menghindari Deadlock

Sistem perlu memiliki informasi awal mengenai kebutuhan sumber daya
- Tiap proses menyatakan kebutuhan maksimum tiap jenis sumber yg dibutuhkan

- Algoritma deadlock-avoidance secara dinamis memeriksa state alokasi sumber daya untuk menjamin tdk terjadinya kondisi circular-wait

-State alokasi sumber daya didefinisikan oleh banyaknya sumber daya yg tersedia dan yg dialokasikan, dan permintaan sumber daya maksimum oleh proses. Jika proses meminta sumber daya yg tersedia, sistem harus memutuskan apakah alokasi sumber daya ini akan menghasilkan safe state

Sistem berada pada safe state jika terdapat urutan event yg tidak menyebabkan deadlock jika semua proses meminta sumber daya maksimum sekaligus

• Logikanya:

– Jika sistem berada pd safe state 􀃆 no deadlock
– Jika sistem berada pd unsafe state 􀃆 kemungkinan deadlock
– Pencegahan: sistem tidak masuk ke unsafe state

5. Mengatasi Deadlock

Prevention : memastikan paling sedikit satu penyebab Deadlock tidak berlaku

- Mutual Exclusion : membuat file spool untuk resource yang digunakan bersama-sama

-Hold and Wait : memaksa sebuah proses untuk melepaskan resource yang dimilikinya ketika meminta resource baru

-Circular Waiting : memberikan penamaan resource berdasarkan urutan atau level

-No Preemption : membolehkan adanya preemption

Avoidance : sistem menolak request terhadap resource yang berpotensi deadlock, Algoritma Banker

-Resource manager menolak proses yang meminta resource yang berpotensi deadlock

-Jika ada permintaan resource yang maksimum digunakan, maka proses tersebut akan dipaksa untuk melepaskan resource yang sudah dimiliknya

-Perlu adanya informasi tambahan

Detection and Recovery : membiarkan Deadlock terjadi, lalu mendeteksinya, kemudian melakukan recovery, Algoritma Ostrich

-Tindakan recovery yang dilakukan adalah : melakukan preemption, membuat checkpoint untuk rollback lalu membunuh proses yang prioritasnya kecil

6. Mencegah Deadlock

- Tiap proses harus meminta semua sumber daya yang diperlukan sekaligus dan tidak berlanjut sampai semuanya diberikan

- Jika proses telah sedang memegang resource tertentu, untuk permintaan berikutnya proses harus melepas dulu resource yg dipegangnya.
- Beri pengurutan linear terhadap resource pada semua proses

7. Algoritma

• Algoritma Bankir

Algoritma ini dapat digambarkan sebagai seorang bankir (Resources) di kota kecil yang berurusan dengan kelompok orang yang meminta pinjaman (Proses). Jadi algoritma bankir ini mempertimbangkan apakah permintaan mereka itu sesuai dengan jumlah dana yang ia miliki, sekaligus memperkirakan jumlah dana yang mungkin diminta lagi. Jangan sampai ia berada pada kondisi dimana dananya habis dan tidak dapat meminjamkan uang lagi. Jika hal tersebut terjadi, maka akan terjadi kondisi deadlock. Agar kondisi aman, maka asumsi setiap pinjaman harus dikembalikan waktu yang tepat.

Untuk sumber daya dengan instan banyak, ketika sebuah proses meminta sumber daya ia harus menunggu terlebih dahulu. Ketika sebuah proses telah mendapatkan semua sumber dayanya ia harus mengembalikannya dalam suatu batasan waktu. Algoritma ini dapat ditulis secara lebih jelas sebagai berikut:

Let P ={P1, P2, P3, …., Pn}be set of all processes while P is not empty do
Seek Pi, an element of P that can finish
If no Pi can be found then
End algorithm: state is unsafe
else
Remove Pi from P
Return resource of Pi to allocated pool
end if
end while
End algorithm: state is safe