What Is a Resource-Allocation Graph?
Learn the resource-allocation graph — request/assignment edges, cycles, and deadlock detection — with an OS interview question and code.
Expected Interview Answer
A resource-allocation graph is a directed graph model used to represent which processes hold which resources and which processes are waiting for which resources, where a request edge points from a process to a resource and an assignment edge points from a resource to a process, and it is the standard visual and algorithmic tool for reasoning about deadlock.
Each process and each resource type is a node; a request edge (process to resource) means the process is waiting for an instance of that resource, and an assignment edge (resource to process) means an instance is currently held by that process. For resource types with only a single instance, a cycle in this graph is both necessary and sufficient for deadlock. For resource types with multiple instances, a cycle is necessary but not sufficient — the cycle only guarantees deadlock if it cannot be broken by another process outside the cycle releasing a resource, so the graph must be reduced (removing processes whose requests can be fully satisfied) to confirm deadlock, similar in spirit to the Banker’s Algorithm’s safety check. Simplifying the multi-instance graph into a plain process-to-process wait-for graph (by contracting resource nodes) is the basis of deadlock detection algorithms, and the graph is also the mental model behind explaining the four necessary conditions for deadlock: mutual exclusion, hold-and-wait, no preemption, and circular wait.
- Gives a precise, visual model for reasoning about resource contention
- A cycle test provides an exact deadlock check for single-instance resource types
- Generalizes to a reduction algorithm for multi-instance resource types
- Underpins both deadlock detection algorithms and teaching the four necessary conditions
AI Mentor Explanation
A resource-allocation graph is like a whiteboard in the ground office with an arrow from a team to a net meaning “waiting for this net” and an arrow from a net to a team meaning “currently holding this net.” If Team A’s arrow points to a net held by Team B, and Team B’s arrow points to equipment held by Team A, the loop drawn on the board is a visible cycle. With only one net per type, that loop always means a real standoff; with multiple identical nets available, the loop only proves a standoff once nobody outside the loop can free one up.
Step-by-Step Explanation
Step 1
Model nodes
Represent each process and each resource type as a node in a directed graph.
Step 2
Draw edges
Add a request edge (process to resource) for waiting processes and an assignment edge (resource to process) for held instances.
Step 3
Search for a cycle
Trace the graph for a closed loop of requests and assignments among processes and resources.
Step 4
Interpret the cycle
For single-instance resources, a cycle means deadlock; for multi-instance resources, reduce the graph to confirm whether the cycle is unbreakable.
What Interviewer Expects
- Correct definition of request edges vs assignment edges
- Knowing that a cycle is necessary and sufficient for deadlock only in the single-instance case
- Ability to explain graph reduction for the multi-instance case
- Connecting the graph model to the four necessary conditions for deadlock
Common Mistakes
- Claiming a cycle always means deadlock regardless of how many instances a resource has
- Confusing request edges and assignment edges (mixing up direction)
- Not knowing the graph reduces to a wait-for graph for detection algorithms
- Thinking the resource-allocation graph is only a diagram with no algorithmic use
Best Answer (HR Friendly)
“A resource-allocation graph is a simple diagram the OS can use to track which processes are holding which resources and which are waiting for which. It draws an arrow from a waiting process to the resource it wants, and an arrow from a held resource back to the process holding it, and if you can trace a closed loop through those arrows, that is a strong signal of deadlock — a certain one when each resource has just a single copy, and something that needs a bit more checking when there are multiple identical copies available.”
Code Example
#define P 6 /* processes */
#define R 4 /* resource types, single instance each */
/* request[p][r] = 1 => process p requests resource r
assigned[r][p] = 1 => resource r is currently assigned to process p */
int request[P][R];
int assigned[R][P];
/* Collapse the bipartite graph into a process-only wait-for graph:
p waits for q if p requests a resource that q currently holds. */
void build_wait_for(int wait_for[P][P]) {
for (int p = 0; p < P; p++) {
for (int q = 0; q < P; q++) wait_for[p][q] = 0;
}
for (int p = 0; p < P; p++) {
for (int r = 0; r < R; r++) {
if (!request[p][r]) continue;
for (int q = 0; q < P; q++) {
if (assigned[r][q]) wait_for[p][q] = 1;
}
}
}
}Follow-up Questions
- Why is a cycle sufficient for deadlock only when each resource type has one instance?
- How do you reduce a multi-instance resource-allocation graph to check for real deadlock?
- How does the resource-allocation graph relate to the wait-for graph used in detection?
- How does the resource-allocation graph illustrate the four necessary conditions for deadlock?
MCQ Practice
1. In a resource-allocation graph, an edge from a process to a resource represents?
A request edge points from process to resource, indicating the process is waiting for an instance of it.
2. For single-instance resource types, what does a cycle in the graph indicate?
With only one instance per resource type, a cycle is both necessary and sufficient proof of deadlock.
3. For multi-instance resource types, a cycle in the graph is?
A cycle can exist without deadlock if a process outside the cycle can release a resource that breaks it, so reduction is needed to confirm.
Flash Cards
What is a resource-allocation graph? — A directed graph of processes and resources showing request and assignment edges, used to reason about deadlock.
What does a request edge mean? — The process is waiting for an instance of that resource.
When is a cycle sufficient for deadlock? — Only when every resource type in the cycle has a single instance.
How is the multi-instance case checked? — By reducing the graph, similarly to the Banker’s Algorithm’s safety check.