Prevention and avoidance: safe states and the banker's algorithm

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. The four deadlock conditions? from Lesson 4.1.1
2. Cycle in a RAG with multiple instances means? from Lesson 4.1.1
3. What does a counting semaphore initialised to k allow? from Lesson 3.2.1

1 · The Hook

A bank has ₹10 lakh to lend. Three businesses each have a credit limit. The banker never lends money if, afterwards, there would be no way for every business to finish its project and repay. That cautious banker is exactly the banker's algorithm, and it is GATE's favourite deadlock question: build the Need matrix, then find a safe sequence.

3 · Core Concept

Predict First — the answer

Yes. Give B its 2 more (B finishes, returns 4 → 5 free), then A its 5 more (→ 10 free), then C its 7 more. That order is a safe sequence.

In plain words

Prevention designs the system so that one of the four conditions can never be true. Avoidance lets processes ask for resources freely, but before granting a request the OS checks: "after this, is there still some order in which everyone can finish?" If yes the state is safe and the request is granted; if not, the process waits.

1. Prevention: break one condition

2. Safe state

A state is safe if there is at least one order (a safe sequence) in which every process can get its maximum demand, finish and release everything.

• Safe → no deadlock is possible if the OS keeps the state safe.
• Unsafe ≠ deadlocked: unsafe only means a deadlock might happen if processes ask for their maximum.

3. Banker's algorithm: data

For n processes and m resource types:

• Available[m]: free instances of each type.
• Max[n][m]: maximum each process may ever need.
• Allocation[n][m]: what each process holds now.
• Need = Max − Allocation: what each may still ask for.

4. Safety algorithm

1. Work = Available; all processes unfinished.
2. Find an unfinished process with Need ≤ Work (every type). If none, stop.
3. Pretend it runs to the end: Work = Work + its Allocation; mark it finished. Go to 2.
4. If every process finished, the state is safe (the order found is a safe sequence); otherwise unsafe.

5. Resource-request algorithm (process i asks for Request)

1. If Request > Need_i → error (asked for more than declared).
2. If Request > Available → wait.
3. Pretend to grant: Available −= Request, Allocation_i += Request, Need_i −= Request. Run the safety algorithm. Safe → grant; unsafe → undo and make the process wait.

6. Worked example (resource types A, B, C; totals 8, 5, 5)

Available = (2, 1, 2).

• Work (2,1,2): only P3's need (2,1,1) fits → Work = (2,2,3).
• P1's need (1,2,1) fits → (4,2,4). P0's (4,2,2) fits → (5,3,4). P2's (3,0,2) fits → (6,5,5). P4's (2,3,1) fits → (8,5,5).
• Safe sequence P3, P1, P0, P2, P4 → the state is safe.

Request: P1 asks for (1,0,1). It is ≤ Need and ≤ Available. Pretend: Available (1,1,1), P1's need (0,2,0). Now no process's need fits in (1,1,1): unsafe → P1 must wait.

4 · Visual

Safety check = "can somebody finish with what is free?"

Work (2,1,2)  --P3 finishes-->  (2,2,3)  --P1-->  (4,2,4)  --P0-->  (5,3,4)
              --P2-->  (6,5,5)  --P4-->  (8,5,5) = all resources back: SAFE

each step: Need of that process <= Work, then Work += its Allocation

5 · Worked Examples

Example 1 Easy

A process has Max (7, 5, 3) and Allocation (0, 1, 0). What is its Need?

Solution

(7 − 0, 5 − 1, 3 − 0) = (7, 4, 3).

Example 2 Medium

13 units of one resource. A holds 6 (max 9), B holds 2 (max 5), C holds 2 (max 8). Is the state safe?

Solution

Free = 13 − 10 = 3. Needs: A 3, B 3, C 6. A finishes (3 ≤ 3) → 9 free; B → 11; C (6) → 13. Safe, e.g. A, B, C.

Example 3 GATE

In the Medium example, C asks for 1 more unit. Should it be granted?

Solution

Pretend: free 2; needs A 3, B 3, C 5. Nobody's need fits in 2: unsafe, so no (C waits). (If B asked for 1 instead: free 2, B's need 2 fits, and the state stays safe.)

6 · GATE Traps

• Need = Max − Allocation, not Max − Available.
• Compare Need with Work for every resource type.
• After a process "finishes", add its Allocation (not its Need or Max) to Work.
• Unsafe does not mean deadlocked; it means the OS can no longer guarantee safety.
• There may be several safe sequences; any one proves safety.

7 · Memory Hook

"Need = Max − Alloc. Find someone whose Need fits, let them finish, collect their Alloc, repeat."

8 · Connect the Dots

Avoidance needs to know every process's maximum in advance, which real systems rarely do. The last deadlock lesson lets deadlocks happen, detects them and recovers, and gives the quick formula for how many resources make deadlock impossible.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Need

A process has Max (5, 3, 2) and Allocation (1, 1, 0) for types A, B, C. Sum of its Need values?

Numerical answer: ________

Q2 · MCQ · 1 mark(s) — Prevention

Requiring processes to request resource types in increasing numerical order prevents deadlock by breaking:

1. (A) hold and wait
2. (B) no pre-emption
3. (C) mutual exclusion
4. (D) circular wait

Q3 · MCQ · 2 mark(s) — Safe sequence

Worked example of this lesson (Available (2,1,2)): which process is the only one that can run first in a safe sequence?

1. (A) P1
2. (B) P3
3. (C) P0
4. (D) P4

Q4 · MCQ · 2 mark(s) — Request

In the worked example, P3 asks for (1, 1, 0). What does the banker's algorithm do?

1. (A) Grants it: the new state is safe
2. (B) Makes P3 wait: the new state is unsafe
3. (C) Makes P3 wait: not enough available
4. (D) Refuses: it exceeds P3's need

Q5 · MCQ · 1 mark(s) — Unsafe

An unsafe state means:

1. (A) the banker's algorithm has failed
2. (B) a deadlock may occur, and the OS can't guarantee it won't
3. (C) no process can ever run
4. (D) the system is deadlocked

10 · Rule Card

• Prevention breaks a condition: all-at-once requests (hold and wait), pre-emption, resource ordering (circular wait).
• Safe state: some order lets everyone finish. Unsafe ≠ deadlock.
• Banker's: Need = Max − Allocation; Work = Available; pick Need ≤ Work; Work += Allocation; all finish → safe.
• Request: ≤ Need, ≤ Available, pretend, check safety; grant only if safe.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

deadlock preventionresource orderingdeadlock avoidancesafe statesafe sequenceunsafe statebanker's algorithmAvailable, Max, Allocation, Needsafety algorithmresource-request algorithm