Lesson 7.7: Deadlock Detection and Recovery

01 Introduction

Unit 7 has presented three strategies for handling deadlock. Prevention (Lesson 7.4) makes deadlock impossible by design, breaking one of the four Coffman conditions. Avoidance (Lessons 7.5 and 7.6) permits the conditions to hold but checks each request and defers it if granting it would lead to an unsafe state. Both of these strategies are proactive: they act before a deadlock can occur, and their correctness depends on information or discipline established in advance.

This lesson presents the third strategy: detection and recovery. It is reactive. The system allows deadlock to occur — it grants every request that can be satisfied, without any safety check and without any ordering discipline. Periodically or on demand, it runs a detection algorithm that examines the current state and determines whether a deadlock has occurred. If it has, the system runs a recovery procedure that breaks the deadlock by aborting one or more processes, or by preempting a resource from its holder and giving it to another process.

Detection and recovery has a different character from the other two strategies. It does not require a discipline (unlike prevention) and it does not require advance knowledge of resource needs (unlike avoidance). It requires only that the system be able to observe its current state and that it have a mechanism for undoing the work of a process it decides to abort. The first requirement is easy to satisfy; the second is the hard part, and it is what limits the strategy to systems with recovery support.

Detection and recovery is the strategy used by database systems, and it is the strategy that most closely matches the intuition of "if something goes wrong, clean it up". It is also the strategy that a user encounters directly when a hung program is killed from a terminal, or when the operating system terminates a process that has stopped responding. This lesson presents both halves: the detection algorithms (which build on the resource-allocation graph and the reduction algorithm of Lesson 7.3) and the recovery procedures (process termination and resource preemption), together with the practical considerations that determine which strategy a real system uses.

Prerequisites

This lesson builds on all of Unit 7. The four Coffman conditions (Lesson 7.2) and the resource-allocation graph with its reduction algorithm (Lesson 7.3) are used throughout. The distinction between prevention, avoidance, and detection (Lesson 7.4, section 4.1) is assumed. The lock primitives from Unit 6 are referenced in the discussion of recovery, and the discussion of transaction rollback draws on the database examples in earlier lessons. This is the last lesson of the unit; it also includes a synthesis of the unit as a whole.

02 Learning objectives

By the end of this lesson you will be able to

Describe the detection-and-recovery strategy and distinguish it from prevention and avoidance.
Apply the wait-for graph and the reduction algorithm to determine whether a system is deadlocked.
Explain when detection should be run and how the frequency of detection affects system cost.
Describe the recovery strategies of process termination and resource preemption, with their costs.
Explain the role of rollback and checkpointing in recovery and why they limit the strategy to specific systems.

This lesson contributes to U7.4 and U7.5, and to course learning outcomes CLO2, CLO3, and CLO8.

03 Required reading

Operating System Concepts — Chapter 8, Section 8.7, Deadlock Detection, and Section 8.8, Recovery from Deadlock. The standard treatment of both halves of the strategy, including the wait-for graph, the detection algorithm for multi-instance resources, and the recovery options.
Silberschatz et al. — Chapter 8, Sections 8.7–8.8. Read the worked example of the detection algorithm for multiple instances, which is the multi-instance version of the reduction algorithm from Lesson 7.3.
Holt, R. C. — Some Deadlock Properties of Computer Systems. ACM Computing Surveys, 1972. The original paper; section 4 discusses the detection problem and the reduction algorithm.
Tanenbaum & Bos — Modern Operating Systems, Chapter 6, Section 6.4, Deadlock Detection, and Section 6.5, Recovery from Deadlock. A complementary treatment with the classic discussions of which process to abort.
OSTEP — Chapter 32, Concurrency Bugs, through the section on Deadlock. The practical view of detection, and the reasons general-purpose systems do not implement it.
Love, R. — Linux Kernel Development, 3rd ed., Chapter 9, Kernel Synchronization Methods. The discussion of the kernel's own detection facilities and why the kernel relies on lock ordering for prevention.
Garcia-Molina, H., Ullman, J. D., & Widom, J. — Database Systems: The Complete Book, the sections on concurrency control and deadlock detection. The best available description of how a real system implements detection and recovery.

Reading strategy

Read the Silberschatz sections on detection and recovery together. The detection algorithm is a direct application of the reduction algorithm from Lesson 7.3, and it will feel familiar; the recovery sections are where most of the new material lies. Pay particular attention to the discussion of how often to run detection: the trade-off between the cost of running the algorithm and the cost of leaving a deadlock undetected is the central practical decision of the strategy. Then read the database concurrency-control material for the real-world view, which is where the strategy is actually deployed.

04 Core content

4.1 The detection-and-recovery strategy

The detection-and-recovery strategy consists of three phases:

Allow. The system grants every resource request that can be satisfied from the current free pool, without any safety check and without any ordering discipline. The four Coffman conditions may hold freely, and a deadlock may occur.
Detect. Periodically, or on demand, the system runs an algorithm that examines the current state and determines whether a deadlock has occurred. The algorithm may be run on a schedule (every t seconds), on a trigger (whenever CPU utilization drops below some threshold, or whenever a process has been blocked for longer than some limit), or on user request.
Recover. If a deadlock is detected, the system runs a recovery procedure that breaks it. The two general approaches are process termination (abort one or more of the processes in the cycle) and resource preemption (take a resource from one of the processes in the cycle and give it to another).

The strategy is fundamentally different from prevention and avoidance. Prevention is a design-time decision; avoidance is a runtime decision made before each request; detection is a runtime decision made after the fact. The strategy is therefore sometimes called optimistic: it assumes that deadlock is rare, and it pays the cost of detection and recovery only when a deadlock actually occurs.

The strategy's appeal is that it imposes no restrictions on resource usage. A process may request resources in any order, hold as many as it likes, and use the resources for as long as it needs. It may declare no maximum and follow no discipline. The only requirement is that the system be able to detect a deadlock and undo the work of a process it chooses to abort. This is a much weaker requirement than the ones imposed by prevention and avoidance, and it is why detection is used in real systems where the other strategies are not practical.

Figure 7.7 — The detection-and-recovery cycle. The system grants requests freely and a deadlock may occur. Detection is run periodically or on demand; if no deadlock is found, the system continues normally, and if a deadlock is found, recovery is run and the system returns to normal operation. Detection uses the tools of Lesson 7.3; recovery uses process termination or resource preemption.

4.2 Detection with single-instance resources

For a system in which every resource has a single instance, detection is done with the wait-for graph from Lesson 7.3. The wait-for graph is derived from the resource-allocation graph by eliminating the resource vertices: an edge P_i → P_j means that P_i is waiting for a resource held by P_j.

The detection algorithm is simply cycle detection. A cycle in the wait-for graph is a deadlock: because every resource has one instance, the cycle cannot be broken by a free instance of a resource on the cycle, and every process in the cycle is permanently blocked. Cycle detection in a directed graph is O(V + E) — linear in the size of the graph — using a depth-first search with colour marking.

