Session 3.4 - Deadlock Fundamentals

Learning Objectives

By the end of this session, you will be able to:

Define deadlock and understand its characteristics
Identify the four necessary conditions for deadlock
Understand system models for deadlock analysis
Construct and analyze resource allocation graphs
Detect deadlock situations using graph algorithms
Analyze real-world deadlock scenarios

Key Concept

Deadlock occurs when a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process in the set.

System Model

To understand deadlock, we need to establish a system model that describes how processes and resources interact in an operating system.

Resource Types

Physical Resources

CPU cores
Memory blocks
I/O devices (printers, disk drives)
Network interfaces

Logical Resources

Files and databases
Semaphores and locks
Shared memory segments
Message queues

Resource Usage Protocol

// Standard resource usage pattern
1. Request: Process requests resource
   - If available: granted immediately
   - If not available: process must wait

2. Use: Process uses the resource
   - Perform operations on resource
   - Resource is exclusively held

3. Release: Process releases resource
   - Resource becomes available
   - Waiting processes may be awakened

Resource Instances

Each resource type may have multiple instances. For example, a system might have 3 printers (3 instances of printer resource type) or 4 CPU cores (4 instances of CPU resource type).

Deadlock Characterization

What is Deadlock?

A deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process in the set. Since all processes are waiting, none can proceed.

Real-World Analogy

Traffic Deadlock

Imagine a narrow bridge where cars from both directions meet in the middle. Each car holds its position (resource) and waits for the other to move, but neither can proceed without the other moving first.

Dining Philosophers

Five philosophers need two forks to eat. If each picks up their left fork simultaneously, all will wait forever for the right fork, creating a circular wait condition.

Deadlock vs Other Conditions

Deadlock

Permanent blocking - processes cannot proceed without external intervention

Starvation

Indefinite postponement - process may eventually get resources

Livelock

Processes actively change state but make no progress toward completion

Necessary Conditions for Deadlock

Deadlock can occur if and only if all four of the following conditions hold simultaneously in a system:

1. Mutual Exclusion

At least one resource must be held in a non-shareable mode. Only one process can use the resource at a time.

Example: Printer resource
- Only one process can print at a time
- If P1 is using printer, P2 must wait
- Cannot be shared simultaneously

2. Hold and Wait

A process must be holding at least one resource and waiting to acquire additional resources held by other processes.

Example: Process P1
- Holds resource A (printer)
- Waits for resource B (scanner)
- Will not release A until gets B

3. No Preemption

Resources cannot be preempted. A resource can only be released voluntarily by the process holding it.

Example: File locks
- Process P1 locks file F
- OS cannot force P1 to release F
- P1 must voluntarily unlock F

4. Circular Wait

A set of processes {P0, P1, ..., Pn} exists such that P0 waits for P1, P1 waits for P2, ..., Pn waits for P0.

Example: Circular dependency
- P1 holds A, waits for B
- P2 holds B, waits for C  
- P3 holds C, waits for A
- Forms cycle: P1→P2→P3→P1

Important Note

All four conditions are necessary for deadlock to occur. If any one condition is eliminated, deadlock cannot happen. However, the presence of all four conditions does not guarantee deadlock - it only makes it possible.

Resource Allocation Graphs

Resource allocation graphs provide a visual method for describing deadlocks. They help us understand the relationships between processes and resources.

Graph Components

Vertices

Process vertices: Represented as circles (P1, P2, P3, ...)
Resource vertices: Represented as rectangles (R1, R2, R3, ...)
Resource instances: Dots inside resource rectangles

Edges

Request edge: Process → Resource (Pi requests Rj)
Assignment edge: Resource → Process (Rj assigned to Pi)
Direction matters: Shows the flow of requests and assignments

Example: Simple Resource Allocation Graph

Scenario: Two processes, two resources

P1

R1

P2

R2

P1

P1 holds R2, requests R1 | P2 holds R1, requests R2 → DEADLOCK!

Graph Analysis Rules

No Deadlock

No cycles in the graph
All processes can eventually complete
Resources can be allocated safely

Possible Deadlock

Cycle exists in the graph
If single instance per resource type → deadlock
If multiple instances → may or may not be deadlock

Multiple Instance Example

Resource R1 has 2 instances: [•][•]
Resource R2 has 1 instance:  [•]

Process P1: holds 1 instance of R1, requests R2
Process P2: holds R2, requests 1 instance of R1  
Process P3: requests 1 instance of R1

Analysis:
- Cycle exists: P1 → R2 → P2 → R1 → P1
- But R1 has 2 instances, P3 can get the second instance
- When P3 finishes, it releases R1 instance
- P2 can then get R1 instance and finish
- P2 releases R2, allowing P1 to continue
- Result: NO DEADLOCK despite cycle!

