UNIT4 3
UNIT
Deadlock
A deadlock is a situation where a process or a set of processes is blocked, waiting for some
resource that is held by some other waiting processes
Eg:P1 and P2 are 2 processes, R1 and R2 are 2 resources. P1 requests resource R1, R1 is held by Process
P2. P2 requests resource R2, R2 is held by Process P1.P1 & P2 are in waiting state and no work process.
If there are multiple resources of the same type, each is called an instance of that resource type
System Model
Let the resource types be R1, R2,… Rn like CPU cycles, memory space, I/O devices, etc. Each
resource type Ri has Wi instances. Each process utilizes a resource as follows:
i. Request
A process requests the OS for assignment of the needed resource. The process waits till OS
assigns it an instance of the requested resource
ii. Assignment
The OS assigns the requesting resource an instance of the requested resource when it is available.
The process comes out of its waiting state
iii. Use
The process will use the assigned resource. In case, the resource is non-sharable process , the
process will have exclusive access to it.
iv. Release
After the process finished with the use of assigned resource, it will return the resource to the
system pool. A set of processes is in a deadlock state when every process in the set is waiting for an event
that can be caused by only another process in the set
Resource Allocation Graph
A RAG is a directed graph used to represent the deadlocks. The graph has 2 nodes, one for
process represented by circle and other for resources represented by square. If there are more instances of
a Resource type, it is denoted by dots. It has 2 types of edges. One is requesting edge and another one is
assignment edge. An edge from process to resource is said to be a requesting edge and an edge a resource
to a process is said to be an assignment edge. If RAG has cycles, then the system may or may not in dead
lock. If the system is in dead lock state, the RAG must consist of cycles
J. Paul Rajasingh, Assistant Professor / CSE, SRM Institute of Science & Technology, Tiruchirappalli Campus
For Internal Circulation Only
In the above Resource Allocation Graph,
Process to Resource: Requesting Edge
Resource to Process: Assignment Edge
If RAG consists of cycles, then the system may or may not contain deadlock. If the system is in deadlock
state, RAG must contain cycle(s)
Deadlock Characteristics - Necessary Conditions for Deadlock
1. Mutual Exclusion 2.Hold- and –Wait 3.No Preemption 4.Circular wait
These 4 conditions must be held simultaneously for a deadlock to occur
1. Mutual Exclusion
• It means resources are in non-sharable mode only and only one process at a time can use a
resource
• If some other process requests that resource, the requesting process must wait until the resources
has been released
Eg: Line Printers
Line printers are always in non – sharable mode only and only one process can use the resource at
a time. Any other process requesting for that resource has to wait for the user process to release it
2. Hold and Wait
A process is holding a resource allocated to it, and waiting to acquire another resource held by
some other processes. Some processes must be holding some resources in a non – sharable mode and at
the same time, they must be waiting to acquire some more resources, which are currently held by other
processses in a non-sharable mode
Eg: P1, P2, P3 – 3 processes, R1,R2,R3 and R4. Each holds a resource and waits for another resource
Hold and Wait
3. No Preemption
Resource allocated to a process cant be forcibly revoked by the system. It can be only released
voluntarily by the process holding it. It means that resources are not released in the middle of the work.
They are released only after the process has completed its task
4. Circular Wait
Deadlocked processes are involved in a circular chain such that each process holds one or more
resources being requested by the next process in that chain
Deadlock Detection
1. Resource Allocation Graph
A RAG is a directed graph used to represent the deadlocks. The graph has 2 nodes, one for
process represented by circle and other for resources represented by square. If there are more instances of
a Resource type, it is denoted by dots. It has 2 types of edges. One is requesting edge and another one is
assignment edge. An edge from process to resource is said to be a requesting edge and an edge a resource
to a process is said to be an assignment edge
If RAG has cycles, then the system may or may not in dead lock. If the system is in dead lock
state, the RAG must consist of cycles
Deadlock Prevention
Deadlock can be prevented by not allowing all 4 conditions to be satisfied simultaneously:
1.Eliminating Mutual Exclusion
2. Eliminating Hold- and –Wait
3. Eliminating No Preemption
4. Eliminating Circular wait
1. Eliminating Mutual Exclusion
• Mutual Exclusion means only one process at a time can use a resource
• It means the resources are not shared by the number of processes at a time
• We can deny this condition by a simple protocol “Convert all non sharable resources to sharable
resources”
2. Eliminating Hold- and –Wait
o It means each and every process must hold atleast one resource and waiting for atleast one
resource
o We can deny this condition with a protocol “ A process request the resources only when the
process has none
3. Eliminating No Preemption
It means the resources are not released in the middle of the processing of a resource
Protocol:
A process requests some resources. We first check whether they are available. If they are
available, we allocate them. If they are not available, we check whether they are allocated to some other
process that is waiting for additional resources
If so, we preempt the desired resources from the waiting process and allocate them to the
requesting process
If the resources are not either available or held by a waiting process, then requesting process must
wait. While it is waiting, some of its resources may be used by other process
4. Eliminating Circular wait
This is an easiest condition to violate. A cycle can be prevented by bringing an order in the
resources types, and assigning an ascending number of resource ids to the various resources available to
the OS
Resource ids
The OS can put a restriction that a process can ask for a resource whose resource id > than the
resource ids of the resource already held by the process.
Eg
A process with id =3 can ask for a resource with id >3
Deadlock Avoidance
It is a method of dynamically escaping from the deadlocks. If a process requests for resources, the
avoidance a algorithm checks the state of the system. If the state is safe, the system will allocate the
resources; otherwise it wont allocate,
Safe state
No dead lock will happen, even we allocate the resources to requesting processes
Unsafe state
In unsafe state, deadlock may happen
Safe, Unsafe, Deadlock State
A safe state is not a dead lock state. Conversely, a deadlock state is an unsafe state. Not all unsafe states
are dead locks. But an unsafe state may lead to a deadlock
Avoidance Algorithms
For Single instance of a resource type, use a resource-allocation graph. For Multiple instances of
a resource type, use the banker’s algorithm
Resource-Allocation Graph(RAG) algorithm – One Instance
Claim edge Pi Rj indicated that process Pj may request resource Rj at some time in future and
represented by a dashed line
Claim edge is converted to request edge when a process requests a resource
Request edge converted to an assignment edge when the resource is allocated to the process
When a resource is released by a process, assignment edge is reconverted to a claim edge
Resources must be claimed a priori in the system. ie, Before ap process starts executed, all its
clam edges must appear in RAG
RAG
Unsafe State In Resource-Allocation Graph
RAG
Suppose that process Pi requests a resource Rj
The request can be granted only if converting the request edge to an assignment edge does not
result in the formation of a cycle in the resource allocation graph
Banker’s Algorithm – Multiple instances
• This is applicable to a resource allocation system with multiple instances of each resource type
• The name was chosen as this algorithm could be used in a banking system to ensure that the bank
never allocates its available cash such that it can no longer satisfy the needs of all its customers
• When a new process enters the system, it has to declare the max no of instances of each resource
type that it may need
• This number should be less than the total no of resources in the system
• When a process requests a set of resources, the system must determine whether the allocation of
these resources will leave the system in a safe state
Let n = number of processes, and m = number of resources types.
Available: A Vector of length m indicates the number of available resources of each type
If available [j] = k, there are k instances of resource type Rj available
Max: n x m matrix defines the maximum demand of each process
If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj
Allocation: A n x m matrix defines the number of resources of each type currently allocated to
each process . If Allocation[i,j] = k then Pi is currently allocated k instances of Rj
Need: A n x m matrix indicates the remaining need of each process. If Need[i,j] = k, then Pi may
need k more instances of Rj to complete its task
Need [i,j] = Max[i,j] – Allocation [i,j]
Safety Algorithm
1. Let Work and Finish be vectors of length m and n, respectively. Initialize:
Work = Available
Finish [i] = false for i = 0, 1, …, n- 1
2.Find an i such that both:
(a) Finish [i] = false
(b) Needi Work
If no such i exists, go to step 4
3. Work = Work + Allocationi
Finish[i] = true
go to step 2
4. If Finish [i] == true for all i, then the system is in a safe state
Resource-Request Algorithm for Process Pi
Let Requesti be a request vector for process Pi. If Requesti [j] = k then process Pi wants k instances of
resource type Rj .
When a request for resources is made by the process, Pi, the following actions are taken:
1. If Requesti Needi go to step 2. Otherwise, raise error condition, since process has exceeded its
maximum claim
2. If Requesti Available, go to step 3. Otherwise Pi must wait, since resources are not available
3. Pretend to allocate requested resources to Pi by modifying the state as follows:
Available = Available – Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;
If the resource allocation is safe , the resources are allocated to Pi
If the resource allocation unsafe, Pi must wait, and the old resource-allocation state is restored
Recovery from Deadlock
There are 2 methods to break a deadlock.
A. To abort one by one processes to break the circular wait
B. To preempt some resources from one or more of the deadlocked process
A. Process Termination
i. Abort all deadlocked processes
This will ensure that the system recovers from a deadlock.
Drawback:
Many processes may have executed for a long time and may be close to completion. Terminating
them now will mean discarding all computations performed so far
ii. Abort one by one process until the deadlock cycle is eliminated
Here, one of the processes in the deadlocked state is aborted first and the resources are allocated
to some other process in the deadlocked state.
Steps:
Check whether the deadlocked state is broken or not.
If not, another process gets aborted from the deadlocked state.
This process is continued until the deadlock is recovered
2. Resource Preemption
It means preemptimg the resources from the processes one by one and allocate them to other
processes until the circular- wait condition is eliminated
Steps
A. Selecting a victim
The choice of resources and processes must be such that they incur minimum cost to the system
B. Roll back of the process
After preempting the resources, the corresponding process must be rolled back properly, so that it
does not leave the system in an inconsistent state
C. Preventing starvation
If the selection of a process is based on the cost factor, there is a possibility that the same process
can be selected repeatedly for the rollback, leading to a situation of starvation
This can be mitigated by including the number of rollbacks of a given process in the cost factor
Problems
1. Consider a system with 5 process P1 to P5 and 3 resources R1, R2 and R3.
Given:
Resources type R1 has 10 instances. Resources type R2 has 5 instances. Resources type R3 has 7
instances. Suppose that at a time to, the following snapshot of the system has been taken:
Process Allocation Max
R1 R2 R3 R1 R2 R3
P1 0 1 0 7 5 3
P2 2 0 0 3 2 2
P3 3 0 2 9 0 2
P4 2 1 1 2 2 2
P5 0 0 2 4 3 3
1. Calculate the available matrix of resources. Find the need matrix. Find the safe sequence.
2. If P2 requests one additional request of (1,0,2), can it be granted access? What is the new content
of matrix need? Find the safe sequence
Solution:
1.The available matrix is calculated as
Available = Total – Allocation
R1= 10-(2+3+2) =3
R2 = 5-(1+1) = 3
R3= 7-(2+1+2)=2
The available matrix is (3,3,2)
Need =Max – Allocation
Process R1 R2 R3
P1 7-0 5-1 3-0
P2 3-2 2-0 2-0
P3 9-3 0-0 2-2
P4 2-2 2-1 2-1
P5 4-0 3-0 3-2
Need Matrix
Process R1 R2 R3
P1 7 4 3
P2 1 2 2
P3 6 0 0
P4 0 1 1
P5 4 3 1
Applying Banker’s algorithm:
Search the need matrix from P1 to P5 which is less than the available matrix.,i.e.,(3,3,2)
We find that (1,2,2) < (3,3,2). So, allocate the requesting resource to P2.
P2’s allocation:
(2,0,0)+(1,2,2) =(3,2,2)
After the completion of job P2, it releases the total resources. Then the available resource is
(3,3,2) + (2,0,0)= (5,3,2)
We search the need matrix again, which is less than the available. Now we find that
(0,1,1) < (5,3,2)
So, resources are allocated to P4.
After P4 completes, it releases all its resources.
Then Available = Available + Allocation
= (5,3,2) + (2,1,1)
= (7,4,3)
We search the need matrix again, which is less than the available. Now we find that
(4,3,1) < (7,4,3)
So, resources are allocated to P5.
After P5 completes, it releases all its resources.
Then Available = Available + Allocation
= (7,4,3) + (0,0,2)
= (7,4,5)
We search the need matrix again, which is less than the available. Now we find that
(6,0,0) < (7,4,5)
So, resources are allocated to P3.
After P3 completes, it releases all its resources.
Then Available = Available + Allocation
= (7,4,5) + (3,0,2)
= (10,4,7)
We search the need matrix again, which is less than the available. Now we find that
(10,4,7) < (7,4,3)
So, resources are allocated to P1.
After P1 completes, it releases all its resources.
Then Available = Available + Allocation
= (10,4,7) + (0,1,0)
= (10,5,7)
Safe Sequence <P2,P4,P5,P3,P1>
2. If a process p2 makes a request(1,0,2):
The available matrix is calculated as
Available = Total – Allocation
R1= 10-(3+3+2) =2
R2 = 5-(1+1) = 3
R3= 7-(2+2+1+2)=0
The available matrix is (2,3,0)
New allocation
Process Allocation Max Available Need
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 0 1 0 7 5 3 2 3 0 7 4 3
P2 3 0 2 3 2 2 0 2 0
P3 3 0 2 9 0 2 6 0 0
P4 2 1 1 2 2 2 0 1 1
P5 0 0 2 4 3 3 4 3 1
Applying Banker’s algorithm:
Search the need matrix from P1 to P5 which is less than the available matrix.,i.e.,(2,3,0)
We find that (0,2,0) < (2,3,0). So, allocate the requesting resource to P2.
After the completion of job P2, it releases the total resources. Then the available resource is
(2,3,0) + (3,0,2)= (5,3,2)
We search the need matrix again, which is less than the available. Now we find that
(0,1,1) < (5,3,2)
So, resources are allocated to P4.
After P4 completes, it releases all its resources.
Then Available = Available + Allocation
= (5,3,2) + (2,1,1)
= (7,4,3)
We search the need matrix again, which is less than the available. Now we find that
(4,3,1) < (7,4,3)
So, resources are allocated to P5.
After P5 completes, it releases all its resources.
Then Available = Available + Allocation
= (7,4,3) + (0,0,2)
= (7,4,5)
We search the need matrix again, which is less than the available. Now we find that
(6,0,0) < (7,4,5)
So, resources are allocated to P3.
After P3 completes, it releases all its resources.
Then Available = Available + Allocation
= (7,4,5) + (3,0,2)
= (10,4,7)
We search the need matrix again, which is less than the available. Now we find that
(10,4,7) < (7,4,3)
So, resources are allocated to P1.
After P1 completes, it releases all its resources.
Then Available = Available + Allocation
= (10,4,7) + (0,1,0)
= (10,5,7)
Safe Sequence <P2,P4,P5,P3,P1>
Therefore, the additional request of (1,0,2) by P2 will be granted.
Exercise:
1. It is proposed to use a multi-resource Banker’s algorithm in an OS containing 3 resource classes
R1,R2 and R3. The number of resource units available for allocation is 7,7,and 10.The current
resource allocation is given as
Process Max Allocation
R1 R2 R3 R1 R2 R3
P1 3 6 8 2 2 3
P2 4 3 3 2 0 3
P3 3 4 4 1 2 4
1. Is the current allocation state safe?
2.Would the following requests be granted in current state?
a.Process P1 requests (1,1,0)
b.Process P2 requests (0,1,0)
c.Process P3 requests (0,1,0)
Solution:
Process Max Allocation Need
R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 3 6 8 2 2 3 1 4 5
P2 4 3 3 2 0 3 2 3 0
P3 3 4 4 1 2 4 2 2 0
Available
R1 R2 R3
2 3 0
1. Yes, The current state is safe because the safe sequence <P2,P3,P1> exists
2. A. Request of P1 cant be granted, because after allocation, the rest of its claim (0,3,5) cant be
met. So it will result in an unsafe state.
B. Request of P2 can be granted because the safe sequence <P2,P3,P1> exists
C. Request of P3 can be granted because after accepting the request of P2, the safe sequence
<P3,P2,P1> exists
2. Consider a system with 5 processes and 3 resource types. At time T0, the snapshot of the system
was taken, which is given in fig
Process Max Allocation
R1 R2 R3 R1 R2 R3
P0 7 5 3 0 1 0
P1 3 2 2 2 0 0
P2 9 0 2 3 0 2
P3 2 2 2 2 1 1
P4 4 3 3 0 0 2
Show that the system is in a safe state.Find the sequence which satisfies the safety criteria.
Available
R1 R2 R3
3 3 2
Solution:
Process Max Allocation Need
R1 R2 R3 R1 R2 R3 R1 R2 R3
P0 7 5 3 0 1 0 7 4 3
P1 3 2 2 2 0 0 1 2 2
P2 9 0 2 3 0 2 6 0 0
P3 2 2 2 2 1 1 0 1 1
P4 4 3 3 0 0 2 4 3 1
The system is in safe state and the safe sequence is <P1,P3,P4,P2,P0>
J. Paul Rajasingh, Assistant Professor / CSE, SRM Institute of Science & Technology, Tiruchirappalli Campus
For Internal Circulation Only