The wait-for graph is not a theoretical construct: it is reconstructed from the process table of a real system. Each blocked process records the resource (or the lock) it is waiting for, and the resource records the process that holds it. From these two pieces of information, the wait-for graph is built directly. This is what a database system does when it runs its deadlock detector, and it is what a kernel debugger does when it reconstructs the state of a hung kernel from the thread backtraces.

The wait-for graph is the diagnostic tool of practice

When a programmer examines a deadlocked user-space program with gdb, the mental model they construct — "thread A is blocked on lock L, which is held by thread B; thread B is blocked on lock M, which is held by thread A" — is exactly the wait-for graph. The theory of Lesson 7.3 is not an abstraction that lives only in textbooks: it is the model that every practitioner uses when diagnosing a hang.

4.3 Detection with multiple instances

For a system in which some resources have multiple instances, the wait-for graph is not sufficient: a cycle does not necessarily imply a deadlock, because the cycle may be broken by a free instance of a resource type. The detection algorithm is the reduction algorithm from Lesson 7.3, applied to the current state.

The reduction algorithm is repeated here for convenience. Let Available[m] be the free resources and Allocation[n][m] the current allocations. The algorithm maintains a copy Work of the available resources and a Finish flag for each process.

Initialize Work = Available and Finish[i] = false for all i.
Find an index i such that Finish[i] == false and Request[i] ≤ Work — a process whose pending request can be satisfied from the current free pool.
If no such i exists, go to step 4. Otherwise, simulate the process's completion: Work = Work + Allocation[i] and Finish[i] = true. Return to step 2.
If Finish[i] == true for all i, there is no deadlock. Otherwise, the processes with Finish[i] == false are deadlocked.

The algorithm is identical to the safety algorithm of the Banker's algorithm (Lesson 7.6), with one difference: the test in step 2 uses the processes' current pending requests rather than their maximum declared needs. The Banker's algorithm asks "can every process finish if it requests its maximum?"; the detection algorithm asks "can every process finish if it requests only what it has already asked for?" The difference is the information required: the detection algorithm needs only the current state, which the kernel can observe, whereas the Banker's algorithm needs the maximum needs, which the kernel cannot observe.

This is the crucial practical point. The detection algorithm can be run in any system, because the state it needs — current allocations and pending requests — is always available. The Banker's algorithm can be run only in systems where the processes declare their maxima. The detection algorithm is therefore applicable in a far wider range of systems, which is why the strategy of detection and recovery is more widely deployed than avoidance.

4.4 When to run detection

The detection algorithm must be run at some point, and the choice of when to run it is a genuine trade-off between the cost of running it and the cost of leaving a deadlock undetected.

Run detection on every request: The deadlock is detected the instant it occurs, and recovery can begin immediately. The cost is that the detection algorithm — which is O(m n²) — is run on every request, even though the vast majority of requests do not lead to a deadlock. On a system with a high request rate, the overhead can dominate the useful work.
Run detection periodically: The detection algorithm runs every t time units. The cost is amortized over the period, and the system pays only once per period. The cost is that a deadlock may go undetected for up to t time units, during which the deadlocked processes are blocked and any resources they hold are unavailable. The choice of t balances the overhead against the delay.
Run detection on a trigger: The detection algorithm runs when some condition indicates that a deadlock might exist — for example, when CPU utilization drops below a threshold, or when a process has been blocked for longer than a bound. The intuition is that a deadlock leaves the CPU idle (the deadlocked processes are blocked) and leaves processes waiting for a long time. This is the approach used by many database systems: a background process runs periodically, but the frequency is adjusted based on the observed rate of lock waits.
Run detection on demand: The detection algorithm runs only when a user or an administrator requests it — for example, when a process appears to be hung. The cost is paid only when it is needed. This is the approach used in general-purpose systems for user-space deadlocks: the operating system does not detect them at all, and the user must intervene by killing the process.

The general principle is that the frequency of detection should be proportional to the frequency of deadlock and to the cost of leaving a deadlock undetected. A system where deadlocks are rare and the cost of a delay is small — a batch system, a system with many idle resources — should run detection rarely. A system where deadlocks are frequent or the cost of a delay is high — a busy database, a real-time system — should run detection frequently, or prevent the deadlock in the first place.

4.5 Recovery by process termination

Once a deadlock is detected, the system must recover. The simplest recovery procedure is to terminate one or more processes in the deadlock cycle. Terminating a process releases all the resources it holds, breaking the cycle and allowing the remaining processes to proceed.

There are two variants.

Abort all deadlocked processes: Terminate every process in the cycle. This definitely breaks the deadlock, because no process in the cycle remains to hold a resource that another needs. The cost is that all the work done by those processes is lost — potentially a large amount, if the processes have been running for a long time. This is the simplest and most decisive approach, and it is the one a user usually takes when a program hangs: kill the whole program and start over.
Abort processes one at a time: Terminate one process at a time, re-running the detection algorithm after each termination, until the cycle is broken. This minimizes the amount of work lost, at the cost of running the detection algorithm repeatedly. The order of termination is chosen by a policy — for example, terminate the process that has done the least work, or the one holding the fewest resources, or the one with the lowest priority.

4.6 Choosing the victim

When the system terminates processes one at a time, the choice of which process to terminate is a policy decision. The classical criteria are:

Priority. Abort the process with the lowest priority. A process that is less important should be sacrificed before one that is more important. This criterion is directly applicable when the system has priorities; in a system without them, it does not apply.
Work done and work remaining. Abort the process that has done the least work, or the one that has the most work remaining. The intuition is that a process that has not yet accomplished much can be aborted with less loss, and a process that still has a lot to do is a better candidate for abortion than one that is almost finished.
Resources held. Abort the process that holds the fewest resources (or the fewest of the resources that are needed to break the cycle). Aborting a process that holds few resources releases fewer, but it is also likely to be cheaper to abort. Aborting a process that holds many resources releases more, which is more likely to break the cycle in one step.
Resources needed. Abort the process that needs the most resources, or the one that will need the most time to finish. The intuition is that a process with a large remaining need is likely to contend for resources again, and aborting it prevents the cycle from re-forming.
Number of processes. If the goal is to minimize the number of processes aborted, the system should abort the one whose termination breaks the cycle with the least additional aborts. This requires running the detection algorithm after each candidate abortion to see whether the cycle is broken.
Cost of rollback. In a system with transaction support, abort the process whose rollback is cheapest. A process that has made few modifications to shared state can be rolled back quickly; a process that has made many cannot.

