Banker’s Algorithm

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.

Let,

• 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

Rj

available.

Max: n x m matrix. If Max [i,j] = k, then process Pimay request at most k instances of resource

type Rj

.

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

task.

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

Safety Algorithm

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

(b) Needi≤Work

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.