Short Notes: Process Management - Deadlock | Short Notes for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

 Page 1


In a multi-programming environment, a situation when permanent blocking of a set 
of processes that either compete for system resources or communicate with each 
other happens, we can call this as deadlock situation. This deadlock problem 
involves conflicting needs for resources by two or more processes. Necessary 
Conditions for Deadlock: A deadlock situation can arise, if the following four 
conditions hold simultaneously in a system. •
• Mutual Exclusion: Resources must be allocated to processes at any time in an 
exclusive manner and not on a shared basis for a deadlock to be possible. If 
another process requests that resource, the requesting process must be 
delayed until the resource has been released.
• Hold and Wait Condition: Even if a process holds certain resources at any 
moment, it should be possible for it to request for new ones. It should not give 
up (release) the already held resources to be able to request for new ones. If it 
is not true, a deadlock can never take place.
• No Preemption Condition: Resources can't be preempted. A resource can be 
released only voluntarily by the process holding it, after that process has 
completed its task.
• Circular Wait Condition: There must exist a set = {P0, Pi, P2 . ..., Pn) of waiting 
processes such that Po is waiting for a resource that is held by Pi, Pi is 
waiting for a resource that is held by P2 , ..., Pn -1 is waiting for a resource that 
is held by Pn and Pn is waiting for a resource that is held by Pq .
Page 2


In a multi-programming environment, a situation when permanent blocking of a set 
of processes that either compete for system resources or communicate with each 
other happens, we can call this as deadlock situation. This deadlock problem 
involves conflicting needs for resources by two or more processes. Necessary 
Conditions for Deadlock: A deadlock situation can arise, if the following four 
conditions hold simultaneously in a system. •
• Mutual Exclusion: Resources must be allocated to processes at any time in an 
exclusive manner and not on a shared basis for a deadlock to be possible. If 
another process requests that resource, the requesting process must be 
delayed until the resource has been released.
• Hold and Wait Condition: Even if a process holds certain resources at any 
moment, it should be possible for it to request for new ones. It should not give 
up (release) the already held resources to be able to request for new ones. If it 
is not true, a deadlock can never take place.
• No Preemption Condition: Resources can't be preempted. A resource can be 
released only voluntarily by the process holding it, after that process has 
completed its task.
• Circular Wait Condition: There must exist a set = {P0, Pi, P2 . ..., Pn) of waiting 
processes such that Po is waiting for a resource that is held by Pi, Pi is 
waiting for a resource that is held by P2 , ..., Pn -1 is waiting for a resource that 
is held by Pn and Pn is waiting for a resource that is held by Pq .
State diagram of circular wait condition
Resource Allocation Graph: The resource allocation graph consists of a set of 
vertices V and a set of edges E . Set of vertices V is partitioned into two types
1. P = {P|, P2 , ... ,Pn }, the set consisting of all the processes in the system.
2. R = {R|, R 2 , ..., Rm }, the set consisting of all resource types in the system.
• Directed Edge Pi -? Pj is known as request edge.
• Directed Edge Pj -» Pj is known as assignment edge.
Resource Instance
• One instance of resource type Ri.
• Two instances of resource type R 2.
• One instance of resource type R3.
• Three instances of resource type R 4
Example of resource allocation graph 
Process States
• Process Pi is holding an instance of resource type R 2 and is waiting for an 
instance of resource type R |.
• Process P2 is holding an instance of Ri and R 2 is waiting for an instance of 
resource type R 3.
• Process P3 is holding an instance of R3.
• Basic facts related to resource allocation graphs are given below
Note: If graph consists no cycle it means there is no deadlock in the system. If 
graph contains cycle
1. If only one instance per resource type, then deadlock.
2. If several instances per resource type, then there mayor may not be deadlock.
Deadlock Handling Strategies In general, there are four strategies of dealing with 
deadlock problem:
1. The Ostrich Approach: Just ignore the deadlock problem altogether.
Page 3


