📝 Deadlock Detection in Operating System (37 MCQs)

📖 From Operating System • 7. Deadlocks • 37 questions available

←Previous Topic:Resource Allocation Graph Algorithm in Deadlock Avoidance📝 Deadlock Detection in Operating SystemSingle Instance of Each Resource Type Deadlock Detection:Next Topic→

What is Deadlock Detection in Operating System?

Definition:
Deadlock detection allows the system to enter deadlock states but periodically runs an algorithm to identify deadlocked processes and initiate recovery.

Example:
A detection routine executes every $T$ milliseconds, examining the current allocation state $S_t$ to determine if set $D \subseteq \{P\}$ is deadlocked.

Reason:
Detection trades occasional deadlock occurrence for reduced runtime overhead during normal operation, optimizing performance when deadlocks are rare.

Easy

Medium

Hard

📝 All Deadlock Detection in Operating System MCQs

Q1. When is a deadlock detection scheme typically employed?

A.When the system uses strict deadlock prevention.

B.When the system uses deadlock avoidance.

C.When the system employs neither prevention nor avoidance algorithms. ✅

D.When the system has only one process.

💡 Difficulty: easy | ✅ Correct: C

📖 Explanation: Deadlock detection is used in environments where the system does not proactively prevent deadlocks (via prevention) or avoid them (via avoidance). It allows deadlocks to occur and then detects and recovers from them.

Q2. What are the two primary components of a deadlock detection-and-recovery scheme?

A.Prevention and Avoidance

B.Detection Algorithm and Recovery Algorithm ✅

C.Allocation and Request

D.Safety Check and Cycle Check

💡 Difficulty: easy | ✅ Correct: B

📖 Explanation: The system must provide an algorithm to examine the state and determine if a deadlock has occurred (Detection) and an algorithm to resolve the situation once detected (Recovery).

Q3. What is the primary function of the detection algorithm?

A.To prevent deadlocks from forming.

B.To avoid unsafe states.

C.To examine the system state to determine if a deadlock has already occurred. ✅

D.To allocate resources efficiently.

💡 Difficulty: easy | ✅ Correct: C

📖 Explanation: Unlike prevention or avoidance, which act proactively, the detection algorithm acts reactively. It inspects the current state of resource allocation and process waiting to identify if a circular wait (deadlock) currently exists.

Q4. What is the role of the recovery algorithm?

A.To detect the deadlock.

B.To break the deadlock after it has been detected. ✅

C.To prevent the deadlock from occurring.

D.To simulate resource requests.

💡 Difficulty: easy | ✅ Correct: B

📖 Explanation: Once the detection algorithm confirms a deadlock, the recovery algorithm takes steps to resolve it, such as terminating processes or preempting resources, to allow the system to continue functioning.

Q5. Does the detection-and-recovery scheme apply to systems with single-instance resources?

A.No, only multiple instances.

B.Yes, it applies to single-instance systems. ✅

C.No, only single-instance systems.

D.It depends on the CPU architecture.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: The text explicitly states that the discussion elaborates on detection requirements for systems with only a single instance of each resource type, as well as those with several instances.

Q6. Does the detection-and-recovery scheme apply to systems with multiple-instance resources?

A.No, only single instances.

B.Yes, it applies to multiple-instance systems. ✅

C.No, Banker's algorithm is used instead.

D.It depends on the memory size.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: The text confirms that detection-and-recovery schemes are applicable to systems with several instances of each resource type, offering an alternative to avoidance algorithms like Banker's.

Q7. What is a significant disadvantage of using a detection-and-recovery scheme?

A.It guarantees no deadlocks.

B.It requires no overhead.

C.It incurs overhead including run-time costs and potential recovery losses. ✅

D.It is faster than prevention.

💡 Difficulty: hard | ✅ Correct: C

📖 Explanation: The text notes that this scheme requires overhead. This includes the computational cost of maintaining state information, executing the detection algorithm, and the potential negative impacts (losses) associated with recovering from a deadlock (e.g., process termination).

Q8. Which of the following is NOT part of the overhead associated with detection-and-recovery?

A.Run-time costs of maintaining information.

B.Execution cost of the detection algorithm.

C.Potential losses from recovery.

D.Cost of preventing deadlocks initially. ✅

