Algoritma Banker

Hy everybody....hehehe

Saya akan membahas tentang deadlock dengan algoritma Banker, Safety, dan Ostrich. Karena untuk menangani suatu deadlock dilakukan beberapa proses dengan algoritma-algoritma tersebut. Berikut algoritma-algoritma yang sering digunakan dalam penanganan dan pencegahan deadlock. tapi yang pertama saya akan membahas tentang algoritma Banker.

ALGORITMA BANKER

Nama Banker dari Banker’s algorithm diperoleh dari fakta bahwa algoritma ini dapat digunakan oleh bank untuk memastikan bank tidak akan mengalami kekurangan resource, dalam hal ini uang nasabah. Dengan algoritma ini, bank dapat memastikan bahwa ketika nasabah menarik uang, bank tetap pada kondis safe state. Jika penarikan uang oleh nasabah tidak membuat bank keluar dari safe state (masuk ke dalam unsafe state), maka penarikan dan akan diijinkan. Jika tidak, nasabah harus menunggu hingga ada tambahan uang (deposit dari nasabah lain) di dalam kas bank.
Banker’s algorithm adalah algoritma resource allocation dan deadlock avoidance yang dikembangkan oleh Edsger Dijkstra. Algoritma ini menguji tingkat keamanan dari kemungkinan deadlock dengan melakukan simulasi berdasarkan jumlah maksimum resources dan kemudian mengecek kondisi safe state terhadap semua kemungkinan kondisi deadlock dari semua aktifitas yang berada dalam posisi pending, sebelum memutuskan pengalokasian resource.
Algoritma Banker’s ini dijalankan oleh sistem operasi ketika proses melakukan request resource. Penghindaran terhadap deadlock dilakukan dengan menolak atau menunda suatu request jika sekiranya penerimaan terhadap request tersebut dapat membawa sistem dalam kondisi unsafe state. Berdasar algoritma ini, ketika suatu proses masuk ke dalam sistem, proses ini harus memberikan jumlah maksimum resource yang diperlukan dimana resource tersebut tidak boleh melebihi total resource yang dimiliki oleh sistem. Selain itu, ketika suatu proses mendapatkan resource yang diinginkan, proses tersebut harus mengembalikan resource yang digunakan dalam jangka waktu tertentu.
Agar algoritma Banker’s ini dapat berkerja, harus ada tiga hal yang dimiliki/diketahui, yaitu:

1. Jumlah resource dari tiap proses yang mungkin di request.
2. Jumlah resource dari tiap proses yang sedang di pegang atau di gunakan (hold).
3. Jumlah sisa resource yang dimiliki oleh sistem.
   

Resource hanya dapat diberikan pada suatu proses jika:

1. request* ≤ max**, jika tidak set error, karena request melebihi jumlah klaim sebelumnya.
2. request ≤ available***, jika tidak proses harus menunggu hingga resource yang diminta ada.
   

*request adalah jumlah resource yang di request oleh proses.
**max adalah jumlah resource yang sebelumnya sudah di klaim oleh proses. Seperti yang telah disebutkan di awal, ketika masuk ke dalah sistem, proses harus memberikan jumlah maksimum proses yang diperlukan.
***available adalah jumlah sisa resource system yang sedang tidak terpakai.
Berikut ini adalah contoh lagi mengenai safe state dalam kaitannya dengan Banker’s Algorithm untuk multiple resources. Anggap suatu sistem memiliki proses  dengan resource A, B, C, dan D. Mapping proses dan resource tampak seperti tabel dibawah.

	P1		P2		P3		Free resources	Total Resources
	current	max	current	max	current	max
A	1	3	1	1	2	1	3	7
B	2	3	0	2	2	3	1	5
C	2	2	3	3	1	5	1	7
D	1	2	3	4	0	0	2	6

State dalam tabel diatas dianggap safe state jika semua proses dengan resource yang diperlukan dapat tereksekusi. Sistem tidak dapat mengetahui kapan suatu proses selesai eksekusi dan jumlah proses yang diperlukan saat eksekusi, karena itu sistem akan mengasumsikan bahwa resources yang diperlukan adalah maksimum, dengan asumsi proses segera mengembalikan resource tersebut ketika eksekusinya telah selesai. Dengan asumsi maksimum ini, jika ternyata proses tidak memerlukan resource pada jumlah maksimum, maka justru akan memperingan kerja sistem.

Berdasarkan asumsi diatas, sistem akan menentukan safe state dengan cara melakukan (simulasi) pengujian  terhadap proses dengan permintaan resource maksimum. Misalkan P1 meminta lagi 2 resource A, 1 resource B, dan 1 resource D, contoh simulasi pengujian oleh sistem adalah sebagai berikut.

• P1 menggunakan lagi 2 resource A, 1 resource B, dan 1 resource D, sehingga sampai pada maksimum resources yang dimintanya. Sisa available resources adalah 1 resources A, 1 resources C, dan 1 resource D.
  

	P1		P2		P3		Free resources	Total Resources
	current	max	current	max	current	max
A	3	3	1	1	2	1	1	7
B	3	3	0	2	2	3	0	5
C	2	2	3	3	1	5	1	7
D	2	2	3	4	0	0	1	6

• P1 terminates (proses P1 telah selesai) dan mengembalikan 3 resource A, 3 resource B, 2 resource C, dan 2 resource D. Free resources yang dimiliki sistem sekarang adalah 4 resource A, 3 resource B, 2 resource C, dan 3 resource D.
  

	P1		P2		P3		Free resources	Total Resources
	current	max	current	max	current	max
A	0	3	1	1	2	1	4	7
B	0	3	0	2	2	3	3	5
C	0	2	3	3	1	5	3	7
D	0	2	3	4	0	0	3	6

• P2 mengambil lagi 2 resources B dan 1 resources D, kemudian terminate. Sisa resources yang dimiliki sistem sekarang adalah 5 resources A, 3 resources B, 6 resources C, dan 6 resources D.
  

• P3 mengambil 4 resources C dan kemudian terminate. Sisa resources adalah 6 resources A, 4 resources B, 7 resources C, dan 6 resources D.
  

Simulasi atau perhitungan diatas (catatan:baru simulasi) menunjukkan bahwa semua proses dapat berjalan hingga selesai dan mendapatkan resources maksimum masing-masing. Permintaan 2 resource A, 1 resource B, dan 1 resource oleh proses P1 tidak akan membawa ke kondisi unsafe state. Artinya sistem tetap akan berada dalam safe state. Sebagai hasil akhir, sistem akan mengijinkan proses P1 mengambil resources yang diminta.
Sebagai contoh untuk unsafe state, lakukan simulasi atau perhitungan seperti di atas dengan kondisi awal state awal P2 menggunakan 1 resource B lebih banyak (3 resource B).
Secara umum, gambaran algoritma ketika suatu proses meminta resources adalah sebagai berikut.

• Dapatkah permintaan terhadap resources diberikan? (berkaitan dengan ada tidaknya resources).
• Jika ternyata ada resources tersisa dan resource tersebut di berikan, apakah akan membawa ke kondisi safe state? Pada titik inilah Banker’s algorithm bekerja.
  
  
  Nah itulah penjelasan tentang algoritma banker. semoga bermanfaat... (^_^)
  di lanjut postingan berikut nya tentang algoritma Safty.