Banker’s Algorithm | Operating System - Computer Science Engineering (CSE) PDF Download

Banker’s Algorithm in Operating System

The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.

Why Banker’s algorithm is named so?
Banker’s algorithm is named so because it is used in banking system to check whether loan can be sanctioned to a person or not. Suppose there are n number of account holders in a bank and the total sum of their money is S. If a person applies for a loan then the bank first subtracts the loan amount from the total money that bank has and if the remaining amount is greater than S then only the loan is sanctioned. It is done because if all the account holders comes to withdraw their money then the bank can easily do it.
In other words, the bank would never allocate its money in such a way that it can no longer satisfy the needs of all its customers. The bank would try to be in safe state always.

Following Data structures are used to implement the Banker’s Algorithm:
Let ‘n’ be the number of processes in the system and ‘m’ be the number of resources types.

Available: 

• It is a 1-d array of size ‘m’ indicating the number of available resources of each type.
• Available[ j ] = k means there are ‘k’ instances of resource type Rj

Max:

• It is a 2-d array of size ‘n*m’ that defines the maximum demand of each process in a system.
• Max[ i, j ] = k means process P_i may request at most ‘k’ instances of resource type R_j.

Allocation:

• It is a 2-d array of size ‘n*m’ that defines the number of resources of each type currently allocated to each process.
• Allocation[ i, j ] = k means process P_i is currently allocated ‘k’ instances of resource type R_j

Need:

• It is a 2-d array of size ‘n*m’ that indicates the remaining resource need of each process.
• Need [ i,   j ] = k means process P_i currently need ‘k’ instances of resource type R_j
• for its execution.
• Need [ i,   j ] = Max [ i,   j ] – Allocation [ i,   j ]

Allocation_i specifies the resources currently allocated to process P_i and Need_i specifies the additional resources that process Pi may still request to complete its task.
Banker’s algorithm consists of Safety algorithm and Resource request algorithm

Safety Algorithm

The algorithm for finding out whether or not a system is in a safe state can be described as follows:

1. Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.
   Initialize: Work = Available
   Finish[i] = false; for i=1, 2, 3, 4….n
2. Find an i such that both
   a) Finish[i] = false
   b) Need_i <= Work
   if no such i exists goto step (4)
3. Work = Work + Allocation[i]
   Finish[i] = true
   goto step (2)
4. if Finish [i] = true for all i
   then the system is in a safe state

Resource-Request Algorithm

Let Request_i be the request array for process P_i. Request_i [j] = k means process P_i wants k instances of resource type R_j. When a request for resources is made by process P_i, the following actions are taken:

1. If Request_i <= Need_i
   Goto step (2) ; otherwise, raise an error condition, since the process has exceeded its maximum claim.
2. If Requesti <= Available
   Goto step (3); otherwise, Pi must wait, since the resources are not available.
3. Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows:
   Available = Available – Request_i
   Allocation_i = Allocation_i + Request_i
   Need_i = Need_i– Request_i

Example:
Considering a system with five processes P0 through P4 and three resources of type A, B, C. Resource type A has 10 instances, B has 5 instances and type C has 7 instances. Suppose at time t0 following snapshot of the system has been taken:

In simple terms, it checks if allocation of any resource will lead to deadlock or not, OR is it safe to allocate a resource to a process and if not then resource is not allocated to that process. Determining a safe sequence(even if there is only 1) will assure that system will not go into deadlock.
Banker’s algorithm is generally used to find if a safe sequence exist or not. But here we will determine the total number of safe sequences and print all safe sequences.

The data structure used are: 

• Available vector
• Max Matrix
• Allocation Matrix
• Need Matrix

Example:

Input: 

Output: Safe sequences are:
P2--> P4--> P1--> P3
P2--> P4--> P3--> P1
P4--> P2--> P1--> P3
P4--> P2--> P3--> P1
There are total 4 safe-sequences 

Explanation: 
Total resources are R1 = 10, R2 = 5, R3 = 7 and allocated resources are R1 = (0 + 2 + 3 + 2 =) 7, R2 = (1 + 0 + 0 + 1 =) 2, R3 = (0 + 0 + 2 + 1 =) 3. Therefore, remaining resources are R1 = (10 – 7 =) 3, R2 = (5 – 2 =) 3, R3 = (7 – 3 =) 4.
Remaining available = Total resources – allocated resources
and
Remaining need = max – allocated

So, we can start from either P2 or P4. We can not satisfy remaining need from available resources of either P1 or P3 in first or second attempt step of Banker’s algorithm. There are only four possible safe sequences. These are:
P2–> P4–> P1–> P3
P2–> P4–> P3–> P1
P4–> P2–> P1–> P3
P4–> P2–> P3–> P1