Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 66 ยท Deadlocks

Resource Allocation Graphs and Cycle Detection

Draw and read resource allocation graphs, learn when a cycle means deadlock, and run cycle detection and graph reduction for single and multiple instances.

To reason about deadlocks, the operating system keeps a picture of who holds what and who waits for what: the resource allocation graph (RAG). It is a directed graph with two kinds of nodes and two kinds of edges, and one glance at it reveals whether a deadlock exists or is possible.

Reading the graph

  • Process nodes are drawn as circles: P1, P2, ...
  • Resource nodes are drawn as rectangles: R1, R2, ... Each dot inside stands for one instance of that resource type.
  • A request edge P -> R means process P is waiting for an instance of R.
  • An assignment edge R -> P means an instance of R is currently allocated to P.
  • (For avoidance, a dashed claim edge P ..> R means P may request R in the future.)
flowchart LR
    P1(("P1")) -- "request" --> R1["R1 (1 instance)"]
    R1 -- "assigned" --> P2(("P2"))
    P2 -- "request" --> R2["R2 (1 instance)"]
    R2 -- "assigned" --> P1

P1 holds R2 and wants R1; P2 holds R1 and wants R2. The graph contains a cycle: P1, R1, P2, R2, P1.

What a cycle means

The rules depend on how many instances each resource type has:

Situation Conclusion
No cycle No deadlock.
Cycle, every resource in it has a single instance Deadlock. The cycle is both necessary and sufficient.
Cycle, but some resource type has several instances Possible deadlock, not certain. Another process outside the cycle may release an instance.

With multiple instances a cycle is only a warning. To decide for sure, we reduce the graph: repeatedly find a process that can get everything it is waiting for, pretend it runs to completion, and release what it holds. Processes that remain at the end are deadlocked.

When every resource has one instance, the graph can be simplified to a wait-for graph: remove the resources and draw Pi -> Pj if Pi waits for a resource that Pj holds. A deadlock is then exactly a cycle in that graph, and a depth-first search finds it.

Python Finding a cycle with depth-first search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first call prints a cycle through P1, P2 and P3. P4 is blocked by the deadlock but not part of it; once the operating system breaks the cycle P4 can continue. In the second call, P3 can finish, which frees P2, which frees P1.

Multiple instances: graph reduction

Now give resources several instances. We need, for each process, how many units of each resource it holds and how many it is waiting for. The reduction algorithm then works like this:

  1. Compute available = total instances - allocated instances.
  2. Find an unfinished process whose outstanding requests are all <= available.
  3. Mark it finished and add everything it holds back to available.
  4. Repeat until no such process exists. Unfinished processes are deadlocked.

Here is the scenario from the diagram idea above: R1 has two instances (held by P2 and P4), R2 has one (held by P1). P1 waits for R1, P2 waits for R2. P4 is not waiting for anything. There is a cycle P1 -> R1 -> P2 -> R2 -> P1, but P4 is not stuck.

Python Cycle does not always mean deadlock

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In case A, P4 finishes first, returning an instance of R1; P1 gets it, finishes, and frees R2 for P2. The cycle was only a possible deadlock. In case B, P4 also wants R2, nobody can finish, and the survivors P1, P2 and P4 are deadlocked.

This reduction is the heart of the detection algorithm in the detection lesson, and its cousin with maximum claims instead of current requests is the banker's algorithm.

Using the graph

  • Detection: build the graph from the system's tables and search for cycles or reduce it, periodically or when the CPU becomes suspiciously idle.
  • Avoidance (single instances): grant a request only if converting the request into an assignment edge does not create a cycle (considering claim edges).
  • Debugging: lock-order analysis tools such as Linux lockdep or database deadlock reports are RAGs in disguise.

When you read a deadlock report from a database, look for the cycle: transaction A waits for a row held by B, B waits for one held by A. The fix is nearly always to lock rows in a consistent order.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a resource allocation graph, what does an edge from a resource R to a process P mean?

    R -> P is an assignment edge; P -> R is a request edge.
  2. 2. A RAG has a cycle and every resource has exactly one instance. What follows?

    With single instances, no outside process can release anything into the cycle, so the cycle is a deadlock.
  3. 3. Why is a cycle not always a deadlock when a resource has two instances?

    If a process outside the cycle finishes and returns an instance, a process inside the cycle can proceed, which dissolves the cycle.
  4. 4. In the reduction algorithm, which process is chosen at each step?

    A process that can obtain everything it waits for can finish and release its holdings; repeat until nobody qualifies.

Summary

  • A RAG has process nodes, resource nodes (with instance dots), request edges and assignment edges.
  • No cycle means no deadlock. A cycle with single-instance resources is a deadlock; with multiple instances it is only a possibility.
  • A wait-for graph (single instances) turns detection into DFS cycle search.
  • Graph reduction repeatedly finishes any process whose requests fit in what is available; the leftovers are deadlocked.

Next: Deadlock Prevention