Chapter 7: Deadlocks¶

System Model¶

System Resources
- Resources include CPU cycles, memory, files, and I/O devices.
- Each resource type may have several instances.
- Processes must request, use, and release resources.
Resource Allocation Graph (RAG)
- Vertices:
  - P = Process
  - R = Resource
- Edges:
  - Request edge (P → R) : Process P requests resource R.
  - Assignment edge (R → P) : Resource R is allocated to process P.
- Cycle:
  - One instance per resource type → Cycle means deadlock.
  - Multiple instances → Cycle may lead to deadlock.

A deadlock occurs when processes are waiting indefinitely for resources held by one another.

Necessary Conditions (Coffman Conditions):

Mutual Exclusion – At least one resource must be held in a non-sharable mode.
Hold and Wait – A process holds at least one resource and waits for others.
No Preemption – Resources cannot be forcibly taken away.
Circular Wait – Circular chain of processes, each waiting for a resource held by the next.

All four conditions must hold simultaneously for a deadlock to occur.

Deadlock Prevention – Ensure that at least one necessary condition cannot hold.
Deadlock Avoidance – Dynamically ensure system never enters an unsafe state.
Deadlock Detection and Recovery – Detect and recover after a deadlock occurs.
Ignore the Problem – Often used in practice if deadlocks are rare.

Mutual Exclusion: Make resources sharable whenever possible.
Hold and Wait: Require processes to request all resources at once or release held ones before requesting new.
No Preemption: Allow preemption when a process must wait.
Circular Wait: Impose a total ordering of all resource types; processes request resources in increasing order only.

Safe State: There exists at least one sequence of process execution that allows all to complete.
Unsafe State: May lead to a deadlock.
Banker’s Algorithm: - Works with multiple resource instances. - Checks if granting a request keeps the system in a safe state before approval.

Single Instance per Resource Type: - Use a Wait-for Graph (edges from process to process). - Cycle in the graph ⇒ Deadlock.
Multiple Instances per Resource Type: - Use an algorithm similar to the Banker’s algorithm. - Periodically check for deadlocks.

Process Termination: - Abort all deadlocked processes. - Or abort one at a time until the cycle is broken. - Selection criteria: process priority, time used, or number of resources held.
Resource Preemption: - Select a victim and take its resources. - Rollback process state as needed. - Avoid starvation by tracking preemption counts.