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 StructureDefinitionExample
AvailableIt 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.

MaxIt 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.

AllocationIt 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.

 

NeedIt 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 StructureDefinitionExample
WorkIt 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.

FinishIt 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.

Summary
Banker's Algorithm | Deadlock Avoidance
Article Name
Banker's Algorithm | Deadlock Avoidance
Description
Banker's Algorithm in OS is a deadlock avoidance strategy. Banker's Algorithm Example. Banker's Algorithm maintains a set of data. If entertaining the request causes the system to move to unsafe state, then it is aborted.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-