Banker’s Algorithm in Operating System: Examples & Implementation

In implementing the Banker's Algorithm, three fundamental components are necessary: 

• Initial Allocation: The number of resources initially allocated to each process. It carries out a record of the number of each resource instance currently assigned to each process.
• Maximum Need: It is the maximum number of resources that each process may require during its execution. It may be used to predict future resource requests for each process.
• Available: This refers to the total number of instances for every resource type in the system that were unallocated before allocation.

The Banker's Algorithm can allocate resources safely without entering a deadlock state using these three components. 

Implementing the Banker's Algorithm in an operating system adopts several key data structures, which aid in administrating and tracking resources and processes within the system. The following data structures are required:

• Available: A vector of length "m" that tracks the number of available instances for each resource type in the system. For example, if Available[j] = k, there are k instances of resource type Rj available.
• Max: A matrix of size [n × m] expressing the maximum number of resources each process can demand. If Max[i][j] = k, process Pi can request up to k instances of resource Rj.
• Allocation: A matrix of size [n × m] representing the number of resources allocated to each process. For example, Allocation[i][j] = k means that process Pi has been allocated k of resource Rj.
• Need: A matrix of size [n × m] that provides the number of resources still needed for each process. For example, Need[i][j] = k means process Pi still needs k more instances of resource Rj to complete.
• Finish: A vector of length n, where each entry is a Boolean value (TRUE or FALSE). It shows if the process has finished executing and released all its resources. Hence, if Finish[i] = TRUE, process Pi is said to have completed execution with the resources freed.

Here are the key concepts in banker’s algorithm:

• Safe State: A system is said to be in a secure state when there is a sequence of processes such that by each process obtaining required resources, finishing, and then releasing resources that might be needed by other methods, such other processes have a possibility of finishing. In a safe state, no deadlock can occur in the system.‍
• Unsafe State: It is called unsafe when resources may still be allocated to processes, allowing them to proceed but with no guarantees that all will be completed without causing deadlocks. In this case, a deadlock occurs, and the process may not finish.

Here are the key steps involved in the banker’s algorithm process such as:

Step 1: Mark active processes as running or blocked.

Active := Running ∪ Blocked
for k = 1 to r:
    New_request[k] := Requested_resources[requesting_process, k]

Step 2:.This is done by changing the resource allocation state to include the most recent request.

Simulated_allocation := Allocated_resources
for k = 1 to r:
    // Compute projected allocation state
    Simulated_allocation[requesting_process, k] := Simulated_allocation[requesting_process, k] + New_request[k]

Step 3: Now, we can verify if such resource allocation exceeds the available resources; if not, it proceeds.

Feasible := true
for k = 1 to r:
    // Check if projected allocation state is feasible
    if Total_resources[k] < Simulated_total_alloc[k]:
        Feasible := false

Step 4: The algorithm removes active processes that can finish upon accessing the available resources.

if Feasible = true:
    while set Active contains a process P1 such that:
        for all k, Total_resources[k] - Simulated_total_alloc[k] >= Max_need[P1, k] - Simulated_allocation[P1, k]:
            Delete P1 from Active
        for k = 1 to r:
            Simulated_total_alloc[k] := Simulated_total_alloc[k] - Simulated_allocation[P1, k]

Step 5: If all processes can be finished, the request will be granted, and resources will be re-updated accordingly.

if set Active is empty:
    for k = 1 to r: 
        Requested_resources[requesting_process, k] := 0
    for k = 1 to r: 
        Allocated_resources[requesting_process, k] := Allocated_resources[requesting_process, k] + New_request[k]
    Total_alloc[k] := Total_alloc[k] + New_request[k]

There are two types of banker’s algorithms such as:

Safety Algorithm

Here are the steps involved in the safety algorithm:

Step 1: The algorithm will initialise vectors Work and Finish.

Initialize: Work = Available
Finish[i] = false; for i = 1, 2, 3, 4....n