The choice of criteria is a design decision, and real systems often combine several. The important consideration is that the criteria should be applied consistently and should not create the possibility of starvation: if the same process is always chosen as the victim, it may be aborted repeatedly and never finish. This is the same starvation problem we saw in scheduling (Lesson 5.4) and in reader–writer locks (Lesson 6.4), and the same solution applies: the system must record the number of times a process has been aborted and include that count in the victim-selection criteria, so that a repeatedly-aborted process becomes progressively less attractive as a victim.

The rollback problem

Terminating a process is easy; undoing its effects is not. A process that has modified shared state — a database table, a file system, a data structure in memory — leaves the state inconsistent when it is killed. The system must be able to restore the state to a consistent point, either by rolling back the process's modifications or by restarting the process from a checkpoint. Without this ability, terminating a process may leave the system in a corrupted state, which is worse than the deadlock it was meant to resolve. The need for rollback is what limits the detection-and-recovery strategy to systems with recovery support.

4.7 Recovery by resource preemption

The alternative to termination is resource preemption: take a resource away from one of the processes in the cycle and give it to another, breaking the cycle without terminating any process. Preemption has three sub-problems.

Selecting a victim: Which resource should be preempted, and from which process? The criteria are similar to those for process termination: minimize the cost, maximize the resources freed, avoid starvation. The victim must be a resource whose preemption breaks the cycle; a resource held by a process outside the cycle does not help.
Rolling back: A process that has a resource taken away is, in effect, returned to an earlier point in its execution — the point at which it had not yet acquired the resource. Its work since that point must be rolled back. In a database, this is done by aborting the transaction and restoring the database from the undo log. In a general-purpose system, there is no built-in mechanism for rolling back a process's work; the process can be restarted from a checkpoint if one was taken, or its work can simply be lost. The need for rollback is the central difficulty of preemption, just as it is for termination.
Avoiding starvation: A process that is repeatedly chosen as the victim will never finish. The system must ensure that a process is chosen as a victim only a bounded number of times, either by including the number of past preemptions in the victim-selection criteria, or by limiting the number of times a given process can be preempted. The same consideration applies to termination.

Preemption is generally harder to implement than termination, and it is used less often. The classical examples are database row locks (a transaction can be aborted and its locks released) and CPU scheduling (the CPU is preempted from a process, which is then suspended and later resumed). For general-purpose locks, preemption is generally impossible without the process being aborted or suspended, which brings us back to termination.

4.8 Rollback and checkpointing

Both termination and preemption require the ability to roll back a process's work. The mechanism for rollback depends on the system.

Transaction rollback. A database transaction maintains a log of every modification it has made to the database. If the transaction is aborted, the log is used to undo the modifications in reverse order, restoring the database to its state before the transaction began. This is the standard mechanism for deadlock recovery in databases, and it is why databases can use detection and recovery safely.
Checkpointing. A process periodically saves its complete state — registers, memory contents, file positions — to a checkpoint. If the process is later aborted, it can be restarted from the last checkpoint, losing only the work done since then. The interval between checkpoints determines how much work is lost on a rollback; a short interval means less lost work but more overhead. Checkpointing is used in long-running scientific computations and in some fault-tolerant systems.
Restart from the beginning. The process's work is simply discarded, and the process is restarted from its initial state. This is the simplest approach, and it is what happens when a user kills a hung program and runs it again. It requires no built-in mechanism, but it loses all the work the process had done.
Suspension and resume. The process is suspended rather than terminated, and its state is preserved. When the resource becomes available again, the process resumes. This requires the ability to suspend and resume a process — which the operating system can do — and the ability to remove the resource from the process without the process noticing, which the operating system generally cannot do for a user-space lock. Suspension is used for CPU preemption (the process is suspended and later resumed), but not for resource preemption in general.

The availability of a rollback mechanism is what determines whether detection and recovery is practical. A system with transaction support — a database, a transactional file system, a language runtime with exceptions and cleanup handlers — can roll back a process and recover cleanly. A system without it — a general-purpose operating system running arbitrary user code — can only terminate the process and hope the user will restart it.

4.9 Detection in practice: databases and kernels

The detection-and-recovery strategy is used in two kinds of real systems.

Database systems. A database with row-level locking must handle the possibility that two transactions lock rows in opposite orders and deadlock. The database maintains a wait-for graph of the transactions and the rows they are waiting for, and it runs detection periodically. When a cycle is found, the transaction with the lowest priority — or the one with the least work done, or the one with the fewest locks — is aborted, and its modifications are rolled back from the undo log. The aborted transaction is typically restarted by the application, which may retry the operation. This is the classic use of detection and recovery, and it works because the database has the two things the strategy needs: a way to observe the state (the wait-for graph) and a way to undo the work (the undo log).
Operating-system kernels. The Linux kernel does not run a deadlock detector on its own locks, for the reasons discussed in Lesson 7.4: the kernel relies on lock ordering for prevention. However, the kernel does provide a diagnostic facility, lockdep, that records lock dependencies and warns about potential lock-order inversions. When a kernel hang is suspected, tools such as sysrq can dump the state of all blocked threads, from which a human or a script can reconstruct the wait-for graph. The kernel's approach is therefore prevention for the normal case and manual detection for the exceptional case.

The contrast is instructive. The database's strategy works because the database controls the operations it performs — every modification goes through the transaction log, so the log can always be used to undo. The kernel's strategy is prevention because the kernel cannot undo the operations it performs — a system call that has partially completed may have left the file system or the network stack in a state that cannot be rolled back. The availability of a rollback mechanism determines the strategy.

4.10 Comparing the three strategies

Unit 7 has presented three strategies for handling deadlock. The following table summarizes their character, requirements, and applicability.

Prevention, avoidance, and detection compared
Aspect	Prevention	Avoidance	Detection and recovery
When it acts	Design time	Before each request	After a deadlock occurs
Restriction on the program	Discipline on resource acquisition	None, but requests may be deferred	None
Information required	A discipline (e.g., a lock order)	Each process's maximum needs	Current state only
Deadlock possible?	No	No	Yes
Work lost on recovery	None	None (requests are deferred, not aborted)	Yes — the aborted process's work
Runtime overhead	None after start-up	Safety check on every request	Detection periodically or on trigger
Requires rollback support	No	No	Yes, for clean recovery
Where used	Kernels, well-written concurrent programs	Real-time systems, batch systems with declared jobs	Databases, transactional file systems

The pattern that emerges is that each strategy is appropriate in a different context, and the choice depends on what the system can provide. A kernel can enforce a lock order, so it uses prevention. A real-time system knows its tasks' resource needs, so it uses avoidance. A database can roll back transactions, so it uses detection and recovery. A general-purpose system can do none of these things for arbitrary user code, so it relies on the ostrich algorithm: it allows deadlock, does not detect it, and relies on the user to kill the offending process.

4.11 The ostrich algorithm revisited

Lesson 7.1 introduced the ostrich algorithm — ignore the problem and hope it does not occur — as the fourth strategy for handling deadlock. With the full unit behind us, we can now give it a more careful treatment.

