The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.

Following Data structures are used to implement the Banker’s Algorithm:

Let ‘n’ be the number of processes in the system and ‘m’ be the number of resources types.

Available : 

• It is a 1-d array of size ‘m’ indicating the number of available resources of each type.


• Available[ j ] = k means there are ‘k’ instances of resource type R_j

Max :

• It is a 2-d array of size ‘n*m’ that defines the maximum demand of each process in a system.


• Max[ i, j ] = k means process P_i may request at most ‘k’ instances of resource type R_j.

Allocation :

• It is a 2-d array of size ‘n*m’ that defines the number of resources of each type currently allocated to each process.


• Allocation[ i, j ] = k means process P_i is currently allocated ‘k’ instances of resource type R_j

Need :

• 
  
  
  
  •  It is a 2-d array of size ‘n*m’ that indicates the remaining resource need of each process.
  
  
  • Need [ i,   j ] = k means process P_i currently need ‘k’ instances of resource type R_j
  
  
  
  

for its execution.

• Need [ i,   j ] = Max [ i,   j ] – Allocation [ i,   j ]

 

Allocation_i specifies the resources currently allocated to process P_i and Need_i specifies the additional resources that process P_i may still request to complete its task.

Banker’s algorithm consists of Safety algorithm and Resource request algorithm

For example, suppose at time T_0. The status of system is as following

Allocation         Max          Available

A     B     C       A   B   C      A     B     C

P_0    0      1      0       7    5   3      3      3      2

P_1     2      0     0       3    2   2

P_2    3      0      2       9    0   2

P_3    2      1       1       2    2   2

P_4    0      0      2       4    3   3

and the max-allocation matrix is as following:

Need

A     B     C

P_0    7      4      3

P_1     1      2      2

P_2     6      0      0

P_3     0      1      1

P_4     4      3      1

first, assign resources to p1, and the available is 5 3 2

then assign resources to p3, and the available is 7 4 3

later assign resources to p4, and the available is 7 4 5

then assign resources to p2, and the available is 10 4 7

at last assign resources to p1 and the available is 12 5 8