1. Introduction

To understand, analyze, and detect deadlocks, the operating system requires a structured way to represent the relationships between processes and resources.

A Resource Allocation Graph (RAG) is a graphical model used to represent how resources are allocated to processes and how processes request resources.

It provides a visual representation of resource usage and waiting relationships within a system, making it one of the most important conceptual tools for deadlock analysis.

Resource Allocation Graphs are widely used in operating system theory for:

• Deadlock modeling

• Deadlock detection

• Deadlock avoidance

• Resource allocation analysis

2. Definition

A Resource Allocation Graph (RAG) is defined as:

A directed graph consisting of processes, resources, and directed edges that represent resource requests and resource allocations.

The graph captures two fundamental relationships:

• Which resources are currently allocated to processes

• Which resources are being requested by processes

By examining these relationships, the operating system can determine whether a deadlock exists or may occur in the future.

3. Core Idea

The central idea behind a Resource Allocation Graph is simple:

Who Holds Which Resource?
+
Who Is Waiting For Which Resource?

A deadlock occurs when waiting relationships form a circular dependency among processes.

The graph provides a convenient way to visualize these dependencies.

4. Components of a Resource Allocation Graph

A Resource Allocation Graph consists of:

• Nodes

• Directed Edges

These elements collectively describe the state of resource allocation in the system.

4.1 Process Nodes

Processes are represented as circles.

Example:

(P1)   (P2)   (P3)

Each process node represents an active process executing within the system.

4.2 Resource Nodes

Resources are represented as rectangles.

Example:

[R1]   [R2]   [R3]

Each resource node represents a specific resource type.

Examples include:

• Printer

• Scanner

• File Lock

• Tape Drive

• Database Lock

4.3 Resource Instances

If a resource has multiple instances, each instance is represented by a dot inside the resource rectangle.

Example:

[R1 • • •]

This indicates that Resource R1 has three available instances.

Example:

[R2 •]

This indicates that Resource R2 has a single instance.

5. Types of Edges in RAG

Two primary edge types are used.

5.1 Request Edge

A request edge represents a process requesting a resource.

Representation:

Process → Resource

Example:

P1 → R1

Meaning:

P1 is waiting for Resource R1

The resource has not yet been allocated.

The process remains blocked until the resource becomes available.

5.2 Assignment Edge

An assignment edge represents a resource currently allocated to a process.

Representation:

Resource → Process

Example:

R1 → P1

Meaning:

Resource R1 is allocated to P1

The process is currently using the resource.

6. Example of Resource Allocation Graph

Consider:

Resource R1 allocated to P2

and

P1 requesting R1

Graphically:

P1 → R1 → P2

Interpretation:

• P2 currently owns R1

• P1 is waiting for R1

• P1 cannot proceed until P2 releases R1

This creates a dependency relationship.

7. Building a Resource Allocation Graph

Consider two processes:

P1
P2

and two resources:

R1
R2

Suppose:

R1 allocated to P2

R2 allocated to P1

and

P1 requests R1

P2 requests R2

The graph becomes:

P1 → R1 → P2
↑           ↓
R2 ← P2 ← R2

More clearly:

P1 → R1
R1 → P2

P2 → R2
R2 → P1

8. Cycles in Resource Allocation Graphs

The most important concept in RAG analysis is the cycle.

A cycle occurs when following directed edges eventually returns to the starting node.

Example:

P1 → R1 → P2 → R2 → P1

This forms a circular dependency.

Interpretation:

P1 waits for P2

and

P2 waits for P1

Neither process can proceed.

9. Cycle Detection and Deadlocks

The significance of a cycle depends on the number of resource instances.

9.1 Single Instance of Each Resource

If every resource has exactly one instance:

Cycle ⇔ Deadlock

This is an extremely important theorem.

Meaning:

• If a cycle exists → deadlock definitely exists

• If no cycle exists → deadlock does not exist

Example:

P1 → R1 → P2 → R2 → P1

Since:

R1 has one instance
R2 has one instance

the cycle guarantees deadlock.

9.2 Multiple Resource Instances

If resources have multiple instances:

Cycle ⇒ Possible Deadlock

but not necessarily a deadlock.

A cycle only indicates the possibility of deadlock.

Additional analysis is required.

Example:

R1 has 3 instances

One instance may still be available.

Processes might eventually proceed.

Therefore:

Cycle ≠ Guaranteed Deadlock

10. Why Cycles Matter

Deadlocks fundamentally arise from circular waiting.

Example:

P1 waits for P2

P2 waits for P3

P3 waits for P1

Graphically:

P1 → P2 → P3 → P1

This circular dependency prevents progress.

The Resource Allocation Graph makes such situations immediately visible.

11. Resource Allocation Graph with Multiple Instances

Consider:

Resource R1 has 3 instances

Representation:

[R1 • • •]

Suppose:

Instance 1 → P1
Instance 2 → P2
Instance 3 → Available

Even if:

P3 → R1

the system may still satisfy the request.

Therefore:

Cycle alone is insufficient

for deadlock detection when multiple instances exist.

12. Claim Edges (Deadlock Avoidance)

For deadlock avoidance, RAGs may include a third edge type.

12.1 Claim Edge

A claim edge represents a resource that a process may request in the future.

Representation:

P1 - - -> R1

(dashed edge)

Meaning:

P1 may request R1 later

but currently does not need it.

Claim edges are used in deadlock avoidance algorithms.

13. Purpose of Claim Edges

The operating system uses claim edges to:

• Predict future resource requests

• Analyze safe allocations

• Prevent unsafe states

Example:

P1 - - -> R1

If granting another request would create a cycle involving this claim edge:

Allocation Denied

This prevents deadlock before it occurs.

14. Deadlock Detection Using RAG

For systems with single resource instances:

Step 1

Construct the graph.

Step 2

Search for cycles.

Step 3

Interpret result:

Cycle Exists
      ↓
Deadlock Exists

or

No Cycle
      ↓
No Deadlock

15. Graph Reduction Technique

Deadlock detection can also be viewed as graph reduction.

Procedure:

Find Process That Can Complete

Remove:

Process
+
Allocated Resources

Release Resources

Resources become available.

Repeat

Continue removing processes that can complete.

If all processes can be removed:

No Deadlock

If some processes remain permanently:

Deadlock Exists

16. Advantages of Resource Allocation Graphs

Visual Representation

Easy to understand.

Cycle Identification

Deadlock patterns become obvious.

Useful for Teaching

Excellent conceptual tool.

Foundation for Other Algorithms

Many deadlock algorithms build upon RAG concepts.

17. Limitations of Resource Allocation Graphs

Scalability Issues

Large systems may contain thousands of processes and resources.

Graphs become difficult to manage.

Multiple Resource Instances

Cycle analysis becomes insufficient.

Additional algorithms are needed.

Dynamic Systems

Frequent changes require graph updates.

High Complexity for Large Systems

Visual analysis becomes impractical.

18. Resource Allocation Graph vs Wait-For Graph

A Wait-For Graph (WFG) is a simplified form of RAG.

Example:

RAG:

P1 → R1 → P2

becomes:

P1 → P2

in a Wait-For Graph.

19. Resource Allocation Graph vs Banker’s Algorithm

20. Real-World Analogy

Imagine:

• Workers = Processes

• Tools = Resources

If:

Worker A waiting for Hammer

and

Hammer being used by Worker B

then:

A → Hammer → B

If every worker waits for another worker's tool:

A → B → C → A

nobody can continue.

This is exactly how deadlocks appear in a Resource Allocation Graph.