Deadlock: Definition, Characterization, Necessary Conditions & Resource Allocation Graph

1. What is a Deadlock? (Definition)

In a multiprogramming environment, several processes compete for a finite number of resources (such as Printers, Tape Drives, Files, or Database Locks). If a process requests a resource that is currently not available, the process enters a Waiting State.

Definition of Deadlock: A set of processes is in a Deadlock state when every process in the set is waiting for an event (release of a resource) that can ONLY be caused by another waiting process in the same set! As a result, none of the processes can ever finish executing or release their resources, and they remain frozen forever.

Simple Real-Life Analogy:

• Example 1 (Narrow Single-Lane Bridge): Two cars approach each other from opposite ends on a narrow one-lane bridge. Car A is halfway across and waits for Car B to back up; Car B is halfway across and waits for Car A to back up. Neither moves!
• Example 2 (Computer Resources):
  • Process P1 is holding the Printer (R1) and is waiting for the Scanner (R2).
  • Process P2 is holding the Scanner (R2) and is waiting for the Printer (R1). Both P1 and P2 wait for each other forever!

Normal Sequence of Resource Use by a Process:

Under normal operation, a process uses a resource in 3 steps:

1. Request: The process requests the resource. If unavailable, it must wait until it acquires it.
2. Use: The process operates on the resource (e.g., prints a document on the printer).
3. Release: The process releases the resource so other processes can use it.

2. Deadlock Characterization: The 4 Necessary and Sufficient Conditions

A deadlock situation can arise in an Operating System if and only if all FOUR of the following conditions hold simultaneously in the system (known as Coffman’s 4 Conditions).

This is a 100% guaranteed 5- to 8-mark question in DAVV BCA Operating System exams!

Detailed Explanation of the 4 Necessary Conditions:

1. Mutual Exclusion

• At least one resource must be held in a non-shareable mode—meaning only ONE process can use the resource at any given time.
• If another process requests that resource, the requesting process must be delayed until the resource has been released (e.g., a Printer cannot print two documents on the same paper at the same instant).

2. Hold and Wait

• A process must be currently holding at least one resource and simultaneously waiting to acquire additional resources that are currently being held by other processes.

3. No Preemption

• Resources cannot be preempted (forcibly taken away) from a process by the OS.
• A resource can be released only voluntarily by the process holding it, after that process has completed its task.

4. Circular Wait

• A closed circular chain of waiting processes {P0, P1, P2, …, Pn} must exist such that:
  • P0 is waiting for a resource held by P1,
  • P1 is waiting for a resource held by P2,
  • …
  • Pn-1 is waiting for a resource held by Pn, and
  • Pn is waiting for a resource held by P0!

Important Exam Note: Even if any ONE of these 4 conditions is false/broken, a Deadlock can NEVER occur!

3. Resource-Allocation Graph (RAG)

Deadlocks can be described and detected visually using a directed graph called a System Resource-Allocation Graph (RAG).

Components of a Resource-Allocation Graph:

1. Two Types of Vertices (Nodes):
   • Process Nodes (P = {P1, P2, …}): Drawn as Circles (○).
   • Resource Nodes (R = {R1, R2, …}): Drawn as Rectangles (□). Dots (•) inside the rectangle represent the number of instances of that resource.
2. Two Types of Directed Edges (Arrows):
   • Request Edge (Pi → Rj): An arrow pointing from Process Pi to Resource Rj. It means Process Pi has requested an instance of Resource Rj and is currently waiting for it.
   • Assignment Edge (Rj → Pi): An arrow pointing from Resource Rj to Process Pi. It means an instance of Resource Rj has been allocated (assigned) to Process Pi.

Golden Rules of Cycle Detection in RAG:

1. If the Resource-Allocation Graph contains NO cycles: Then NO process in the system is deadlocked (100% safe!).
2. If the Graph CONTAINS a cycle:
   • Case A (Single Instance of Each Resource Type): If every resource has only 1 instance, then a cycle is both a Necessary and Sufficient condition—a Deadlock DEFINITELY exists!
   • Case B (Multiple Instances per Resource Type): If resources have multiple instances (e.g., 3 printers), a cycle is a Necessary condition, but NOT Sufficient—a deadlock may or may not exist!

💡 Exam Preparation Tips for DAVV BCA

• Memorize the 4 Coffman Conditions in exact order using the acronym M-H-N-C:
  1. Mutual Exclusion
  2. Hold and Wait
  3. No Preemption
  4. Circular Wait
• Always include the Resource Allocation Graph (RAG) rules (Request Edge Pi → Rj, Assignment Edge Rj → Pi, and the Cycle rules) to make your Deadlock Characterization answer stand out!