algoritma menangani deadlock

1. Algoritma Banker

Algoritma ini mencegah terjadinya deadlock dengan memutuskan apakah menyetujui atau menunda permintaan sumber daya oleh proses. Ketika sebuah proses meminta sumber daya, maka permintaan tersebut harus diperiksa oleh bankir. Analogi dari algoritma Banker dengan sistem operasi adalah

1.      Nasabah merupakan proses-proses yang sedang berjalan.

2.      Uang (dana yang dimiliki bank) merupakan sumber daya.

3.      Bankir merupakan sistem operasi.

Dalam algoritma Banker, setiap nasabah memiliki batas kredit dan apabila seorang nasabah telah mencapai batas kredit pinjaman maksimum, maka diasumsikan nasabah tersebut telah menyelesaikan semua permasalahan bisnisnya dan dapat mengembalikan semua pinjamannya kepada bank. Tetapi ada kalanya, seorang nasabah dapat menyelesaikan semua permasalahan bisnisnya dan mengembalikan semua pinjamannya kepada bank sebelum mencapai batas kredit maksimum.

Bankir adalah seorang peminjam yang konservatif. Ketika sebuah proses meminta peminjaman sumber daya, bankir melihat buku bank dengan cermat dan berusaha untuk memutuskan apakah peminjaman tersebut dapat menyebabkan keadaan deadlock (setelah peminjaman tersebut disetujui).

Keputusan bankir dibuat dengan berpura-pura menyetujui peminjaman sumber daya dan kemudian menganalisis keadaan sistem. Setelah peminjaman, akan terdapat sejumlah sumber daya tersisa di dalam sistem. Kita asumsikan masing-masing proses meminta batas maksimum sumber daya. Jika bankir memiliki cukup sumber daya yang tersisa untuk memastikan bahwa semua proses dapat berakhir dengan aman. Ini menunjukkan keadaan berada dalam safe state dan peminjaman disetujui.

Tetapi apabila setelah peminjaman, bankir tidak dapat menjamin semua proses dapat berakhir dengan semestinya, maka ini disebut unsafe state. Dalam kasus ini, peminjaman akan ditunda atau diblok hingga peminjaman tidak  menyebabkan unsafe state pada sistem.

Pada algoritma Banker ini, kondisi mutual exclusion, hold-and-wait, dan no-preemption diijinkan dan proses-proses melakukan klaim penggunaan sumber daya –sumber daya yang diperlukan. Proses-proses diizinkan mengenggam sumber daya-sumber daya sambil meminta dan menunggu sumber daya-sumber daya lain serta sumber daya-sumber daya itu tidak diijinkan untuk di-preempt proses lain.

            Proses-proses dapat meminta satu sumber daya pada satu waktu. Sistem operasi dapat memberikan akses sumber daya atau menolak permintaan. Jika ditolak, proses masih mengenggam sumber daya yang telah dialokasikan untuknya dan menunggu selama waktu tak berhingga sampai permintaannya dapat diberikan.

            Sistem hanya memberikan permintaan yang menghasilkan state selamat. Permintaan proses yang akan menghasilkan state tak selamat secara berulang ditolak sampai permintaan dapat dipenuhi. Tentunya karena sistem selalu memelihara agar dalam safe state, cepat atau lambat (yaitu dalam waktu yang berhingga) semua permintaan dapat dipenuhi dan semua proses dapat berakhir

     2. Algoritma Safty

Algoritma ini adalah algoritma yang dipakai untuk menentukan apakah sebuah sistem berada dalam keadaan safe state atau unsafe state.

Algoritma ini dipakai oleh bankir untuk memeriksa keadaan sistem setelah peminjaman, apakah berada dalam kondisi safe atau tidak. Apabila berada dalam kondisi safe, maka ini berarti sumber daya yang tersisa dapat menjamin pemenuhan pinjaman oleh semua proses yang masih aktif, semua proses akan berakhir dengan aman dan tidak akan  menyebabkan deadlock. Apabila kondisi unsafe, maka ini berarti terdapat kemungkinan untuk terjadinya deadlock


    3. Algoritma Ostrich

Algoritma ini dipakai bankir untuk menentukan apakah peminjaman sumber daya disetujui atau tidak. Algoritma ini dieksekusi oleh sistem setiap terjadinya permintaan peminjaman atas sumber daya oleh proses.

Implementasi algoritma ini adalah dengan berpura-pura memberikan pinjaman kepada proses dan menganalisis keadaan setelah pinjaman (sumber daya dan proses yang tersisa) dengan Safety Algorithm. Apabila menghasilkan keadaan safe, maka pinjaman disetujui. Bila tidak, maka pinjaman diblokir atau ditunda.