Course contentsShow
← Computer Science
Lesson 1317 of 2,87230. Process SynchronizationFree lesson

Detecting Cycles in Resource Allocation Graphs

How cycles in resource allocation graphs indicate potential or actual deadlock situations.

Detecting Cycles in Resource Allocation Graphs

What you'll learn: How to identify when cycles in resource allocation graphs signal potential or actual deadlock situations.

The Core Idea

A cycle in a resource allocation graph means there's a circular chain of processes, each waiting for a resource held by the next process in the chain. This circular waiting is the telltale sign of deadlock trouble.

Think of it like a roundabout where every car is waiting for the car in front of it to move — but since they're all waiting on each other in a circle, nobody can move. That's deadlock.

How Cycles Indicate Deadlock

When you draw a resource allocation graph (processes as circles, resources as squares, arrows showing "requests" and "assignments"), look for paths that loop back to where they started.

Single-Instance Resources

If each resource type has only one instance and you find a cycle, you have definite deadlock. No escape is possible — every process in the cycle is stuck.

Example cycle:

  • Process P1 holds Resource R1, requests R2
  • Process P2 holds Resource R2, requests R1
  • This forms a cycle: P1 → R2 → P2 → R1 → P1 ✗ Deadlock!

Multiple-Instance Resources

If resources have multiple instances, a cycle means possible deadlock, but not guaranteed. Another instance might become available, breaking the wait.

Example:

  • Cycle exists between P1, P2, and R1
  • But R1 has 3 instances, and P3 might release one soon
  • P1 could get that freed instance and continue

Detection Strategy

To detect cycles, you can traverse the graph using depth-first search, keeping track of visited nodes. If you encounter a node you're already visiting in the current path, you've found a cycle.

Key Takeaway: A cycle in a resource allocation graph with single-instance resources guarantees deadlock; with multiple instances, it signals the potential for deadlock that requires deeper analysis.