Deadlock Avoidance: Algoritma Banker

Algorimtma resource-allocation-graph tidak dapat diterapkan pada sistem yang memiliki beberapa sumber daya untuk pengalokasiannya, dengan kata lain tidak dapat diterapkan pada multiple-instances atau hanya dapat diterapakan pada single-instance dari setiap jenis sumber daya. Sehingga untuk menghindari terjadinya deadlock pada sistem multiple-instances, maka dapat menggunakan algoritma Banker yang dibantu dengan algoritma safety dan algoritma resource request. Nama algoritma ini dipilih karena dalam pengaplikasiannya mirip dengan sistem perbanka, yaitu sistem bank tidak pernah mengalokasikan uang tunai (cash) yang tersedia sedemikian rupa hingga tidak dapat lagi memenuhi kebutuhan semua pelanggannya.

Saat proses baru memasuki sistem, maka proses tersebut harus mendeklarasikan atau mendefenisikan jumlah maksimal resource instance yang mungkin diperlukan/dibutuhkan dari setiap jenis/tipe resource. Jumlah resource instance yang diperlukan tidak boleh melebihi jumlah resource yang terdapat pada sistem. Sehingga sistem harus menentukan apakah pengalokasian resource instance tersebut akan membuat sistem dalam kondisi safe state. Jika safe maka berbagai resource instance yang diperlukan akan dialokasikan, sebaliknya jika unsafe maka proses tersebut harus menunggu sampai proses lainnya melepaskan (release) beberapa resource instace yang dibutuhkan hingga cukup.

Beberapa struktur data yang harus dipertahakan agar dapat mengimplementasikan algoritma Banker. Sturktur-struktur data ini membungkus (encode) keadaan/state dari sistem resource-allocation. Berikut struktur data yang diperlukan, sebelumnya kita misalkan pada sistem n adalah jumlah proses dan m adalah jumlah tipe sumber daya.

• Struktur data Available. Vektor dengan panjang m – menunjukkan jumlah resource instance yang tersedia untuk setiap jenisnya. Jika tersedia [j] = k, dan k resource instance dari jenis Rj yang tersedia.
• Sturktur data Max. Matriks n x m – mendefenisikan permintaan (request) maksimum dari setiap proses. Jika Max[i][j] = k, maka proses Pi dapat meminta paling banyak k resource instance dari jenis Rj.
• Sturktur data Allocation. Matriks n x m mendefenisikan jumlah resource dari setiap jenisnya yang sedang dialokasikan untuk setiap proses. Jika Allocation [i][j] = k, maka proses Pi saat ini dialokasikan k resource instance dari jenis Rj.
• Struktur data Need. Matriks n x m menunjukkan/mengindentifikasikan sisa resource yang dibutuhkan untuk setiap proses. Jika Need[i][j] = k, maka proses Pi mungkin memerlukan k lebih banyak resource instance dari jenis Rj untuk menyelesaikan tugasnya. Perhatikan bahwa Need[i][j] = Max[i][j] – Allocation[i][j].

Struktur data diatas bervariasi dari waktu ke waktu baik dalam ukuran maupun nilainya. Berikut beberapa notasi untuk menyederhanakan penyajian algoritma Bankir. Misal X dan Y adalah dengan panjang n. dimana X ≤ Y hanya jika X[i] ≤ Y[i] untuk semua i = 1, 2, 3, …, n. Sebagai contoh, jika X = (1,7,3,2) dan Y = (0,3,2,1), maka Y ≤ X. selain itu, Y < X jika Y ≤ X dan Y ≠ X.

Setiap baris (row) pada matrik Allocation dan Need dapat dianggap sebagai vektor, dan menyebutnya sebagai Allocation_i dan Need_i. Vektor Allocation_i menspesifikasikan/menentukan resource yang saat ini dialokasikan/digunakan untuk memproses Pi; dan vektor Need_i menentukan sisa resource yang masih diminta oleh proses Pi untuk menyelesaikan tugasnya.

Algoritma Safety

Untuk melengkapi agar algoritma Banker dapat mengetahui apakah sistem dalam safe state atau unsafe, maka dapat menggunakan algoritma safety ini, berikut penjelasannya dalam variabel yang terdiri dari beberapa langkah.

• 1. Misal Work adalah vektor dengan panjang m, dan Finish adalah vektor dengan panjang n. inisialisasi variabel Work = Available dan Finish[i] = false untuk i = 0, 1, …, n -1.
• 2. Cari index i, sehingga keduanya (a dan b) menjadi.
  • a. Finish[i] == false
  • b. Need_i ≤ Work
  • Jika index i tidak ada yang menjadi poin (a) dan poin (b), lanjut ke langkah 4, dan jika ada lanjut ke langkah 3.
• 3. Defenisikan variabel berikut menjadi.
  • Work = Work + Allocation_i
  • Finish[i] = true
  • Kemudian kembali ke langka 2.
