- LPU MCA Semester 1
- CAP366
- Unit 6
CAP366 · Unit 6: Deadlocks
Deadlock avoidance and recovery
10 practice questions · in the ETE syllabus
Key points
- Safe state means a safe sequence exists
- Need = Max - Allocation
- Grant a request only if the resulting state is safe
- Recovery: abort processes or preempt resources, avoiding repeated victims
A state is safe if some order (a safe sequence) lets every process finish using the available resources; an unsafe state is not necessarily a deadlock, it only means deadlock may occur. Avoidance keeps the system in safe states.
The Banker's algorithm keeps Available, Max, Allocation and Need, where Need = Max - Allocation. To test safety, repeatedly find a process whose Need <= Work, assume it finishes and add its Allocation to Work; the state is safe if all processes can finish. For a request, check Request <= Need and Request <= Available, pretend to grant it, and run the safety test; if unsafe, the process waits.
Worked example: Available (3,3,2) with five processes has the safe sequence P1, P3, P4, P0, P2.
Detection (for multiple instances) uses the same idea with current Requests instead of Need; processes that cannot finish are deadlocked.
Recovery is by aborting all deadlocked processes, aborting one at a time, or preempting resources from victims. Victim choice weighs priority, work done, resources held and rollbacks; counting past rollbacks prevents starvation.
Exam trap: passing the Available test is not enough; the request is granted only if the resulting state is still safe.
Try two questions
Five processes P0 to P4 share resource types A, B and C with nothing available. Allocation is P0 (0,1,0), P1 (2,0,0), P2 (3,0,3), P3 (2,1,1), P4 (0,0,2), and outstanding requests are P0 (0,0,0), P1 (2,0,2), P2 (0,0,1), P3 (1,0,0), P4 (0,0,2). Which processes are deadlocked according to the detection algorithm?
- P0 and P2 are deadlocked
- P1, P3 and P4 are deadlocked
- P1, P2, P3 and P4 are deadlocked
- No process is deadlocked at all
Show the answer
C. P0 finishes and releases (0,1,0), but no other request fits in that, so P1, P2, P3 and P4 remain blocked.
Why not A: P0 requests nothing, so it finishes and cannot be deadlocked.
Why not B: P2 is also stuck: its request for one C cannot be met by anything released.
Why not D: After P0 finishes, only (0,1,0) is available and nobody else can proceed.
When choosing a victim during recovery from deadlock by termination, which criterion is sensible?
- Choose the process that has been running the longest because it is oldest
- Choose the process with the highest priority to free it
- Choose the process whose termination loses the least work and frees many resources
- Choose any process at random each time so that no pattern appears
Show the answer
C. Victim selection minimises cost: processes with little work done, few resources held but many freed, and low priority are preferred.
Why not A: Killing the oldest process wastes the most computation.
Why not B: Killing high priority work is costly; priority usually protects a process.
Why not D: Random choice ignores cost and can keep hitting the same victim.