Deadlocks: Prevention, Avoidance, Detection, and Recovery

10.1 The Deadlock Problem and the Resource Model

10.1.1 What a Deadlock Is

A deadlock is the situation where a set of processes are all blocked because each one holds a resource and waits for another resource that a different process in the set currently holds. Nobody can release what the others need, so nobody can move. The standard textbook phrasing is the same idea in formal clothes: a set of processes is in a deadlocked state when every process in the set is waiting for an event that can be caused only by another process in the same set — typically, the release of a held resource.

The canonical setup goes like this. Take two resources, R1 and R2, and two processes, P1 and P2. R1 has been allotted to P1, so P1 is holding it, and R2 is held by P2. Now P2 needs R1, and P1 needs R2. Each process waits for the other to release the resource it wants so it can acquire it. That mutual waiting is the deadlock. If you draw this as a graph — P1 waiting for R2 (assigned to P2), P2 waiting for R1 (assigned to P1) — you get a cycle, and a cycle of this kind is the signature of a deadlock.

The same pattern shows up in the real world with devices. Two processes can each be holding a device and be in need of the other one's device. Each waits for the other to release its device so it can be acquired. Nothing ever proceeds, because both releases are conditional on receiving what the other holds.

The deadlock need not involve two different resource types. It can also form among instances of one type: suppose three processes each hold one of three CD-RW drives, and each process now asks for a second drive. Every process is waiting for a release that can only come from another waiting process — deadlock again, with a single resource type.

10.1.2 Resource Types and Instances

Deadlock only matters when the resources in the system are finite in number. If resources were infinite, we would never need to think about deadlock at all. In a real system the resource set is finite: memory space, the CPU, files, and I/O devices such as printers, monitors, and DVD drives are all examples.

Within this model we distinguish a resource type from its instances. A resource type is the category — a monitor, a printer, or a CPU. If there are three printers in the lab, then the resource type "printer" has three instances. In general, with $n$ resource types and each type having some $m$ number of instances, we can describe the whole system as a matrix of counts: which instance of which type is held by which process, and which instances are free. The algorithms we follow for detection and avoidance are built on exactly this picture.

Two cautions about defining types. First, the instances of one type must be interchangeable: if the ninth-floor printer and the basement printer are not equivalent to the users, they belong in separate resource classes. Second, a process cannot ask for more instances than the system has — a process cannot request three printers when the lab has only two.

10.1.3 How a Process Uses Resources

To use a resource, a process follows a fixed three-step routine:

1. Request — the process asks for the resource. If it is not available, the process waits until it can acquire it.
2. Use — the process operates on the resource (for example, prints on the printer).
3. Release — the process gives the resource back.

Remember this order: the process has to request the resource before using it, and it has to release the resource after using it. All of the deadlock analysis that follows — prevention, avoidance, detection, recovery — assumes this request-use-release discipline. In the operating system these steps are system calls: request() and release() for devices, open() and close() for files, allocate() and free() for memory, and wait() and signal() on semaphores for resources the kernel does not manage.

Visual intuition: sketch the two-process deadlock as a four-node diagram. Draw P1 and P2 as circles, R1 and R2 as squares with one box each (one instance per type). Draw the assignment edges from the box of R1 to P1 and from the box of R2 to P2 (P1 holds R1, P2 holds R2), then the request edges P1 → R2 and P2 → R1. Now follow the arrows: P1 → R2 → P2 → R1 → P1 — you return to where you started. That closed loop is the deadlock fingerprint. One-sentence takeaway: a directed cycle of wait-and-hold edges is the signature of a deadlock, and the whole rest of this lecture is about preventing, avoiding, detecting, or breaking that fingerprint.

