Deadlock in Operating system

Everything you need to know about deadlock.

Introduction to deadlock

When there are Two or More processes where Each of them are holding a resource and waiting for a resource held by another process, causing all of them to be stuck and unable to proceed.

Analogy for better understanding

Imagine two people, Bimala and Kumar, are sitting at a table, and each has a item the other wants:

• Bimala has a fork, and Kumar has a knife.
• Bimala needs the knife to cut the cake, but she won't give up the fork until she gets the knife.
• Kumar needs the fork to eat chowmein, but he won't give up the knife until he gets the fork.

Both Bimala and Kumar are now in a Deadlock. They are each waiting for the other to release the resource (fork or knife) they need, so neither can proceed with their meal.

Necessary Conditions for Deadlock

The four conditions required for a deadlock conditions are illustrated below using an Day to day office scenario with Bimala and Kumar:

1. Mutual Exclusion

• Definition: Resources cannot be shared; only one process can use a resource at a time.
• Example:
  • Bimala starts printing a document → claims the printer (non-shareable).
  • Kumar starts scanning a file → claims the scanner (non-shareable).

2. Hold and Wait

• Definition: A process holds a resource while waiting for another.
• Example:
  • Bimala holds the printer but waits for the scanner (to scan a page for her document).
  • Kumar holds the scanner but waits for the printer (to print his scanned file).

3. No Preemption

• Definition: Resources cannot be forcibly taken; they must be released voluntarily.
• Example:
  • Bimala cannot pause her print job to let Kumar use the printer.
  • Kumar cannot stop his scan midway to free the scanner for Bimala.

4. Circular Wait

• Definition: A cycle of processes waiting for each other’s resources.
• Example:
  • Bimala waits for Kumar’s scanner → Kumar waits for Bimala’s printer → deadlock cycle.

NOTE

• The four conditions for deadlock are also called Coffman conditions.
• It is named after Edward G. Coffman Jr., who formalized them

Deadlock Prevention

Definition: Design the system to eliminate one or more of the four Coffman conditions.
Example:

• Mutual Exclusion: Use a spooler to allow multiple print jobs to queue (making the printer shareable).
• Hold and Wait: Require Bimala and Kumar to request both the printer and scanner before starting their tasks.
• No Preemption: Allow the system to pause Bimala’s print job mid-task to let Kumar use the printer.
• Circular Wait: Enforce a rule that resources must be requested in a fixed order (e.g., printer first, then scanner).

Deadlock Avoidance

Definition: Dynamically check resource allocation to ensure the system never enters an unsafe state.
Example:

• Use the Banker’s Algorithm:
  • Before granting a resource, verify that Bimala’s request won’t create a cycle (e.g., if Kumar’s scanner request would block Bimala’s printer access).

Deadlock Recovery

Definition: Resolve a deadlock after it occurs by terminating processes or rolling back actions.
Example:

• Termination: Force Bimala to cancel her print job so Kumar can use the printer.
• Rollback: Save Kumar’s scanned file and restart his task after Bimala frees the printer.

Deadlock Ignorance

Definition: Ignore deadlocks and assume they occur rarely (common in simple systems).
Example:

• The office lets Bimala and Kumar resolve the deadlock themselves (e.g., one person politely yields their resource).
• If no resolution, both wait indefinitely (stalemate).
• Deadlock ignorance is sometime referred to as Ostrich Algorithm

NOTE

• Prevention breaks a condition, avoidance avoids unsafe states, recovery fixes deadlocks, and ignorance accepts the risk.