Banker's Algorithm for Deadlock Avoidance

Introduction

Banker's Algorithm is used in deadlock avoidance. It gives the operating system a practical way to check whether granting a resource request will keep the system in a safe state.

The algorithm does not wait for deadlock to happen. It simulates allocation first, checks whether all processes can still finish in some order, and then decides whether to grant or delay the request.

What Banker's Algorithm Means

Banker's Algorithm is a deadlock avoidance algorithm that grants a resource request only if the resulting state remains safe. A safe state means at least one safe sequence exists for completing all processes.

It is mainly used when there are multiple instances of resource types, and each process declares its maximum possible resource demand in advance. The operating system then uses this information to avoid unsafe allocations.

Data Structures Used

Banker's Algorithm tracks the current resource state using four important data structures. These are usually written as vectors and matrices when there are multiple resource types.

• Available: Number of free instances of each resource type

• Max: Maximum demand declared by each process

• Allocation: Resources currently allocated to each process

• Need: Remaining resources each process may still request

The formula for Need is: Need = Max - Allocation

A useful distinction is that Available is system-level information, while Max, Allocation, and Need are maintained for each process.

Safety Algorithm

The safety algorithm checks whether the current state is safe. It tries to find an order in which all processes can finish using the currently available resources and the resources released by completed processes.

The basic flow is:

• Initialize Work: Set Work = Available.

• Mark processes unfinished: Set Finish[i] = false for every process.

• Find a process: Choose an unfinished process Pi such that Need[i] <= Work.

• Pretend it finishes: Add its allocation back to Work using Work = Work + Allocation[i].

• Record progress: Mark Finish[i] = true and add Pi to the safe sequence.

• Repeat: Continue until all processes finish or no more process can proceed.

If every process can be marked finished, the state is safe. If at least one process cannot be completed, the state is unsafe.

Safety Algorithm Example

Suppose the system has three resource types A, B, and C.

Available = (3, 3, 2)

Start with Work = (3, 3, 2). P1 can finish because its Need (1, 2, 2) is less than or equal to Work. After P1 releases its allocation, Work becomes (5, 3, 2).

Now P3 can finish, so Work becomes (7, 4, 3). Then P4 can finish, so Work becomes (7, 4, 5). After that, P0 can finish and Work becomes (7, 5, 5). Finally, P2 can finish and Work becomes (10, 5, 7).

One valid safe sequence is: P1 => P3 => P4 => P0 => P2

Since all processes can finish, the system is in a safe state.

Resource-Request Algorithm

The resource-request algorithm decides whether a new request from a process can be granted immediately. The decision is not based only on current availability; it also depends on whether the resulting state remains safe.

The compact logic is:

• Check Need: If Request[i] > Need[i], the request is invalid.

• Check Availability: If Request[i] > Available, make process Pi wait.

• Pretend & Check: Temporarily allocate the resources and run the safety check.

• Decide: If the state is safe, grant the request; otherwise, rollback and make Pi wait.

The important point is that Request <= Available is necessary, but not sufficient. A request may be available right now and still be delayed if granting it makes the system unsafe.

Resource-Request Example

Using the same system, suppose process P1 makes this request:

• Request[P1] = (1, 0, 2)

• Need[P1] = (1, 2, 2)

• Available = (3, 3, 2)

First, the request is within the declared need because (1, 0, 2) <= (1, 2, 2). Second, the resources are currently available because (1, 0, 2) <= (3, 3, 2).

Now the system pretends to allocate:

• Available = (3, 3, 2) - (1, 0, 2) = (2, 3, 0)

• Allocation[P1] = (2, 0, 0) + (1, 0, 2) = (3, 0, 2)

• Need[P1] = (1, 2, 2) - (1, 0, 2) = (0, 2, 0)

After this temporary allocation, a safe sequence still exists: P1 => P3 => P4 => P0 => P2

So the request can be granted. If no safe sequence had existed after the pretend allocation, the system would roll back the temporary changes and make P1 wait.

Summary

Banker's Algorithm is a deadlock avoidance algorithm that checks whether granting a request keeps the system in a safe state. It uses Available, Max, Allocation, and Need, where Need = Max - Allocation.

The safety algorithm finds whether all processes can finish in some order. The resource-request algorithm first validates the request, checks availability, pretends to allocate, and then grants the request only if a safe sequence still exists.