Banker's Algorithm
Dijkstra's safety algorithm: pretend to allocate, see if a finish order exists.
Level: advanced
What is it?
Banker's algorithm is a classic deadlock-avoidance method for multiple resource types. Each process declares a maximum demand; the algorithm tracks Allocation, Max, Need, and Available, and tests whether a tentative request leaves the system in a safe state.
Why does it matter?
It turns a qualitative question—could these allocations block everyone?—into a step-by-step safety check. Its assumptions are restrictive for general-purpose systems, but the method teaches resource accounting and safe sequences clearly.
Mental model
Think of a bank granting loans only if the remaining cash and repayments from borrowers who can finish leave enough capacity for the next borrower. It checks a potential sequence, not merely whether the current request fits in the free pool.
How it works
- Need[i][j] = Max[i][j] − Allocation[i][j].
- A request larger than Need is invalid under the declared maximum; a request larger than Available must wait.
- For a plausible request, subtract it from Available and add it to Allocation, then run the safety check hypothetically.
- If the state is safe, grant the request; if unsafe, roll back the tentative values and defer it.
- A request smaller than current Available can still be unsafe after allocation.
Steps
- Compute Need for each process and resource type.
- Copy Available into Work and mark all processes unfinished.
- Repeatedly choose an unfinished process with Need ≤ Work; add its Allocation to Work and mark it finished.
- If every process can finish, the state is safe and the chosen order is a safe sequence.
- When evaluating a request, tentatively allocate, run the test, then commit or roll back.
Real-world usage
- Working through textbook resource-allocation matrices.
- Explaining the difference between safety checking and deadlock detection.
- Validating a simple resource manager with small bounded resource types.
Common mistakes
- Updating Available but forgetting to add released allocations to Work.
- Declaring a state deadlocked as soon as no process fits; that establishes unsafe under the model, not necessarily an existing deadlock.
- Comparing vectors using only their totals rather than each resource dimension.
Interview questions
What are the four key data structures?
Available, Max, Allocation, and Need, where Need = Max − Allocation.
What must be restored when a tentative request fails the safety test?
Restore the original Available, Allocation, and Need state; the rejected request must not change the real allocation.