This algorithm can be used in banking system to ensure that the bank never allocates all its available cash such that it can no longer satisfy the needs of all its customer. This algorithm is applicable to a system with multiple instances of each resource type. When a new process enter in to the system it must declare the maximum number of instances of each resource type that it may need. This number may not exceed the total number of resources in the system. Several data structure must be maintained to implement the banker’s algorithm.
• n = number of processes
• m = number of resources types
Available: Vector of length m. If Available[j] = k, there are k instances of resource type
Max: n x m matrix. If Max [i,j] = k, then process Pimay request at most k instances of resource
Allocation: n x m matrix. If Allocation[i,j] = k then Pi
is currently allocated k instances of Rj.
Need: n x m matrix. If Need[i,j] = k, then Pi
may need k more instances of Rj
to complete its
Need [i,j] = Max[i,j] – Allocation [i,j].
1. Let Workand Finish be vectors of length m and n, respectively. Initialize:
Work = Available
Finish [i] = false for i = 0, 1, …,n- 1.
2. Find and i such that both:
(a) Finish [i] = false
If no such i exists, go to step 4.
3. Work = Work + Allocation
Finish[i] = true
go to step 2.
4. If Finish [i] == true for all i, then the system is in a safe state.