- 2071 Bhadra · 10 marks
Deadlock detection with allocation matrices
Short answer
Total resources are 7 A, 2 B, 6 C instances. Sum allocations equal totals, so Available is (0,0,0). Detection shows all processes can finish (P0→P2→P1→P3→P4), so system is not deadlocked. If P2 requests (0,0,1), only P0 finishes; P1, P2, P3, P4 become deadlocked.
Consider a system with 5 processes P0 through P4 and three resources types A, B, C. Resource type A has 7 instances, B has 2 and C has 6 instances. Suppose at t0 time we have following state:
| Process | Allocation (A B C) | Request (A B C) | Available (A B C) |
|---|---|---|---|
| P0 | 0 1 0 | 0 0 0 | 0 0 0 |
| P1 | 2 0 0 | 2 0 2 | |
| P2 | 3 0 3 | 0 0 0 | |
| P3 | 2 1 1 | 1 0 0 | |
| P4 | 0 0 2 | 0 0 2 | |
| a) Is the given system in deadlock state? | |||
| b) Suppose P2 makes an additional request (0, 0, 1) what will be the effect of this request to the system? |
Method
Use the deadlock detection algorithm: Work = Available; a process is marked Finish if its Request ≤ Work, and then Work = Work + Allocation. Processes that cannot be marked at the end are deadlocked.
Total (A, B, C) = (7, 2, 6). Sum of allocations = (0+2+3+2+0, 1+0+0+1+0, 0+0+3+1+2) = (7, 2, 6), so Available = (0, 0, 0).
a) State at t0
Work = (0, 0, 0)
| Step | Process | Request | Request ≤ Work? | Work after |
|---|---|---|---|---|
| 1 | P0 | 0 0 0 | yes | 0 0 0 + 0 1 0 = 0 1 0 |
| 2 | P2 | 0 0 0 | yes | 0 1 0 + 3 0 3 = 3 1 3 |
| 3 | P1 | 2 0 2 | yes | 3 1 3 + 2 0 0 = 5 1 3 |
| 4 | P3 | 1 0 0 | yes | 5 1 3 + 2 1 1 = 7 2 4 |
| 5 | P4 | 0 0 2 | yes | 7 2 4 + 0 0 2 = 7 2 6 |
All processes can finish, in the order P0, P2, P1, P3, P4 (other orders also work).
Answer (a): The system is NOT in a deadlocked state.
b) P2 additionally requests (0, 0, 1)
Now Request(P2) = (0, 0, 1), and Available is still (0, 0, 0).
Work = (0, 0, 0)
- P0: Request (0,0,0) ≤ Work, so P0 finishes; Work = (0, 1, 0).
- P1: needs (2,0,2) > (0,1,0), cannot proceed.
- P2: needs (0,0,1), but C = 0, cannot proceed.
- P3: needs (1,0,0), but A = 0, cannot proceed.
- P4: needs (0,0,2), cannot proceed.
No further process can proceed. Only P0 finishes, and the resources it releases are too few to help the others.
Answer (b): The system becomes deadlocked, with P1, P2, P3 and P4 deadlocked. The system must then recover, e.g. by aborting one of these processes or preempting its resources.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Deadlock vs postponement; Banker's 4 resources · Operating System, chapter 7
- Deadlock conditions; Banker's with 4 processes · Operating System, chapter 7
- Deadlock conditions; Banker's safe sequence · Operating System, chapter 7
- Banker's algorithm, 5 processes, 4 resources · Operating System, chapter 7
- Deadlock, postponement, prevention, 2 processes · Operating System, chapter 7
- Deadlock conditions, detection, action · Operating System, chapter 7
- Get data from P0, send to P1 (asm and C) · Embedded System, chapter 9
- Short note: Resource allocation and smoothing · Project Engineering, chapter 3 · asked 4×
- Non-preemptive SJF with P4 arriving · Embedded System, chapter 6 · asked 2×
- Preemptive priority scheduling with P4 (6 ms) · Embedded System, chapter 6 · asked 2×