• 4. Jika Finish[i] == true untuk semua i, maka sistem dalam keadaan safe state.

Algorima ini memerlukan urutan operasi m x n² untuk menentukan apakah sistem dalam keadaan safe state atau unsafe.

Algoritma Resource-Request

Algoritma ini digunakan untuk menentukan apakah permintaan resource terhadap proses dapat dikabulkan/diberikan dengan aman (safety).

Misalkan Request_i menjai vektor permintaan untuk proses Pi. Jika Request_i[j] == k, maka proses Pi menginginkan k resource instance dari tipe/jenis Rj. Ketika permintaan resource dibuat oleh proses Pi, tindakan berikut akan dilakukan.

• 1. Jika Request_i ≤ Need_i, maka lanjutkan ke langkah 2. Jika tidak, maka ajukan kondisi kesalahan, karena proses telah melebihi klaim maksimum.
• 2. Jika Request_i ≤ Available, maka lanjutkan ke langkah 3. Jika tidak, maka proses Pi harus menunggu, karena resource tidak tesedia.
• 3. Buat sistem menjadi seakan-akan telah mengalokasikan resource yang diminta untuk proses Pi, dengan memodifikasi status/state menjadi sebagai berikut.
  • Available = Available – Request_i
  • Allocation_i = Allocation_i + Request_i
  • Need_i = Need_i – Request_i

Pada langka ke 3, jika hasil resource-allocation kodisinya safe state, berarti transaksi telah selesai, dan resource proses Pi dapat dialokasikan. Namun jika kondisi new state dari resource-allocation adalah unsafe, Pi harus menunggu Request_i, dan kondisi old state resource-allocation dipulihkan (restore).

Contoh Ilustrasi Algoritma Banker

Untuk mengilustrasikan penggunaan algoritma Banker, misal terdapat 5 proses yaitu P0, P1, P2, P3, P4; dan terdapat 3 tipe resource yaitu A, B, dan C. Setiap tipe resource memiliki resource instance, untuk resource tipe A memiliki 10 resource instances; untuk resource tipe B memiliki 5 resource instances, dan untuk resource tipe C memiliki 7 resource instances. Selanjutnya permisalkan pada T0 telah diambil gambaran singkat (snapshot) sebagai berikut.

Gambar Penggunaan Algoritma Banker (old state).

Isi matrik Need dedefenisikan dari Max – Allocation. Pada tabel ilustrasi penggunaan algoritma diatas, yang mereprenentasikan kondisi sistem, dapat diklaim bahwa kondisinya adalah safe state, dengan safe sequence adalah <P1, P3, P4, P2, P0> sebagai kriteria safety. Selanjutnya misalkan sekarang proses P1 meminta resource instance tambahan dari tipe A hanya 1, dan dari tipe C sebanyak 2, jadi Request1 = (1,0,2). Untuk memutuskan apakan permintaan ini dapat segera dikabulkan, maka pertama-tama dilakukan pemeriksaan bahwa Request1 ≤ Available, yaitu (1,0,2) ≤ (3,3,2) yang berarti benar (true). Kemudian menganggap seakan-akan permintaan ini telah dipenuhi dan sebagai old state, dan selanjutnya dianggap sebagai new state.

Gambar Penggunaan Algoritma Banker (new state).

Kita harus menentukan apakah new state sistem ini safe. Jika algoritma Banker ini dijalankan maka safe sequence adalah <P1, P3, P4, P0, P2> sebagai kriteria safety, sehingga dapat segera memenuhi/mengabulkan permintaan dari proses P1. Perlu diingat bahwa request pertama kali dari setiap proses dianggap sebagai new state, selanjutnya jika berhasil atau dapat dipenuhi (safe), maka new state tersebut menjadi old state, dan request dari proses berikutnya dianggap sebagai new state, tetapi jika tidak berhasil atau tidak dapat dipenuhi (new state) maka old state akan dipulihkan, dan begitulah seterusnya.

Untuk observasi sistem lainnya, jika terdapat permintaan pengalokasian resource instance untuk setiap jenis A, B, dan C dari proses P4, yaitu Request4 (3,3,0) maka permintaan P4 tidak dapat dipenuhi/diberikan, karena jumlah resource dari tipe A tidak tersedia; dan selanjutnya terdapat permintaan resource instance dari Proses P0, yaitu Request0 (0,2,0) maka permintaan ini juga tidak dapat dikabulkan karena state yang dihasilkan adalah unsafe yaitu karena jumlah resource dari tipe A dan B tidak tersedia.

Referensi

1. Operating Systems: Internals and Design Principles (8th Edition), William Stallings, 2014.
2. Operating System Concepts (9th Edition in Chinese) by Abraham Silberschatz et al.
3. The Linux Programming Interface: A Linux and UNIX System Programming Handbook, Michael Kerrisk.