1. Deadlock: Basics and Conditions
Definition
A deadlock occurs when two or more processes cannot proceed because each holds a resource and waits for another, creating a cyclic dependency.
Four Necessary Conditions
| Condition | Description | Example |
|---|
| Mutual Exclusion | Resources are non-sharable. | Printer, file locks. |
| Hold and Wait | Process holds resources while waiting for others. | P1 holds R1, waits for R2. |
| No Preemption | Resources cannot be forcibly taken. | CPU time, memory. |
| Circular Wait | Processes form a cycle of waiting. | P1→P2→P3→P1. |
2. Resource Allocation Graphs (RAGs)
Purpose
Visualize resource allocation states to detect deadlocks. Components:
- Processes: ○ (e.g., P1)
- Resources: □ (single instance: □‧; multi-instance: □‧‧‧)
- Edges:
- Request Edge: Process → Resource.
- Assignment Edge: Resource → Process.
Example: Single-Instance Deadlock
Processes: P1, P2
Resources: R1‧, R2‧
Edges:
R1 → P1 (P1 holds R1)
R2 → P2 (P2 holds R2)
P1 → R2 (P1 waits for R2)
P2 → R1 (P2 waits for R1)
Cycle: P1 → R2 → P2 → R1 → P1 → ... → **Deadlock**.
3. Types of Waiting
| Type | Description | Example |
|---|
| Direct Waiting | Process waits for a held resource. | P1 → R1 (held by P2). |
| Indirect Waiting | Chain of waiting processes. | P1 → P2 → P3 → P1. |
| Indefinite Waiting | Process starved due to unfair policy. | Low-priority process. |
4. Single-Instance vs. Multi-Instance RAGs
Single-Instance RAGs
- Resources have one instance (e.g., printer).
- Cycle in RAG = Deadlock.
- Detection: Use cycle-checking in the graph.
Multi-Instance RAGs
- Resources have multiple instances (e.g., RAM blocks).
- Cycle ≠ Deadlock (if free instances exist).
- Detection: Use the Banker’s Algorithm.
5. Deadlock Detection
1. Single-Instance: Cycle Detection via Wait-For Table
Step 1: Create a Wait-For Table
Step 2: Detect Cycles
- P1 waits for P2, and P2 waits for P1 → Cycle = Deadlock.
2. Multi-Instance: Banker’s Algorithm (Table-Based)
Step 1: Define Resource Allocation Tables
| Process | Allocation (R1) | Max (R1) | Need (R1) | Available (R1) |
|---|
| P1 | 1 | 3 | 2 | 2 |
| P2 | 2 | 4 | 2 | |
- Need = Max – Allocation.
- Total Instances = Allocated + Available = 1 + 2 + 2 = 5.
Step 2: Safety Check via Table Filling
| Step | Process | Work (Available) | Finish |
|---|
| 1 | P1 | 2 → 2 + 1 = 3 | Yes |
| 2 | P2 | 3 → 3 + 2 = 5 | Yes |
- Safe Sequence: P1 → P2. No Deadlock.
Example: Deadlock Scenario
| Process | Allocation | Max | Need | Available |
|---|
| P1 | 2 | 3 | 1 | 1 |
| P2 | 1 | 2 | 1 | |
- Need (P1)=1, Need (P2)=1, Available=1.
- Neither process can be satisfied → Deadlock.
6. Detection Workflow Comparison
| Method | Single-Instance RAGs | Multi-Instance RAGs |
|---|
| Approach | Cycle detection in Wait-For Table | Banker’s Algorithm (tables) |
| Complexity | O(n) for cycle check | O(n² × m) for n processes, m resources |
| Tools | Adjacency matrix/graph | Allocation, Max, Need tables |
7. Visual Examples
Single-Instance Deadlock (Wait-For Table)
Processes: P1, P2
Wait-For Table:
P1 → P2
P2 → P1
Cycle Detected → Deadlock.
Multi-Instance Safe State (Banker’s Tables)
Total Resources: R1=5
Allocation Table:
P1: 1, P2: 2 → Allocated = 3
Available: 2
Need Table:
P1: 2, P2: 2
Safety Sequence: P1 (needs 2 ≤ 2) → P2 (needs 2 ≤ 3).
8. Conclusion
- Single-Instance Deadlocks are detected via cycle-checking in Wait-For tables.
- Multi-Instance Deadlocks require the Banker’s Algorithm with resource tables.
- Use RAGs to visualize and tables to algorithmically resolve deadlocks.