Topic 6.2 · Deadlocks

Deadlock Prevention, Avoidance & Banker's Algorithm

4 min read1 question to test yourself

1Definition

Deadlock Prevention enforces static structural constraints on resource requests to invalidate at least one of the four necessary deadlock conditions. Deadlock Avoidance dynamically monitors runtime resource allocations using advance claim data, approving requests only if the resulting allocation state is a Safe State. The Banker's Algorithm is a classic deadlock avoidance and safe-state verification algorithm for multi-instance resources.

2Simple Explanation

  • Prevention: Like a strict law: "Nobody is allowed to hold a second tool until they put down their first tool" (Eliminating Hold & Wait). This guarantees no deadlocks can ever form, but it makes work slow and inefficient.
  • Avoidance (Banker's Algorithm): Imagine a bank manager with $10,000 in cash reserves. Three customers ask for loans over the day. Before approving a loan request, the banker runs a mathematical check: "If I give Customer A this $2,000 now, do I still have enough cash left to satisfy the maximum remaining needs of at least one customer so everyone can eventually finish paying back?" If yes (Safe State), the loan is granted. If no (Unsafe State), Customer A must wait.

3Real-Life Example / Analogy

A Car Rental Agency: The agency has 10 cars. Three corporate clients reserve fleets. Client 1 might need up to 6 cars total, Client 2 up to 5, and Client 3 up to 4. If the agency hands out cars recklessly, all clients get stuck partially fulfilled and nobody can complete their trip (Unsafe State / Deadlock). The agency uses the Banker's Algorithm to hold a cash reserve so at least one client can get their full fleet, finish their work, and return all cars to the pool.

4Diagram / Visual Representation

All system states

SAFE STATES
At least one safe sequence exists

UNSAFE STATES
No safe sequence currently established

DEADLOCK STATES
System is deadlocked

5Working / How It Works

  • Banker's Algorithm Data Structures (for nn processes and mm resource types):

    • Available[m]\text{Available}[m]: Vector of length mm indicating available instances of each resource.
    • Max[n][m]\text{Max}[n][m]: n×mn \times m matrix defining maximum resource demand of each process.
    • Allocation[n][m]\text{Allocation}[n][m]: n×mn \times m matrix defining resources currently allocated to each process.
    • Need[n][m]\text{Need}[n][m]: n×mn \times m matrix defining remaining resource need of each process (Need[i][j]=Max[i][j]−Allocation[i][j]\text{Need}[i][j] = \text{Max}[i][j] - \text{Allocation}[i][j]).
  • Safety Algorithm Execution:

    1. Let Work=Available\text{Work} = \text{Available} and Finish[i]=False\text{Finish}[i] = \text{False} for all i=0…n−1i = 0 \dots n-1.
    2. Find an index ii such that Finish[i]==False\text{Finish}[i] == \text{False} and Need[i]≤Work\text{Need}[i] \le \text{Work}.
    3. If no such ii exists, skip to Step 4. If found, Work=Work+Allocation[i]\text{Work} = \text{Work} + \text{Allocation}[i], Finish[i]=True\text{Finish}[i] = \text{True}, go back to Step 2.
    4. If Finish[i]==True\text{Finish}[i] == \text{True} for all ii, the system is in a Safe State.

6Types / Components / Characteristics

  • Methods for Preventing the 4 Conditions:
    1. Mutual Exclusion: Allow read-only access to sharable resources (not possible for non-sharable resources like printers).
    2. Hold and Wait: Protocol A: Require process to request and be allocated all resources before starting. Protocol B: Require process to release all held resources before requesting new ones.
    3. No Preemption: If a process holding resources requests a unavailable resource, all its currently held resources are preempted.
    4. Circular Wait: Impose a strict global numerical ordering F(R)F(R) on all resources; processes must request resources in strictly increasing order.

7Solved Examples / Problems

Problem: Consider a system with 3 processes (P0, P1, P2) and 1 Resource type with 10 total instances. Current state:

  • P0: Allocation = 3, Max = 8 -> Need=5\text{Need} = 5
  • P1: Allocation = 2, Max = 4 -> Need=2\text{Need} = 2
  • P2: Allocation = 2, Max = 9 -> Need=7\text{Need} = 7 Total Allocated = 3+2+2=73 + 2 + 2 = 7. Available=10−7=3\text{Available} = 10 - 7 = 3. Is the system in a Safe State? Find the Safe Sequence.

Solution:

  1. Work=3\text{Work} = 3.
  2. Check P0 (Need=5≤3\text{Need}=5 \le 3 False). Check P1 (Need=2≤3\text{Need}=2 \le 3 True!).
    • Process P1 can finish.
    • Work=Work+Allocation[P1]=3+2=5\text{Work} = \text{Work} + \text{Allocation}[P1] = 3 + 2 = \mathbf{5}. Finish[P1]=True\text{Finish}[P1] = \text{True}.
  3. Re-check P0 (Need=5≤5\text{Need}=5 \le 5 True!).
    • Process P0 can finish.
    • Work=Work+Allocation[P0]=5+3=8\text{Work} = \text{Work} + \text{Allocation}[P0] = 5 + 3 = \mathbf{8}. Finish[P0]=True\text{Finish}[P0] = \text{True}.
  4. Re-check P2 (Need=7≤8\text{Need}=7 \le 8 True!).
    • Process P2 can finish.
    • Work=8+2=10\text{Work} = 8 + 2 = 10. Finish[P2]=True\text{Finish}[P2] = \text{True}.
  • All processes finished. The system is in a Safe State with Safe Sequence ⟨P1,P0,P2⟩\langle P1, P0, P2\rangle.

8Advantages, Disadvantages & Applications

  • Banker's Algorithm Advantages: Dynamically prevents deadlocks without restricting resources statically.
  • Disadvantages: Impractical for general OSs because apps cannot know their maximum future resource claims in advance; process count nn and resource availability mm must remain static.

9Important Points to Remember

  • Need[i][j]=Max[i][j]−Allocation[i][j]\text{Need}[i][j] = \text{Max}[i][j] - \text{Allocation}[i][j].
  • An Unsafe State is NOT necessarily a Deadlock, but an unsafe state carries the risk of leading to a deadlock.

10Test Your Understanding

  1. MCQ: What is the correct formula to compute the Need Matrix in the Banker's Algorithm?
    • A) Need=Allocation−Available\text{Need} = \text{Allocation} - \text{Available}
    • B) Need=Max−Allocation\text{Need} = \text{Max} - \text{Allocation}
    • C) Need=Max+Available\text{Need} = \text{Max} + \text{Available}
    • D) Need=Allocation−Max\text{Need} = \text{Allocation} - \text{Max}
    Show answer
    B.
  2. Conceptual Question: Explain the difference between an Unsafe State and a Deadlock State.
  3. Application Question: Run the Banker's Safety Algorithm on a 3-resource system and verify if a given allocation state is safe.

Finished this topic?

0 of 27 topics read in Operating Systems

Handwritten notes for the exam

Unit-wise SPPU notes and PYQs for this subject.

Helpful? Share it with your class

Free for everyone, no login needed.

Share topic