An OS designer is choosing between deadlock prevention and deadlock detection-and-recovery for a high-throughput transaction server. Which consideration most strongly favors detection-and-recovery?
ADeadlocks are impossible to prevent in systems with multiple resource types
BPrevention algorithms always consume more memory than detection algorithms
CIf deadlocks are rare, the overhead of constraining every resource request outweighs the cost of occasionally recovering from one
DDetection-and-recovery guarantees that deadlocks are resolved within a fixed time bound
Detection-and-recovery is a pragmatic strategy: rather than paying a constant overhead on every allocation (prevention/avoidance), you allow the system to run freely and pay the recovery cost only when deadlock actually occurs. If deadlocks are infrequent, prevention overhead accumulates unnecessarily across millions of safe allocations. The philosophical insight is that preventing a rare event by constraining every common operation is often a poor tradeoff. Option A is false (prevention is possible); option B is not generally true; option D is false — detection frequency is a design choice with no timing guarantee.
Question 2 Multiple Choice
A system has three resource types, each with multiple instances. Which technique correctly determines whether a deadlock currently exists?
AChecking for a cycle in the resource allocation graph
BSimulating resource allocation: mark processes that could complete with available resources, release their resources, and repeat; any unmarked process is deadlocked
CChecking whether the number of held resources exceeds the number of available resources
DChecking whether any process has been waiting longer than a defined threshold
For multi-instance resource types, a cycle in the resource allocation graph is necessary but not sufficient to confirm deadlock — a cycle can exist without an actual deadlock if some processes in the cycle can complete and release resources. The correct technique is the simulation algorithm: mark any process that can run to completion with currently available resources, simulate its resource release, and repeat. Processes that are never marked are definitively deadlocked. Options C and D are heuristics, not definitive tests.
Question 3 True / False
Terminating deadlocked processes one at a time — re-running the detection algorithm after each termination — is less destructive than terminating all deadlocked processes at once.
TTrue
FFalse
Answer: True
Killing all deadlocked processes at once guarantees the cycle is broken but discards the work of every process in the deadlock, including those that could have been spared. Terminating one victim at a time and re-running detection allows the OS to stop as soon as the deadlock is resolved. In many cases, terminating a single carefully chosen process (the smallest, lowest-priority, or least progressed) breaks the deadlock without destroying the rest. The tradeoff is that one-at-a-time requires multiple detection passes, adding overhead.
Question 4 True / False
A cycle in the resource allocation graph is sufficient to confirm that a deadlock exists, regardless of how many instances each resource type has.
TTrue
FFalse
Answer: False
This is a common overgeneralization. For single-instance resource types, a cycle is both necessary and sufficient to confirm deadlock. For multi-instance resource types, a cycle is necessary but NOT sufficient — a cycle can exist even when some process in the cycle can complete and release its resources, breaking the cycle without external intervention. The multi-instance detection algorithm (simulation-based, analogous to the Banker's algorithm) is needed to make a definitive determination.
Question 5 Short Answer
Why is the frequency at which the OS runs the deadlock detection algorithm a genuine engineering tradeoff, rather than simply a matter of running it as often as possible?
Think about your answer, then reveal below.
Model answer: Running detection after every resource request catches deadlocks immediately but adds overhead to every allocation, which can be significant in high-throughput systems. Running detection less frequently (periodically or on utilization drop) reduces overhead but allows deadlocked processes to sit idle longer, wasting CPU and holding resources. The optimal frequency depends on the relative cost of detection overhead versus the cost of delayed deadlock recovery in the specific workload.
This tradeoff is a specific instance of the broader monitoring/overhead tradeoff in systems design. In systems where deadlocks are extremely rare (e.g., database transaction managers with disciplined lock ordering), periodic detection is justified. In systems with complex, unpredictable resource dependencies, more frequent detection is warranted despite the cost. There is no universally correct answer — the optimal frequency must be determined empirically for each system's workload and deadlock characteristics.