Bankers Algorithm - TarisMajor/5143-OpSystems GitHub Wiki

Bankers-Algorithm-in-C

Banker's Algorithm is a resource allocation and deadlock avoidance algorithm devised by Edsger Dijkstra. The algorithm is named because it is analogous to the way a bank manages loans and resources. It ensures that a system will remain in a safe state, avoiding deadlock by simulating resource allocation for processes and checking if the system can still satisfy all requests.

Key Characteristics of Banker's Algorithm

  1. Safety Check: The algorithm checks if allocating resources will leave the system in a safe state. A safe state means that there is at least one sequence in which all processes can complete without leading to a deadlock.
  2. Resource Management: It manages multiple types of resources and keeps track of the current allocation, maximum needs, and remaining resources.
  3. Request Handling: When a process requests resources, the algorithm assesses whether fulfilling the request will keep the system in a safe state. If it does, the request is granted; otherwise, the process must wait.

Steps Involved in Banker's Algorithm

  1. Initialization:

    • Available: Vector indicating the number of available resources of each type.
    • Max: Matrix defining the maximum number of resources each process may request.
    • Allocation: Matrix showing the current allocation of resources to each process.
    • Need: Matrix calculating the remaining resource needs of each process (Need[i][j] = Max[i][j] - Allocation[i][j]).

  2. Resource Request:

    • When a process requests resources, the algorithm checks if the request is less than or equal to the need and the available resources.
    • Temporarily allocate the resources to the process and update the available, allocation, and need matrices.

  3. Safety Algorithm:

    • Initialize work (a copy of the available vector) and a finish vector (all false).
    • Find a process i such that Need[i] ≤ Work and Finish[i] is false.
    • If such a process is found, update Work and Finish, repeat until all processes are in a safe state or no such process exists.
    • If all processes can finish (finish vector is all true), the system is in a safe state; otherwise, it is not.

  4. Decision:

    • If the system is in a safe state after the temporary allocation, the request is approved.
    • If not, the temporary allocation is rolled back, and the request is denied until more resources become available.

Advantages of Banker's Algorithm

  1. Deadlock Avoidance: It prevents deadlocks by ensuring that resource allocation keeps the system in a safe state.
  2. Flexible Resource Allocation: The algorithm can handle multiple resource types and varying resource demands from processes.

Disadvantages of Banker's Algorithm

  1. Complexity: The algorithm can be computationally intensive, especially in systems with a large number of resources and processes.
  2. Assumptions: It requires knowledge of the maximum resource needs of each process in advance, which may not always be feasible.
  3. Overhead: The continuous checking of safe states introduces overhead and can impact system performance.

Use Cases for Banker's Algorithm

  1. Real-Time Systems: Suitable for real-time systems where resource availability and deadlock avoidance are critical.
  2. Operating Systems: Used in operating systems for managing resources and ensuring smooth and uninterrupted process execution.

Sources for Further Reading