Chapter 12: Deadlock
Vol 3: Computer Core Expedition · Chapter 12
Metadata Card
| Attribute | Value |
|---|---|
| Keywords | Four Conditions, Prevention, Avoidance, Detection, Recovery, Banker's Algorithm |
Your Progress
"A waits for B, B waits for A. Both are stuck forever. This is deadlock — and it's one of the most feared problems in concurrent programming."
Encounter 1: Four Necessary Conditions
- Mutual exclusion: Resource cannot be shared
- Hold and wait: Holding one resource while waiting for another
- No preemption: Resource cannot be forcibly taken
- Circular wait: Circular chain of waiting processes
Encounter 2: Deadlock Prevention
Break any one of the four conditions:
- Break mutual exclusion: Use shared resources when possible
- Break hold and wait: Request all resources at once
- Break no preemption: Allow resource preemption
- Break circular wait: Impose a total order on resource acquisition
Encounter 3: Deadlock Avoidance (Banker's Algorithm)
Each process declares its maximum resource needs in advance. The system only grants a request if the resulting state is "safe" — there exists some order in which all processes can complete.
Encounter 4: Detection and Recovery
- Detection: Build a resource allocation graph; check for cycles
- Recovery options: Kill processes, preempt resources, rollback
Verification Checklist
- [ ] Can recite the four deadlock conditions
- [ ] Can explain at least one prevention strategy
- [ ] Can describe the Banker's algorithm intuition
- [ ] Can identify a deadlock from a resource allocation graph
→ Next Stop Preview
Chapter 13: File Systems and Crash Recovery