Banker's Algorithm | Safety Algorithm

The resource allocation algorithm can easily find deadlock situation when cycle exist in the RAG for single instances type resources, but resources allocation algorithm may be fail to recognize deadlock for multiple instances type resources. We use Banker’s algorithm to avoidence  deadlock  in multiple instances type resources. Each process must a priori claim maximum use. We need some data structures as following; here ‘n’ is the number of processes in the system and ‘m’ is the number of resources types.

 

  • Available is a vector of length ‘m’ that defines  number of resources available of each type.

  • Maximum is the n x m matrix that defines maximum demands of each process.

  • Allocation is the n x m matrix that defines the number of resources of each type currently allocated to each process.

  • Need is the n x m matrix that defines remaining resources need of each process.

Safety Algorithm

This algorithm is used to find a system is in safe state or not. Algorithm has overall time complexity is O(mn^2).

(i) Two vectors ‘work’ and ‘finish’ of length m and n respectively. Where,

  • Work = available, and finish[i] = false for i = 0, 1, …., (n-1).

(ii) Find an index i such that

  • Finish[i] = = false

  • Need[i] ≤ work

Else go to step (iv)

(iii) work = work + allocation[i]

Finish[i] = true

Go to step (ii)

(iv) if finish[i] = = true for all i, then the system is in safe state, else system is unsafe state.

 

Resource Request Allocation

‘Request’ is a vector for process Pi, if request[j] = = k, then process Pi wants k instances of resource type Rj.

(i) if request[i] ≤ max_need[i], then go to step(ii) else error as request exceeded maximum needs.

(ii) if request[i] ≤ available, then go to step(ii), else Pi must wait, since resources are not available.

(iii) System pretend to have allocated the requested resources to process Pi by modifying following states;

  • Available = available[i] - request[i] ;

  • Allocation[i] = allocation[i] + Request[i] ;

  • Need[i] = Need[i] - request[i] ;

(iv) if resulting state is safe state, then the resources are allocated to process Pi, else system is in unsafe and process Pi must wait.

 

An Example:

Consider the following example with five processes and three resources of multiple instances:

 

 

Maximum Need

Allocated

Remaining Available

 

A B C

A B C

A B C

P1

3 2 2

2 0 0

3 3 2

P2

9 0 2

3 0 2

 

P3

2 2 2

2 1 1

 

P4

4 3 3

0 0 2

 

 

Solution:

            Remaining need =  Maximum need  - allocated

 

 

Maximum Need

Allocated

Remaining Available

Remaining Need

 

A B C

A B C

A B C

A B C

P1

3 2 2

2 0 0

3 3 2

1 2 2

P2

9 0 2

3 0 2

 

6 0 0

P3

2 2 2

2 1 1

 

0 1 1

P4

4 3 3

0 0 2

 

4 3 1

 

Initially, we have remaining available resources 3, 3, 2 instances of A B C. So, we can satisfy the requirements of either process P1 or P3. If we start with P1 then process P1 gets 1, 2, 2 instances of resources of A B C; completed its execution and releases all 4, 5, 4 now we proceed with process P3, and P4 and then process P2. So, safe sequence is P1, P3, P4 and P2.

Contributor's Info

Created: Edited:
0Comment