Notes / University Notes / Operating System / Chapter 7: Deadlocks

Chapter 7: Deadlocks

Created: 2025-12-16Updated: 2025-12-16

The four conditions that together let processes block each other forever, and the three ways out — deny one, check before granting, or clean up after.

Necessary Conditions for Deadlock
1. Mutual Exclusion: exist a resource that only can be used by one process at a time
2. Hold and Wait: a process holding some resources and is waiting for another resource
3. No Preemption: a resource can only be released voluntarily
4. Circular Wait: a set of processes are waiting for each other in a circular chain
System Model
- resources types: $R_1, R_2, ..., R_m$ (e.g. CPU, memory, IO devices)
- each resource type $R_i$ has $W_i$ instances (e.g. a computer has 2 CPUs)
- each process: request → use → release
Resource-Allocation Graph
- a directed graph with processes and resources as nodes
- $P_i \to R_j$ edge: $P_i$ requests $R_j$
- $R_j \to P_i$ edge: $R_j$ is allocated to
- if the graph contains no cycles → no deadlock
- if the graph contains a cycle
  - only one instance per resource type → deadlock
  - multiple instances per resource type → may or may not be deadlock

Necessary Conditions for Deadlock
1. Mutual Exclusion: exist a resource that only can be used by one process at a time
2. Hold and Wait: a process holding some resources and is waiting for another resource
3. No Preemption: a resource can only be released voluntarily
4. Circular Wait: a set of processes are waiting for each other in a circular chain
System Model
- resources types: $R_1, R_2, ..., R_m$ (e.g. CPU, memory, IO devices)
- each resource type $R_i$ has $W_i$ instances (e.g. a computer has 2 CPUs)
- each process: request → use → release
Resource-Allocation Graph
- a directed graph with processes and resources as nodes
- $P_i \to R_j$ edge: $P_i$ requests $R_j$
- $R_j \to P_i$ edge: $R_j$ is allocated to
- if the graph contains no cycles → no deadlock
- if the graph contains a cycle
  - only one instance per resource type → deadlock
  - multiple instances per resource type → may or may not be deadlock