Resource allocation graphs and detection

Describing the deadlock in words took a paragraph. And that was with only two processes.

Give the OS forty processes and a hundred locks, and words are hopeless.

Draw it instead. Deadlock has a shape, and once you know the shape you can spot it in a second.

Why & what

The graph. A resource allocation graph has two kinds of node and two kinds of arrow.

• A circle is a process.
• A square is a resource type. Dots inside it are instances — one dot means there is one of them.
• An arrow from a process to a resource is a request. "I want this."
• An arrow from a resource to a process is an assignment. "You have this."

Our deadlock draws as a square loop: editor → matrix → compile job → build.log → editor.

What a cycle tells you. This is the part that gets tested, and the answer depends on how many instances each resource has.

• One instance of each resource: a cycle means deadlock. Always. No further checking needed.
• Several instances: a cycle means deadlock is possible. Some process outside the cycle might be holding an instance and about to release it, and when it does the cycle dissolves.

And in both cases, no cycle means no deadlock. That direction is always safe.

Detection. An OS can choose to allow deadlocks and simply look for them every so often.

Building the graph and looking for a cycle is exactly that check.

Why would anyone allow deadlocks? Because prevention costs something all the time, and deadlocks are rare. Running a check once a minute may be far cheaper than restricting every lock request forever.

The ostrich algorithm. Most general-purpose systems, including Linux and Windows, do something simpler still: they ignore the problem. If a deadlock happens, the user restarts the application.

That sounds like a joke, and it is a real engineering decision. Deadlocks are rare, detection costs CPU on every process, and a restart is cheap. The name comes from the idea of an ostrich putting its head in the sand.

How it works

Building and reading the graph:

1. Draw a circle for every process and a square for every resource type, with one dot per instance.
2. Draw an assignment arrow from each resource instance to the process currently holding it.
3. Draw a request arrow from each waiting process to the resource it wants.
4. Look for a cycle. No cycle means you are finished — there is no deadlock.
5. If there is a cycle, check the instance counts. Single instances mean a confirmed deadlock. Multiple instances mean you must simulate: can any process outside the cycle finish and release something?

Common confusion

"A cycle always means deadlock." Only when each resource has one instance. This is the single most tested detail of the topic, and the safe way to remember it is to state the reliable direction first: no cycle, no deadlock, guaranteed. The reverse needs a condition attached.

"Assignment and request arrows point the same way." They point in opposite directions, and getting them backwards makes the graph meaningless. A useful check: an arrow out of a process means the process is asking and therefore waiting.

"Detection fixes the deadlock." It only finds it. Something still has to be done afterwards, and that is Topic 5.3's recovery section.

Interview angle

"When does a cycle in a resource allocation graph mean deadlock?" Give both halves: with single-instance resources a cycle is sufficient; with multiple instances it is only necessary. Then add the line that always holds — no cycle, no deadlock.

"Why do real operating systems not detect deadlocks?" Name the ostrich algorithm and give the reasoning: deadlocks are rare, detection and prevention both cost performance continuously, and killing or restarting the affected program is an acceptable price. Interviewers like this answer because it shows you can weigh a cost rather than reciting a technique.