- LPU MCA Semester 1
- CAP366
- Unit 6
CAP366 · Unit 6: Deadlocks
Deadlock characterization
10 practice questions · in the ETE syllabus
Key points
- Four conditions: mutual exclusion, hold and wait, no preemption, circular wait
- Request edge: process to resource; assignment edge: resource to process
- Single-instance cycle means deadlock; multi-instance cycle is only necessary
- No deadlock if units >= n(m-1)+1
A deadlock is a situation in which every process in a set is waiting for a resource held by another process in the same set, so none can ever proceed. It requires four conditions at the same time (the Coffman conditions):
| Condition | Meaning |
|---|---|
| Mutual exclusion | A resource can be held by one process at a time |
| Hold and wait | A process holds resources while waiting for more |
| No preemption | A resource is released only voluntarily |
| Circular wait | A closed chain of processes each waits for the next |
In a resource-allocation graph, a request edge goes from a process to a resource and an assignment edge goes from a resource to a process. With one instance per resource type, a cycle means deadlock. With several instances, a cycle is necessary but not sufficient, because a process outside the cycle may finish and release an instance.
Worked example: with n processes each needing at most m units of one resource, deadlock is possible with up to n(m-1) units, so n(m-1)+1 units guarantee freedom from deadlock. For n = 3 and m = 3 that is 7 units.
Exam trap: a cycle does not always mean deadlock; it does only when each resource type on it has a single instance.
Try two questions
Resource R1 and R2 each have a single instance. P1 holds R1 and requests R2, while P2 holds R2 and requests R1. No other process exists. Is the system deadlocked?
- Yes, P1 and P2 are deadlocked
- No, because each process already holds a resource and will finish
- Yes, but only P2 is deadlocked because it was granted R2 last
- No, because a deadlock needs at least three processes in the cycle
Show the answer
A. P1 waits for P2 and P2 waits for P1, a cycle over single-instance resources, so both are deadlocked.
Why not B: Each holder is waiting for the other, so neither can finish.
Why not C: Both processes sit on the same cycle, so both are deadlocked together.
Why not D: A cycle of two processes is enough; there is no minimum of three.
R1 has two instances held by P2 and P3, and R2 has two instances held by P1 and P4. P1 requests one instance of R1 and P3 requests one instance of R2, forming a cycle. P2 and P4 request nothing. What is the situation?
- Deadlock, because the graph contains a cycle through P1 and P3
- Deadlock, because P1 and P3 each hold a resource and request another
- No deadlock, because P2 and P4 can finish and release instances
- No deadlock, because each resource has two instances available
Show the answer
C. P2 and P4 are not waiting, so they finish and release instances, letting P1 and P3 proceed. A cycle with multiple instances need not mean deadlock.
Why not A: With multiple instances a cycle is necessary but not sufficient.
Why not B: Hold and wait alone does not decide deadlock; someone outside the cycle can release instances.
Why not D: Both instances of each resource are held, so none is free right now.