Wait-for Graph, Safe and Unsafe State

Introduction

Deadlock handling uses a few connected ideas to understand whether processes are blocked, safe, or at risk. A wait-for graph shows who is waiting for whom, while safe and unsafe states explain whether the system still has a guaranteed completion path.

These concepts are especially important before studying deadlock avoidance and Banker's Algorithm. The main goal is to check whether the system can still finish all processes without entering deadlock.

Wait-for Graph

A wait-for graph is a process-only graph used to represent blocking between processes. It removes resource nodes and directly shows which process is waiting for another process.

An edge Pi => Pj means process Pi is waiting for a resource currently held by process Pj. So instead of showing both the resource and its owner, the graph directly shows the dependency between processes.

For example, if P1 requests resource R1, and R1 is assigned to P2, the wait-for graph contains: P1 => P2

This means P1 cannot continue until P2 releases the resource that P1 needs.

Building a Wait-for Graph

A wait-for graph is usually derived from a Resource Allocation Graph. The detailed resource view is converted into a simpler process-to-process view.

The basic flow is:

Start with the Resource Allocation Graph: It contains process nodes, resource nodes, request edges, and assignment edges.
Remove resource nodes: The aim is to focus only on process dependencies.
Collapse the dependency: If Pi requests R, and R is assigned to Pj, replace that relation with Pi => Pj.

This simplification is useful when the main question is not which resource is involved, but whether processes are waiting on each other.

Wait-for Graph & Building it

Cycle in a Wait-for Graph

For single-instance resources, a directed cycle in a wait-for graph indicates deadlock. Every process inside the cycle is waiting for another process in the same cycle.

For example: P1 => P2 => P3 => P1

Here, P1 waits for P2, P2 waits for P3, and P3 waits for P1. Since the waiting chain returns to the starting process, no process in the cycle can move forward by itself.

Safe State and Safe Sequence

A system is in a safe state if all processes can finish in some order. That finishing order is called a safe sequence.

Safe does not mean that no process is waiting right now. A process may wait temporarily, but the system still has a guaranteed order in which every process can eventually receive resources, complete, and release its allocation.

Safe-State Numerical Check

Suppose the system has 12 total resource instances.

Process	Maximum Need	Current Allocation	Remaining Need
P0	10	5	5
P1	4	2	2
P2	9	2	7

Current allocation is 5 + 2 + 2 = 9, so Available = 12 - 9 = 3.

Now check whether all processes can finish:

Step	Work	Process That Can Finish	New Work After Release
Start	3	P1, because need 2 <= 3	3 + 2 = 5
Next	5	P0, because need 5 <= 5	5 + 5 = 10
Next	10	P2, because need 7 <= 10	10 + 2 = 12

All processes can finish, so the state is safe. One valid safe sequence is: P1 => P0 => P2

Safe-State Numerical

Unsafe State

A system is in an unsafe state when no guaranteed safe sequence exists. This does not always mean deadlock has already happened, but it means the system has lost the guarantee that every process can finish safely.

Using the same example, suppose one extra instance is granted to P2. Then the available resources reduce from 3 to 2.

Process	Current Allocation	Remaining Need
P0	5	5
P1	2	2
P2	3	6

Now Work = 2. P1 can finish because its need is 2, so after P1 releases its allocation, Work = 2 + 2 = 4.

At this point, P0 needs 5, and P2 needs 6. Since neither can finish with Work = 4, no safe sequence exists. The state is unsafe.

Unsafe State vs Deadlocked State

Unsafe state and deadlock are related, but they are not the same. An unsafe state is a warning condition, while a deadlocked state means processes are already stuck.

Every safe state is deadlock-free. An unsafe state may lead to deadlock, but it does not prove that deadlock has already occurred.

This distinction matters in deadlock avoidance. The system may delay a request even when resources are currently available because granting it could move the system into an unsafe state.

Summary

A wait-for graph shows process-to-process blocking. An edge Pi => Pj means Pi is waiting for a resource held by Pj, and a directed cycle in a wait-for graph indicates deadlock for single-instance resources.

A safe state has at least one safe sequence, while an unsafe state has no guaranteed completion order. Unsafe does not always mean deadlocked, but deadlock avoidance uses safe-state checking to prevent the system from entering risky allocations.