In a multi-programming environment, a situation when permanent blocking of a set 
of processes that either compete for system resources or communicate with each 
other happens, we can call this as deadlock situation. This deadlock problem 
involves conflicting needs for resources by two or more processes. Necessary 
Conditions for Deadlock: A deadlock situation can arise, if the following four 
conditions hold simultaneously in a system. •
• Mutual Exclusion: Resources must be allocated to processes at any time in an 
exclusive manner and not on a shared basis for a deadlock to be possible. If 
another process requests that resource, the requesting process must be 
delayed until the resource has been released.
• Hold and Wait Condition: Even if a process holds certain resources at any 
moment, it should be possible for it to request for new ones. It should not give 
up (release) the already held resources to be able to request for new ones. If it 
is not true, a deadlock can never take place.
• No Preemption Condition: Resources can't be preempted. A resource can be 
released only voluntarily by the process holding it, after that process has 
completed its task.
• Circular Wait Condition: There must exist a set = {P0, Pi, P2 . ..., Pn) of waiting 
processes such that Po is waiting for a resource that is held by Pi, Pi is 
waiting for a resource that is held by P2 , ..., Pn -1 is waiting for a resource that 
is held by Pn and Pn is waiting for a resource that is held by Pq .
State diagram of circular wait condition
Resource Allocation Graph: The resource allocation graph consists of a set of 
vertices V and a set of edges E . Set of vertices V is partitioned into two types
1. P = {P|, P2 , ... ,Pn }, the set consisting of all the processes in the system.
2. R = {R|, R 2 , ..., Rm }, the set consisting of all resource types in the system.
• Directed Edge Pi -? Pj is known as request edge.
• Directed Edge Pj -» Pj is known as assignment edge.
Resource Instance
• One instance of resource type Ri.
• Two instances of resource type R 2.
• One instance of resource type R3.
• Three instances of resource type R 4
Example of resource allocation graph 
Process States
• Process Pi is holding an instance of resource type R 2 and is waiting for an 
instance of resource type R |.
• Process P2 is holding an instance of Ri and R 2 is waiting for an instance of 
resource type R 3.
• Process P3 is holding an instance of R3.
• Basic facts related to resource allocation graphs are given below
Note: If graph consists no cycle it means there is no deadlock in the system. If 
graph contains cycle
1. If only one instance per resource type, then deadlock.
2. If several instances per resource type, then there mayor may not be deadlock.
Deadlock Handling Strategies In general, there are four strategies of dealing with 
deadlock problem:
1. The Ostrich Approach: Just ignore the deadlock problem altogether.
2. Deadlock Detection and Recovery: Detect deadlock and, when it occurs, take 
steps to recover.
3. Deadlock Avoidance: Avoid deadlock by careful resource scheduling.
4. Deadlock Prevention: Prevent deadlock by resource scheduling so as to 
negate at least one of the four conditions.
Deadlock Prevention Deadlock prevention Is a set of methods for ensuring that 
atleast one of the necessary conditions can't hold.
• Elimination of "Mutual Exclusion" Condition
• Elimination of "Hold and Wait" Condition
• Elimination of "No-preemption" Condition
• Elimination of "Circular Wait" Condition
Deadlock Avoidance This approach to the deadlock problem anticipates deadlock 
before it actually occurs. A deadlock avoidance algorithm dynamically examines 
the resource allocation state to ensure that a circular wait condition can never 
exist. The resource allocation state is defined by the number of available and 
allocated resources and the maximum demands of the processes. Safe State: A 
state is safe, if the system can allocate resources to each process and still avoid a 
deadlock.
Safe, unsafe and deadlock
A system is in safe state, if there exists a safe sequence of all processes. A 
deadlock state is an unsafe state. Not all unsafe states cause deadlocks. It is 
important to note that an unsafe state does not imply the existence or even the 
eventual existence a deadlock. What an unsafe state does imply is simply that 
some unfortunate sequence of events might lead to a deadlock. Banker's 
Algorithm: Data structures for Banker's algorithm available. Vector of length m. If 
available 0 1 = k, there are k instances of resource type R j available. •
• Max n x m matrix. If max [i, j] = k, then process Pi may request at most k 
instances of resource type Rj.
• Allocation n x m matrix. If allocation [i, j] = k, then P | is currently allocated k 
instances of Rj.
• Need n x m matrix. If need [i, j] = k, then P | may need k more instances of R j to 
complete its task.
Need [i, j] = max [i, j] - allocation [i, j]
• Safety Algorithm
Step 1 Let work and finish be vectors of length m and n, respectively. Initialize
Work = Available
Page 4


