Algoritma Banker, Algoritma Safty, Algoritma Ostrich

ALGORITMA BANKER

Algoritma Banker dikemukakan oleh Edsger W.Djikstra dan merupakan salah satu metode untuk menghindari deadlock. Struktur data yang digunakan untuk mengimplementasikan algoritma Banker akan menentukan state dari sumber daya yang dialokasikan oleh sistem. Misalnya n = jumlah proses dan m = jumlah tipe resource. Struktur data yang diperlukan :

• 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.

ALGORITMA SAFETY

algoritma safety untuk menentukan apakah sistem berada pada safe state 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.

If Finish [i] = true for all i, then the system is in a safe state.

ALGORITMA BANKER

Algoritma Banker dikemukakan oleh Edsger W.Djikstra dan merupakan salah satu metode untuk menghindari deadlock. Struktur data yang digunakan untuk mengimplementasikan algoritma Banker akan menentukan state dari sumber daya yang dialokasikan oleh sistem. Misalnya n = jumlah proses dan m = jumlah tipe resource. Struktur data yang diperlukan :

• 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.

ALGORITMA OSTRICH

Dalam ilmu komputer, algoritma ostrich 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.

Trade-offs

• Kenyamanan
• Kebenaran

Ini adalah salah satu metode untuk menangani deadlock. Metode lainnya adalah: penghindaran ('s algoritma bankir), pencegahan, deteksi dan pemulihan.
Beberapa algoritma dengan kinerja yang buruk banyak digunakan karena mereka hanya menunjukkan kinerja yang buruk pada kasus yang sengaja dibuat dan jarang terjadi dalam praktik sesungguhnya, contoh-contoh yang khas adalah algoritma simplex dan algoritma pengecekan tipe Standard ML. Masalah seperti integer overflow dalam bahasa pemrograman tetap juga sering diabaikan karena mereka hanya terjadi dalam kasus luar biasa yang tidak muncul untuk input sederhana.

Pendekatan Hybrid

Pendekatan Hybrid menggunakan algoritma Ostrich adalah menentukan bahwa kasus sangat jarang tidak terjadi, dan kemudian beralih dari algoritma lain yang lebih kompleks. Trade-off di sini adalah bahwa jika keadaan berubah atau belum ditemukan, masalah langka dapat kembali terjadi.
Contohnya dapat ditemukan di Hard Mengunci Non-ReadWriteLocker  situs ini, di mana Anda memiliki pilihan untuk menentukan di mana deadlock mungkin terjadi, dan kemudian mematikan deteksi kebuntuan setelah Anda menentukan tidak perlu digunakan.