Deadlock

Keadaan dimana 2 atau lebih proses saling menunggu meminta resources untuk waktu yang tidak terbatas lamanya. Analoginya seperti pada kondisi jalan raya dimana terjadi kemacetan parah. Deadlock adalah efek samping dari sinkronisasi, dimana satu variabel digunakan oleh 2 proses.

Model Deadlock

Model Deadlock

Penyebab Deadlock

• Mutual Exclusion
• Hold and Wait
• Circular Waiting
• No Preemption

Strategi mengatasi Deadlock

• Prevention : memastikan paling sedikit satu penyebab Deadlock tidak berlaku

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

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

Algoritma Ostrich

Algoritma ostrich yaitu strategi mengabaika masalah yang mungkin terjadi atas dasar pada masalah itu sendiri yang mungkin sangat jarang terjadi melainkan jarang banget dah istilanya seperti seolah kita menempel kepala kita di pasir dan berpura-pura bahwa tidak ada masalah.
Maka lebih efektif untuk memungkinkan masalah itu terjadi dibanding upaya pencegahannya itu sendiri.
Pada algoritma ini juga bisa digunakan untuk menangani terjadi deadlock pada pemrograman concurrent jika untuk mendeteksi atau pencegahan lebih tinggi.
Sedikit gambaran pada Algoritma Ostrich ini

• Jangan lakukan apapun, cukup restart sistem
  (ostrich: benamkan kepala ke pasir dan berpura-pura tidak masalah sama sekali)
• Dilakukan bila:
  - Deadlock sangat jarang terjadilah
  - Algoritma deadlock lainnya biayanya lebih tinggi
• Diimplementasikan oleh Windows dan UNIX
• Trade off
  - Kenyamanan (convenience) vs keakuratan (correctness)

Sumber

Algoritma Safety

Algoritma ini untuk menentukan sistem berada dalam state selamat atau tidak diantaranya:
1. Work dan finish vektor dengan panjang (m) dan (n), inisialisasi : work = available dan finish[i] = false untuk i = 1,3,…,n.

2. Cari I yag memenuhi kondisi berikut:
(a) Finish [i] = false
(b) Need , ≤ Work
jika tidak terdapat I ke langkah 4.

3. Work = Work + Allocation
Finish[i] = true
Kembali ke langkah 2.

4.  Jika Finish [i]= true untuk semua I, maka sistem dalam state selamat.

Sumber

Algoritma Banker

Algoritma banker dipelopori oleh Edsger W.Djikstra, untuk metode ini adalah salah satu untuk menghindari akan terjadinya deadlock pada komputer. Pada metode algoritma ini bisa disebut juga algoritma penjadwalan tapi lebih kita kenal dengan sebutan algoritma banker. Algoritma Banker itu sendiri dapat kita gambarkan sebagai seorang bankir yang mempunyai urusan kepada kelompok orang yang meminta pinjam tetapi pada untuk yang meminjamkannya tahu akan batas maksimum peminjaman dana tersebut.
Secara umumnya algortima banker tersebut dibagi menjadi 4 struktur data, untuk variabel (n) adalah jumlah pada sistem dan (m) sendiri ialah jumlah sumber daya yang ada :

1. Allocation :  Matriks (n) X (m) mendefinisikan sumber daya setiap tipe yang dialokasi oleh setiap proses. Jika allocation [i,j]=k, maka proses P1 dialokasikan k  instansi dari sumber daya Rj. 
2. Available :  Sebuah vektor (m) menandakan sumber daya yg ada untuk setiap tipe, jika available [j]= k, dimana k instansi dari tipe Rj yang ada.
3. Need : Matriks (n) X (m) menandakan sisa sumber daya yang dibutuhkan setiap proses. Jika need [i,j]= k, maka proses Pi membutuhkan k  instansi dari sumber daya Rj untuk menyelesaikan tugasnya. Need[i,j]= Max[i,j] – Allocation[i,j]. 
4. Max : Matriks (n) X (m) menandakan maksimal permintaan tiap proses. Jika Max [i,j]= k, maka proses Pi meminta paling banyak k  instansi dari sumber daya tipe Rj.

Untuk membentuk penyajian algoritma ini secara sederhananya, misalkan X dan Y adalah vektor dengan panjang n. Sehingga X ≤ Y jika dan hanya jika X[i] ≤ Y[i] untuk semua l = 1,2..,n. contohnya : jika X=(1,7,3,2) dan Y(0,3,2,1) maka Y≤X. Y≤X dan Y≠X
Disamping itu semua Algoritma ini :

– Proses harus “declare” max. kredit resource yang diinginkan
– Proses dapat block (pending) sampai resource diberikan
– Menjamin sistem dalam keadaan safe state
– OS menjalankan algoritma banker
* Saat proses melakukan request resource
* Saat proses terminate atau release resource yang digunakan => memberikan resource ke proses yang pending
request.

Ada sedikit contoh gambar Algoritma Banker

Kelemahan dari algoritma ini adalah:

• Proses kebanyakan belum mengetahui jumlah maksimum resource yang dibutuhkannya
• Beberapa resource itu sendiri dapat diambil dari sistem sewaktu-waktunya
• Algoritma membuat sistem hingga waktu yang tidak terbatas
• Jumlah proses tidak tetap

Sumber