Deadlock

Definition

A Deadlock is a situation where a set of processes are blocked forever, each waiting for resources held by other processes in the set. No process can proceed because the resource it needs is held by another waiting process. The system makes no progress - processes stuck indefinitely.

Simple Example

Process A:                      Process B:
holds Resource 1                holds Resource 2
waits for Resource 2            waits for Resource 1

Result: Both wait forever!

Four Conditions for Deadlock

ALL four conditions must be present simultaneously for deadlock to occur:

1. Mutual Exclusion

Resource cannot be shared - only one process uses it at a time:

Printer: Only one job can use at time
Database record: Only one transaction can update
Mutex: Only one thread holds lock

If resource sharable → No deadlock possible

2. Hold and Wait

Process holds allocated resource while waiting for another:

Process 1:
- Holds: Resource A
- Waits for: Resource B (held by Process 2)

If all resources allocated at start (no waiting) → No deadlock
If all resources released before requesting new ones → No deadlock

3. No Preemption

Resources cannot be forcibly taken from processes:

Process A has Resource 1
Process B can't say: "Give me Resource 1!"
Resource stays with A until A voluntarily releases

If preemptive (can take away) → Deadlock handled

Exception: Some systems allow preemption (e.g., memory paging)

4. Circular Wait

Circular chain of processes, each waiting for next:

P1 waits for P2's resource
P2 waits for P3's resource
P3 waits for P4's resource
P4 waits for P1's resource
↑________ circular chain

If linear chain: P1→P2→P3→P4 (P4 doesn't wait on anyone) → No deadlock

Why All Four Must Exist?

If remove ANY one condition → Deadlock impossible

Remove Mutual Exclusion

Allow sharing:
Process 1: Read file
Process 2: Read same file
Process 3: Read same file
No conflict → No deadlock

Remove Hold and Wait

Get all resources at start or none:
Process 1: Request(A, B, C) at start
If unavailable, wait. If available, get all.
Never hold some while requesting others → No deadlock

Remove No Preemption

Take away resources:
If Process A waiting, forcibly take its resources, give to B
A goes back to ready queue, try again later
No circular wait possible → No deadlock

Remove Circular Wait

Order resources (e.g., 1 < 2 < 3):
Process must request in order
P1: wants 1, 3 → request 1 then 3
P2: wants 2, 3 → request 2 then 3
No circular chain possible → No deadlock

Deadlock vs Starvation

Deadlock vs Livelock

Deadlock

Process 1: Locked (waiting)
Process 2: Locked (waiting)
No change, both stuck

Livelock

Process 1: Keep trying to acquire lock (fails)
Process 2: Keep trying to acquire lock (fails)
Both keep executing but make no progress

Both bad, deadlock more serious

Deadlock in Resource Allocation

Basic Scenario

Resources:
- 2 Printers
- 3 Disk Drives

Process P1:
- Holds: 1 Printer
- Waits for: 1 Disk Drive

Process P2:
- Holds: 1 Printer, 2 Disk Drives
- Waits for: nothing (needs nothing more)

Available: 0 Printers, 1 Disk Drive

Problem:
- P1 waits for disk drive (only 1 available)
- P2 has 2, only needs P1 to finish to release printer
- P2 could finish if had 1 more disk drive
- But P1 waiting for that disk drive

DEADLOCK! (Circular wait)

Deadlock Scenarios

Scenario 1: Bridge Crossing

        ───Bridge───

Car A ←─────────┐
                ├─ Bridge (narrow, one car at time)
Car B ───────────┘

Both enter bridge from opposite ends simultaneously
Both stop (mutual exclusion)
Both wait for other to back up (hold-and-wait)
Can't go backward on bridge (no preemption)
Both stuck (circular wait)

Scenario 2: Thread Deadlock

Thread 1:                       Thread 2:
lock(mutex1);                   lock(mutex2);
// wants mutex2                 // wants mutex1
lock(mutex2);  [BLOCKED]        lock(mutex1);  [BLOCKED]

DEADLOCK!

Scenario 3: Database Transaction

Transaction A:
- Holds lock on Record 1
- Waits for lock on Record 2

Transaction B:
- Holds lock on Record 2
- Waits for lock on Record 1

DEADLOCK!

Deadlock Detection in System

Signs of Deadlock

1. System stops making progress
   • CPU utilization normal but nothing gets done
2. Processes blocked indefinitely
   • Checked system processes
   • Some in “blocked” state, don’t change
3. Resource allocation looks circular
   • Resource allocation graph shows cycle

Impact of Deadlock

For Single Process

• That process frozen
• Others may continue

For Multiple Processes (Circular)

• All processes in cycle frozen
• System appears hung

For System

• Minor deadlock: Few processes affected, system continues
• Major deadlock: Critical processes affected, system appears crashed

Examples

Minor:

Background backup process deadlocked
Users don't notice, system continues
Eventually detect and kill process

Major:

Init process deadlocked
System doesn't boot
Complete system failure

Deadlock Probability

Deadlock more likely when:

1. Many processes competing
2. Complex resource dependencies
3. Poor synchronization design
4. Random timing (hard to predict)

Deadlock less likely when:

1. Few processes
2. Simple resource needs
3. Good design (avoid hold-and-wait)

Strategies to Handle Deadlock

Three approaches:

1. Prevention

Eliminate one condition so deadlock impossible

• Design phase
• Guaranteed no deadlock

2. Avoidance

Careful allocation to stay in safe state

• Runtime decisions
• Dynamically prevent deadlock

3. Detection and Recovery

Let deadlock happen, then detect and recover

• Monitor system
• Kill processes if deadlock detected
• Restart from checkpoint

Real-World Deadlock Examples

1. Dining Philosophers

Classic synchronization problem leading to deadlock

2. Database Transactions

Two transactions waiting for locks each other holds

3. Distributed Systems

Server A waiting for Server B, B waiting for A (network deadlock)

4. Operating System

Kernel deadlock in process scheduling (rare but has happened)

Summary

Deadlock occurs when all four conditions exist: mutual exclusion, hold-and-wait, no preemption, circular wait. It’s a serious problem causing system to hang. Not a crash (system doesn’t detect automatically), but makes no progress. Can be handled by prevention (design), avoidance (runtime), or detection-recovery (monitoring). Understanding deadlock conditions is prerequisite for designing deadlock-free systems. Most modern systems use deadlock prevention strategies during design phase.