Introduction

1. Deadlock: Definition and Basics

What is Deadlock?

A deadlock is a state in a system where two or more processes are unable to proceed because each is waiting for a resource held by another. This results in a permanent blocking of the involved processes.

Four Necessary Conditions for Deadlock

1. Mutual Exclusion: At least one resource must be non-sharable (used by one process at a time).
2. Hold and Wait: Processes hold resources while waiting for others.
3. No Preemption: Resources cannot be forcibly taken from a process.
4. Circular Wait: A cycle of processes exists where each waits for a resource held by the next.

Example of Deadlock

• Process P1 holds Resource R1 and requests Resource R2.
• Process P2 holds Resource R2 and requests Resource R1.
• Neither can proceed, resulting in a deadlock.

2. Resource Allocation Graphs (RAGs)

Purpose of RAGs

A RAG is a directed graph used to model resource allocation states and detect deadlocks. It visualizes:

• Processes (circles)
• Resources (rectangles with dots for instances)
• Edges:
  • Request Edge: Process → Resource (P1 → R2: P1 is waiting for R2).
  • Assignment Edge: Resource → Process (R1 → P1: R1 is allocated to P1).

RAG Components

Component	Symbol	Description
Process	○ (e.g., P1)	A running entity.
Resource	□ (e.g., R1‧‧‧)	Rectangles with dots for instances.
Request Edge	→ (P1 → R2)	Process is waiting for a resource.
Assignment Edge	→ (R1 → P1)	Resource is allocated to a process.

Deadlock Detection in RAGs

• Single-Instance Resources: A cycle in the RAG = Deadlock.
• Multi-Instance Resources: A cycle does not always imply deadlock (depends on availability).

Example 1: Deadlock (Cycle in RAG)

Processes: P1, P2
Resources: R1 (1 instance), R2 (1 instance)
Edges:
- P1 → R1 (assignment: R1 is held by P1)
- P1 → R2 (request: P1 is waiting for R2)
- P2 → R2 (assignment: R2 is held by P2)
- P2 → R1 (request: P2 is waiting for R1)
Cycle: P1 → R1 → P2 → R2 → P1 → ...

Example 2: No Deadlock (No Cycle)

Processes: P1, P2, P3
Resources: R1 (2 instances)
Edges:
- R1 → P1 (assignment)
- R1 → P2 (assignment)
- P3 → R1 (request)
No cycle exists. P3 waits, but no deadlock.

3. Types of Waiting

1. Direct Waiting

• A process waits directly for a resource held by another.
• Example: P1 holds R1; P2 requests R1 → P2 waits for P1.

2. Indirect Waiting (Chain Waiting)

• A chain of processes where each waits for the next.
• Example: P1 waits for P2, which waits for P3, which waits for P1 (forming a cycle).

3. Indefinite Waiting (Starvation)

• A process waits indefinitely due to resource allocation policies (not deadlock).
• Example: Low-priority processes never get access to a resource.

Comparison Table

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 never gets resources.	Low-priority process starved.

4. Deadlock vs. Starvation

Feature	Deadlock	Starvation
Cause	Circular wait + 4 conditions.	Unfair resource allocation.
Resolution	Requires breaking the cycle.	Adjust allocation policies.
Processes Affected	All in the cycle.	One or more (not necessarily linked).

5. Summary

• Deadlocks arise from 4 conditions and can be visualized via RAGs.
• RAGs use nodes (processes/resources) and edges (requests/allocations).
• Cycles in RAGs indicate deadlocks for single-instance resources.
• Types of waiting include direct, indirect, and indefinite (starvation).
• Starvation is not deadlock but unfair resource access.