Banker's Algorithm (Avoidance)

While Deadlock Prevention statically ensures that a deadlock can never occur by placing strict constraints on resource requests, Deadlock Avoidance requires the operating system be given additional information in advance concerning which resources a process will request and use during its lifetime.

With this knowledge, the OS dynamically checks the resource-allocation state to ensure that there can never be a circular-wait condition.

1. Safe State

A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock. More formally, a system is in a safe state only if there exists a safe sequence of processes [P_1, P_2, ..., P_n] such that for each P_i, the resources that P_i can still request can be satisfied by the currently available resources plus the resources held by all the previous processes.

• If a system is in a safe state, there are NO deadlocks.
• If a system is in an unsafe state, there is a POSSIBILITY of deadlock.

The goal of deadlock avoidance is to ensure the system never enters an unsafe state.

2. The Banker's Algorithm

The Banker's Algorithm (developed by Edsger Dijkstra) is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, before deciding whether allocation should be allowed to continue.

It gets its name because the algorithm could be used in a banking system to ensure that the bank never allocates its available cash in such a way that it can no longer satisfy the needs of all its customers.

Data Structures Required

Let $n$ be the number of processes in the system and $m$ be the number of resource types.

1. Available: A vector of length $m$. Indicates the number of available resources of each type.
2. Max: An $n \times m$ matrix. Defines the maximum demand of each process.
3. Allocation: An $n \times m$ matrix. Defines the number of resources of each type currently allocated to each process.
4. Need: An $n \times m$ matrix. Indicates the remaining resource need of each process. (Need[i][j] = Max[i][j] - Allocation[i][j]).

The Resource-Request Algorithm

When a process $P_i$ makes a request for resources, the OS performs the following steps:

1. If the Request $\le$ Need, proceed to step 2. Otherwise, raise an error condition.

2. If the Request $\le$ Available, proceed to step 3. Otherwise, $P_i$ must wait, since the resources are not available.

3. The system pretends to allocate the requested resources to process $P_i$ by modifying the state:

   • Available = Available - Request
   • Allocation = Allocation + Request
   • Need = Need - Request

4. Run the Safety Algorithm. If the resulting state is Safe, the transaction is completed and the resources are officially allocated. If the new state is Unsafe, $P_i$ must wait, and the old resource-allocation state is restored.