💡 Difficulty: medium | ✅ Correct: D

📖 Explanation: Prevention is a different strategy. The overheads listed for detection-and-recovery are maintaining info, running detection, and recovery losses. Prevention costs are irrelevant because this scheme is used when prevention is *not* employed.

Q9. In a system using detection, when can a deadlock occur?

A.Never.

B.Only during startup.

C.At any time if resources are requested in a conflicting manner. ✅

D.Only if there are multiple instances.

💡 Difficulty: medium | ✅ Correct: C

📖 Explanation: Since neither prevention nor avoidance is used, there are no restrictions on resource requests to prevent circular waits. Therefore, a deadlock can occur whenever processes request and hold resources in a way that creates a cycle.

Q10. What distinguishes detection from avoidance?

A.Detection prevents deadlocks; avoidance finds them.

B.Detection finds existing deadlocks; avoidance prevents entering unsafe states. ✅

C.Detection is faster; avoidance is slower.

D.Detection uses graphs; avoidance does not.

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: Avoidance (like Banker's) proactively ensures the system stays in a safe state to prevent deadlocks. Detection allows the system to enter potentially unsafe states and only acts after a deadlock has actually formed.

Q11. In a Wait-For Graph, what do the nodes represent?

A.Resources

B.Processes ✅

C.Both Processes and Resources

D.Memory Blocks

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: A Wait-For Graph is a simplified version of the Resource-Allocation Graph used for single-instance resources. It removes the resource nodes and only contains process nodes. An edge indicates one process is waiting for another.

Q12. How is a Wait-For Graph derived from a Resource-Allocation Graph?

A.By adding more resource nodes.

B.By removing process nodes.

C.By removing resource nodes and collapsing edges. ✅

D.By reversing all edges.

💡 Difficulty: hard | ✅ Correct: C

📖 Explanation: To create a WFG from a RAG (for single instances), you remove the resource nodes. If Process P1 waits for Resource R, and Resource R is held by Process P2, you create a direct edge P1 -> P2 in the WFG. This collapses the P1->R->P2 path into P1->P2.

Q13. What does an edge from Pi to Pj in a Wait-For Graph signify?

A.Pi is holding a resource needed by Pj.

B.Pi is waiting for a resource held by Pj. ✅

C.Pj is waiting for a resource held by Pi.

D.Pi and Pj are sharing a resource.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: In a WFG, an edge $P_i \to P_j$ means that process $P_i$ is blocked, waiting for a resource that is currently allocated to (held by) process $P_j$ .

Q14. If a Wait-For Graph contains a cycle, what does it indicate?

A.The system is safe.

B.A deadlock has occurred. ✅

C.Resources are free.

D.The system is efficient.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: For systems with single-instance resources, a cycle in the Wait-For Graph is a necessary and sufficient condition for deadlock. It means a circular chain of processes is waiting for each other.

Q15. Why might a system choose detection over prevention?

A.Prevention is too complex.

B.Prevention may reduce system throughput and concurrency by imposing strict rules. ✅

C.Detection is always faster.

D.Detection requires no algorithms.

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: Deadlock prevention often imposes restrictive conditions (e.g., no hold-and-wait) that can lead to poor resource utilization and reduced concurrency. Detection allows more freedom in resource usage, accepting the risk of occasional deadlocks which are then resolved.

Q16. What is meant by potential losses inherent in recovering from a deadlock"?"

A.Loss of electrical power.

B.Loss of data or work done by terminated/preempted processes. ✅

C.Loss of network connectivity.

D.Loss of hardware components.

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: Recovery often involves aborting processes or preempting resources. Aborting a process may mean losing the computation it has performed so far. Preempting resources may require rolling back a process to a previous state, leading to lost work.

Q17. Can a detection algorithm be used for multiple-instance systems?

A.No, never.

B.Yes, but the algorithm is different from the single-instance case. ✅

C.Yes, using the same Wait-For Graph method.

D.No, only Banker's algorithm works.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: The text states detection applies to both single and multiple instances. However, the simple cycle detection in a WFG works for single instances. For multiple instances, a more complex algorithm (similar to the safety algorithm but checking for current deadlock rather than future safety) is required.

Q18. What information must be maintained at run-time for detection?

A.Only the number of processes.

B.The state of resource allocation (who holds what, who waits for what). ✅

C.Only the CPU speed.

D.The history of all past allocations.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: To detect deadlocks, the system must track the current state: which resources are allocated to which processes, and which processes are waiting for which resources. This dynamic information is essential for the detection algorithm.

Q19. If a system employs deadlock avoidance, does it need a detection algorithm?

A.Yes, always.

B.No, because avoidance prevents deadlocks from occurring. ✅

C.Yes, for backup.

D.No, because detection is impossible.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: Deadlock avoidance ensures the system never enters an unsafe state where deadlock could occur. Therefore, if implemented correctly, deadlocks should never happen, making a detection algorithm unnecessary.

Q20. What is the main trade-off when choosing not to use prevention or avoidance?

A.Higher complexity for better safety.

B.Lower overhead during normal operation but risk of deadlock and recovery costs. ✅

C.Faster processing but less memory.

D.More resources but slower CPU.

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: By skipping prevention/avoidance, the system avoids their continuous computational overhead and restrictions. However, it risks deadlocks occurring, which incurs the cost of detection and the potential damage/cost of recovery.

Q21. If P1 waits for R2, and R2 is held by P2, how does this appear in the Wait-For Graph?

A.Edge P1 -> R2

B.Edge R2 -> P2

C.Edge P1 -> P2 ✅

D.Edge P2 -> P1

💡 Difficulty: hard | ✅ Correct: C

📖 Explanation: The WFG collapses the resource node. Since P1 waits for R2 and P2 holds R2, P1 is effectively waiting for P2. Thus, a direct edge P1 -> P2 is created in the WFG.

Q22. Which graph is more compact for single-instance systems?

A.Resource-Allocation Graph

B.Wait-For Graph ✅

C.They are the same size.

D.Depends on the number of resources.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: The Wait-For Graph is more compact because it eliminates resource nodes. It only shows the dependencies between processes, reducing the number of nodes and simplifying cycle detection.

Q23. What happens if a deadlock is detected but no recovery algorithm is present?

A.The system automatically fixes it.

B.The involved processes remain blocked indefinitely. ✅

C.The system reboots.

D.The resources are freed.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: Detection only identifies the problem. Without a recovery mechanism, the system knows a deadlock exists but cannot resolve it. The processes involved will remain in a permanent waiting state, effectively hanging that part of the system.

Q24. Why is maintaining state information considered an overhead?

A.It requires extra hardware.

B.It consumes CPU cycles and memory to track allocations and requests continuously. ✅

C.It slows down the disk.

D.It increases network traffic.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: Every time a resource is requested or released, the system must update its internal data structures (tables, graphs). This bookkeeping consumes processing time and memory, which is overhead that wouldn't exist if no tracking was done.

Q25. Is deadlock detection proactive or reactive?

A.Proactive

B.Reactive ✅

C.Both

D.Neither

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: Detection is reactive because it identifies a deadlock *after* it has occurred. Prevention and avoidance are proactive because they try to stop deadlocks from happening in the first place.

Q26. What is the condition for deadlock in a single-instance system using a Wait-For Graph?

A.Absence of cycles

B.Presence of a cycle ✅

C.High CPU usage

D.Low memory

💡 Difficulty: easy | ✅ Correct: B

📖 Explanation: In a single-instance resource system, the presence of a cycle in the Wait-For Graph is equivalent to a deadlock. Each process in the cycle is waiting for the next, creating an unresolvable circular wait.

Q27. Which strategy allows the highest degree of concurrency?

A.Deadlock Prevention

B.Deadlock Avoidance

C.Deadlock Detection and Recovery ✅

D.None, they are equal.

💡 Difficulty: hard | ✅ Correct: C

📖 Explanation: Prevention imposes strict rules (limiting concurrency). Avoidance restricts requests to stay safe (limiting concurrency). Detection allows processes to request resources freely, maximizing concurrency, at the risk of occasional deadlocks.

Q28. What is the primary goal of the recovery algorithm?

A.To detect the deadlock.

B.To restore the system to a non-deadlocked state. ✅

C.To prevent future deadlocks.

D.To optimize resource usage.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: Once a deadlock is detected, the recovery algorithm's job is to break the circular wait. This restores the system to a state where processes can proceed, although it may involve sacrificing some progress (e.g., killing a process).

Q29. Can a Wait-For Graph be used for multiple-instance resources?

A.Yes, directly.

B.No, because a cycle doesn't necessarily imply deadlock in multiple-instance systems. ✅

C.Yes, if you add weights.

D.No, because resources are not shared.

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: In multiple-instance systems, a cycle in a WFG (if one were constructed) is necessary but not sufficient for deadlock. A process might be waiting for a resource held by another, but if multiple instances exist, the resource might become available without the holder releasing it (if another instance is freed). Thus, simple WFG cycle detection is insufficient.

Q30. What is the run-time cost" mentioned in the text?"

A.The cost of buying the computer.

B.The computational overhead of executing the detection algorithm and maintaining state. ✅

C.The cost of electricity.

D.The salary of the operator.

💡 Difficulty: easy | ✅ Correct: B

📖 Explanation: Run-time cost refers to the CPU time and system resources consumed while the operating system is running the detection logic and updating the necessary data structures during normal operation.

Q31. If a system rarely experiences deadlocks, which approach might be most efficient?

A.Strict Prevention

B.Complex Avoidance

C.Detection and Recovery ✅

D.Manual Intervention

💡 Difficulty: hard | ✅ Correct: C

📖 Explanation: If deadlocks are rare, the overhead of constant prevention or avoidance checks may outweigh the occasional cost of detection and recovery. Allowing the system to run freely and only intervening when a deadlock actually occurs can be more efficient overall.

Q32. What does the edge direction in a Wait-For Graph represent?

A.Resource flow

B.Waiting dependency ✅

C.Process creation

D.Memory allocation

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: An edge from Pi to Pj represents a waiting dependency: Pi is dependent on Pj releasing a resource before Pi can proceed.

Q33. Why is recovery considered to have potential losses"?"

A.It always crashes the system.

B.It may require aborting processes, losing their computed results. ✅

C.It deletes all files.

D.It formats the hard drive.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: Recovering from deadlock often involves selecting a victim" process to terminate or roll back. Any work done by that process since its last checkpoint is lost, representing a loss to the user or system."

Q34. Which of the following is true about the Resource-Allocation Graph?

A.It contains only processes.

B.It contains only resources.

C.It contains both processes and resources. ✅

D.It contains neither.

💡 Difficulty: easy | ✅ Correct: C

📖 Explanation: A standard Resource-Allocation Graph includes nodes for both processes (usually circles) and resources (usually squares/rectangles), connected by request and assignment edges.

Q35. What is the benefit of using a Wait-For Graph over a Resource-Allocation Graph for detection in single-instance systems?

A.It shows more detail.

B.It simplifies cycle detection by removing resource nodes. ✅

C.It works for multiple instances.

D.It requires more memory.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: By removing resource nodes, the WFG reduces the graph size and complexity. Cycle detection algorithms can run faster on a graph with fewer nodes, making it more efficient for single-instance deadlock detection.

Q36. If a system uses detection, when is the detection algorithm typically executed?

A.Continuously in real-time.

B.Periodically or when a request cannot be granted immediately. ✅

C.Only at startup.

D.Never.

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: Running detection continuously is expensive. Systems often run it periodically (e.g., every hour) or trigger it when a process has been waiting for a resource for a certain threshold time, balancing overhead with timely detection.

Q37. What is the relationship between Prevention, Avoidance, and Detection?

A.They are used together.

B.They are alternative strategies for handling deadlocks. ✅

C.Detection is part of Prevention.

D.Avoidance is part of Detection.

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: These are three distinct approaches to dealing with deadlocks. A system typically chooses one primary strategy: either prevent them, avoid them, or allow them and detect/recover. They are alternatives, not usually combined components of a single mechanism.

🔗 Related Topics (MCQs)

📝 Deadlocks Introduction in Operating System MCQs 📝 Deadlocks System Model in Operating System MCQs 📝 Deadlock Characterization in Operating System MCQs 📝 Necessary Conditions for Deadlock Characterization MCQs 📝 Methods for Handling Deadlocks in Operating System MCQs

←Previous Topic:Resource Allocation Graph Algorithm in Deadlock Avoidance📝 Deadlock Detection in Operating SystemSingle Instance of Each Resource Type Deadlock Detection:Next Topic→