The ostrich algorithm is not a failure of engineering. It is a deliberate choice that reflects the actual trade-offs in a general-purpose system. Consider what a general-purpose operating system would have to do to implement the other three strategies for user-space code:

Prevention would require the operating system to enforce a lock order on user-space locks. This is impossible, because the locks are managed by user-space libraries, not by the kernel. The kernel does not know which locks a thread holds or is waiting for, because the locks are ordinary memory locations that the kernel does not track.
Avoidance would require every user process to declare its maximum resource needs. This is impossible for arbitrary programs, as we have seen.
Detection and recovery would require the operating system to detect a cycle of waits among user-space locks and to abort a process to break it. Detection is possible in principle — the kernel could track the locks, or the library could report them — but recovery is not. The operating system cannot roll back the work of an arbitrary user process; it can only terminate it, which loses all the process's work and may leave shared state (files, databases) in an inconsistent state.

Given these obstacles, the ostrich algorithm is the rational choice for a general-purpose system. The operating system does not detect user-space deadlocks, but it does provide the tools for the user to do so: the /proc file system, the debugger, strace, and the ability to kill a process. The user who suspects a deadlock can inspect the process with these tools, reconstruct the wait-for graph manually, and kill the offending process. The responsibility is transferred from the operating system to the user, because the user is the only one with the information needed to decide which process to sacrifice.

The ostrich algorithm is therefore not "do nothing". It is "do what you can, and leave the rest to the user". In practice, this turns out to be a reasonable compromise. User-space deadlocks are rare, and when they occur, the cost of killing and restarting a process is usually acceptable.

4.12 Common misconceptions

"Detection is the same as prevention."

Detection allows deadlock and finds it after the fact; prevention makes it impossible by design. They are at opposite ends of the timing spectrum: prevention acts before the request, detection after the deadlock.

"Detection prevents deadlock."

Detection does not prevent deadlock; it finds it. The system must still recover, and recovery loses the work of the aborted process. Prevention and avoidance are the strategies that guarantee no deadlock; detection is the strategy that guarantees deadlock will be found and cleaned up.

"Recovery always means terminating a process."

Termination is one option; the other is resource preemption, which takes a resource from a process and gives it to another. Preemption is used in databases (via transaction abort) and in CPU scheduling, though it is harder to implement than termination.

"The victim should always be the oldest process."

There is no single correct criterion. Priority, work done, resources held, resources needed, and rollback cost are all valid criteria, and real systems combine several. The one constraint is that the choice must not starve any process.

"Detection should be run as often as possible."

Detection has a cost. Running it on every request makes the system slow; running it rarely leaves deadlocks undetected for longer. The optimal frequency balances the two costs.

"Aborting a process is always safe."

No. A process that has modified shared state leaves the state inconsistent when it is killed. Without a rollback mechanism — a transaction log, a checkpoint, a restart from a known-good state — aborting a process may corrupt the system.

"Linux detects deadlock in user-space locks."

It does not. The kernel does not track user-space locks and cannot detect a cycle among them. The kernel provides tools — /proc, debuggers, strace — that the user can use to reconstruct the state, but detection is the user's responsibility.

"Detection requires knowing maximum resource needs."

No — that is the Banker's algorithm's requirement. Detection requires only the current state: which resources each process holds and which it is waiting for. This is the crucial practical advantage of detection over avoidance.

05 Worked example

The following example applies the detection algorithm to two systems — one with single-instance resources and one with multi-instance resources — and then walks through the recovery procedures for each.

Detection with single-instance resources

Four processes P₀, P₁, P₂, P₃ share four resources R₀, R₁, R₂, R₃, each with one instance. The current state:

Process	Holds	Waiting for
P₀	R₀	R₁
P₁	R₁	R₂
P₂	R₂	—
P₃	R₃	R₁

Build the wait-for graph. Each request is translated into an edge from the waiting process to the holder of the requested resource:

P₀ waits for R₁, held by P₁. Edge P₀ → P₁.
P₁ waits for R₂, held by P₂. Edge P₁ → P₂.
P₂ is not waiting. No outgoing edge.
P₃ waits for R₁, held by P₁. Edge P₃ → P₁.

The wait-for graph is: P₀ → P₁, P₁ → P₂, P₃ → P₁. Run cycle detection. Starting from P₀: P₀ → P₁ → P₂. P₂ has no outgoing edges, so the DFS terminates without finding a cycle. Starting from P₃: P₃ → P₁ → P₂. Again, no cycle.

Conclusion: no cycle, no deadlock. P₂ is not waiting for anything, so it can finish and release R₂. Then P₁ can finish and release R₁. Then P₀ and P₃ can finish. The state is safe.

Now suppose P₂ requests R₃, which is held by P₃. The new state:

Process	Holds	Waiting for
P₀	R₀	R₁
P₁	R₁	R₂
P₂	R₂	R₃
P₃	R₃	R₁

The wait-for graph now has edges P₀ → P₁, P₁ → P₂, P₂ → P₃, P₃ → P₁. Run cycle detection: P₁ → P₂ → P₃ → P₁. A cycle is found.

Conclusion: deadlock. The deadlocked processes are P₁, P₂, and P₃. (P₀ is also blocked — it is waiting for R₁, held by P₁ — but it is not part of the cycle; it is an innocent bystander blocked by the deadlock.)

Recovery from the single-instance deadlock

The system must break the cycle P₁ → P₂ → P₃ → P₁. Consider the two recovery options.

Option A: abort all deadlocked processes. Terminate P₁, P₂, and P₃. All three release their resources. R₁, R₂, and R₃ become free. P₀ can then acquire R₁ and finish. The cost is that three processes are terminated, and their work is lost.

Option B: abort one process at a time. Choose the process with the least work done. Suppose that is P₂. Terminate P₂. It releases R₂. Now P₁ can acquire R₂, run to completion, and release R₁. Then P₃ can acquire R₁. The cycle is broken with a single termination. The cost is the work lost by P₂, but the other two processes continue.

Option C: resource preemption. Take R₂ from P₂ and give it to P₁. This requires rolling back P₂'s work to the point at which it had not acquired R₂. If P₂ has a rollback mechanism (a transaction log, a checkpoint), it can be restored. If it does not, it must be terminated — which reduces Option C to Option B.

In a system with transaction support, Option C is attractive: P₂ can be aborted and restarted without losing the other processes' work. In a system without rollback, Options A and B are the practical choices. Option B is generally preferred because it minimizes the number of terminated processes, at the cost of running the detection algorithm more often.

Detection with multi-instance resources

Now consider a system with multiple instances. Three processes P₀, P₁, P₂ share two resource types A and B. A has three instances; B has two instances. The current state:

