← 🚧 Deadlock
Subtopic 2 of 4

4.2Resource allocation graph

The idea

A resource allocation graph shows who holds and who wants what. With one instance per resource a cycle means deadlock; with several instances it only means deadlock is possible.

Think of it like this: A map of IOUs: A waits for B who waits for C who waits for A. But if the lender has two copies of the thing, someone else may return one.

Why it exists

It lets you check small systems by eye and explains exactly why cycle ≠ deadlock when instances are multiple.

How it works

  1. Draw processes as circles, resources as boxes with dots for instances.
  2. Request edge P → R; assignment edge R → P.
  3. No cycle: no deadlock. Single instances and a cycle: deadlock.
  4. Multiple instances: run the reduction (find a process whose requests can be met, release its holdings, repeat).

Worked example: Cycle with two instances of R1

P1 and P2 hold the two R1 instances, P3 holds R2 and wants R1, P1 wants R2. There is a cycle P1 → R2 → P3 → R1 → P1, but P2 wants nothing: it finishes and frees an R1, P3 then gets it, finishes and frees R2, and P1 finishes. No deadlock, so a cycle alone proved nothing; only the detection algorithm settles it.

Now play with it

  • →Load "Cycle with single instances": deadlock.
  • →Load "Cycle with 2 instances": there is a cycle but no deadlock.
P1P2R1●R2●

Dashed red = request edge, solid green = assignment edge.

Cycle in the graph?yes
Deadlock?YES
Deadlocked processesP1, P2

Single instance per resource: a cycle means deadlock. Several instances: a cycle is necessary but not sufficient, so run the detection algorithm (find a process whose requests can be met, let it finish and release, repeat). Here that algorithm decides the answer.

Check yourself

A resource allocation graph has a cycle and every resource has one instance. Then

Remember: Single instance: cycle ⇔ deadlock. Several instances: cycle is only necessary. No cycle: never deadlock.
Exam notes (the dense version)

Vertices: processes (circles) and resources (squares with a dot per instance). Request edge P → R, assignment edge R → P. With one instance per resource, a cycle is both necessary and sufficient for deadlock. With several instances, a cycle is only necessary: another process outside the cycle may release an instance and break it. No cycle always means no deadlock.

Previous year questions: Deadlock (9)

PYQs are grouped by topic, so this is the full set for Deadlock; try the ones that match this subtopic. Open all 9 on the topic page.