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. Banker's algorithm is the avoidance strategy: prevention breaks one of the four necessary conditions up front, detection lets a deadlock form and then recovers from it, and avoidance grants a request only when the state that results is still safe. Operating Systems for GATE sets the three approaches side by side.
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.
Written out in full, the sixteen orderings are these:
Prefix P1, P3, at Work
(7, 4, 3): P1 P3 P0 P2 P4, P1 P3 P0 P4 P2, P1 P3 P2 P0 P4, P1 P3 P2 P4 P0, P1 P3 P4 P0 P2, P1 P3 P4 P2 P0.Prefix P1, P4, P3, at Work
(7, 4, 5): P1 P4 P3 P0 P2, P1 P4 P3 P2 P0.Prefix P3, P1, at Work
(7, 4, 3): P3 P1 P0 P2 P4, P3 P1 P0 P4 P2, P3 P1 P2 P0 P4, P3 P1 P2 P4 P0, P3 P1 P4 P0 P2, P3 P1 P4 P2 P0.Prefix P3, P4, P1, at Work
(7, 4, 5): P3 P4 P1 P0 P2, P3 P4 P1 P2 P0.
The trace solved above, P1, P3, P4, P0, P2, is the fifth entry in the first group. Checking a hand-derived answer against this list is the fastest way to catch a branch you closed too early: any ordering that starts P0, P2 or P4 is wrong, because only P1 and P3 clear the initial Work of (3, 3, 2).
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. Only the request form needs an extra step in front of the safety algorithm, so it is worth working once.
Return to the five-process state and let P1 request (1, 0, 2). Two admissibility checks come first: the request must lie within P1's Need (1, 2, 2), which it does, and within Available (3, 3, 2), which it also does. Now pretend to grant it. Available falls to (3, 3, 2) - (1, 0, 2) = (2, 3, 0), P1's Allocation rises to (3, 0, 2), and P1's Need drops to (0, 2, 0).
Run the safety algorithm on that pretended state. Work starts at (2, 3, 0). P1 now needs only (0, 2, 0) and fits, releasing its enlarged Allocation to give (5, 3, 2). P3 follows to (7, 4, 3), then P4 to (7, 4, 5), P0 to (7, 5, 5), and P2 to (10, 5, 7). A safe sequence exists, so the request is granted for real. Had no process qualified, the pretended state would be discarded and P1 would wait, holding what it already had.
About 2,000 Operating System questions in the KnowledgeGate question bank give the topic plenty of surrounding practice, including process synchronisation questions.
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.
