Banker's Algorithm

The Banker's Algorithm is a strategy for deadlock avoidance in systems where multiple instances of various resource types exist. This algorithm is less efficient than using a resource-allocation graph but is suitable for more complex systems with multiple resource instances. It is named for its analogy to banking, where the bank ensures it doesn't allocate all its cash such that it cannot meet the needs of all its clients.

For the algorithm to work, each new process must declare the maximum instances of each resource type it might need throughout its execution. This maximum demand cannot exceed the total resources available in the system. Whenever a process requests resources, the system evaluates whether granting these resources will keep the system in a "safe state," meaning it can still meet the maximum demands of all processes. If so, the resources are allocated; otherwise, the requesting process must wait until the system can safely allocate the resources.

To implement the Banker's Algorithm, the system maintains several key data structures that represent the state of resource allocation:

• Available: An array indicating how many instances of each resource type are available. For example, if Available[j] is k, then there are k instances of resource type Rj available.

• Max: A matrix representing the maximum number of instances each process might request for every resource type. If Max[i][j] is k, process Pi may request up to k instances of resource type Rj.

• Allocation: A matrix showing the current allocation of each resource type to each process. If Allocation[i][j] is k, process Pi currently has k instances of resource type Rj.

• Need: A matrix indicating how many more instances of each resource type each process might need to complete its task. Need[i][j] is calculated as Max[i][j] - Allocation[i][j], showing the remaining resource requirement for process Pi regarding resource type Rj.

The above data structures evolve over time, reflecting changes in resource allocation and process requirements.

For operational purposes, we introduce notation for comparing resource vectors. Given vectors X and Y of length n, we define X ≤ Y if every element in X is less than or equal to the corresponding element in Y for all positions i (1 through n). For instance, if X = (1,7,3,2) and Y = (0,3,2,1), then it is true that Y ≤ X. Moreover, we define Y < X if Y ≤ X but Y is not equal to X.

In this framework, we can consider each row of the Allocation and Need matrices as vectors, denoted as Allocationi and Needi, which represent the resources currently allocated to process Pi and the resources Pi still requires, respectively.

The algorithms for determining a system's safety and handling resource requests are vital for avoiding deadlocks in systems where multiple instances of resources exist. These processes ensure that system operations proceed without leading to a state where processes indefinitely wait on each other, a condition known as deadlock. Here’s a detailed breakdown and explanation of both the Safety Algorithm and the Resource-Request Algorithm.

Safety Algorithm

The Safety Algorithm assesses whether the current state of the system is one from which all processes can complete their tasks without leading to a deadlock. It operates as follows:

1. Initialization:

   • Two vectors are established: Work and Finish. Work has a length equal to the number of resource types (m), initialized with the Available resources. Finish has a length equal to the number of processes (n), with all entries initially set to false, indicating that no process has yet been found to be able to complete with the available resources.

2. Search for an Eligible Process:

   • The algorithm searches for a process (indexed as i) that hasn’t been finished (Finish[i] == false) and whose remaining resource needs (Needi) can be satisfied with the current Work resources. If such a process is found, it moves to the next step; if not, it proceeds to step 4.

3. Pretend Allocation:

   • Once a suitable process is found, the algorithm simulates the allocation of resources to this process by adding the resources currently allocated to it (Allocationi) to the Work vector. It then marks this process as finished (Finish[i] = true) and loops back to step 2 to find the next process. This loop continues until no further processes can be found that meet the criteria of step 2.

4. Check for Safe State:

   • If all processes have been marked as finished (Finish[i] == true for all i), the system is in a safe state, meaning all processes can complete without causing a deadlock. Otherwise, the system is not safe.

This algorithm ensures safety by verifying that there exists a sequence of processes that can finish one after the other, releasing their resources back into the pool for other processes to use, hence preventing deadlocks. The computational complexity of this approach can be significant, requiring up to m × n^2 operations.

Resource-Request Algorithm

When a process requests additional resources, the system must decide if these resources can be allocated without leading to an unsafe state. This process works as follows:

1. Check Against Maximum Claim:

   • First, the system checks if the requested resources (Requesti) do not exceed the process's previously declared maximum needs (Needi). If the request exceeds what the process declared it might need, an error is raised for attempting to claim more than initially stated.

2. Check Availability:

   • If the request is within the process's maximum needs, the system then checks if enough resources are available (Requesti ≤ Available). If not, the process must wait, as granting the request would leave insufficient resources for other processes.

3. Simulate Allocation:

   • To check the safety of granting the request, the system simulates allocating the requested resources to the process. This involves temporarily adjusting the Available, Allocation, and Need matrices to reflect the proposed allocation.

     • Available resources are reduced by the Requesti.

     • The Allocationi for the process is increased by Requesti.

     • The Needi for the process is decreased by Requesti.

   • After this temporary allocation, the Safety Algorithm is run to determine if the system would still be in a safe state.

If this simulation proves that the system remains in a safe state after the allocation, the request is granted, and the temporary changes are made permanent. Otherwise, the request is denied, and the system reverts to its original state, awaiting resource releases that might enable a safe allocation in the future.

To demonstrate the Banker's Algorithm, let's examine a scenario in a system with five processes (P0 through P4) and three types of resources (A, B, and C), where resource A has 10 instances, resource B has 5 instances, and resource C has 7 instances. At a certain point in time, T0, we have the following system snapshot:

Allocation Matrix:

    A B C
P0  0 1 0
P1  2 0 0
P2  3 0 2
P3  2 1 1
P4  0 0 2

Maximum Demand Matrix (Max):

    A B C
P0  7 5 3
P1  3 2 2
P2  9 0 2
P3  2 2 2
P4  4 3 3

Available Resources:

A B C
3 3 2

The Need matrix, which represents the remaining resources each process may need to complete its tasks, is calculated as Max - Allocation:

Need Matrix:

    A B C
P0  7 4 3
P1  1 2 2
P2  6 0 0
P3  0 1 1
P4  4 3 1

At this snapshot, the system is in a safe state. A sequence that satisfies the safety criteria is <P1, P3, P4, P2, P0>, indicating that each process can complete its tasks one after the other without leading to a deadlock.

Now, suppose process P1 requests one more instance of resource A and two instances of resource C, making the request vector Request1 = (1,0,2). To evaluate this request, we first check if it can be fulfilled with the currently available resources:

Request1 <= Available:

(1,0,2) <= (3,3,2)

This condition is true, so we proceed by simulating the allocation of these resources to P1, updating the system state:

New Allocation Matrix after fulfilling P1's request:

    A B C
P0  0 1 0
P1  3 0 2
P2  3 0 2
P3  2 1 1
P4  0 0 2

New Need Matrix after fulfilling P1's request:

    A B C
P0  7 4 3
P1  0 2 0
P2  6 0 0
P3  0 1 1
P4  4 3 1

New Available Resources after fulfilling P1's request:

A B C
2 3 0

Running the safety algorithm on this new state, we find a safe sequence, <P1, P3, P4, P0, P2>, indicating the system remains in a safe state after allocating resources to P1, hence P1's request can be safely granted.

However, in this state, a request by P4 for (3,3,0) cannot be granted due to insufficient available resources. Similarly, a request by P0 for (0,2,0) cannot be granted, even though the resources are technically available, because fulfilling this request would lead the system into an unsafe state, potentially causing a deadlock.