Process	Alloc A	Alloc B	Request A	Request B
P₀	1	0	1	0
P₁	0	1	1	0
P₂	1	1	0	1
Available		1	0	—

The total instances: A = 1 + 0 + 1 + Available A = 3; B = 0 + 1 + 1 + Available B = 2. Consistent.

Run the reduction algorithm. Work = (1, 0) and no process is finished.

P₀: Request (1, 0) ≤ Work (1, 0)? Yes. Finish P₀. Work = (1, 0) + (1, 0) = (2, 0).
P₁: Request (1, 0) ≤ Work (2, 0)? Yes. Finish P₁. Work = (2, 0) + (0, 1) = (2, 1).
P₂: Request (0, 1) ≤ Work (2, 1)? Yes. Finish P₂. Work = (2, 1) + (1, 1) = (3, 2).

Conclusion: all processes finish; no deadlock. The state is safe.

Now suppose P₂ requests an additional instance of B, making its request (0, 2). The new state:

Process	Alloc A	Alloc B	Request A	Request B
P₀	1	0	1	0
P₁	0	1	1	0
P₂	1	1	0	2
Available		1	0	—

Run the reduction algorithm. Work = (1, 0).

P₀: Request (1, 0) ≤ Work (1, 0)? Yes. Finish P₀. Work = (2, 0).
P₁: Request (1, 0) ≤ Work (2, 0)? Yes. Finish P₁. Work = (2, 1).
P₂: Request (0, 2) ≤ Work (2, 1)? No — B needs 2, only 1 available.
No more processes can finish.

P₂ remains unfinished. Conclusion: the state is deadlocked — specifically, P₂ is deadlocked. It is waiting for B, and no process can provide it: P₀ and P₁ finish, but their releases bring Work to (2, 1), and B remains 1, which is insufficient for P₂'s request of 2.

Wait — is this right? P₀ and P₁ finish and release their resources, and Work becomes (2, 1). But P₂ holds B = 1 and is requesting 2 more. Total B is 2. P₂ holds 1, so at most 1 more B can be available. P₂'s request of 2 is therefore impossible to satisfy — the total number of B instances in the system is only 2, and P₂ wants to hold 3. This state is impossible in a well-formed system: the request exceeds the total number of instances, and the system should not have allowed it. This illustrates that the detection algorithm's results depend on the state being well-formed.

Let us correct the example. Suppose P₂ requests an additional instance of B, making its request (0, 1) — but B is already fully allocated (P₁ holds 1, P₂ holds 1, Available B = 0), so the request cannot be satisfied and P₂ waits. This is the same as the previous state; the algorithm correctly reports no deadlock, because P₀ and P₁ finish first and their release of B (from P₁) satisfies P₂.

To construct a genuine multi-instance deadlock, we need a cycle that cannot be broken by the resources that become available. Let us modify the example: A has three instances, B has three instances, and the state is:

Process	Alloc A	Alloc B	Request A	Request B
P₀	1	1	1	0
P₁	1	0	0	1
P₂	0	2	1	0
Available		1	0	—

Totals: A = 1 + 1 + 0 + 1 = 3; B = 1 + 0 + 2 + 0 = 3. Consistent. Run the reduction algorithm with Work = (1, 0):

P₀: Request (1, 0) ≤ Work (1, 0)? Yes. Finish P₀. Work = (1, 0) + (1, 1) = (2, 1).
P₁: Request (0, 1) ≤ Work (2, 1)? Yes. Finish P₁. Work = (2, 1) + (1, 0) = (3, 1).
P₂: Request (1, 0) ≤ Work (3, 1)? Yes. Finish P₂.

All processes finish; no deadlock. Constructing a genuine multi-instance deadlock requires care: the cycle must not be breakable by the resources that become available. The classical example uses all four processes and all three resource types, as in the Silberschatz text. The essential point is that the reduction algorithm finds deadlock when no sequence of completions exists, and the multi-instance case is exactly the case where a cycle may exist without a deadlock.

Recovery from a multi-instance deadlock

Once a deadlock is detected, recovery follows the same options as for the single-instance case: terminate one or more processes in the cycle, or preempt a resource. The detection algorithm's output — the set of processes with Finish[i] == false — is the set of deadlocked processes. Recovery operates on that set.

In a database, the recovery decision is made by the transaction manager: the transaction with the lowest priority is aborted and its changes are undone. The aborted transaction's locks are released, allowing the other transactions in the cycle to proceed. The application that submitted the aborted transaction may retry it, and the retry may succeed — the deadlock was a coincidence of timing, and the retry runs with a different interleaving.

Comparing detection to the other strategies

Consider how the same deadlock would be handled by each of the three strategies:

