Topic 6.1 · Deadlocks

Resource Allocation & 4 Necessary Conditions of Deadlock

3 min read1 question to test yourself

1Definition

A Deadlock is a severe system condition in a multiprogramming environment where two or more processes are permanently blocked because each process holds a non-sharable resource while waiting to acquire another resource currently held by another blocked process in the set. A deadlock can occur if and only if four necessary conditions hold simultaneously in the system.

2Simple Explanation

Imagine a narrow one-lane bridge over a river. Car A drives on from the left, and Car B drives on from the right. They meet in the exact middle of the single-lane bridge. Car A cannot move forward because Car B is blocking it. Car B cannot move forward because Car A is blocking it. Neither car is willing to reverse. Both cars are stuck forever. This is a Deadlock. System resources (RAM, GPU, disk locks, tables) become tied up, freezing the operating system.

3Real-Life Example / Analogy

Two People Writing a Document: Person A holds the blue pen and needs the red pen. Person B holds the red pen and needs the blue pen. Neither person will drop their current pen until they finish writing. Both people sit waiting infinitely.

4Diagram / Visual Representation

Requests

Allocated to

Requests

Allocated to / held by

Process 1

Resource 2

Process 2

Resource 1

5Working / How It Works

  • Resource Utilization Steps:
    1. Request: Process requests a resource instance. If free, lock it; if busy, process enters Waiting state.
    2. Use: Process operates on the resource (e.g., writes to disk, computes on GPU).
    3. Release: Process releases resource, waking up waiting processes.
  • The 4 Necessary Conditions for Deadlock:
    1. Mutual Exclusion: At least one resource must be held in a non-sharable mode (only 1 process at a time can use it).
    2. Hold and Wait: A process must be holding at least one resource and waiting to acquire additional resources held by other processes.
    3. No Preemption: Resources cannot be forcibly taken away from a process; they must be released voluntarily after execution.
    4. Circular Wait: A closed loop set of waiting processes P0,P1,…,Pn{P_0, P_1, \dots, P_n} exists such that P0P_0 waits for a resource held by P1P_1, P1P_1 waits for P2P_2, and PnP_n waits for P0P_0.

6Types / Components / Characteristics

  • Resource Types: Single-instance resources (1 printer) vs. Multi-instance resources (4 CPU cores).
  • Deadlock Handling Strategies:
    1. Deadlock Prevention: Structural rules preventing at least 1 of the 4 necessary conditions from occurring.
    2. Deadlock Avoidance: Dynamic runtime tracking using advance claim information (e.g., Banker's Algorithm) to grant requests only if the system remains in a Safe State.
    3. Deadlock Detection & Recovery: Periodically checking resource graphs for cycles and aborting processes or preempting resources upon detection.
    4. Deadlock Ignorance (Ostrich Algorithm): Ignoring deadlocks entirely under the assumption they occur rarely (Used by Windows, Linux, macOS).

7Solved Examples / Problems

Problem: Why do modern general-purpose operating systems like Linux and Windows employ the Ostrich Algorithm (Deadlock Ignorance)? Solution:

  1. Implementing continuous runtime Deadlock Avoidance (Banker's Algorithm) requires every process to declare its maximum resource needs in advance, which is impractical for user applications.
  2. Continuous Deadlock Detection algorithms introduce heavy CPU calculation overhead.
  3. Because deadlocks occur infrequently in desktop/server usage, rebooting or killing a single stuck process is far cheaper than paying perpetual performance overhead.

8Advantages, Disadvantages & Applications

  • Prevention Advantages: Guarantees zero system deadlocks.
  • Disadvantages: Reduces CPU utilization, device throughput, and system concurrency.

9Important Points to Remember

  • All 4 conditions must hold simultaneously for a deadlock to exist. Breaking any single condition prevents deadlocks.
  • The Ostrich Algorithm ignores deadlocks to maintain high OS performance.

10Test Your Understanding

  1. MCQ: Which of the following is NOT one of Coffman's four necessary conditions for a deadlock?
    • A) Mutual Exclusion
    • B) Hold and Wait
    • C) Preemptive CPU Scheduling
    • D) Circular Wait
    Show answer
    C.
  2. Conceptual Question: Explain how breaking the Circular Wait condition prevents deadlocks.
  3. Application Question: Contrast the trade-offs of Deadlock Prevention versus Deadlock Ignorance.

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