Deadlock
Untuk menangani deadlock ada yang dinamakan, Algoritma Banker, Algoritrma Safty, dan Algoritma Ostrich. Nah dibawah ini lebih jelasnya :
A). Algoritma Banker
Algoritma banker yaitu algoritma reseource allocation graph yang tidak bisa di aplikasikan pada suatu sitem yang memiliki beberapa anggota pada setiap tipe sumber dayanya. Pada saat memproses sebelumnya harus menentukan jumlah sumber daya maksimun yang dibutuhkannya.
Pada algoritma banker akan menentukan yang namanya state dari sumber daya yang dialokasikan oleh sisistemnya, misalnya:
n=jumlah proses m=jumlah tipe resource
dan sumber data yang diperlukannya adalah :
• Available : Vektor panjang m. Jika Available[j] = k, terdapat k anggota tipe sumber daya Rj yang tersedia.
• Max : matrik n x m. Jika Max[i, j] = k, maka proses Pi meminta paling banyak k
anggota tipe resource Rj.
• Allocation : matrik n x m. Jika Allocation[i, j] = k maka Pi sedang dialokasikan k
anggota tipe resource Rj.
• Need : matrik n x m. Jika Need[i, j] = k, maka Pi membutuhkan k anggota tipe
resource Rj untuk menyelesaikan task. Need[i, j] = Max[i, j] – Allocation[i, j].
Beberapa notasi yang perlu diketahui adalah misalnya X dan Y adalah vektor
dengan panjang n. X ≤ Y jika dan hanya jika X[i] ≤ Y[i] untuksemua i = 1, 2, .., n.
Sebagai contoh jika X = (1, 7, 3, 2) dan Y = (0, 3, 2, 1) maka Y ≤ X.
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.
B). Algoritma Safty
adalah Algoritma ini untuk menentukan apakah sistem berada dalam state selamat atau
tidak.
1. Work dan Finish adalah vector dengan panjang m dan n. Inisialisasi : Work =
Available dan Finish[i] = false untuk i = 1,3, …, n.
2. Cari i yang memenuhi kondisi berikut :
(a) Finish [i] = false
(b) Needi ≤ Work
Jika tidak terdapat i ke langkah 4.
3. Work = Work + Allocationi
Finish[i] = true
Kembali ke langkah 2.
4. Jika Finish [i] == true untuk semua i, maka sistem dalam state selamat.
A B C A B C A B C
P0 0 1 0 7 4 3 2 3 0
P1 3 0 2 0 2 0
P2 3 0 1 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1
Kemudian yang harus ditentukan adalah apakah sistem berada dalam state selamat. Setelah mengeksekusi algoritma safety ternyata urutan memenuhi kriteria safety. Setelah sistem berada pada state diatas, permintaan (3,3, 0) oleh P4 tidak dapat dipenuhi karena sumber daya tidak tersedia. Permintaan (0, 2, 0) oleh P1 juga tidak dapat dipenuhi karena meskipun sumber daya tersedia, hasilnya state tidak selamat.
C). Algoritma Ostrich
Adalah adalah strategi mengabaikan masalah yang mungkin terjadi atas dasar bahwa masalah itu mungkin sangat jarang terjadi - "menempel kepala di pasir dan berpura-pura bahwa tidak ada masalah". Dengan mengasumsikan bahwa lebih efektif untuk memungkinkan masalah itu terjadi dibandingkan upaya pencegahannya.
Pendekatan ini dapat digunakan dalam menangani deadlock pada pemrograman concurrent jika deadlock diyakini sangat jarang terjadi, dan jika biaya untuk mendeteksi atau pencegahan lebih tinggi.
• Available : Vektor panjang m. Jika Available[j] = k, terdapat k anggota tipe sumber daya Rj yang tersedia.
• Max : matrik n x m. Jika Max[i, j] = k, maka proses Pi meminta paling banyak k
anggota tipe resource Rj.
• Allocation : matrik n x m. Jika Allocation[i, j] = k maka Pi sedang dialokasikan k
anggota tipe resource Rj.
• Need : matrik n x m. Jika Need[i, j] = k, maka Pi membutuhkan k anggota tipe
resource Rj untuk menyelesaikan task. Need[i, j] = Max[i, j] – Allocation[i, j].
Beberapa notasi yang perlu diketahui adalah misalnya X dan Y adalah vektor
dengan panjang n. X ≤ Y jika dan hanya jika X[i] ≤ Y[i] untuksemua i = 1, 2, .., n.
Sebagai contoh jika X = (1, 7, 3, 2) dan Y = (0, 3, 2, 1) maka Y ≤ X.
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.
B). Algoritma Safty
adalah Algoritma ini untuk menentukan apakah sistem berada dalam state selamat atau
tidak.
1. Work dan Finish adalah vector dengan panjang m dan n. Inisialisasi : Work =
Available dan Finish[i] = false untuk i = 1,3, …, n.
2. Cari i yang memenuhi kondisi berikut :
(a) Finish [i] = false
(b) Needi ≤ Work
Jika tidak terdapat i ke langkah 4.
3. Work = Work + Allocationi
Finish[i] = true
Kembali ke langkah 2.
4. Jika Finish [i] == true untuk semua i, maka sistem dalam state selamat.
A B C A B C A B C
P0 0 1 0 7 4 3 2 3 0
P1 3 0 2 0 2 0
P2 3 0 1 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1
Kemudian yang harus ditentukan adalah apakah sistem berada dalam state selamat. Setelah mengeksekusi algoritma safety ternyata urutan memenuhi kriteria safety. Setelah sistem berada pada state diatas, permintaan (3,3, 0) oleh P4 tidak dapat dipenuhi karena sumber daya tidak tersedia. Permintaan (0, 2, 0) oleh P1 juga tidak dapat dipenuhi karena meskipun sumber daya tersedia, hasilnya state tidak selamat.
C). Algoritma Ostrich
Adalah adalah strategi mengabaikan masalah yang mungkin terjadi atas dasar bahwa masalah itu mungkin sangat jarang terjadi - "menempel kepala di pasir dan berpura-pura bahwa tidak ada masalah". Dengan mengasumsikan bahwa lebih efektif untuk memungkinkan masalah itu terjadi dibandingkan upaya pencegahannya.
Pendekatan ini dapat digunakan dalam menangani deadlock pada pemrograman concurrent jika deadlock diyakini sangat jarang terjadi, dan jika biaya untuk mendeteksi atau pencegahan lebih tinggi.