Real-world and domain connection: the same standoff appears at every scale of real systems. The classic historical example is the Kansas legislature law: "When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone" — a guaranteed deadlock written into law. In modern software, deadlocks show up in database transactions (two transactions each hold a row lock and ask for the other's row), in multithreaded programs that take mutex locks in opposite orders, and in distributed systems. That is why every operating systems course teaches the same model: a handful of finite resource types, their instances, and the request-use-release discipline — the vocabulary for all the analysis that follows.

10.2 The Four Necessary Conditions for Deadlock

Four conditions characterize a deadlock. All four must hold at the same time. They are called the characterization of deadlocks, and you should not forget them: mutual exclusion, hold and wait, no preemption, and circular wait.

10.2.1 Mutual Exclusion

Mutual exclusion means that only one process at a time can use a resource. If two printers are held by a particular process, then at that moment only that process can use them. No other process — say P2 or P3 — can use either printer until that process releases one or both of them. If a resource is non-shareable, only the process currently holding it may use it. For deadlock, what matters is that the resource at the center of the conflict is non-shareable: shareable resources, such as a read-only file, can be used by many processes at once and never force anyone to wait, so they can never take part in a deadlock.

10.2.2 Hold and Wait

Hold and wait means a process is holding at least one resource and is waiting to acquire additional resources that are currently held by another process. This is the condition we saw in the earlier diagram: the holding process sits on its resource while it waits for someone else's resource. The important word is and: the process both keeps what it already has and asks for more. A process that released everything before waiting would not satisfy this condition.

10.2.3 No Preemption

No preemption means a resource is released by a process voluntarily, and only by it. Whatever process is holding a resource has to release it on its own, after completing its task. This point is very, very important: the CPU cannot simply relinquish a process from a resource; that cannot be done. The process must voluntarily release the resource after finishing its work. Note that "preemption" here means taking a held resource away — it is not about CPU scheduling. A printer or a file in use cannot simply be yanked from its holder and handed to someone else.

10.2.4 Circular Wait

Circular wait is the chain that closes the loop. If we start from P0 and end back at P0, the pattern is: P0 waits for a resource held by P1, P1 waits for a resource held by P2, P2 waits for a resource held by P3, and so on, until $P_{n-1}$ waits for a resource held by P0. This is called a circular wait. If this pattern is present in any graph, then we can say there is a deadlock.

10.2.5 Necessary, Not Sufficient — and Characterizations Are Not Tools

All four conditions must happen simultaneously. If all four hold together, the deadlock has settled in; if even one is missing, we cannot call it a deadlock. But hold on: the four conditions are a necessary condition for deadlock, not a sufficient one. That distinction matters.

A common mistake is to write the characterizations when asked for something else. The characterizations are the four conditions above; they are not the tools. A tool is a mechanism — the way we avoid, prevent, or detect a deadlock. If we find a mechanism that prevents deadlock, that mechanism is a tool, not a characterization. Keep the two apart: the characterizations say what a deadlock is; the tools — prevention protocols, avoidance algorithms such as the Banker's algorithm, detection algorithms, and recovery mechanisms — say what we do about it.

Visual intuition: picture the four conditions as four switches that must all be on for the deadlock "machine" to run. Each switch is a property of the system: exclusivity of the resource, retention while waiting, no forced release, and a closed waiting chain. If any switch is off, the machine cannot start. The deadlock itself is the fourth switch — circular wait — closing; the first three just make that closure possible.

Real-world and domain connection: these four conditions are the checklist every real system uses when diagnosing a stuck system. Database deadlock reports, thread dumps from server runtimes, and distributed lock managers all end up asking the same four questions: was the resource exclusive, did the holders keep it while waiting, could anything force a release, and is there a closed waiting chain? If the answer is "yes, yes, no, yes", the diagnosis is a deadlock — and the cure will be one of the strategies in the next sections.

10.3 Resource Allocation Graphs

10.3.1 Notation and Edge Types

The resource allocation graph (RAG) is a way to draw the state of processes and resources. The vertices come in two kinds: circles for processes and squares for resource types. Inside each square, small boxes represent the instances of that resource type; the number of boxes inside the square is the number of instances.

There are two kinds of edges. A request edge goes from a process to a resource, $P_i\to R_j$, meaning process $P_i$ has requested resource $R_j$. The arrow touches the square itself, not one of the instance boxes, because the resource has not been allocated yet. An assignment edge goes from an instance to a process: the arrow starts at one of the boxes inside the square and ends at the circle of the process that holds that instance. Only when an arrow comes from a specific instance box to the process circle can we say that instance is held by that process.

10.3.2 The Cycle Rule

The next diagram changes the story: P3 is requesting R2, and R2 is currently held by P1 and P2. Now a cycle can be traced — start from P1, go to P2, come to P3, and end back at P1 by following the arrows. This gives us the rules you have to remember:

1. If the graph contains no cycle, there is no deadlock. This point is very important.
2. If the graph contains a cycle, and every resource type in the cycle has only one instance, then there is a deadlock. With single instances, a cycle is both a necessary and a sufficient condition for the existence of a deadlock. Only one instance — very, very important.
3. If the graph contains a cycle but some resource type has several instances, then there may or may not be a deadlock. Some other process might release one of its instances, and that instance could then be allocated to the process that is requesting it; in that case the deadlock never materializes. So with multiple instances, a cycle is a necessary condition for deadlock but not a sufficient one.

You can see the contrast in a graph that contains two cycles — one that starts with P1 and ends with P1, and another that starts with P2 and ends with P2. If the involved resource types are single-instance, there is a deadlock. In a different diagram a cycle is present but no deadlock exists, because the number of instances is more than one: for example, if P4 is going to release a particular instance, that instance may be allocated to P3, and then the waiting chain breaks. The presence of a cycle only creates the chance of a deadlock; it does not force one.

Exam note: the single-instance rule — cycle in the graph is necessary and sufficient — and the multiple-instance rule — cycle is necessary but not sufficient — are favorite question points. Do not forget them.

Visual intuition: think of the graph as a map of arrows. Circles and squares are the landmarks; request edges run into squares, assignment edges run out of instance boxes into circles. The landmark to hunt for is any closed walk that returns to its starting vertex. When you find one, the single-instance case makes the verdict immediate — deadlock — while the multi-instance case leaves an open question: can some other process release the instance that would break the loop?

Real-world and domain connection: resource allocation graphs are not just a textbook drawing. Lock checkers in kernels and deadlock detectors in databases construct exactly these wait-for relationships — who holds what, who waits for whom — and hunt for cycles in real time. The single-instance rule is why database row-lock detectors can declare a deadlock the moment a cycle appears, while allocators over pools of identical buffers, where several instances of a kind exist, must run the heavier multi-instance machinery.

10.4 The Three Strategies for Handling Deadlocks

10.4.1 Prevention and Avoidance versus Detection and Recovery

There are three broad ways to handle deadlocks. The first is deadlock prevention or avoidance: we make sure the system will never enter the deadlock state. The second is detection and recovery: we allow the system to enter the deadlock state, detect that it has happened, and then recover from it. The third is to ignore the problem as if it had never occurred. This is very important: prevention and avoidance aim at never entering the deadlock state, while detection and recovery accept that the deadlock can happen and deal with it afterwards.

Prevention and avoidance differ in one decisive way: prevention just stops a condition from ever being true, while avoidance uses declared maximums to check each allocation against the future. The "when to pick which" rule of thumb: prevention and avoidance suit systems where deadlock is expensive; detection and recovery suit systems where deadlock is possible but rare; and ignoring is what most real operating systems do, because they treat deadlock as too rare to justify constant protection.

10.4.2 Ignoring the Problem

Ignoring the deadlock is the last way of handling it. In real-time systems the possibility of a deadlock is pretty much small — it may happen something like once in a year or two — so this case is often handled by simply acting as if the problem had not occurred and going ahead. We will return to this point at the end, because it matches what real organizations actually do.

Ignoring is not carelessness; it is an economic choice. Prevention, avoidance, and detection all run constantly and therefore cost constantly, while an undetected deadlock may cost almost nothing for months at a time. If a deadlock does arrive, the system degrades — held resources sit idle, waiting processes pile up — until an operator notices and restarts it. That restart is the de facto "recovery" of the ignore strategy.

Real-world and domain connection: most production operating systems, including UNIX and Windows, offer no general deadlock-prevention machinery; the platform assumes applications avoid deadlock on their own and deals with the consequences when they do not. Database systems, in contrast, cannot afford to ignore the problem: they detect deadlocked transactions and abort one of them automatically. The three strategies are not competing theories — they are a toolkit, and each system picks the combination that fits its cost of failure.

10.5 Deadlock Prevention

The idea of prevention is to make sure at least one of the four necessary conditions never holds. Since all four conditions are needed for a deadlock, if any one of them is knocked out, the deadlock cannot occur. Note the difference from avoidance, which we will see next: prevention does not need any a priori information. In advance, we do not know how many resources each process will need, and that is fine — we just stop one of the conditions from ever being true.

10.5.1 Breaking Mutual Exclusion

Mutual exclusion can be attacked directly: resources are either shareable or non-shareable. For non-shareable resources we must keep mutual exclusion, but for shareable resources it is not required. A read-only file is the classic example: any number of processes can use it at the same time. Only when something is being written to a file do we need exclusion. So by designing resources to be shareable where possible — for instance, read-only files — the mutual exclusion condition simply does not occur, and that condition of the deadlock is prevented.

The honest limit: most resources cannot be shared. A printer cannot serve two processes at once, and only one process may update a file at a time. So breaking mutual exclusion is the cheapest prevention where the resource allows it, and it is off the table for intrinsically non-shareable resources — which is why the other three conditions each need their own protocols.

10.5.2 Breaking Hold and Wait

To break hold and wait, we must guarantee that a process requests a resource only when it is not holding any other resource. Two protocols achieve this:

• Protocol 1 — request everything up front: every process requests and is allocated all the resources it will ever need before it starts its execution. If P1 wants R1 and R2, both must be allocated before execution begins. If only R1 is allocated, the problem of hold and wait appears: P1 has R1 and is in need of R2, which is exactly the condition we are trying to prevent.
• Protocol 2 — release before asking again: a process may request a resource only when it holds no resource at all. It uses the resource, releases it, and only then asks for the next one.

Following either protocol prevents hold and wait, but the cost shows up in utilization. Whichever protocol we follow, resource utilization will always be lower. If P1 is in need of R1 and R2, we either give it all the resources or none. If we give everything to P1, P2 may not get R1 or R2 and has to stop. If we give nothing, then R1 or R2 is not used properly while P1 sits waiting. Either way some resource goes unused, and that problem cannot be avoided.

10.5.3 Breaking No Preemption

To break no preemption, we force preemption to happen. Two protocols are commonly used:

• Protocol 1 — take the held resources back: if a process holding some resources requests another resource that cannot be satisfied immediately, we take the held resources away from it. Suppose P1 holds R1 and R2 and asks for R3, but the request cannot be satisfied until R1 and R2 are released. We forcibly take R1 and R2 out of P1 — even though P1 has not completed its execution — add them to the list of available resources, and later let P1 restart afresh by requesting all the resources it needs again.
• Protocol 2 — preempt from a waiting process: when a process requests a resource that is currently held by a process which is itself waiting for something else, we preempt the resource from that waiting process. It is not doing any work anyway. If P1 is holding R1 and waiting for R2, we can take R1 away from P1 and allocate it to P2 or P3, whichever is requesting it. Why should R1 sit with P1 when P1 is blocked?

Either protocol makes preemption occur, and by doing so prevents the deadlock. These are some of the protocols in use; there may be others, but these two show the pattern. Note the scope: preemption is practical for resources whose state can be saved and restored — CPU registers and memory space — and not for printers or tape drives, whose state cannot be rolled back.

10.5.4 Breaking Circular Wait

Circular wait is broken by imposing a total ordering on the resource types: resources must always be allocated to processes in increasing order of enumeration. Each resource type gets a number, and a process may request resources only in that increasing order.

An example walks through it: suppose a particular process wants a file, a disk drive, and a printer. The natural order of access is first the disk drive, then — using the disk drive — the file, and then sending the file to the printer. So numbers are assigned in that same order: the disk drive gets the smallest number, the file next, the printer last. The process must request the disk drive first, then the file, then the printer. If every process requests in increasing order of enumeration, the circular wait condition cannot arise — the cycle has no way to close.

Why the ordering kills the cycle: suppose a circular wait did exist, with $P_0$ waiting for a resource held by $P_1$, $P_1$ waiting for one held by $P_2$, and so on around the ring. Under the ordering rule, $P_{i+1}$ holding $R_i$ and asking for $R_{i+1}$ forces $F(R_i)<F(R_{i+1})$ at every step, so $F(R_0)<F(R_1)<\cdots <F(R_n)<F(R_0)$ — a number that is less than itself, which is impossible. Since the contradiction cannot hold, the circular wait cannot form.

The price again is low device utilization and reduced system throughput: some resources may not be used, or may wait longer than necessary before being used. But if we need to prevent the deadlock, this ordering is one way to do it.

Real-world and domain connection: the ordering trick is the workhorse of lock ordering in real code — databases and multithreaded servers order their locks by address or by table identifier so every transaction acquires them in the same sequence. The no-preemption protocols appear in memory management, where a process's memory can be saved to disk and handed to another process, and in kernel locking code that releases a spinlock before waiting on a second one. The witness lock-order verifier on FreeBSD is a live example of the ordering rule enforced by software at runtime.

10.6 Deadlock Avoidance: Safe and Unsafe States

10.6.1 A Priori Information

If the deadlock cannot be prevented, the next line of defense is avoidance: make sure the system never enters the deadlock state — that is, never enters an unsafe state. Avoidance needs something prevention does not: a priori information. Each process must declare, in advance, how many resources it is going to request — its maximum demand. With that information in hand, we can allocate resources and check whether the allocation keeps the system in a safe state.

The difficulty is that we cannot know the future requests and releases of the processes. Sometimes a process acquires a resource and never uses it; sometimes we cannot tell whether a resource will be required at all. Prediction is hard. But based on the declared maximums we can describe the resource allocation state — how many resources there are, how many have been allocated, and what the maximum demand of each process is for each resource — and check whether the state is safe.

10.6.2 Safe States, Unsafe States, and Deadlocks

A state is safe when there exists a sequence of processes such that there are enough resources for the first process to finish; as soon as it finishes it releases its resources, which are enough for the second process to finish its execution; and so on until every process has finished. The sequence need not be the order in which the processes arrived — the order may be different, but some sequence must exist. Formally: a sequence $⟨P_1,P_2,\dots ,P_n⟩$ is a safe sequence for the current state if each $P_i$ can get everything it still needs from the currently available resources plus the resources held by the processes that finished before it.

If a process requests a resource that is not immediately available, it waits until some other process completes. That waiting does not by itself mean a deadlock. Avoidance simply ensures the system stays in a safe state.

Three facts follow, and they are basic facts to understand:

• If the system is in a safe state, there are no deadlocks.
• If the system is in an unsafe state, the possibility of a deadlock is there — which does not mean there is a deadlock.
• All deadlocks are unsafe states, but not all unsafe states are deadlocks. An unsafe state may still be rescued if the processes happen to release their resources in a helpful order; a deadlock is the worst case where that rescue fails.

We have to make sure the system never enters the unsafe state. That is the whole job of avoidance.

The choice of algorithm depends on the instance count. If each resource type has a single instance, we can use the resource allocation graph with claim edges, which we have already seen. If there are multiple instances, we have to go for the Banker's algorithm.

Visual intuition: picture the state space as three nested regions. The largest region holds all states. Inside it sits the smaller region of unsafe states. Inside that sits the deadlock states. Safe states lie in the ring outside the unsafe region: no deadlock is possible there, and the system can always reach a state where every process finishes. Entering the unsafe ring does not force a deadlock — some paths through it still reach completion — but the system no longer controls its fate; the processes do. The avoidance algorithms in the next two sections are trip wires that refuse to step out of the safe ring.

Real-world and domain connection: the safe/unsafe distinction is the same idea that database schedulers apply with lock tables and that resource managers apply in virtualization platforms — never commit to an allocation unless a completion order still exists. The tape-drive example is the textbook classic because it shows in one paragraph how a safe state can turn unsafe on a single grant, which is the entire reason avoidance algorithms exist.

10.7 Avoidance with Single-Instance Resources: Claim Edges

10.7.1 The Claim Edge

For avoidance, the resource allocation graph gains a third kind of edge. Besides the request edge (process to resource) and the assignment edge (instance to process), we now draw claim edges. A claim edge is a dashed or dotted line from a process to a resource, and it records a priori information: this process may request that resource in the future. It has not requested it yet, but it might. Whatever resources a process must claim, it should claim them a priori in the system so that avoidance has something to work with.

In the example: resource R1 is allocated to P1 — an assignment edge. P2 is requesting R1 — a request edge. Dashed claim edges from both P1 and P2 toward R1 show that both may be in need of this resource in the future; we do not know yet.

10.7.2 Edge Conversions and the Granting Rule

The edges are not static; they convert into each other as the system moves:

• A claim edge converts into a request edge whenever the process actually requests the resource. The dashed line turns solid.
• A request edge converts into an assignment edge whenever the resource has been allocated to the process.
• When the process releases the resource, the assignment edge converts back into a claim edge, because in the future the process may request the same resource again — we do not know.

The rule for granting a request is the cycle check. A request may be granted only if converting the claim edge to a request edge does not create a cycle in the graph. If the conversion would create a cycle, granting would let the system enter an unsafe state, so the request is not granted. This is the resource allocation graph method for deadlock avoidance, and it works for the single-instance case. If a problem gives a resource type with several instances — say A has four instances, B has three, C has two — this graph method will not work, and we have to switch to the Banker's algorithm.

Visual intuition: the graph is the same map as before — circles for processes, squares for resources, one box per instance — now decorated with dashed spokes (claims). Each dashed spoke says "this process might ask for this resource." A request becomes safe exactly when turning the relevant dashed spoke solid closes no loop. Watch the graph as requests arrive: the allowed grants are precisely those that leave every walk able to end somewhere new.

Real-world and domain connection: the claim-edge idea maps directly onto lock declarations in concurrent programming — a thread announces the locks it may take, and a runtime or static analyzer refuses the transition that would close a wait-for loop. The cycle test is also the same check that graph-based deadlock detectors run, which is why the single-instance rule keeps coming back: the graph encodes everything the scheduler needs to know.

10.8 The Banker's Algorithm

The Banker's algorithm handles deadlock avoidance when resource types have multiple instances. Under this algorithm, each process must claim the maximum use of the resources in advance. Whenever a process requests a resource, it may have to wait; and once a process gets all its resources, it must return them within a finite amount of time — after some point it has to release them. One honest note: the Banker's algorithm is not a very powerful algorithm, but it is the standard one we use to avoid a deadlock in this setting.

Why the name? The idea comes from banking: a banker must never lend out cash in a way that leaves it unable to honor every customer's declared need when that customer asks for it. The algorithm applies the same principle to resources: never allocate in a way that could leave some process unable to finish.

10.8.1 The Data Structures

The algorithm works on four data structures. Let there be $n$ processes and $m$ resource types.

• Available: a vector of length $m$ giving how many instances of each resource type are present (free) right now. Available of type $j$ is written $\text{Available}[j]$. If $\text{Available}[j]=k$, then $k$ instances of resource type $R_j$ are free.
• Max: an $n\times m$ matrix giving the maximum demand of each process for each resource type. $\text{Max}[i][j]$ is the maximum demand of process $P_i$ for resource type $R_j$ — the most $P_i$ may ever ask for. This is the a priori declaration.
• Allocation: an $n\times m$ matrix giving what has been allocated to each process so far. $\text{Allocation}[i][j]$ is how many instances of $R_j$ process $P_i$ currently holds.
• Need: an $n\times m$ matrix giving what each process still needs to complete. $\text{Need}[i][j]$ is how many more instances of $R_j$ process $P_i$ requires.

These four vectors and matrices are all we need to run the algorithm. Each row, such as $\text{Allocation}[i]$ or $\text{Need}[i]$, is treated as a vector, and a statement like $\text{Need}[i]\le \text{Work}$ means the comparison holds component-wise: every entry of the need vector must be at most the corresponding entry of the work vector.

10.8.2 Computing Need

The Need matrix is not given; we compute it from Max and Allocation. For each process and each resource type:

$$\text{Need}[i][j]=\text{Max}[i][j]-\text{Allocation}[i][j]$$

The verbal rule is "max minus allocation gives the need of each instance of a resource with respect to each process." If you know how to solve this problem from a snapshot, you can solve any question that is given: the only thing that changes is whether some incoming request can be satisfied — that is, whether it keeps the system in a safe state.

10.8.3 The Safety Algorithm

The safety algorithm decides whether a state is safe. It is carried out for any number of processes to check whether the system is in a safe state.

1. Let Work = Available, and let Finish[i] = false for all processes $i$. Finish[i] means "process i has completed and returned its resources." Initially nothing has completed.
2. Find an index $i$ such that Finish[i] == false and $\text{Need}[i]\le \text{Work}$. The comparison $\text{Need}[i]\le \text{Work}$ is component-wise: every entry of the need vector must be less than or equal to the corresponding entry of work. If no such $i$ exists, go to step 4.
3. $\text{Work}=\text{Work}+\text{Allocation}[i]$ and Finish[i] = true. Then go back to step 2 and look for the next process.
4. If Finish[i] == true for all $i$, the system is in a safe state. Otherwise it is not.

The narration that goes with it: work always starts equal to available; finish is false for all processes. We take the first process and check whether its finish is false, then check the condition need less than or equal to work. If the condition holds, we can allocate those instances to the process, complete its work, and the resources it held — its allocation — have to be returned. We add the allocation back to work and mark the process finished. Then we check the next process. If a process's need is not less than or equal to work, we leave it aside and try others; that is why the order of selection matters.

Always try to select a process with a small need, so that a safe sequence can be formed: if we finish small-need processes first, the available pool grows and can later be allocated to a process that needs more resources. That is the main idea.

10.8.4 Worked Example: Finding a Safe Sequence

Start from the snapshot above. Work = Available = (3,3,2) and Finish = (false, false, false, false, false).

Exam note: this is the computation to practice — given allocation, max, and available, compute need, run the safety algorithm, and report a safe sequence.

10.8.5 The Resource-Request Algorithm

The safety algorithm alone handles the static question. The resource request algorithm handles a live request: when some process $P_i$ requests resources right now, can the request be satisfied? Let the request vector be Request[i]. The steps:

1. If Request[i] $\le$ Need[i], go to step 2; otherwise raise an error — the process is asking for more than it declared. Remember this very important rule: a process cannot request resources beyond its maximum; the request must stay within its need.
2. If Request[i] $\le$ Available, go to step 3; otherwise the process must wait.
3. Pretend to allocate the requested resources to $P_i$: modify the state as if the request were granted:

$$\text{Available}=\text{Available}-\text{Request}[i]$$ $$\text{Allocation}[i]=\text{Allocation}[i]+\text{Request}[i]$$ $$\text{Need}[i]=\text{Need}[i]-\text{Request}[i]$$

Then run the safety algorithm on this pretend state. If the resulting state is safe, the request is granted and the pretend state becomes the real one. If the resulting state is unsafe, the process has to wait, and the pretend changes are rolled back.

The request must be within the need and within the availability; only then can the request be satisfied, and only when the safety check passes. Whether the system is safe decides whether we grant or restore and wait.

10.8.6 Worked Example: A Request That Is Granted

Suppose P1 requests (1,0,2). Check the two conditions against the original snapshot:

• Request (1,0,2) $\le$ Need[P1] = (1,2,2) — yes.
• Request (1,0,2) $\le$ Available = (3,3,2) — yes.

Both conditions hold, so we pretend to allocate and modify the state:

• Available becomes (3,3,2) − (1,0,2) = (2,3,0).
• Allocation[P1] becomes (2,0,0) + (1,0,2) = (3,0,2).
• Need[P1] becomes (1,2,2) − (1,0,2) = (0,2,0).

10.8.7 Worked Example: A Request That Must Wait

Now suppose P4 requests (3,3,0). Check the conditions:

• Request (3,3,0) $\le$ Need[P4] = (4,3,1) — yes.
• Request (3,3,0) $\le$ Available = (3,3,2) — yes.

Both conditions pass, so we pretend to allocate:

• Available becomes (3,3,2) − (3,3,0) = (0,0,2).
• Allocation[P4] becomes (0,0,2) + (3,3,0) = (3,3,2).
• Need[P4] becomes (4,3,1) − (3,3,0) = (1,0,1).

Real-world and domain connection: the Banker's algorithm is the standard textbook avoidance method for multi-instance systems, but it is not a very powerful algorithm and is rarely what production systems actually run; its real value is in understanding safe and unsafe states. Its direct descendants are credit limits in database schedulers and admission control in systems where a maximum demand per client is known — the pattern of "never commit to a request whose future completion you cannot guarantee" shows up wherever a system hands out scarce resources with promises attached.

10.9 Deadlock Detection

Prevention and avoidance stop deadlocks from happening. Detection starts from the opposite assumption: the deadlock may already exist. We detect whether a deadlock has occurred, and if it has, we rectify it. Two tools, chosen by the instance count: for single instances the method uses the wait-for graph; for multiple instances it uses the detection algorithm.

10.9.1 Single-Instance Resources: The Wait-For Graph

For detection with single instances we build a wait-for graph, a variation of the resource allocation graph. The nodes are the processes only — no resource nodes — and an edge $P_i\to P_j$ means process $P_i$ is waiting for a resource that is currently allocated to process $P_j$. The whole point is to remove the resources: when a deadlock has occurred, we should be able to tell from the processes alone which one is waiting for which. If an arrow comes from one process to another, that first process is in need of a resource currently allocated to the second.

The graph is produced by converting the resource allocation graph: wherever an edge runs from $P_i$ to a resource held by $P_j$, draw $P_i\to P_j$ directly, so the converted graph holds edges only between processes. An edge $P_i\to P_j$ exists in the wait-for graph exactly when the resource allocation graph contains the two edges $P_i\to R_q$ and $R_q\to P_j$ for some resource $R_q$.

Then we check whether a cycle exists. If the wait-for graph contains a cycle, there is a deadlock. Detecting the cycle costs $O(n^2)$ operations — "n squared" — where $n$ is the number of vertices, and the vertices are always the processes. With four processes, that is $4^2=16$ operations.

10.9.2 Multiple-Instance Resources: The Detection Algorithm

When resource types have several instances, we go back to vectors and matrices — availability, allocation, and request — and run the detection algorithm. It is a variation of the safety algorithm:

1. Let Work = Available. For each process $i$: if $\text{Allocation}[i]\ne 0$ — meaning some resources are still allocated to it — set Finish[i] = false; otherwise set Finish[i] = true. A process holding nothing does not need to wait for anything to return.
2. Find an index $i$ such that Finish[i] == false and Request[i] $\le$ Work. If no such $i$ exists, go to step 4.
3. $\text{Work}=\text{Work}+\text{Allocation}[i]$; Finish[i] = true; go back to step 2.
4. If Finish[i] == false for some process $i$, the system is in a deadlock state, and the processes with Finish[i] == false are the deadlocked ones.

The narration: work equals available; start checking each process. When a process has completed its work, it returns its resources; if it has not returned them, its allocation is not zero and its finish stays false. Every time we check whether the finish is false and then whether the request is less than or equal to work. If the condition holds, we add the availability to the allocation — that is, the process completes and its resources join the pool — and mark it finished. Then we check the next process. After all checks, if some finish vector entries are still false, the system is in a deadlock state. Remember: Finish[i] should be true for all processes. Even if one process has finish false, that process is deadlocked — it is waiting for a resource.

10.9.3 Worked Example: Detection with No Free Instances

The example differs from the Banker's one in the instance counts: here A has 7 instances, B has 2, and C has 6. Again there are five processes, P0 to P4, with allocation, request, and availability vectors. The key fact: there is no availability of any resource type — Available = (0,0,0) — every instance is allocated. The state is:

Note that P2 is making a request for one instance of resource type C — request (0,0,1) — one more than it was asking before. We take the processes in some order — it can be any order, for example P0, P2, P3, P4, P1 — and check each one; the aim is only to check all of them. For a request to be satisfied, the condition Request[i] $\le$ Work would have to hold. Consider P2: its request (0,0,1) against work (0,0,0) — the third component needs 1 ≤ 0, which is false, so the request cannot be granted and Finish[P2] stays false. The same happens for every process that has a request: even if some other process asks for any resource, it cannot be granted, because there are no free instances.

Exam note: when the request cannot be satisfied — request is not less than or equal to available — that process's finish stays false; after checking every process, the ones still false are deadlocked. Know when to use the wait-for graph (single instance) versus the detection algorithm (multiple instances).

Real-world and domain connection: wait-for graphs are exactly what database systems maintain as they track row locks — when a cycle appears among transactions, one transaction is chosen and aborted. The multi-instance detection algorithm is the model for detecting buffer and memory-pool deadlocks in kernels. The detection schedule matters in practice too: databases run detection on every lock wait, while batch systems check periodically, trading CPU cost against how long a deadlock is allowed to strangle the system.

10.10 Deadlock Recovery

Once a deadlock is present, we have to recover from it. There are two families of recovery: process termination and resource preemption.

10.10.1 Process Termination

Terminating processes is one way to recover. There are two versions:

• Abort all the deadlocked processes. In the detection example above, that would mean killing all of P1 to P4. Simple, but drastic: every partial computation of those processes is thrown away, and the work must be redone later.
• Abort one process at a time. Suppose we abort only P1; P2 and P3 are still there, so we have to check whether the cycle still exists. If the cycle disappears, we need not terminate P2, P3, or P4. If it does exist, we abort another process and check again. Each abort costs a fresh detection run, so this version is cheaper in damage and more expensive in overhead.

The next question is the order in which we abort. The choice depends on several criteria, and the first one is the priority of the process. If a process's priority is high, we should not choose that process to abort; we consider some other process. Then we look at how long the process has been executing and how long it will still take to complete. Then how much of the resources the process has used, and how much more it needs. Then how many processes will be terminated because of this one. Finally, whether it is an interactive process or a batch process. Based on these conditions we choose the order of aborting.

The same priority idea appears everywhere, even in networking. In computer networks you have differentiated service classes: every message or process sent is tagged with a class, and based on that class it gets priority. When messages travel from source to destination they cross many nodes, and at each node many messages arrive and form a queue. The higher-priority message is sent first because it should not stay in the queue; it leaves the queue first, while the other processes wait in the queue. So priority decides the order there too — the same principle as choosing which deadlocked process to abort.

10.10.2 Resource Preemption, Rollback, and Starvation

The other family of recovery is resource preemption: we voluntarily take a resource away from a process. Three things have to be handled.

First, select a victim — decide from which process the resource is to be taken. The same ordering rules apply as in process termination: if a process has a high priority, it should not be selected as the first victim. From the lower-priority processes the resources are preempted, and the deadlock is resolved.

Second, rollback. Suppose R1 is currently held by P1 and we take R1 from P1. P1 cannot continue, because it has not completed its execution — if it had completed, it would have returned the resource itself. So we have to start it again after some time, restarting it from the state where it was terminated, or from the point where it rolled back. Sometimes, if the operation is an atomic action, it has to start from the very beginning and complete again. We do not always know whether the action is atomic or not, which is part of the difficulty.

Third, starvation. If we take R1 from P1 once, we must make sure starvation does not occur — but we cannot give that guarantee. P1 should not always be the victim; P1 should not starve always. Can we give that guarantee? No, that also cannot be guaranteed — no such guarantee exists. If we always take R1 from P1, or R2 from P1, or R3 from P1 — whatever P1 is holding — then P1 will be starving. Each of these recovery ways has its own problem that cannot be avoided entirely, but we still use them to recover.

Real-world: this is why, in real-time systems and in organizations, deadlock rarely occurs — something like once in a year or two — because the event is so rare, and organizations tend to ignore the deadlock as if it had not occurred. That is the true sense of what happens. The prevention, avoidance, detection, and recovery machinery is the theory; the ignore strategy is what practice leans on because the event is so rare.

To recap the tool selection: for detection with single instances, use the wait-for graph; for detection with multiple instances, run the deadlock detection algorithm and find out which processes are deadlocked. For avoidance with multiple instances, use the Banker's algorithm; for avoidance with single instances, use the resource allocation graph. Keep all these points in mind — a problem based on them is likely.

Real-world and domain connection: the priority-first abort policy is standard in real-time systems, where missing a deadline costs more than losing a process, and in databases, where the transaction with the fewest locks or the youngest start time is usually the chosen victim. The networking parallel is direct: differentiated service classes tag every message, and routers forward higher-priority classes first — the same rule that decides which deadlocked process is aborted first. The whole recovery toolbox matters most in mission-critical servers; in everyday systems, the once-a-year deadlock is met with a manual restart.

Exam Guidance Summary

• Expect a problem on deadlocks — "you will have, sure, you may get a problem based on which you have to solve." Practice the end-of-chapter deadlock problems from the textbook; try solving them yourself, and if you cannot, bring them up in the next class.
• Master the computations: given a snapshot (allocation, max, available), compute the need matrix as max minus allocation, run the safety algorithm to produce a safe sequence, and test incoming requests with the resource-request algorithm, granting only when the pretend state is safe. The full arithmetic pipeline — need matrix, safety run, request check, refusal with restore — is the single most practiced skill in this lecture.
• Memorize the four necessary conditions — mutual exclusion, hold and wait, no preemption, circular wait — and remember they are necessary but not sufficient, and that characterizations are not the tools.
• Remember the cycle rules: no cycle means no deadlock; a cycle with a single instance per resource type means deadlock (necessary and sufficient); a cycle with multiple instances is only necessary, not sufficient.
• Remember the safe-state facts: safe state means no deadlock; unsafe state means only a possibility; all deadlocks are unsafe states, but not all unsafe states are deadlocks.
• Know the algorithm choice: single instance → resource allocation graph with claim edges for avoidance, wait-for graph for detection; multiple instances → Banker's algorithm for avoidance, detection algorithm for detection. Wait-for graph cycle detection costs O(n²) for n processes.
• Know the recovery criteria order: priority first (lowest integer is the highest priority), then how long the process has executed, how much longer it needs, resources used and needed, how many processes will be terminated, and interactive versus batch last.
• Quiz: it covers the topics of module 4 and module 5 — the two important topics covered so far. One attempt is allowed, with no timeline, and it must be completed before the 28th. Inform your classmates.
• In the next contact session, the solutions of both the regular and the makeup exam papers will be discussed.

Key Industry Applications

• Real-world: most real systems and organizations face deadlocks so rarely — roughly once in a year or two — that they use the ignore strategy: they act as if the deadlock problem has not occurred and keep going. The elaborate prevention and detection machinery is mostly insurance for rarer, mission-critical cases.
• Real-world: priority-driven process selection in deadlock recovery mirrors differentiated service classes in computer networks: at every node, messages of higher-priority classes are forwarded first so they do not linger in queues, while lower-priority messages wait.
• Real-world: shareable resources in practice — such as read-only files that any number of processes may read at once — remove the mutual exclusion condition without any scheduling machinery, which is the cheapest possible prevention.
• Real-world: the resource model itself is built from everyday finite resources: memory space, the CPU, files, printers, monitors, and DVD drives are the instances that the deadlock algorithms count and allocate.
• Real-world: the Banker's algorithm is the standard textbook avoidance method for multi-instance systems, but it is not a very powerful algorithm and is rarely what production systems actually run; its real value is in understanding safe and unsafe states.
• Real-world: database systems are the one place where detection and recovery are never skipped — lock-wait cycles among transactions are detected and one transaction is aborted automatically, which is the practical form of the wait-for graph and the abort-one-at-a-time recovery from this lecture.