A Banker's algorithm numerical is usually lost through one subtraction or one wrong Work update, not through a difficult idea. You are given Allocation and Max, then asked whether the state is safe, which sequences work, or what extra resource would make an unsafe state safe. The reliable approach is to write every vector before choosing any process.
The four structures in a Banker's algorithm question
For n processes and m resource types, keep these four structures separate:
Allocation records what each process currently holds.
Max records the maximum claim of each process.
Need = Max - Allocation records what each process may still request.
Available = Total - column sum of Allocation records what is free now.
A state is safe when at least one ordering lets every process obtain its remaining Need and finish. An unsafe state is not automatically deadlocked. It simply has no guaranteed completion order. The wider Operating Systems for GATE guide places this distinction beside prevention, avoidance, and detection.
Safety algorithm: update Work, not Max
Start with Work = Available and mark every process unfinished. Find an unfinished process whose Need is at most Work in every resource component. Pretend that it completes, then update Work = Work + Allocation for that process. It releases what it was holding, not its Max claim.
Repeat until either every process finishes or no unfinished process qualifies. The first outcome proves safety. The second proves that the current state is unsafe.
Worked Allocation, Max, and Need matrices
Consider five processes, three resource types, and total resources (A, B, C) = (10, 5, 7).
Process | Allocation | Max | Need = Max - Allocation |
|---|---|---|---|
P0 | (0, 1, 0) | (7, 5, 3) | (7, 4, 3) |
P1 | (2, 0, 0) | (3, 2, 2) | (1, 2, 2) |
P2 | (3, 0, 2) | (9, 0, 2) | (6, 0, 0) |
P3 | (2, 1, 1) | (2, 2, 2) | (0, 1, 1) |
P4 | (0, 0, 2) | (4, 3, 3) | (4, 3, 1) |
Check the subtraction row by row. For example, P3 has (2-2, 2-1, 2-1) = (0, 1, 1), while P4 has (4-0, 3-0, 3-2) = (4, 3, 1).
The Allocation columns sum to (7, 2, 5). Therefore:
Available = (10, 5, 7) - (7, 2, 5) = (3, 3, 2).
Now choose the sequence P1, P3, P4, P0, P2.
Step | Need checked against Work | Work after release |
|---|---|---|
P1 |
|
|
P3 |
|
|
P4 |
|
|
P0 |
|
|
P2 |
|
|
Every comparison passes. Final Work equals the total resource vector, which is a useful addition check. The state is safe.
Counting all 16 safe sequences
At initial Work (3, 3, 2), only P1 and P3 qualify. That gives two top-level branches.
After P1, Work is
(5, 3, 2). P3 or P4 can run. The prefix P1, P3 reaches(7, 4, 3), where P0, P2, and P4 can appear in any order, giving3! = 6sequences. The prefix P1, P4 forces P3 next, after which P0 and P2 can swap, giving2sequences.After P3, Work is
(5, 4, 3). P1 or P4 can run. P3, P1 leaves three freely ordered processes, giving6sequences. P3, P4 forces P1 next, then P0 and P2 can swap, giving2sequences.
The total is 6 + 2 + 6 + 2 = 16. The factorial shortcut is valid only when current Work covers every remaining Need. Before that point, branch explicitly.
Smallest extra resource for an unsafe state
Now use totals (7, 4, 5) and this smaller state:
Process | Allocation | Max | Need |
|---|---|---|---|
P1 | (1, 1, 0) | (3, 3, 3) | (2, 2, 3) |
P2 | (2, 1, 1) | (5, 2, 1) | (3, 1, 0) |
P3 | (2, 0, 2) | (4, 2, 5) | (2, 2, 3) |
Allocation sums to (5, 2, 3), so Available is (2, 2, 2). P1 and P3 each lack one C; P2 lacks one A. Nobody can start.
Test one added instance, because zero does not work and one is the next possible minimum:
Add one A: Work becomes
(3, 2, 2). P2 runs, producing(5, 3, 3), then P1 and P3 can finish. Safe.Add one B: Work becomes
(2, 3, 2). Every original shortage remains. Unsafe.Add one C: Work becomes
(2, 2, 3). P1 runs, producing(3, 3, 3), then P2 and P3 can finish. Safe.
The minimum addition is one instance, specifically one A or one C. This variant rewards testing the smallest candidate and then running the complete safety check.
How GATE tests the algorithm
The common forms are finding one safe sequence, testing a pending request, counting valid sequences, and finding a minimum resource addition. For a pending request, pretend to grant it, update Available, Allocation, and Need, then run the same safety algorithm. About 2,000 published Operating System questions in the KnowledgeGate bank give the topic plenty of surrounding practice, including process synchronisation questions.
Confirm current paper instructions on the official GATE portal of the organising IIT.
The short version
Compute Need and Available first. Compare vectors component by component, release Allocation after a process finishes, and check that final Work reaches the total. When counting sequences, branch until all remaining processes are eligible. Then use factorial counting.
Hand-solve both examples once without looking at the updates. After that, use the GATE Test Series for timed practice, and the GATE category page to place this drill inside your broader preparation plan.
