Mastering the Banker’s Algorithm: One Sentence, One Diagram to Prevent Deadlock

One Sentence

When a process requests resources, the Banker’s algorithm first tentatively allocates them, then uses a safety check to see if the system remains in a safe state; if not, the tentative allocation is discarded and the process continues waiting.

One Diagram

The diagram visualizes the algorithm’s workflow, from tentative allocation to safety verification and possible rollback.

Algorithm Details

Each process Pi is characterized by:

MAX : the maximum demand for each resource type.

Allocation (A): resources currently allocated to Pi.

Need (N = MAX – Allocation): remaining resources required.

Available represents the pool of free resources; the sum of Available and all Allocations equals the total resources in the system.

If a process requests resources, the algorithm first checks whether the request does not exceed Available . It then pretends to allocate the resources, updates Available , Allocation , and Need , and runs the safety test. If no process can finish after this tentative allocation, the system is unsafe and the allocation is rolled back, preventing a potential deadlock.

If at least one process can finish, it is marked as completed, its resources are released back to Available , and the test continues with the remaining processes. When all processes can finish, the system is safe and a safe sequence (e.g., {P0, P3, P2, P1}) is produced.

Example

Consider the following resource allocation state (four resource types, five processes):

Analysis shows a safe sequence {P0, P3, P4, P1, P2}, confirming the system is initially safe.

Now, process P2 requests resources (1,2,2,2). The algorithm checks:

Request ≤ Need (1,2,2,2) ≤ (2,3,5,6) ✔

Request ≤ Available (1,6,2,2) ✔

It tentatively allocates, resulting in:

Available = (0,4,0,0)

Allocation P2 = (2,5,7,6)

Need P2 = (1,1,3,4)

A subsequent safety check finds that no process can finish with the remaining Available resources, so the system becomes unsafe and the request must be denied, preventing a deadlock.

Thus, the Banker’s algorithm effectively avoids unsafe states by using tentative allocation and rigorous safety verification.