Banker’s algorithm in Deadlocks

Banker’s algorithm in Deadlocks

• Banker’s algorithm is the deadlock avoidance algorithm that is applicable to the resource allocation system having multiple instances of each resource type.
• The name banker’s algorithm depicts the similarity of the concept used in the field of banking. A banker never allots the cash available in such a manner that the banker cannot fulfill needs of its clients.
• The banker’s algorithm has two parts : Safety algorithm and resource request algorithm.
• The safety algorithm is applied by an operating system to determine whether or not a system is in safe state. The resource request algorithm is applied by an operating system to determine whether or not a request forwarded by a process for acquiring resource would lead the system to an unsafe state.

Banker’s algorithm is based on the following assumptions :

1. The system has a limited number of resources.
2. Each process must use the resource for a finite amount of time.
3. Each process must declare the maximum number of instances of each resource type that it may need, when it enters the system.
4. The number of instances of each resource type required by the process may not exceed the total number of resources in the system.
5. When a user requests a set of resources, the system must determine whether the allocation of these resources will leave the system in safe state. If it will the resources are allocated; otherwise, the process must wait until some other process release enough resources.

• Banker’s algorithm uses several data structures in form of vectors and matrices for its implementation. There are:

Let there be n processes and m resource types.

1. Available : It is a vector of order m. It indicates the number of resources of each type that are currently available.
2. Maximum : It is a request matrix of order of n x m. It indicates the maximum demand of each process.
3. Allocation : It is a request matrix of order n x m. It indicates the number of resources currently allocated to each process.
4. Need : It is a matrix of the order n x m. It indicates the number of resources that a process may need in future.
5. Finish : It is the vector of order n. It contains the Boolean value (true of false) to indicate if a process has been allocated the required resources and has released all of its resources after using them.

i. Safety Algorithm

The safety algorithm finds out whether the system is in safe state. The algorithm is given as follows :

1. Initialization Set

Finish [i] = false for i = 1 to n

2. Compute available and need

Available vector can be obtained directly from given conditions

Set need [i, jl = Maximum [i, j] – Allocation [i, j] for all processes i and for all resource type j.

3. Find a process i such that

Set finish [i] = false and need [i, j]<= Available [j] for all resource type.

(This implies that P, needs the resources, which the system can easily grant as its need is less than available resources) If no such i exists go to step 5

4. Schedule process i for execution so that it can utilize the resources and then free up its resources by doing the following :

Set Available [j] = Available [j] + Allocation [i, j]

Set Need [i, jl =0 for all j

Set finish [i] = True

Go to step 3

5. If Finish [i] = true for all i, return (safe) else return (unsafe)

ii. Resource-request algorithm

• Resource request algorithm determines whether granting a resource according to any claim by a process leads to an unsafe state. This algorithm is applied when a process sends a request to grant one or a set of resources.
• This algorithm introduces one more data structure – Request. It is a matrix of order n * m. It indicates the number of resources of each type requested by a particular process at some moment of time.

The various steps followed by this algorithm are :

1.  If Request [i, jl<= Need [i, j], for all resource type j, go to step 2 (Here i is a process which has made a request)
2. If Request [i, jl <= Available [i, j], go to step 3. Otherwise process P, must wait, since the resources are unavailable.
3. Assume that the requested resources have been allocated to process P. Do the following updations:

Set Available [j] = Available [j] – Request [i, jl, for all j

Set Allocation [i, j] = Allocation [i, j] + Request [i, j], for all j

Set Need [i, j] = Need [i, j] – Request [i, j], for all j.

4. Now apply safety part of algorithm, if the resulting state is safe, the transaction shown in step 3 should be completed otherwise, transaction shown in step 3 should be rollbacked and the process P, must wait.

 

Example of Banker’s Algorithm:

Consider 5 processes P1, P2, P3, P4, P5 to be executed with limited resources that are A=10, B=5 and C=7. The Table for allocation and max. need is given below:

Process	Allocation (A)	Allocation (B)	Allocation (C)	Max. Need (A)	Max. Need (B)	Max. Need (C)
P1	0	1	0	7	5	3
P2	2	0	0	3	2	2
P3	3	0	2	9	0	2
P4	2	1	1	4	2	2
P5	0	0	2	5	3	3

To find remaining need, we use this formula i.e.:

Remaining need = Max need – Allocation

and for available resources:

Available = Total – Sum of Allocation

Process	Allocation	Max. Need	Available	Remaining need
	A B C	A B C	A B C	A B C
P1	0 1 0	7 5 3	3 3 2	7 4 3
P2	2 0 0	3 2 2	5 3 2	1 2 2
P3	3 0 2	9 0 2	7 4 3	6 0 0
P4	2 1 1	4 2 2	7 4 5	2 1 1
P5	0 0 2	5 3 3	10 4 7	5 3 1
Total	7 2 5		10 5 7

Here, we find remaining need and then available need. then we check available resources of A, B and C. If any of the process can execute then we execute these processes by Safe method. If neither of these processes can be execute then deadlock occurs. First we execute P2, then the resources held by P2 will be free and these are added to available resources. then we execute next process by checking available resources. the sequence for safe method will be:

P2->P4->P5->P1->P3