Deadlock Detection Methods

There are several algorithms to detect deadlock in a system. The choice depends on the system characteristics and resource types.

Single Instance Algorithm

Wait-for Graph Method

For systems where each resource type has exactly one instance, we can use a simplified wait-for graph.

Wait-for Graph Construction:
1. Remove resource nodes from resource allocation graph
2. Collapse edges: if Pi → Rj → Pk, create edge Pi → Pk
3. Result: Graph with only process nodes
4. Edge Pi → Pj means Pi waits for Pj to release a resource

Deadlock Detection:
- Run cycle detection algorithm on wait-for graph
- If cycle exists → deadlock present
- Time complexity: O(n²) where n = number of processes

Multiple Instance Algorithm

Banker's Algorithm Variant

For systems with multiple instances per resource type, we use a more complex detection algorithm.

Data Structures:
- Available[m]: Available instances of each resource type
- Allocation[n][m]: Current allocation matrix
- Request[n][m]: Current request matrix

Algorithm:
1. Initialize Work = Available
2. Find process Pi such that:
   - Pi is not finished
   - Request[i] ≤ Work
3. If found:
   - Work = Work + Allocation[i]
   - Mark Pi as finished
   - Go to step 2
4. If no such process found:
   - If all processes finished → no deadlock
   - Otherwise → deadlock exists

Time Complexity: O(m × n²)
where m = resource types, n = processes

Detection Frequency

Every Request

Run detection after each resource request. High overhead but immediate detection.

Periodic

Run detection at regular intervals. Balance between overhead and detection delay.

On Demand

Run when CPU utilization drops below threshold. Indicates possible deadlock.

Practical Examples

Example 1: Database Deadlock

Scenario: Two transactions accessing database records

Transaction T1:          Transaction T2:
1. Lock Record A         1. Lock Record B
2. Read/Update A         2. Read/Update B  
3. Lock Record B         3. Lock Record A
4. Read/Update B         4. Read/Update A
5. Commit                5. Commit

Deadlock occurs at step 3:
- T1 holds A, waits for B
- T2 holds B, waits for A
- Circular wait condition satisfied

Example 2: File System Deadlock

Scenario: Processes accessing multiple files

Process P1:              Process P2:
1. Open file1 (exclusive) 1. Open file2 (exclusive)
2. Process file1         2. Process file2
3. Open file2 (exclusive) 3. Open file1 (exclusive)
4. Merge files           4. Merge files
5. Close files           5. Close files

Analysis:
✓ Mutual Exclusion: Files opened exclusively
✓ Hold and Wait: Hold one file, wait for another
✓ No Preemption: Cannot force file closure
✓ Circular Wait: P1→file2→P2→file1→P1

Result: DEADLOCK at step 3

Example 3: Memory Allocation Deadlock

Scenario: Processes requesting memory blocks

System: 200 MB total memory, 50 MB available

Process P1: Has 80 MB, requests 70 MB more
Process P2: Has 70 MB, requests 80 MB more

Analysis:
- P1 needs 150 MB total (has 80, needs 70 more)
- P2 needs 150 MB total (has 70, needs 80 more)
- Available: 50 MB
- Neither can proceed without the other releasing memory
- Classic hold-and-wait deadlock scenario

Solution approaches:
1. Process termination
2. Resource preemption (swap to disk)
3. Prevention through resource ordering

Session Summary

Key Takeaways:

Deadlock Definition: Permanent blocking where processes wait for each other indefinitely
Four Necessary Conditions: Mutual exclusion, hold and wait, no preemption, circular wait
System Model: Understanding resource types, instances, and usage protocols
Resource Allocation Graphs: Visual representation for deadlock analysis
Detection Algorithms: Wait-for graphs for single instances, matrix algorithms for multiple instances
Real-world Impact: Database transactions, file systems, and memory management

Study Tips:

Practice drawing resource allocation graphs
Identify the four conditions in real scenarios
Work through detection algorithms step by step
Analyze different deadlock examples

Important Concepts:

Deadlock vs Starvation: Permanent vs indefinite postponement
Graph Cycles: Necessary but not sufficient for deadlock
Resource Instances: Multiple instances complicate analysis
Detection Frequency: Trade-off between overhead and response time

Next Topics:

Deadlock prevention strategies
Deadlock avoidance algorithms
Recovery from deadlock
Combined approaches to deadlock handling

Next Session:

Session 3.5: Deadlock Prevention and Avoidance
Strategies to prevent deadlock occurrence and algorithms to avoid unsafe states

Session 3.4: Deadlock Fundamentals