PART 2 • RESOURCE CONTROL
Recognise, Avoid and Recover from Deadlock
Model processes and resources precisely, distinguish a deadlock from ordinary waiting, then prove whether a state is safe using the same Work and Finish reasoning used by Banker’s Algorithm.
BY THE END, YOU CAN
Defend a deadlock decision
- Identify all four Coffman conditions.
- Read request and assignment graph edges.
- Separate prevention, avoidance and detection.
- Calculate Need and find a safe sequence.
- Explain recovery costs and victim selection.
Deadlock Is Permanent Circular Waiting among a Set of Processes
Each process in the set waits for an event that only another process in that same set can cause—normally the release of a resource.
returns to P1
Deadlock
The involved processes cannot progress without external intervention.
Starvation
One process may wait indefinitely while other processes continue progressing.
Livelock
Processes keep changing state and reacting, but useful work does not advance.
Long waiting
A process waits for a slow event that can still complete normally.
Deadlock Requires All Four Coffman Conditions at the Same Time
Mutual exclusion
At least one resource is non-shareable; only one process can use its instance at a time.
Example: one printerHold and wait
A process holds at least one resource while requesting additional resources held elsewhere.
Example: hold file lock, request database lockNo preemption
A resource cannot simply be taken away; its holder must release it voluntarily.
Example: partially updated critical stateCircular wait
A closed chain exists where every process waits for a resource held by the next.
Example: P1 → P2 → P3 → P1Edge Direction Tells You Who Requests and Who Holds
P1
request →
R2
P2
← assignment
R2
R1
assignment →
P1
R1
← request
P2
Read one edge at a time
Pi → Rj
Pi requests an instance of Rj.
Rj → Pi
An instance of Rj is assigned to Pi.
Single instance per resource type: a cycle is both necessary and sufficient for deadlock.
Multiple instances: a cycle is necessary but may not be sufficient because another instance can break the wait.
Prevention, Avoidance and Detection Solve Different Problems
| Strategy | Main idea | Information needed | Cost or limitation |
|---|---|---|---|
| Ignore | Assume deadlocks are rare; recover manually or restart. | No future demand model | Failure remains possible |
| Prevention | Structurally break one Coffman condition. | Rules for allocation | Lower utilisation or concurrency |
| Avoidance | Grant only requests that keep the state safe. | Maximum future claims | Conservative; needs advance knowledge |
| Detection | Allow deadlock, periodically discover it, then recover. | Current allocation and requests | Detection and recovery overhead |
Break hold and wait
Request everything together or release held resources before requesting more.
Permit preemption
Take or roll back resources when a request cannot be satisfied safely.
Order resources
Require every process to request resource types in one global order.
Calculate Need and Search for a Safe Sequence
Edit Available, Allocation and Maximum values for three processes and three resource types. The checker validates the matrices before running the safety algorithm.
AVAILABLE
| Process | Allocation | Maximum | Need = Max − Allocation | ||||||
|---|---|---|---|---|---|---|---|---|---|
| A | B | C | A | B | C | A | B | C | |
SAFETY RESULT
Ready to analyse
Select a dataset or edit the values, then run the safety check.
Work and Finish trace
- No safety test has run yet.
Detection Identifies the Set; Recovery Chooses the Damage
Snapshot
Collect Available, Allocation and outstanding Request.
Reduce
Find processes whose requests can be met by current Work.
Release
Simulate completion and add their allocation to Work.
Identify
Unfinished processes form the detected deadlocked set.
Abort processes
Abort all deadlocked processes at once, or choose victims one at a time until the cycle breaks.
Consider priority, progress, resources and restart costTake resources and roll back
Select a victim, reclaim resources, restore a safe checkpoint and retry later.
Prevent repeatedly choosing the same victimClassify the Situation before Choosing a Remedy
Ten Misconception-Specific Checks
Each option explains the exact deadlock reasoning behind it.
Answered correctly: 0 of 10
University and Placement Questions
- Define deadlock.
- List Coffman conditions.
- Define a safe state.
- What is a request edge?
- What is rollback?
- Explain deadlock prevention.
- Run Banker’s safety algorithm.
- Explain allocation graphs.
- Compare avoidance and detection.
- Discuss recovery methods.
- Does a graph cycle always mean deadlock?
- Unsafe versus deadlocked?
- How does lock ordering help?
- What makes a good victim?
- Deadlock versus starvation?
Show a strong answer: “Explain Banker’s safety algorithm”
- Compute Need = Maximum − Allocation.
- Set Work = Available and every Finish value false.
- Find an unfinished process with Need ≤ Work component-wise.
- Assume it completes: Work = Work + its Allocation; set Finish true.
- Repeat. All true means safe and the chosen order is a safe sequence; otherwise the state is unsafe.
LEVEL 7 SUMMARY
You Can Now Separate a Cycle, an Unsafe State and a Deadlock
- Deadlock requires mutual exclusion, hold and wait, no preemption and circular wait.
- Graph cycles prove deadlock only when each resource type has one instance.
- Prevention breaks a condition; avoidance preserves safety; detection acts after allocation.
- Banker’s Algorithm proves safety by finding at least one completion sequence.
- Recovery balances termination, rollback and victim-selection cost.
COURSE CHECKPOINT
Mark Level 7 after you can calculate Need and explain why an unsafe state is not necessarily already deadlocked.
Saved only in this browser.