Step 2: It searches for processes not finished yet for available resources.

Find an i such that both:
    2.1 Finish[i] = false
    2.2 Needi <= Work
    if no such i exists, go to step (4)

Step 3: The processes are finished after available resources are updated.

Work = Work + Allocation[i]
Finish[i] = true
Go to step (2)

Step 4: It ensures a safe state if all processes are successfully finished.

If Finish[i] = true for all i, then the system is in a safe state

Resource-Request Algorithm

Here are the steps for resource request algorithm:

Step 1: This requires a check to see if the request for resources by a process is valid

If Requesti <= Needi, go to step (2);

Step 2: The process request for resources does not exceed the maximum claim.

If Requesti <= Available, go to step (3);

Step 3: If requested resources are unavailable in the system, the process waits until they are released.

    Available = Available - Requesti
    Allocationi = Allocationi + Requesti
    Needi = Needi - Requesti

Here is the banker's algorithm example with solution. We have the following tables for processes, allocations, maximum needs, and available resources:

Process Table:

1. Calculate the Need Matrix

The Need matrix is calculated using the formula:

Need[i]=Max[i]−Allocation[i]

So for each process:

2. Is the system in a safe state? If Yes, then what is the safe sequence?

To determine if the system is in a safe state, we will follow the Safety Algorithm.

Step 1: Initialize Work and Finish

• Work = Available resources = (3, 2, 1)
• Finish = [False, False, False, False, False] (None of the processes are finished initially)

Step 2: Find a process that can finish

Look for a process i where Need[i] <= Work.

• P0: Need = (3, 1, -3), but this contains a negative value, which is invalid. Therefore, P0 cannot finish.
• P1: Need = (2, 2, 0) and Work = (3, 2, 1). Since Need ≤ Work, P1 can finish.
  
  • After P1 finishes, update Work:
    Work = Work + Allocation[P1] = (3, 2, 1) + (2, 1, 2) = (5, 3, 3)
  • Finish[P1] = True.
• P2: Need = (6, 1, -6), but this contains a negative value, so P2 cannot finish.
• P3: Need = (4, 4, -4), which also contains a negative value, so P3 cannot finish.
• P4: Need = (1, 1, 3) and Work = (5, 3, 3). Since Need ≤ Work, P4 can finish.
  
  • After P4 finishes, update Work:
              Work = Work + Allocation[P4] = (5, 3, 3) + (1, 1, 2) = (6, 4, 5)
  • Finish[P4] = True.

Step 3: Repeat the process 

Now, we have the updated Work = (6, 4, 5). We will check again for other processes.

• P2: Need = (6, 1, -6), but this still contains a negative value, so P2 cannot finish.
• P3: Need = (4, 4, -4), which also contains a negative value, so P3 cannot finish.
• P0: Need = (3, 1, -3), but again, there are negative values, so P0 cannot finish.

Safe Sequence:

• Since P1 and P4 can finish, we have a safe <P1, P4> sequence.

Here is the CPP program implementation of the banker’s algorithm:

C++ code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 5, m = 3;
    vector<vector<int>> Max = {{6, 5, 3}, {4, 2, 1}, {5, 1, 2}, {1, 0, 2}, {5, 2, 3}};
    vector<vector<int>> Alloc = {{1, 0, 2}, {3, 1, 0}, {0, 1, 1}, {1, 0, 1}, {1, 0, 2}};
    vector<int> Total = {7, 5, 7}; // Total available resources
    vector<int> Avail(m); // Available resources after allocation

    for (int j = 0; j < m; j++) {
        int s = 0;
        for (int i = 0; i < n; i++) {
            s += Alloc[i][j];
        }
        Avail[j] = Total[j] - s;
    }

    vector<int> Exec(n, 0);
    vector<vector<int>> Need(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            Need[i][j] = Max[i][j] - Alloc[i][j];
        }
    }

    int k, c = 0;
    vector<int> seq;
    while (c < n) {
        for (int i = 0; i < n; i++) {
            if (Exec[i] == 0) {
                int mark = 0;
                for (int j = 0; j < m; j++) {
                    if (Need[i][j] > Avail[j]) {
                        mark = 1;
                        break;
                    }
                }
                if (mark == 0) {
                    seq.push_back(i + 1);
                    for (k = 0; k < m; k++) {
                        Avail[k] += Alloc[i][k];
                    }
                    Exec[i] = 1;
                }
            }
        }
        c++;
    }

    cout << "The safe sequence of execution is ";
    for (int i = 0; i < n; i++) {
        if (i == n - 1)
            cout << " P" << seq[i] << "\n";
        else
            cout << " P" << seq[i] << " ->";
    }
}

