Banker’s Algorithm | Deadlock Avoidance

Deadlock Avoidance-

 

Before you go through this article, make sure that you have gone through the previous article on Deadlock and Handling Strategies.

 

We have discussed-

• In a deadlock state, the execution of multiple processes is blocked.
• Deadlock avoidance strategy involves maintaining a set of data.
• The data is used to make a decision whether to entertain any new request or not.
• If entertaining the new request causes the system to move in an unsafe state, then it is discarded.

 

Banker’s Algorithm-

 

• Banker’s Algorithm is a deadlock avoidance strategy.
• It is called so because it is used in banking systems to decide whether a loan can be granted or not.

 

Prerequisite-

 

Banker’s Algorithm requires-

• Whenever a new process is created, it specifies the maximum number of instances of each resource type that it exactly needs.

 

Data Structures Used-

 

To implement banker’s algorithm, following four data structures are used-

 

 

1. Available
2. Max
3. Allocation
4. Need

 

Data Structure	Definition	Example
Available	It is a single dimensional array that specifies the number of instances of each resource type currently available.	Available[R1] = K It means K instances of resource type R1 are currently available.
Max	It is a two dimensional array that specifies the maximum number of instances of each resource type that a process can request.	Max[P1][R1] = K It means process P1 is allowed to ask for maximum K instances of resource type R1.
Allocation	It is a two dimensional array that specifies the number of instances of each resource type that has been allocated to the process.	Allocation[P1][R1] = K It means K instances of resource type R1 have been allocated to the process P1.
Need	It is a two dimensional array that specifies the number of instances of each resource type that a process requires for execution.	Need[P1][R1] = K It means process P1 requires K more instances of resource type R1 for execution.

 

Working-

 

• Banker’s Algorithm is executed whenever any process puts forward the request for allocating the resources.
• It involves the following steps-

 

Step-01:

 

• Banker’s Algorithm checks whether the request made by the process is valid or not.
• If the request is invalid, it aborts the request.
• If the request is valid, it follows step-02.

 

Valid Request A request is considered valid if and only if- The number of requested instances of each resource type is less than the need declared by the process in the beginning.

 

Step-02:

 

• Banker’s Algorithm checks if the number of requested instances of each resource type is less than the number of available instances of each type.
• If the sufficient number of instances are not available, it asks the process to wait longer.
• If the sufficient number of instances are available, it follows step-03.

 

Step-03:

 

• Banker’s Algorithm makes an assumption that the requested resources have been allocated to the process.
• Then, it modifies its data structures accordingly and moves from one state to the other state.

 

Available = Available - Request(i)
Allocation(i) = Allocation(i) + Request(i)
Need(i) = Need(i) - Request(i)

 

• Now, Banker’s Algorithm follows the safety algorithm to check whether the resulting state it has entered in is a safe state or not.
• If it is a safe state, then it allocates the requested resources to the process in actual.
• If it is an unsafe state, then it rollbacks to its previous state and asks the process to wait longer.

 

Safe State A system is said to be in safe state when- All the processes can be executed in some arbitrary sequence with the available number of resources.

 

Safety Algorithm Data Structures-

 

To implement safety algorithm, following two data structures are used-

 

 

1. Work
2. Finish

 

Data Structure	Definition	Example
Work	It is a single dimensional array that specifies the number of instances of each resource type currently available.	Work[R1] = K It means K instances of resource type R1 are currently available.
Finish	It is a single dimensional array that specifies whether the process has finished its execution or not.	Finish[P1] = 0 It means process P1 is still left to execute.

 

Safety Algorithm-

 

Safety Algorithm is executed to check whether the resultant state after allocating the resources is safe or not.

 

Step-01:

 

Initially-

• Number of instances of each resource type currently available = Available
• All the processes are to be executed.
• So, in Step-01, the data structures are initialized as-

 

Work = Available
Finish(i) = False for i = 0, 1, 2, ..., n-1

 

Step-02:

 

• Safety Algorithm looks for an unfinished process whose need is less than or equal to work.
• So, Step-02 finds an index i such that-

 

Finish[ i ] = False
Need(i) <= Work.

 

• If such a process exists, then step-03 is followed otherwise step-05 is followed.

 

Step-03:

 

• After finding the required process, safety algorithm assumes that the requested resources are allocated to the process.
• The process runs, finishes its execution and the resources allocated to it gets free.
• The resources are then added to the work and finish(i) of that process is set as true.

 

Work = Work + Allocation
Finish(i) = True

 

Step-04:

 

• The loop of Step-02 and Step-03 is repeated.

 

Step-05:

 

• If all the processes can be executed in some sequence, then the system is said to be in a safe state.
• In other words, if Finish(i) becomes True for all i, then the system is in a safe state otherwise not.

 

To gain better understanding about Banker’s Algorithm,

Watch this Video Lecture

 

Next Article- Practice Problems On Banker’s Algorithm

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.