--- title: "Deadlock detection with examples" subject: "Operating System" chapter: 7 key: "semester_6/operating_system:deadlock-detection-examples" source: https://www.bctengineer.com/q/semester_6/operating_system/deadlock-detection-examples site: BCT Engineering --- # Deadlock detection with examples Operating System · Chapter 7: Deadlock - Asked in: year not given - Video: [Deadlock detection algorithm with example](https://www.youtube.com/watch?v=RRnv6FD1He4) — Naimish Garg - 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-examples - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-7 ## Question How can you detect deadlock? Explain with examples. ## Short answer Deadlock detection uses a wait-for graph for single-instance resources where a cycle indicates deadlock, or a matrix algorithm for multiple instances where processes are marked if their requests can be satisfied by available resources. In the example with three processes and resources (3,2,2), all processes finish so no deadlock exists; if all requested (1,0,0), none could proceed and all would be deadlocked. ## Answer **Deadlock detection** lets the system enter deadlock, then uses an algorithm to find the deadlocked processes and recovers afterwards. #### 1. Single instance of each resource: wait-for graph / RAG Edges: resource → process (allocated), process → resource (requested). A cycle means deadlock. Example: P1 holds R1 and wants R2; P2 holds R2 and wants R1. ```text R1 --> P1 --> R2 --> P2 --> R1 (cycle) ``` The graph has a cycle, so P1 and P2 are deadlocked. #### 2. Multiple instances: matrix algorithm Data: Available, Allocation, Request. 1. Work = Available. Finish[i] = true if Allocation[i] is zero, else false. 2. Find a process i with Finish[i] = false and Request[i] ≤ Work. 3. Work = Work + Allocation[i]; Finish[i] = true; go to step 2. 4. Processes with Finish = false are deadlocked. **Example:** 3 processes, resource types A, B, C with 3, 2, 2 instances. | Process | Allocation (A B C) | Request (A B C) | |---|---|---| | P0 | 1 0 0 | 0 1 1 | | P1 | 1 1 0 | 1 0 0 | | P2 | 1 0 1 | 0 0 1 | Available = total − allocated = (3,2,2) − (3,1,1) = (0,1,1). - Work = (0,1,1). P0 requests (0,1,1) ≤ Work, so P0 finishes: Work = (1,1,1). - P1 requests (1,0,0) ≤ (1,1,1), so it finishes: Work = (2,2,1). - P2 requests (0,0,1) ≤ (2,2,1), so it finishes: Work = (3,2,2). All processes finish, so there is **no deadlock**. If instead every process requested (1,0,0), then Work = (0,1,1) has A = 0, so no request could be met; no process could be marked and P0, P1 and P2 would all be reported as deadlocked. #### When to run At every request (costly), at fixed intervals, or when CPU utilisation falls (many processes blocked). After detection, recover by terminating processes or preempting resources. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In a resource allocation graph with single instances, what indicates deadlock? A. Any process node with an outgoing edge B. More resources than processes C. A cycle in the graph D. A resource node with no edges Answer: C. With single instances a cycle means deadlock. (Key point: RAG detection) 2. In the matrix algorithm, which process can be marked Finish? A. One with Need > Work; then Work -= Allocation B. Any process in index order C. One with the largest Allocation D. One with Finish false and Request <= Work; then Work += its Allocation Answer: D. A process whose request can be met will finish and release its allocation. (Key point: Matrix algorithm step) 3. Available (0,1,1); P0 requests (0,1,1). What happens? A. P0 finishes giving Work (1,1,1), then P1 and P2 follow, so no deadlock B. P0 cannot finish, so deadlock C. P0 finishes but Work stays (0,1,1) D. All processes are deadlocked Answer: A. Allocation (1,0,0) is added to Work, enabling the others in turn. (Key point: Example result) 4. When may the detection algorithm run? A. Only at boot B. At every request, at intervals, or when CPU utilisation falls C. Only after a process is killed D. Never; it runs by itself in hardware Answer: B. Running at every request is costly; low CPU use suggests many blocked processes. (Key point: When to run) ## Related in Operating System - [Deadlock conditions, detection, action](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-conditions-detection-recovery-action) — Operating System, chapter 7 - [Deadlock conditions; detection with example](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-conditions-detection-example) — Operating System, chapter 7 - [Deadlock detection with allocation matrices](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-detection-matrices) — Operating System, chapter 7 - [Avoidance, detection, prevention techniques](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-avoidance-detection-prevention) — Operating System, chapter 7 ## Related in other subjects - [Back-face detection algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Aback-face-detection-method) — Computer Graphics, chapter 7, asked 8× - [Distributed deadlock; two-phase commit](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adistributed-deadlock-2pc) — Distributed System, chapter 8 - [Parallelism, IPC deadlock and OS role](https://www.bctengineer.com/question.md?key=semester_4%2Fmicroprocessor%3Aparallelism-deadlock-os-role) — Microprocessor, chapter 6 - [Event types; airport weapon detection Bayes](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Aairport-weapon-bayes) — Probability and Statistics, chapter 1