--- title: "Deadlock conditions, detection, action" subject: "Operating System" chapter: 7 key: "semester_6/operating_system:deadlock-conditions-detection-recovery-action" source: https://www.bctengineer.com/q/semester_6/operating_system/deadlock-conditions-detection-recovery-action site: BCT Engineering --- # Deadlock conditions, detection, action Operating System · Chapter 7: Deadlock - Asked in: 2071 Magh, 4+6 marks - Video: [7.37- (Eng) Detection And Recovery Of Deadlocks | Wait For Graph | Recovery of Deadlock | Deadlock](https://www.youtube.com/watch?v=IUQY-QvXj-k) — TutorialsSpace- Er. Deepak 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-conditions-detection-recovery-action - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-7 ## Question Explain the necessary conditions of deadlock. How can a system detect deadlock and what does it do after detection? ## Short answer The four conditions are mutual exclusion, hold and wait, no preemption, circular wait. Detection uses a resource-allocation graph (single instance) for cycles or a matrix algorithm (multiple instances). After detection, recovery includes process termination (abort some or all), resource preemption with rollback, or manual killing. ## Answer #### Necessary conditions 1. **Mutual exclusion:** a resource can be used by only one process at a time. 2. **Hold and wait:** a process holds resources while requesting more. 3. **No preemption:** resources cannot be taken away forcibly. 4. **Circular wait:** a cycle of processes exists, each waiting for a resource held by the next. #### Deadlock detection The system allows deadlock to happen and periodically runs an algorithm to find it. **1. Resource allocation graph (single instance per resource)** Nodes are processes and resources; a request edge is P → R and an assignment edge is R → P. A *cycle* in the graph means deadlock. (A wait-for graph is also used: P → Q if P waits for a resource held by Q.) ```text P1 --> R1 --> P2 --> R2 --> P1 (cycle = deadlock) ``` **2. Matrix algorithm (multiple instances)** Uses Available, Allocation and Request. 1. Work = Available; Finish[i] = false if Allocation[i] ≠ 0, otherwise true. 2. Find i with Finish[i] = false and Request[i] ≤ Work. 3. Work = Work + Allocation[i]; Finish[i] = true; repeat. 4. Processes with Finish = false are deadlocked. Detection is run at fixed time intervals or when CPU utilisation falls below a threshold, since running it on every request is costly. #### Action after detection (recovery) **1. Process termination** - Abort all deadlocked processes (simple but costly), or - Abort one process at a time until the cycle is broken. The victim is chosen by priority, time already computed, resources held, resources still needed, and whether it is interactive. **2. Resource preemption** - Select a victim and take its resources away to give to another process (minimising cost). - Roll the victim back to a safe state (checkpoint) and restart it. - Prevent starvation by limiting the number of times the same process is chosen as a victim. **3. Manual recovery:** the operator is informed and kills processes by hand; e.g. in UNIX, which largely ignores deadlock (the ostrich approach), the system administrator kills the stuck processes. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. With one instance per resource, what indicates deadlock? A. A cycle in the resource allocation graph B. Any request edge C. More processes than resources D. An empty graph Answer: A. With multiple instances a cycle is not sufficient. (Key point: Single-instance detection) 2. In the matrix algorithm, which processes are deadlocked? A. Those with Finish = true B. Those with zero allocation C. Those with Finish = false at the end D. Those with largest request Answer: C. They could not be satisfied by Work. (Key point: Matrix algorithm result) 3. Why is detection not run on every request? A. It cannot detect on request B. It is costly; it runs at intervals or when CPU utilisation drops C. It prevents deadlock D. It needs no CPU Answer: B. Periodic checks balance cost. (Key point: Run frequency) 4. Which are recovery methods? A. Increasing Available only B. Granting more mutual exclusion C. Ordering resources D. Process termination and resource preemption with rollback Answer: D. Victim selection considers priority, time computed and resources held; limit victim count to avoid starvation. (Key point: Recovery) ## Related in Operating System - [Deadlock; necessary conditions with examples](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-necessary-conditions-examples) — Operating System, chapter 7 - [Deadlock conditions and why all necessary](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-conditions-why-necessary) — Operating System, chapter 7 - [Necessary conditions; deadlock prevention](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-prevention-necessary-conditions) — 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 examples](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-detection-examples) — 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 ## Related in other subjects - [Deadlock and Coffman conditions](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Acoffman-deadlock) — Embedded System, chapter 6, asked 4× - [Deadlock and its conditions](https://www.bctengineer.com/question.md?key=semester_4%2Fmicroprocessor%3Adeadlock-conditions) — Microprocessor, chapter 6, asked 2× - [Buffer action; pH after adding KOH to acetic acid buffer](https://www.bctengineer.com/question.md?key=semester_2%2Fengineering_chemistry%3Aacidic-buffer-koh-ph) — Engineering Chemistry, chapter 1 - [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×