Banker's Safety Algorithm

Safe States vs Deadlock

A system state is Safe if there exists an ordering of all processes such that each process can satisfy its worst-case remaining resource need using currently available resources plus the allocations returned by earlier processes in the sequence. An Unsafe state means no such guarantee exists if all processes simultaneously demand their maximum claim; however, an unsafe state is not proof of an immediate deadlock because processes might release resources early without requesting their full maximum ceiling.

Work Vector and Eligibility Condition

Initialize the working vector Work = (Available R1, Available R2) and mark all processes P₁, P₂, P₃ unfinished. At each step, identify the lowest-numbered unfinished process P_i satisfying the componentwise inequality Need_i,1 ≤ Work₁ and Need_i,2 ≤ Work₂. When found, mark P_i finished and update Work ← Work + Allocation_i. If all 3 processes finish, the state is Safe; if no unfinished process satisfies Need_i ≤ Work, the state is Unsafe.

Worked Example

Consider the Shared scenario with Available = (1, 1) and three processes:

• P1: Maximum (2, 1), Allocation (1, 0) → Need (1, 1)
• P2: Maximum (1, 2), Allocation (0, 1) → Need (1, 1)
• P3: Maximum (2, 2), Allocation (1, 1) → Need (1, 1)

1. Step 1: Work = (1, 1). All three processes have Need (1, 1) ≤ Work (1, 1). Lowest-numbered eligible process P1 finishes and returns Allocation (1, 0), updating Work = (1 + 1, 1 + 0) = (2, 1).
2. Step 2: Work = (2, 1). P2 has Need (1, 1) ≤ (2, 1), finishes, and returns Allocation (0, 1), updating Work = (2, 2).
3. Step 3: Work = (2, 2). P3 has Need (1, 1) ≤ (2, 2), finishes, and returns Allocation (1, 1), updating Work = (3, 3) with safe completion sequence ["P1", "P2", "P3"].

Experiment

Test safe chains and unsafe resource shortages in https://riano.app/module/bankers-safety-algorithm:

1. Select scenario Chain, set Available R1 to 2 and Available R2 to 0, and click Step three times to see P2 finish first (releasing 2 units of R2), unlocking P1 and then P3 for sequence ["P2", "P1", "P3"].
2. Reduce Available R1 to 0 and Available R2 to 0 in Shared or Chain and click Finish to observe Unsafe (not proof of current deadlock).
3. Switch to No claims with Available = (0, 0) to confirm that when Need = (0, 0) for all processes, all three finish immediately even with zero free resources.

Limitations

In real operating systems, processes rarely declare their exact maximum lifetime resource needs before execution, and the set of active threads and hardware resources changes dynamically over time.

Common Pitfalls

Two frequent errors are (1) adding Maximum_i instead of Allocation_i to Work when a process finishes, and (2) claiming that an Unsafe state is already deadlocked.

References

The resource-allocation matrices, safety test, and distinction between unsafe and deadlocked states follow standard operating systems literature:

• UIC Operating Systems Course Notes: Chapter 7 Deadlocks and Banker's Algorithm