In a multi-programming environment, a situation when permanent blocking of a set 
of processes that either compete for system resources or communicate with each 
other happens, we can call this as deadlock situation. This deadlock problem 
involves conflicting needs for resources by two or more processes. Necessary 
Conditions for Deadlock: A deadlock situation can arise, if the following four 
conditions hold simultaneously in a system. •
• Mutual Exclusion: Resources must be allocated to processes at any time in an 
exclusive manner and not on a shared basis for a deadlock to be possible. If 
another process requests that resource, the requesting process must be 
delayed until the resource has been released.
• Hold and Wait Condition: Even if a process holds certain resources at any 
moment, it should be possible for it to request for new ones. It should not give 
up (release) the already held resources to be able to request for new ones. If it 
is not true, a deadlock can never take place.
• No Preemption Condition: Resources can't be preempted. A resource can be 
released only voluntarily by the process holding it, after that process has 
completed its task.
• Circular Wait Condition: There must exist a set = {P0, Pi, P2 . ..., Pn) of waiting 
processes such that Po is waiting for a resource that is held by Pi, Pi is 
waiting for a resource that is held by P2 , ..., Pn -1 is waiting for a resource that 
is held by Pn and Pn is waiting for a resource that is held by Pq .
State diagram of circular wait condition
Resource Allocation Graph: The resource allocation graph consists of a set of 
vertices V and a set of edges E . Set of vertices V is partitioned into two types
1. P = {P|, P2 , ... ,Pn }, the set consisting of all the processes in the system.
2. R = {R|, R 2 , ..., Rm }, the set consisting of all resource types in the system.
• Directed Edge Pi -? Pj is known as request edge.
• Directed Edge Pj -» Pj is known as assignment edge.
Resource Instance
• One instance of resource type Ri.
• Two instances of resource type R 2.
• One instance of resource type R3.
• Three instances of resource type R 4
Example of resource allocation graph 
Process States
• Process Pi is holding an instance of resource type R 2 and is waiting for an 
instance of resource type R |.
• Process P2 is holding an instance of Ri and R 2 is waiting for an instance of 
resource type R 3.
• Process P3 is holding an instance of R3.
• Basic facts related to resource allocation graphs are given below
Note: If graph consists no cycle it means there is no deadlock in the system. If 
graph contains cycle
1. If only one instance per resource type, then deadlock.
2. If several instances per resource type, then there mayor may not be deadlock.
Deadlock Handling Strategies In general, there are four strategies of dealing with 
deadlock problem:
1. The Ostrich Approach: Just ignore the deadlock problem altogether.
2. Deadlock Detection and Recovery: Detect deadlock and, when it occurs, take 
steps to recover.
3. Deadlock Avoidance: Avoid deadlock by careful resource scheduling.
4. Deadlock Prevention: Prevent deadlock by resource scheduling so as to 
negate at least one of the four conditions.
Deadlock Prevention Deadlock prevention Is a set of methods for ensuring that 
atleast one of the necessary conditions can't hold.
• Elimination of "Mutual Exclusion" Condition
• Elimination of "Hold and Wait" Condition
• Elimination of "No-preemption" Condition
• Elimination of "Circular Wait" Condition
Deadlock Avoidance This approach to the deadlock problem anticipates deadlock 
before it actually occurs. A deadlock avoidance algorithm dynamically examines 
the resource allocation state to ensure that a circular wait condition can never 
exist. The resource allocation state is defined by the number of available and 
allocated resources and the maximum demands of the processes. Safe State: A 
state is safe, if the system can allocate resources to each process and still avoid a 
deadlock.
Safe, unsafe and deadlock
A system is in safe state, if there exists a safe sequence of all processes. A 
deadlock state is an unsafe state. Not all unsafe states cause deadlocks. It is 
important to note that an unsafe state does not imply the existence or even the 
eventual existence a deadlock. What an unsafe state does imply is simply that 
some unfortunate sequence of events might lead to a deadlock. Banker's 
Algorithm: Data structures for Banker's algorithm available. Vector of length m. If 
available 0 1 = k, there are k instances of resource type R j available. •
• Max n x m matrix. If max [i, j] = k, then process Pi may request at most k 
instances of resource type Rj.
• Allocation n x m matrix. If allocation [i, j] = k, then P | is currently allocated k 
instances of Rj.
• Need n x m matrix. If need [i, j] = k, then P | may need k more instances of R j to 
complete its task.
Need [i, j] = max [i, j] - allocation [i, j]
• Safety Algorithm
Step 1 Let work and finish be vectors of length m and n, respectively. Initialize
Work = Available
Finish [i] = False (for i = 1, 2 , ; n)
Step 2 Find i such that both
1. Finish [i] = False
2. Need<= Work
If no such i exists, go to step 4.
Step 3 Work = Work + Allocation Finish [i] = True Go to step 2. Step 4 Finish [i] = 
True (for all i) Then, the system is in a safe system
Deadlock Detection
Allow system to enter deadlock state and then there is (i) Detection algorithm (ii) 
Recovery scheme Single instance of each resource type
1. Maintain wait for graph.
2. Nodes are processes.
3. Pi -? Pj if Pi is waiting P j
4. Periodically invoke an algorithm that searches for a cycle in the graph.
5. An algorithm to detect a cycle in a graph requires an order of n2 operations, 
where n is the number of vertices in the graph. •
Example of resource allocation graph 
Recovery Scheme
• Temporarily prevent resources from deadlocked processes.
• Back off a process to some check point allowing preemption of a needed 
resource and restarting the process at the checkpoint later.
• Successively kill processes until the system is deadlock free.