Algoritma Ostrich

Menurut Dijkstra (1965) algoritma penjadwalan dapat menghindari Deadlock dan algoritma penjadwalan itu lebih dikenal dengan sebutan algoritma banker. Algoritma ini dapat digambarkan sebagai seorang bankir yang berurusan dengan kelompok orang yang meminta pinjaman.

kepada siapa dia dapat memberikan pinjamannya. Dan setiap pelanggan memberikan batas pinjaman maksimum kepada setiap peminjam dana. Tentu saja si bankir tahu bahwa si peminjam tidak akan meminjam dana maksimum yang mereka butuhkan dalam waktu yang singkat melainkan bertahap. Jadi dana yang ia punya lebih sedikit dari batas maksimum yang dipinjamkan. Lalu ia memprioritaskan yang meminta dana lebih banyak, sedangkan yang lain disuruh menunggu hingga peminta dana yang lebih besar itu mengembalikan pinjaman berikut bunganya, baru setelah itu ia meminjamkan pada peminjam yang menunggu.

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 sampai pada kondisi dimana dananya habis dan tidak dapat meminjamkan uang lagi. Jika demikian maka akan terjadi kondisi deadlock. Agar kondisi aman, maka asumsi setiap pinjaman harus dikembalikan waktu yang tepat.

Secara umum algoritma bankir dapat dibagi menjadi empat struktur data, anggap variabel n adalah jumlah proses dalam sistem dan m jumlah sumber daya yang ada:

1. Available: Sebuah vektor m mengindikasikan sumber daya yang tersedia untul setiap tipe. Jika Avilable[j] = k, dimana k instansi dari tipe Rj yang tersedia.

2. Max: Matriks n x m mendefinisikan maksimal permintaan tiap proses. Jika Max[i,j] = k, maka proses Pi meminta paling banyak k instansi dari sumber daya tipe Rj. 

3. Allocation: Matriks n x m mendefinsikan jumlah sumber daya setiap tipe yang dialokasian oleh setiap proses. Jika Allocation[i,j] = k, maka proses Pi dialokasikan k instansi dari sumber daya Rj.

4. Need: Matriks n x m yang mengindikasikan sisa sumber daya yang dibutuhkan setiap proses.

Jika Need[i,j] = k, maka proses Pi membutuhkan lebih k instansi dari sumber daya Rj untuk menyelesaikan tugasnya. Need[i,j]= Max[i,j] – Allocation[i,j].

Bentuk penyajian algoritma ini secara sederhana, misalkan X dan Y adalah vektor dengan panjang n. sehingga X < Y jika dan hanya jika X[i] < Y[i] untuk semua I = 1,2,..,n. contohnya, jika X=(1,7,3,2) dan Y = (0,3,2,1) maka Y=!X. Y