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

Resource Allocation Graphs

Visual representation of processes, resources, and allocation/request relationships using directed graphs.

Resource Allocation Graphs

You'll learn how to visualize deadlock situations using directed graphs that show which processes hold or request which resources.

What Is a Resource Allocation Graph?

A Resource Allocation Graph (RAG) is a visual tool that helps us understand and detect deadlock conditions in a system. It's a directed graph where nodes represent either processes or resources, and edges show the relationships between them.

Think of it like a diagram showing who's holding what and who's waiting for what — similar to mapping out a group of people where some have keys to rooms, and others are waiting outside those rooms.

Graph Components

The graph contains two types of nodes:

  • Process nodes (circles): Represent active processes in the system
  • Resource nodes (rectangles): Represent resource types, with dots inside showing how many instances exist

Graph Edges

There are two types of directed edges:

  • Request edge: An arrow from a process to a resource means that process is requesting that resource (process → resource)
  • Assignment edge: An arrow from a resource to a process means that resource is currently allocated to that process (resource → process)

Reading the Graph

When you look at a RAG, you can quickly identify potential problems. If you see a cycle in the graph (a path that loops back to its starting point), you may have found a deadlock — especially if each resource in the cycle has only one instance.

For example: Process P1 holds Resource R1 and requests R2, while Process P2 holds R2 and requests R1. This creates a cycle, indicating both processes are stuck waiting for each other.

Key Takeaway: Resource Allocation Graphs provide a clear visual representation of process-resource relationships, making it easier to spot potential deadlocks by identifying cycles in the graph.