--- title: "Deadlock detection with allocation matrices" subject: "Operating System" chapter: 7 key: "semester_6/operating_system:deadlock-detection-matrices" source: https://www.bctengineer.com/q/semester_6/operating_system/deadlock-detection-matrices site: BCT Engineering --- # Deadlock detection with allocation matrices Operating System · Chapter 7: Deadlock - Asked in: 2071 Bhadra, 10 marks - Video: [Deadlock Detection Algorithm Example - Deadlocks - Operating Systems (KIIT DU)](https://www.youtube.com/watch?v=_d5A_T-AQUE) — Jyotiprakash Mishra CS - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/operating_system/deadlock-detection-matrices - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-7 ## Question 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? ## 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. ## Answer #### 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. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which process may be marked finished? A. One whose Allocation <= Work B. One with the largest Request C. One whose Request <= Work, after which Work += Allocation D. One with zero Request only after all others Answer: C. Finished processes release their allocation. (Key point: Detection rule) 2. At t0, what is the state? A. Deadlocked: all processes B. Deadlocked: P1 only C. Deadlocked: P3 and P4 D. Not deadlocked; e.g. P0, P2, P1, P3, P4 all finish Answer: D. Work grows to (7,2,6), so all finish. (Key point: Part a) 3. Why can P0 and P2 go first with Work (0,0,0)? A. Their requests are (0,0,0) B. They hold most resources C. They have no allocation D. Available is large Answer: A. A zero request is always <= Work. (Key point: Why P0 and P2 first) 4. After P2 requests (0,0,1), what happens? A. No change B. Only P0 finishes; P1, P2, P3, P4 are deadlocked C. All finish D. Only P2 is deadlocked Answer: B. Work stays (0,1,0), which meets none of the others' requests. (Key point: Part b) ## Related in Operating System - [Deadlock vs postponement; Banker's 4 resources](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-vs-postponement-banker-6442) — Operating System, chapter 7 - [Deadlock conditions; Banker's with 4 processes](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afour-conditions-banker-p1-p4) — Operating System, chapter 7 - [Deadlock conditions; Banker's safe sequence](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afour-conditions-banker-snapshot-332) — Operating System, chapter 7 - [Banker's algorithm, 5 processes, 4 resources](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Abanker-five-process-four-resource) — Operating System, chapter 7 - [Deadlock, postponement, prevention, 2 processes](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-postponement-two-process-three-resource) — Operating System, chapter 7 - [Deadlock conditions, detection, action](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-conditions-detection-recovery-action) — Operating System, chapter 7 ## Related in other subjects - [Get data from P0, send to P1 (asm and C)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3A8051-p0-to-p1-assembly-c) — Embedded System, chapter 9 - [Short note: Resource allocation and smoothing](https://www.bctengineer.com/question.md?key=semester_7%2Fproject_engineering%3Aresource-allocation-smoothing-note) — Project Engineering, chapter 3, asked 4× - [Non-preemptive SJF with P4 arriving](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-sjf-nonpreemptive-6-8-2) — Embedded System, chapter 6, asked 2× - [Preemptive priority scheduling with P4 (6 ms)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asched-priority-10-5-7-p4) — Embedded System, chapter 6, asked 2×