Home

Learning Hub

Articles

Bankers Algorithm in OS (Operating System) – A Comprehensive Guide

The name Banker’s Algorithm is used in the banking system to avoid deadlock. By using the banker’s algorithm, the bank guarantees that it will never leave a safe state when consumers want money. When the customer’s request does not lead the bank to withdraw from a safe state, the cash is allocated when a customer makes her deposit on time; should the customer keep spare funds, she will have to wait for other customers who accomplish their deposits. The deadlock avoidance algorithm in OS is also known as the Bankers algorithm.

Banker’s Algorithm in OS

According to Edsger Dijkstra, the resource allocation and deadlock avoidance algorithms in Banker’s algorithm test safety by simulating the allocation of the maximum possible amount of all resources. The algorithm then checks if any of the pending activities can create a deadlock by going into a state check for each pending activity. If none of the possible deadlocks exists, it decides to allow the allocation to proceed.

A new process arriving at a system must declare the maximum number of instances it will ever claim per given resource type. This number cannot be higher than the total number of resources in the system. Additionally, a process must return all the requested resources within a finite amount of time, even if all of the resources are provided.

Implementing Banker’s Algorithm using Data structures

The following data structures are needed to implement the Banker’s Algorithm in OS:

• Available Resources Array: To determine the type of current available resource stored in an array. The second one is a vector of length “m” with the value indicating the number of available resources per type in the system available. If Available [j] = k, it is said that ‘k’ are instances of resource type Rj available in the system.
• Maximum Need Matrix: A matrix used to identify the maximum number of units and the resources required by each process. A [n × m] matrix defines each process’s max resources demand. Within the given function library, only a single variable is announced as the class constructor, and simultaneously, it is also defined as a static variable of the class. When Max [ I, j ] = k, a process Pi may request k maximum instances of R j.
• Allocation Matrix: It records the number of resources for each type currently allocated to each process. A [n × m] matrix also represents the number of … of each type allocated to each process now. So if we have Allocation [i, j] = k, then process Pi is currently allocated “k” instances of resource type Rj.
• Need Matrix: The matrix that stores the amounts of remaining resources of each type required by each process (the matrix of the Difference of the Maximal Need and Allocation matrices). [It is] an [n x m] matrix representing the remaining resource needs of processes. If a process Pi requires ‘k’ more instances of resource type Rj (for example, to finish its task assignment), then we need [i, j] = k.
• Completed Processes Set: A set of IDs for complete processes that have released their resources. It is a matrix of length “m” and finish. It contains a Boolean, i.e., True or False, along with whether a process has been invested in resources needed for the performed work or all necessary resources ended by completing the task performed.

These data structures represent the state of the system and resources being requested and allocated by processes. Using this information, the Bankers Algorithm in OS determines whether a resource request can be granted without locking into a deadlock situation.

Classification of Banker’s Algorithm

The Banker’s Algorithm is made up of two algorithms which are:

• Safety Algorithm
• Resource Request Algorithm

Safety Algorithm

The Safety Algorithm of the Banker’s Algorithm of OS is used to verify whether a system is in a safe state and whether a request for a resource can be granted without creating a deadlock.

Steps of the Safety Algorithm:

• Initialization:
  • Define two arrays:
    • Work: It contains a temporary copy of the available resources, with the values from the Available array (the number of currently available resources of each type).
    • Finish: An array, one element for every process, initialized to false for all processes so that no process has finished (true means finished).
  • Check for an Unfinished Process:
    • Find a process Pi for which:
      • The process still needs to be finished.
      • Work (the resources available) is greater than or equal to the Need[i] of the process.
    • Allocate Resources Temporarily:
      • If such a process Pi is found, pretend to allocate the necessary resources:
        • Increment Work by Allocation[i] (currently allocated resources of Pi).
        • We set Finish[i] to true (indicating that this process is finished).
      • Repeat step 2 until all processes marked as Finish[i] = true or no processes that match the conditions exist.
    • Determine System State:
      • The system is safe if all processes are marked with Finish[i] = true.
      • Otherwise, the resource request will make the system unsafe, and granting it may cause a deadlock.

Resource Request Algorithm

An operating system resource request algorithm is a process for allocating resources. The algorithm decides whether or not to allow a process to request additional resources without violating the system’s safety. The algorithm checks to see if the request can be granted and grants it, provided that the request does not exceed a process’s maximum resource use and there are enough resources for granting the request.

A request [i, j] = x is a process in Pi that attempts to request x instances of a resource of type j.