Explanation

The above C++ code implements the Banker's Algorithm to determine a safe sequence of process execution. s. It computes the Need, Available, and Allocation matrices and then iterates through processes to check whether their resource needs can be satisfied. If so, that process runs, and resources are updated. Finally, the safe sequence is printed.

Output

The safe sequence of execution is P1 -> P3 -> P4 -> P2 -> P5

Example of an Unsafe State in Banker’s Algorithm

Let us consider a system with 3 processes (P1, P2, P3) with 6 instances of Resources. The state of the system is defined by the following conditions:

Step 1: Available Resources: 1 instance of resource.

Step 2: Current Allocation:

• P1: 2 instances.
• P2: 3 instances.
• P3: 1 instances.

Step 3: Maximum Demand (maximum resources each process may request):

• P1: 4 instances.
• P2: 5 instances.
• P3: 3 instances.

Step 4: Now, to find the need for each process: 

Need = Maximum Demand – Allocation

• P1: 4 – 2 = 2
• P2: 5 – 3 = 2
• P3: 3 – 1 = 2

Thus, the Need matrix is:

In this example:

• P1 needs 2 more instances to complete.
• P2 needs 2 more instances to complete.
• P3 needs 2 more instances to complete.

The system has only one instance of the resource, and each process needs two more resources in order to complete. Even in the presence of resources, there is no guarantee that all processes will reach termination without a deadlock.

Here are the advantages of the banker’s algorithm such as:

• The algorithm detects a deadlock and prevents it as it allocates resources safely.
• The algorithm caters to process requests by checking safe or unsafe allocation of resources.
• One advantage of this algorithm is that it allows processes to declare their maximum resource requirements in advance.
• The safety algorithm ensures that resources are allocated to avoid leaving the system unsafe.

Here are the disadvantages of the banker’s algorithm such as:

• The processes must declare the maximum resource requirements before and cannot be changed during execution.
• All processes must declare their maximum requirements before.
• It starts with a fixed number of processes; at no time during execution can another process be entered.
• The algorithm has a certain finite period within which resource allocation must be done; if unsuccessful, there is a maximum time limit (e.g., one year).

In conclusion, the Banker's Algorithm is a simple but competent way of resource allocation and deadlock avoidance in an operating system. The Banker's Algorithm will always keep a system in a safe state. It has some overheads, and there are restrictions on its use. It suits those systems in which resource requirements are known, and deadlock avoidance is essential. Other methods may prove more effective for real-time systems with highly variable resource requirements.

1. What is the Banker's Algorithm? What is an example of it?

The Banker's Algorithm is an example of a deadlock avoidance algorithm. It ensures that resources are allotted so the system can safely avoid entering a deadlock state by checking for potential safe sequences in resource allocation.

2. What is the Banker's Algorithm in OS?

The Banker's Algorithm manages resource allocation and avoids deadlock. It determines whether a requested resource can be safely allocated to a process without leaving the system unsafe so that all processes can finish in time.

3. What is the Deadlock Algorithm in OS?

The deadlocks in an operating system are the set of strategies to detect, avoid, and even resolve the deadlocks. The standard algorithms for deadlock avoidance include the Banker's algorithm, while the resource allocation graph and wait-for graphs are used for deadlock detection.