DEADLOCK USING GRAPH
Deadlock:
Deadlock is situation where two or more processes are unable to
proceed
Deadlock resources allocation :
Resources allocation refers how the system is allocated the
memory to processes .
Condition:
1. Mutual exclusion : A resources can be used for one process at a
time not for more than one processes simultaneously.
2. Hold and wait : A process holding atleast a resource and wait for
the another resource which other process holds the resources.
3. No preemption : resources cannot be forcibly taken from the
process,must be released voluntarily.
4. Circular wait : A set of process waiting for a resource in circular
link which all process wants all resources .
Components:
1. Process Nodes – Represent active processes in the system,
depicted as circles in a Resource Allocation Graph.
2. Resource Nodes – Represent available resources, shown as
squares, with multiple instances represented by multiple dots
inside.
3. Request Edge (P → R) – A directed edge from a process to a
resource indicates the process is requesting that resource.
4. Assignment Edge (R → P) – A directed edge from a resource to a
process means the resource is allocated to that process.
Deadlocks can be handled using four main strategies:
1. Deadlock Prevention – Designing the system to ensure that at
least one of the four necessary conditions (Mutual Exclusion, Hold
and Wait, No Preemption, Circular Wait) never holds.
2. Deadlock Detection – Allowing deadlocks to occur but using
detection algorithms (like the Wait-for Graph) to identify them.
Recovery method :
1. Process Termination – Killing one or more processes involved in
the deadlock to free resources.
Abort all deadlocked processes (drastic but
guarantees resolution).
Abort one process at a time until the deadlock is
resolved (minimizes disruption).
2. Resource Preemption – Temporarily taking resources from some
processes and reallocating them to break the deadlock.Selecting
a victim (choosing which process loses its resources based on
priority, execution time, etc.).Rollback (returning the process to a
safe state before the deadlock).Starvation Handling (ensuring a
process is not indefinitely preempted).
Step by step process:
1. Construct Allocation & Request Matrix – Create a table
representing allocated and requested resources, then draw the
Resource Allocation Graph (RAG).
2. Check RAG Conditions – Analyze the graph for resource
requests, allocations, and potential circular wait conditions.
3. Detect Deadlock – Identify cycles in the graph, as a cycle
confirms the presence of deadlock.
4. Resolve Deadlock – Break the cycle by terminating processes or
preempting resources to restore system functionality.
1.Construct the Allocation and Request Matrix
The given example consists of three processes (P1, P2, P3) and
two resources (R1, R2).
The allocation matrix represents which resources are currently
held by each process.
The request matrix shows which resources each process is waiting
for.
2. Construct the Resource Allocation Graph (RAG)
P1 is waiting for R2, which is held by P2.
P2 is waiting for R1, which is held by P1.
P3 holds R2 but does not explicitly wait for any resource.
The available resources in the system are (0,0), meaning no free
resources exist.
3. Detect Deadlock Using RAG
A cycle is detected in the graph: P1 → R2 → P2 → R1 → P1.
This means P1 is waiting for R2 (held by P2), and P2 is waiting for
R1 (held by P1).
Since a cycle is a necessary condition for deadlock, the system is
in a deadlock state.
4. Resolve the Deadlock
The deadlock can be resolved using one of the following methods:
1. Process Termination – Terminate P1 or P2 to break the cycle.
2. Resource Preemption – Temporarily take R1 or R2 from one
process and assign it to another.
3. Rollback – Revert the processes to a previous safe state.
