Banker’s Algorithm in OS

Banker’s Algorithm in operating systems is a deadlock avoidance and resource allocation algorithm. It ensures that the resources are allocated to processes in a way that avoids deadlock. The algorithm is named after a banker who lends money only to those he knows can repay him. The operating system works on a similar principle. In this blog, we will explore how the Banker’s Algorithm works, its components, how it avoids deadlocks, and how it’s implemented in C++.

Table of Contents:

• What is Banker’s Algorithm in OS?
• Components of the Banker’s Algorithm
• How Does the Banker’s Algorithm Work?
  • Step 1: Input the Required Matrices
  • Step 2: Calculate the Need Matrix
  • Step 3: Find a Process Whose Need Can Be Satisfied
  • Step 4: Execution of the Process
  • Step 5: Update the Safe Sequence
  • Step 6: Repeat The Steps
• Banker’s Algorithm Components
  • Safety Algorithm
  • Resource-Request Algorithm
• Implementation of Banker’s Algorithm in C++
• Conclusion

What is Banker’s Algorithm in OS?

Banker’s algorithm in an OS is a deadlock avoidance algorithm that needs prior knowledge of all the resource requests of processes. A deadlock is a state where a process is waiting for a resource indefinitely while holding a resource that is requested by another process in the system, forming a circular chain. The name “banker’s algorithm” comes from the way a banker might allocate available resources to avoid bankruptcy. Similarly, the operating system also assigns the available resources to processes to avoid deadlock. Banker’s algorithm is os ensures that a system never enters a deadlock state.

Components of the Banker’s Algorithm

The bankers algorithm is OS that works on three matrices. They are maximum resources, allocated resources, and available resources.

• Maximum Array: The maximum array holds the maximum number of resources a process needs. It is the prior knowledge of requests that is essential for banker’s algorithm in OS. It is a 2-D array.
• Allocated Array: The Allocated Array tells how many resources of each type are allocated to each process at any given moment. It is a 2-D array.
• Available Array: The Available Array tells how many resources of each type are available to be allocated. It is a 1-D array.
• Need Matrix: This is also a two-dimensional matrix that indicates the remaining resource needs of each process.
• Safe Sequence: Safe sequence is the list of processes that shows the order in which they can safely run.

How does the Banker’s Algorithm Work?

Now that we are familiar with the component matrices of the banker’s algorithm in OS, let us understand the working of the banker’s algorithm and how it uses the Maximum Array, Allocated Array, and Available Array.

Step 1: Input the Required Matrices

Initially, the banker’s algorithm takes into account the prior knowledge of all resource requests throughout the lifetime of the system. It takes in three input matrices:

Let us suppose we have n is the number of processes and k be the number of resource types. Then,

1. Maximum Array

It is a 2D matrix where rows depict the processes and columns depict the resource types. Therefore, it would be of size n*k.

Max[i][j] = m means that process Pi may request at most m instances of resource type Rj.

2. Available Array

It is a 1D array since it just lists the count of available instances for each resource type. It is of ‘k’ size.

Available[i] = m means that there are m instances of the resource R_i.

3. Allocated Array

Allocation[i][j] = m says that the process Pi is currently allocated m instances of resource type Rj.

Step 2: Calculate the Need Matrix

In this step, the banker’s algorithm in OS calculates the need matrix. A need matrix at any given instance indicates how many more resources each process may request to complete its task.

Need[i][j]=Maximum[i][j]−Allocated[i][j]

This matrix determines whether the system can satisfy the future requests of a process. It is calculated at each timestamp and also after changes are made.

Step 3: Find a Process Whose Need Can Be Satisfied

Once you have calculated the need matrix at t=0, compare the Available Array and need matrix and choose that process whose need can be satisfied with the available instances of each resource.

For each process Pi​:
    if Need[i] ≤ Available, then the process can safely execute.

If there is no such process, then this state is an unsafe state and is prone to deadlock.

Step 4: Execution of the Process

Once you have found the process whose needs can be met using the available resources, assume that the process has been completely executed. Once the process executes, it releases the allocated resources.

Add these resources back to their type of resources in the Available Array.

Available[i] = Available[i] + Allocated[i][j]

Step 5: Update the Safe Sequence

Once the process is marked as completed, it is added to the Safe Sequence.

Step 6: Repeat The Steps

Repeat the algorithm from Steps 3 to 5 and continue updating the available and need matrix after finding the next process that can safely execute with the updated Available Array.

• If the processes can safely execute with the given matrices, then the system is in a safe state.
• If the algorithm cannot find any process whose needs can be met, the system is in an unsafe state, which could potentially lead to a deadlock.

Banker’s Algorithm Components

Banker’s algorithm in OS comprises two algorithms: the safety algorithm and the resource request algorithm. Safety algorithm checks whether the current state is safe or not, and the resource-request algorithm is responsible for requesting resources for a process and checking whether a process’s new request can be safely granted or not.

1. Safety Algorithm

Step 1: Create two arrays, work[] and finish[]. The work array will be a duplicate of the Available Array, and the finish array will be a boolean array for all the processes to keep track of which have finished execution (true or 1) and which ones are still executing (false or 0)

Step 2: Find a process P[i] such that finish[i] == false and need[i] <= work. If no such process exists, go to step 4.

Step 3: Assuming that the process is completed, add its allocated resources back to the work[] array and mark this process as finished (true or 1) in the finish[] array.

Step 4: If finish[i] == true for all processes, the system is in a safe state. If not, then it is in an unsafe state

Pseudo-code:

work := Available
finish[i] := false for all i = 0 to n-1

while there exists i such that finish[i] == false and Need[i] <= work:
    work := work + Allocation[i]
    finish[i] := true

if finish[i] == true for all i:
    System is in a safe state
else:
    System is not in a safe state

2. Resource-Request Algorithm

Step 1: Check whether the request of a process is well within the maximum need of that same process. If it is more than the maximum allowed, then throw an exception.

Step 2: Check if the system has enough available resources. If yes, then you can proceed.

Step 3: Assume you have to allocate the requested resources now. Calculate and assign from the available resources. Then run the safety algorithm. If, after the allocation of the resources, the state is still safe, proceed to the next step.

Pseudo-code:

if Request[i] > Need[i]:
    Error: process has exceeded its maximum claim

else if Request[i] > Available:
    Process must wait

else:
    // Pretend to allocate
    Available = Available - Request[i]
    Allocation[i] = Allocation[i] + Request[i]
    Need[i] = Need[i] - Request[i]

    Run Safety Algorithm

    if system is safe:
        Grant request
    else:
        Rollback to previous state
        Process must wait

Implementation of Banker’s Algorithm in CPP

Let us look at the implementation of the banker’s algorithm in CPP programming language.

Output:

Explanation: The logic above is the implementation of the banker’s algorithm in OS. The system under consideration has 5 processes and 3 resources. We define the two functions calculateNeed() and isSafeState().

Conclusion

Banker’s algorithm in OS plays an important role in avoiding deadlocks in the system. In this article, we explored the different arrays used by the banker’s algorithm, including the maximum array, allocated array, and need array, and understood their functions and how to maintain them. We discussed the safety function and the resource-request function. We saw the implementation of the logic of banker’s algorithm in CPP. The Banker’s Algorithm is an excellent tool for understanding the fundamentals of deadlock avoidance and safe state detection. You should try experimenting with different matrices to observe how safe sequences are formed.

Banker’s Algorithm in OS – FAQs