Resource-Allocation Graphs and Cycles

From four conditions to one picture

In the previous guide you learned that a deadlock needs all of the four necessary conditions at once, and the last of them — circular wait — is the one that closes the trap: a chain of processes where each holds something the next one needs, looping back on itself. That circular wait is hard to spot by reading code. So this guide gives you a tool that makes it visible: a resource-allocation graph, a small drawing of who holds what and who is waiting for what. Once you can draw it, deadlock stops being an abstract worry and becomes something you can literally trace with a finger.

Remember the system resource model from the opening of this rung: the operating system manages resource types (a printer, a tape drive, a lock, a chunk of memory), and each type may have one or more identical instances. A process asks for a resource (request), gets granted it for a while (held), then gives it back (release). The graph is just an honest snapshot of that bookkeeping at one instant. Think of the kernel as a building manager holding a clipboard: the clipboard says which tenant currently has which key, and which tenant has put in a request and is now waiting at the desk. The resource-allocation graph is that clipboard, redrawn as dots and arrows.

Dots and arrows: how to read the graph

The graph has two kinds of dots and two kinds of arrows, and that is the whole vocabulary. A circle is a process. A rectangle is a resource type, and inside it we draw a little dot for each instance of that type — one dot for a single printer, three dots for three identical tape drives. The arrows tell the story. A request edge points from a process to a resource (the process is asking and waiting): draw it as an arrow from the circle to the rectangle. An assignment edge points from a specific instance dot inside a resource back to a process (the process currently holds that instance): draw it from a dot inside the rectangle to the circle.

Here is the natural rhythm of a request. A process P first draws a request edge to a resource R — an arrow from P toward R — meaning 'I want one R and I'm now waiting.' When the kernel grants it, that request edge flips around: it becomes an assignment edge from an instance dot in R back to P, meaning 'P now holds this one.' When P is done and releases the resource, that assignment edge is simply erased, freeing the instance for whoever is waiting. So at any instant the graph is alive — edges appearing as requests come in, flipping as grants happen, vanishing as releases happen. Deadlock is what we see when this living picture stops being able to change.

Two processes, two single-instance resources (R1, R2):

   (P1) --- request ---> [ R2 . ]
    ^                       |
    |                   assignment
  assignment                |
    |                       v
   [ R1 . ] <--- request --- (P2)

P1 holds R1, and is waiting for R2.
P2 holds R2, and is waiting for R1.

Follow the arrows:  P1 -> R2 -> P2 -> R1 -> P1
That path comes back to where it started: a CYCLE.
Neither can proceed. This is a deadlock.

When does a cycle mean a deadlock?

Here is the most important and most misunderstood fact about these graphs, so read it slowly. If every resource type has exactly one instance, then a cycle in the graph means a deadlock — full stop. With single-instance resources, a cycle is both necessary and sufficient: find a loop and the system is stuck; no loop and it is safe. That is the case in the picture above, and it matches the circular wait condition exactly, because the cycle just is the circular chain of waiting drawn out.

But the moment a resource type has several instances, a cycle no longer guarantees deadlock — it becomes only a warning sign, a necessary condition but not a sufficient one. Why? Because a cycle can be broken from the outside. Suppose the loop runs P1 to R, R to P2, P2 to S, S back to P1 — a cycle on paper. But if resource type R also has a second instance, and that second instance is held by some process P3 outside the cycle, then when P3 finishes and releases its instance of R, the waiting process can grab it, its request edge flips to an assignment edge, and the cycle is cut. No one was ever truly stuck. So with multiple instances: no cycle means definitely no deadlock, but a cycle means maybe — you have to look closer.

A tighter drawing: the wait-for graph

When every resource is single-instance, there is a slimmer drawing that throws away the resource boxes entirely. Collapse each chain 'P1 waits for R, R is held by P2' into a single arrow 'P1 waits for P2.' Now the picture has only process dots and only one kind of arrow. This is the wait-for graph, and it is exactly the resource-allocation graph with the resource nodes squeezed out. A cycle here means the same thing it did before — a deadlock — but the graph is smaller and faster to check, which is precisely why the deadlock detection machinery you will meet later prefers it.

So how does a program actually find a cycle in such a graph? It does what you do by hand, only systematically: it walks the arrows. Detecting a cycle in a directed graph is a standard, cheap operation — you can do it by following edges and watching for a node you have already visited on the current path. The kernel doesn't redraw pictures, of course; it keeps the same information as tables of who-holds-what and who-waits-for-what, and runs the cycle check over those tables. Here is the search, walked one step at a time.

1. Pick an unvisited process node and start walking. Mark it as 'on the current path.'
2. Follow this process's outgoing wait-for arrow to the process it is waiting on.
3. If that next process is already marked 'on the current path,' you have looped back to it — a cycle exists, and those processes are deadlocked.
4. If it is brand new, mark it 'on the current path' too and keep following its arrow, repeating the check.
5. If you reach a process that waits for nothing (a dead end), back out, unmark the nodes on this path, and start a fresh walk from another unvisited node. If every walk ends without revisiting a path node, there is no cycle — and therefore no deadlock.

Breaking the cycle is breaking a condition

The graph is not only a diagnosis; it quietly tells you the cure. To break a deadlock you must remove an edge from the cycle, and every way of removing an edge maps back onto denying one of the four conditions. Erase an assignment edge by forcibly taking a resource away from a process — that is denying no preemption. Refuse to draw a new request edge until a process is holding nothing — that attacks hold-and-wait. Make all processes request resources in one fixed global order so an arrow can never point 'backward' to close a loop — that is the ordering trick that prevents circular wait. Each is a scissors aimed at a different strand of the same knot.

And the same picture explains why most real systems do none of this at runtime. Drawing and re-scanning a graph for cycles costs time on every single resource request, and genuine deadlocks are rare in practice. So Linux, Windows, and the like usually take the pragmatic path you will meet later — the detect-and-recover approach run only occasionally, or simply ignoring the problem and rebooting on the rare hang. The graph remains the right way to think about deadlock even when the kernel never literally builds one; it is the mental model behind both the avoidance strategies and the detection ones. Next we turn from drawing the picture to staying out of trouble in the first place: keeping the system in a safe state, with the banker's algorithm.