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