Steps of the Resource Request Algorithm:

1. Receive the Request:

• For instance, in this case, let Request[i] be the resource request of process Pi, which requests x instances of resource type j (e.g., Request[i, j] = x).

2. Validate the Request:

• Check if the request is within the maximum limit:
  • Otherwise, proceed: If Request[i] <= Need[i].
  • Otherwise, the process has successfully claimed its maximum, generating an error.
• Check if the available resources are sufficient:
  • Proceed if Request[i] <= Available.
  • The process will wait if not.

3. Pretend to Allocate Resources Temporarily:

• If the above conditions are met, the algorithm temporarily allocates resources to Pi:
• Available in this case would be Available – Request[i] (reduce the available resources).
• The requested resources are added to the process’s allocation; in other words, Allocation[i] = Allocation[i] + Request[i].
• Reduce Need[i] by Request[i] (reduce the need as the resources have been given temporarily).

4. Check System Safety:

• Call the Safety Algorithm to check if this temporary allocation keeps the system safe.
• If the system remains safe:
  • The reward is given permanently, and a grant is made to allocate the resources to Pi.
• If the system becomes unsafe:
  • Rolling the changes back to what it was before. It’s denied, and it must wait.

The Bankers Algorithm in OS has the following characteristics:

• Deadlock avoidance: The Banker algorithm uses resource allocation and release rules to avoid the deadlocks.
• Safety state: The Banker’s algorithm checks whether the current state is safe, in which processes running for infinity and never starting would not deadlock.
• Dynamic nature: The Banker’s algorithm is dynamic, as it can support resource requests and releases during processes that are running.
• Non-preemptive: Let me tell you that the Banker’s algorithm does not preempt the resources from the processes; they are only released voluntarily by the processes.
• Conservatism: The Banker’s algorithm is conservative, granting the new state as a safe state; otherwise, it will deny it.
• Resource utilization: The Bankers algorithm makes sure the processes utilize resources efficiently.
• Optimality: The Bankers algorithm does not ensure optimal resource utilization, but it does ensure no deadlocks.

Banker’s Algorithm Advantages in OS

Some advantages of Bankers Algorithm in OS are mentioned below:

• Deadlock avoidance: The first algorithm informs the OS which algorithm to use to detect and avoid a situation where a deadlock occurs and when the OS allocates optimal and safe resources.
• Resource utilization: The Bankers Algorithm ensures that resources are allocated only to the process that really needs them.
• System stability: The Banker’s Algorithm ensures that when processes grab resources, they do not keep them longer than necessary to maintain system stability.
• Safe state detection: We have demonstrated that the Banker’s algorithm can detect when the system is in a safe state. Thus, with the aid of the Banker’s algorithm, we can safely manage the allocation of resources.
• Simplicity: The simplicity with which the Banker’s algorithm can be coded makes it a popular algorithm for resource allocation in operating systems.

Drawbacks of Bankers Algorithm in OS

Some drawbacks of Bankers Algorithm in OS are as follows:

• Overhead: The Bankers algorithm requires additional computation and memory overhead to ensure safe states and perform other operations, decreasing system performance.
• Inflexible resource allocation: Banker’s algorithm policy is a set of previously known rules for assigning resources, and it may have rules that are inappropriate for dealing with complex and dynamic resource requirements.
• Limited applicability: In OS, the Banker’s algorithm only applies to systems with a finite number of resources and may not be applicable to systems with continuous or infinite resources.
• Blocking processes: In particular, if the Banker’s algorithm is performed, processes may be waiting for resources to become available, which can decrease system performance.
• Static resource allocation: Banker’s algorithm in OS uses static resource allocation and never changes resource requirements, resulting in suboptimal resource utilization.

Also read: OS Interview Questions and Answers

Conclusion

The Bankers Algorithm in OS is a deadlock avoidance algorithm that prevents deadlock from occurring and also enables safe process execution. An algorithm maximizes or allocates resources to each process stored in a matrix and checks whether the system is safe before permitting a process to request a resource. The request is granted if it doesn’t crash a process beyond its maximum resource needs and if there are sufficient resources. The algorithm grants the request and updates the allocation matrix if the system is safe. If the system’s state is not safe, we reject the request and block the process until enough resources are available to execute the request. The Banker’s Algorithm can distribute and prevent deadlocks in one part of an operating system’s control. Go through the  Certificate Program in Application Development powered by Hero Vired to get a full walkthrough of Operating Systems.