Strategy	What happens
Prevention (lock ordering)	The deadlock never occurs: the processes acquire their resources in a consistent order, and the cycle cannot form.
Avoidance (Banker's algorithm)	The request that would lead to the cycle is deferred. The requesting process waits, but no process is aborted. The system remains in a safe state.
Detection and recovery	The deadlock occurs and is detected. One process is aborted, its work is lost, and the others proceed. The aborted process may be restarted.

The three strategies differ in when they intervene and what they cost. Prevention costs a discipline at design time. Avoidance costs an information requirement and a runtime check. Detection costs the work of the aborted process. Which cost is acceptable depends on the system and on the frequency of deadlock.

06 Interactive activity

Activity · implement detection and simulate recovery

The goal of this activity is to implement the detection algorithms, simulate recovery procedures, and observe how the choice of victim affects the system. Work through the steps in your course VM.

Implement wait-for graph construction. Write a function that takes a process table — for each process, the resources it holds and the resources it is waiting for — and constructs the wait-for graph. Test it with the worked example from section 5.

# Python sketch
def build_wait_for(processes):
    # processes: dict mapping pid -> {'holds': [...], 'waits': [...]}
    holder = {}
    for pid, info in processes.items():
        for r in info['holds']:
            holder[r] = pid
    graph = {}
    for pid, info in processes.items():
        graph[pid] = []
        for r in info['waits']:
            if r in holder and holder[r] != pid:
                graph[pid].append(holder[r])
    return graph

Implement cycle detection. Write a function that detects a cycle in the wait-for graph using depth-first search with colour marking. Return the cycle if one is found, and None otherwise.

WHITE, GREY, BLACK = 0, 1, 2

def find_cycle(graph):
    color = {v: WHITE for v in graph}
    parent = {v: None for v in graph}

    def dfs(v):
        color[v] = GREY
        for u in graph.get(v, []):
            if color.get(u, WHITE) == GREY:
                # back edge — reconstruct the cycle
                cycle = [v]
                while cycle[-1] != u:
                    cycle.append(parent[cycle[-1]])
                cycle.reverse()
                return cycle + [u]
            if color.get(u, WHITE) == WHITE:
                parent[u] = v
                result = dfs(u)
                if result:
                    return result
        color[v] = BLACK
        return None

    for v in graph:
        if color[v] == WHITE:
            result = dfs(v)
            if result:
                return result
    return None

Implement the reduction algorithm. Write a function that takes the current state (Available, Allocation, Request) and returns the set of processes that are deadlocked, using the reduction algorithm from section 4.3. Test it with the single-instance and multi-instance examples from section 5.
Simulate recovery by termination. Extend the detection program to simulate recovery. When a deadlock is detected, the program chooses a victim according to a policy (for example, the process with the fewest resources held) and terminates it. The resources are released, and the detection algorithm is run again to verify that the cycle is broken. If it is not, another process is terminated. Print a trace of the decisions.
```
def recover_by_termination(state, deadlocked):
    victims = []
    while deadlocked:
        # choose a victim
        victim = min(deadlocked, key=lambda p: len(state['held'][p]))
        victims.append(victim)
        # release its resources
        for r in state['held'][victim]:
            state['available'][r] += 1
            state['held'][victim].remove(r)
        # re-run detection
        deadlocked = detect(state)
    return victims
```
Compare victim-selection policies. Modify the recovery simulation to try different victim-selection policies: fewest resources held, most resources held, shortest-running process, longest-running process. For each policy, record how many processes are terminated and how much "work" is lost (measure work as the running time of the terminated processes). Which policy minimizes the number of terminations? Which minimizes the work lost? Are they the same?
Simulate detection frequency. Modify the simulation so that detection runs only every t time units. Measure how long a deadlock goes undetected for different values of t, and measure the total number of detection runs. Plot or tabulate the trade-off: a smaller t detects deadlocks sooner but runs the algorithm more often.
```
for t in [1, 5, 10, 50]:
    runs, delay = simulate(t)
    print(f"t={t}: detection runs={runs}, max undetected delay={delay}")
```
Reconstruct a wait-for graph from gdb. Take the deadlocking program from Lesson 7.1 (two threads, two locks, opposite order). While it is hung, use gdb to inspect the threads. From the backtraces and the lock addresses, reconstruct the wait-for graph by hand and identify the cycle. This is the manual version of the detection algorithm, and it is what a developer does when debugging a hang.
```
gdb -p $(pgrep deadlock)
(gdb) thread apply all bt
(gdb) info threads
(gdb) quit
```
Use the kernel's hung-task detector. On a Linux system, the kernel periodically checks for tasks that have been blocked for more than 120 seconds. If such a task is found, the kernel prints a warning to the system log. Start the deadlocking program from Lesson 7.1, leave it running for a few minutes, and check dmesg for the "hung task" message.
```
./deadlock &
sleep 130
dmesg | tail -30
```
The kernel is not detecting a deadlock per se — it is detecting a long-running block, which may or may not be a deadlock — but the mechanism is the same: the kernel observes that a process is blocked, and it reports the situation to the administrator.

Reflect: the detection algorithms are simple and general — they require only the current state, which every system can observe. The recovery procedures are where the difficulty lies, because they require the system to undo work that a process has already done. A database can do this; a general-purpose operating system cannot. Is this a fundamental limitation, or an engineering choice? Could a general-purpose system be designed with the transactional support that would make detection and recovery practical for all programs? What would be the cost of such support, and would the benefit be worth it?

07 Knowledge check

Check your understanding

Question 1

Describe the detection-and-recovery strategy. How does it differ from prevention and avoidance in when it acts and what it requires? Why is it sometimes called the optimistic strategy?

Show answer

The detection-and-recovery strategy has three phases: (1) allow — the system grants every resource request that can be satisfied, without any safety check and without any ordering discipline, so a deadlock may occur; (2) detect — periodically, on a trigger, or on demand, the system runs an algorithm that examines the current state and determines whether a deadlock has occurred; (3) recover — if a deadlock is found, the system breaks it by terminating a process or by preempting a resource. The strategy differs from the other two in its timing. Prevention acts at design time: the system is structured so that deadlock is impossible. Avoidance acts before each request: the system checks whether granting the request would leave the state safe, and defers if it would not. Detection acts after the deadlock has occurred: it allows the deadlock to happen and cleans it up. The three also differ in their requirements. Prevention requires a discipline (for example, a global lock order). Avoidance requires each process's maximum resource needs, declared in advance. Detection requires only the current state — which resources each process holds and which it is waiting for — which every system can observe. The strategy is called optimistic because it assumes that deadlock is rare and pays the cost of detection and recovery only when a deadlock actually occurs. It does not restrict the program's behaviour (as prevention does) and does not require advance information (as avoidance does). The cost is paid on the rare occasion when a deadlock happens, and it is paid in the form of lost work from the aborted process.

Question 2

Describe the detection algorithm for single-instance resources and the detection algorithm for multi-instance resources. What is the relationship between the multi-instance algorithm and the reduction algorithm from Lesson 7.3? What is the relationship to the Banker's algorithm?

Show answer

For single-instance resources, the detection algorithm is cycle detection in the wait-for graph. The wait-for graph has one vertex per process, and an edge P_i → P_j means that P_i is waiting for a resource held by P_j. Because every resource has one instance, a cycle implies a deadlock: the cycle cannot be broken by a free instance. Cycle detection is O(V + E) using depth-first search with colour marking. For multi-instance resources, the detection algorithm is the reduction algorithm from Lesson 7.3. The algorithm maintains a copy Work of the available resources and a Finish flag for each process. It repeatedly finds an unfinished process whose pending request can be satisfied from Work, marks it finished, and adds its resources to Work. If all processes can be finished, there is no deadlock; the processes that remain unfinished are deadlocked. The multi-instance algorithm is exactly the reduction algorithm of Lesson 7.3 — it is the same algorithm, applied to the current state of the system. Its relationship to the Banker's algorithm is that both use the same simulation structure, but with a crucial difference in the test. The Banker's algorithm uses the processes' maximum declared needs: it asks "can every process finish if it requests its maximum?" The detection algorithm uses the processes' current pending requests: it asks "can every process finish if it requests only what it has already asked for?" This difference is the source of the detection algorithm's practical advantage: it requires only the current state, which the kernel can observe, rather than the maximum needs, which the kernel cannot observe. The detection algorithm can therefore be run in any system, whereas the Banker's algorithm can be run only in systems where the maxima are declared.

Question 3

How often should detection be run? Describe the trade-off and the different approaches a system might take.

Show answer

The frequency of detection is a trade-off between the cost of running the algorithm and the cost of leaving a deadlock undetected. Running detection more often costs more CPU time but detects deadlocks sooner; running it less often costs less CPU time but leaves deadlocks undetected for longer, during which the deadlocked processes are blocked and any resources they hold are unavailable. Four approaches are possible. On every request: the deadlock is detected immediately, but the algorithm — which is O(m n²) for multi-instance resources — runs on every request, and the overhead can dominate the useful work on a system with a high request rate. Periodically: the algorithm runs every t time units. The cost is amortized, and the system pays only once per period, but a deadlock may go undetected for up to t time units. The choice of t balances the two costs. On a trigger: the algorithm runs when some condition indicates that a deadlock might exist — for example, when CPU utilization drops below a threshold, or when a process has been blocked for longer than a bound. The intuition is that a deadlock leaves the CPU idle and leaves processes waiting. This is the approach used by many database systems. On demand: the algorithm runs only when a user or administrator requests it, for example when a process appears to be hung. The cost is paid only when needed, which is appropriate when deadlocks are rare and the system does not need to recover automatically. The general principle is that the frequency should be proportional to the frequency of deadlock and to the cost of leaving a deadlock undetected. A system where deadlocks are rare and the cost of a delay is small should run detection rarely; a system where deadlocks are frequent or the cost of a delay is high should run detection frequently, or prevent the deadlock in the first place.

Question 4

Describe the two recovery strategies: process termination and resource preemption. What criteria might be used to choose a victim in each case? What is the rollback problem, and why does it limit the applicability of the recovery strategy?

Show answer

The two recovery strategies are: process termination and resource preemption. In process termination, the system aborts one or more of the processes in the deadlock cycle. Two variants exist: abort all deadlocked processes (decisive but loses all their work) and abort one at a time, re-running detection after each, until the cycle is broken (minimizes lost work but requires repeated detection). In resource preemption, the system takes a resource from one of the processes in the cycle and gives it to another, breaking the cycle without terminating any process. The criteria for choosing a victim are similar in both cases: priority (abort the lowest-priority process), work done and remaining (abort the process that has done the least, or that has the most remaining, to minimize loss), resources held (abort the process holding the fewest, or the ones whose release breaks the cycle), and rollback cost (abort the process whose work can be undone most cheaply). In all cases, the choice must avoid starvation: a process that is repeatedly chosen as a victim will never finish, so the system must record the number of times each process has been aborted and include it in the selection criteria. The rollback problem is that terminating a process or preempting a resource leaves the system's shared state inconsistent. A process that has modified a database table, a file, or a data structure leaves the state in a partially updated condition; simply killing the process does not restore the state. The system must be able to roll back the process's work — undo the modifications, restore the file, return the data structure to a consistent state. The mechanisms for this are transaction logs (in databases), checkpointing (in long-running computations), and restart from a known-good state. A system without such a mechanism cannot recover cleanly: aborting a process may leave the system corrupted, which is worse than the deadlock. This is what limits the detection-and-recovery strategy to systems with recovery support — databases and transactional file systems, primarily — and why general-purpose operating systems rely on the ostrich algorithm instead.

Question 5

Unit 7 has presented three strategies for handling deadlock. Compare prevention, avoidance, and detection across the following dimensions: when they act, what they require, whether deadlock is possible, what they cost, and where they are used. Which strategy is appropriate for which kind of system?

Show answer

The three strategies can be compared across five dimensions. When they act: prevention acts at design time, avoidance acts before each resource request, and detection acts after a deadlock occurs. What they require: prevention requires a discipline on resource acquisition (for example, a global lock order); avoidance requires each process's maximum resource needs, declared in advance; detection requires only the current state of the system, which every system can observe. Whether deadlock is possible: with prevention, no; with avoidance, no (requests are deferred if they would lead to an unsafe state); with detection, yes — the strategy assumes deadlock will occur and provides a mechanism to find and fix it. What they cost: prevention costs a discipline that must be enforced everywhere, with no runtime overhead. Avoidance costs the information requirement (the declared maxima) and the runtime overhead of the safety check on every request. Detection costs the runtime overhead of running the detection algorithm and, when a deadlock occurs, the lost work of the aborted process. Where they are used: prevention is used in operating-system kernels (lock ordering) and in well-written concurrent programs; avoidance is used in real-time systems with a fixed task set and in batch systems where jobs declare their requirements; detection and recovery is used in databases and transactional file systems. The choice of strategy depends on what the system can provide. A kernel can enforce a lock order, so it uses prevention. A real-time system knows its tasks' resource needs, so it uses avoidance. A database can roll back transactions, so it uses detection and recovery. A general-purpose system can do none of these for arbitrary user code, so it relies on the ostrich algorithm: it does not detect user-space deadlocks, and it relies on the user to intervene. The general principle is that the strategy should match the system's capabilities: use the strategy that requires the information or the mechanism the system actually has.

08 Unit discussion

Discussion prompt

This lesson closes Unit 7, and it is worth reflecting on the unit as a whole. We have studied four strategies for handling deadlock — prevention, avoidance, detection and recovery, and the ostrich algorithm — and we have seen that none of them is universally applicable. Each requires something the system may not have: prevention requires a discipline, avoidance requires advance information, detection requires rollback support. The ostrich algorithm requires nothing and provides nothing, which is why it is used by general-purpose systems for user-space code.

There is a parallel here with the synchronization primitives of Unit 6. Locks, semaphores, condition variables, and monitors each solve a specific problem, and none is universally applicable. The choice between them depends on the problem and on the guarantees the programmer needs. Deadlock strategies follow the same pattern: the choice depends on the system and on what it can provide.

There is a deeper theme running through both units: the trade-off between discipline and flexibility. A discipline is a constraint on the program — a lock order, a declared maximum, a transaction — and it imposes a cost. But the discipline also enables a guarantee — no deadlock, no starvation, atomic transactions — that would otherwise be impossible. The systems that use disciplines are the systems that need the guarantees. The systems that use the ostrich algorithm are the systems that can tolerate the occasional failure in exchange for greater flexibility.

Which trade-off do you think is the right one for the systems you use? For a general-purpose desktop, a mobile device, a server, an embedded controller? Has your view changed over the course of this unit? Post your response to the Unit 7 discussion forum and reply to at least two classmates. This closes Unit 7 and the Module 2 material on processes and concurrency. Supports CLO2, CLO3, CLO4, and CLO8.

09 Practice exercise

This ungraded exercise consolidates the whole of Unit 7 and prepares you for the midterm examination. Aim to spend 90–120 minutes on it.

Build a wait-for graph. For the following system, construct the wait-for graph and determine whether there is a deadlock. Five processes P₀ through P₄; five single-instance resources R₀ through R₄.

Process	Holds	Waits for
P₀	R₀	R₁
P₁	R₁	R₂
P₂	R₂	R₃
P₃	R₃	R₄
P₄	R₄	R₀

Trace the cycle detection algorithm by hand. Which processes are deadlocked? Which processes are blocked but not deadlocked?

Break the deadlock. For the system in question 1, identify the smallest number of processes you would need to abort to break the deadlock. Justify your choice by considering the victim-selection criteria from section 4.6. Then identify the smallest amount of work (in terms of processes aborted) under a policy that prefers to abort the process that has done the least work.

Run the reduction algorithm. For the following multi-instance system, run the reduction algorithm and determine whether there is a deadlock. Three resource types A, B, C with total instances A = 7, B = 5, C = 6.

Process	Alloc A	Alloc B	Alloc C	Request A	Request B	Request C
P₀	1	1	0	2	0	0
P₁	2	0	1	0	1	2
P₂	0	2	1	1	0	1
P₃	1	0	2	1	2	0

Compute Available first. Show every step of the algorithm: which process finishes, what Work becomes, and which processes remain.

Simulate detection frequency. Suppose the deadlock in question 1 occurs at time t = 0, and the detection algorithm is run every t time units. Each run costs 1 unit of CPU time. Each unit of time that the deadlock remains undetected costs 5 units of idle CPU time (because the deadlocked processes are blocked and no other work can use their resources). Compute the total cost for t = 1, 5, 10, and 50. Which value of t minimizes the total cost? What does this suggest about the optimal detection frequency?
Compare the three strategies on one system. Consider the two-lock deadlock from Lesson 7.1. Describe how each of the four strategies (prevention, avoidance, detection and recovery, ostrich) would handle it:
- What would the strategy require of the program?
- What would happen when the deadlock would otherwise occur?
- What is the cost of the strategy?
- What would a real system actually do?
Present your answer in a table and write a paragraph recommending one strategy for a real system.
Analyse a real deadlock. Take the deadlocking program from Lesson 7.1 and run it. From a second terminal, use gdb to inspect the threads. Reconstruct the wait-for graph by hand from the backtraces. Then apply the detection-and-recovery procedure manually: choose a victim (which thread would you abort?), justify your choice, and describe what would happen to the other thread if you aborted the victim. Compare to the lock-ordering solution from Lesson 7.4.
Read a database deadlock-handling description. Find the documentation for a real database system's deadlock handling — PostgreSQL's Explicit Locking and Deadlock documentation, MySQL's InnoDB Deadlock Detection, or SQL Server's Deadlock Detection pages. Read the description of how the database detects and resolves deadlocks. Write a short summary comparing the database's approach to the theory in this lesson. What does the database do that the theory does not cover? What does the theory describe that the database does not implement?
Reflect on the unit. In your own words, describe the single most important idea you have learned in Unit 7 — the one that changed how you think about concurrency failures — and explain why it matters. Then identify one question that Unit 7 has left unanswered, and suggest how you would go about answering it.

10 Summary

The detection-and-recovery strategy allows deadlock to occur, detects it after the fact, and recovers by terminating a process or preempting a resource. It is the reactive counterpart to prevention and avoidance.
Detection requires only the current state of the system — which resources each process holds and which it is waiting for. It does not require advance knowledge of resource needs (as avoidance does) and does not require a discipline (as prevention does). This makes it applicable to a much wider range of systems.
For single-instance resources, detection is cycle detection in the wait-for graph. A cycle in the graph implies a deadlock. Cycle detection is O(V + E).
For multi-instance resources, detection is the reduction algorithm from Lesson 7.3. It simulates the completion of every process that can be satisfied from the current free resources; the processes that remain unfinished are deadlocked.
The detection algorithm and the Banker's algorithm share the same simulation structure, but with a crucial difference in the test: the Banker's algorithm uses the processes' maximum declared needs, whereas detection uses their current pending requests. This is why detection is applicable to any system, while the Banker's algorithm is restricted to systems where maxima are declared.
When to run detection is a trade-off between the cost of running the algorithm and the cost of leaving a deadlock undetected. Options include on every request, periodically, on a trigger (such as a drop in CPU utilization), and on demand.
Recovery by process termination aborts one or more processes in the cycle. Recovery by resource preemption takes a resource from one process and gives it to another. Both require a mechanism for rolling back the victim's work.
The rollback problem is the central difficulty of recovery. A process that has modified shared state leaves the state inconsistent when it is aborted; the system must be able to undo its modifications. Transaction logs, checkpointing, and restart-from-known-state are the mechanisms.
Victim selection uses criteria such as priority, work done, resources held, and rollback cost. The choice must avoid starvation: a process that is repeatedly chosen as a victim never finishes, so the number of past aborts must be included in the selection criteria.
Detection and recovery is used in database systems and transactional file systems, which have the two things the strategy needs: a way to observe the state (the wait-for graph) and a way to undo the work (the transaction log). It is not used in general-purpose operating systems for user-space code, because the kernel cannot roll back arbitrary user processes.
Comparing the three strategies: prevention acts at design time and requires a discipline; avoidance acts before each request and requires advance information; detection acts after the fact and requires rollback support. Each is appropriate for a different kind of system.
The ostrich algorithm — ignore the problem — is the fourth strategy, and it is the rational choice for general-purpose systems. The operating system provides the tools to inspect and kill a hung process, and leaves the detection and the choice of victim to the user, who has the information needed to make the decision.

Unit 7 complete

This closes the deadlock unit and the Module 2 material on processes and concurrency. You now have the full picture: the definition of deadlock and its distinction from starvation and livelock (Lesson 7.1), the four necessary conditions (Lesson 7.2), the resource-allocation graph and its analysis (Lesson 7.3), and the four strategies — prevention (Lesson 7.4), avoidance (Lessons 7.5 and 7.6), detection and recovery (this lesson), and the ostrich algorithm. Unit 8 begins Module 3 with memory management: the memory hierarchy, address binding, contiguous allocation, fragmentation, and segmentation. The concerns are different — memory is a resource that must be allocated and reclaimed, and the mechanisms are more physical — but the themes of resource management, efficiency, and correctness run through both units.

11 References

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 8, Sections 8.7–8.8.
Holt, R. C. Some Deadlock Properties of Computer Systems. ACM Computing Surveys, 1972. The original paper on the resource-allocation graph and the reduction algorithm.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 6, Sections 6.4–6.5.
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 32. Available online at ostep.org.
Garcia-Molina, H., Ullman, J. D., & Widom, J. Database Systems: The Complete Book, 2nd ed. The chapters on concurrency control and deadlock detection in database systems. The most detailed treatment available of how a real system implements detection and recovery.
Love, R. Linux Kernel Development, 3rd ed., Chapter 9, Kernel Synchronization Methods. The kernel's approach to detection: lock ordering for prevention, and tools such as lockdep and the hung-task detector for diagnosis.
Linux kernel documentation: Documentation/locking/lockdep-design.rst and Documentation/admin-guide/hung-task.rst.
PostgreSQL documentation, Explicit Locking and Deadlock. MySQL documentation, InnoDB Deadlock Detection. Microsoft documentation, Deadlock Detection. Real-world descriptions of detection and recovery in production database systems.
Linux man-pages: man 7 pthreads, man 1 kill, man 5 proc, man 1 gdb, man 1 strace.