See Our team
Wondering how we keep quality?
Got unsolved questions? Ask Questions
GATE
GMAT
CBSE
NCERT
Career
Interview
Railway
UPSC
NID
NIFT-UG
NIFT-PG
PHP
AJAX
JavaScript
Node Js
Shell Script
Research
Operating Systems [10CS53] unit-4
UNIT 4 DEADLOCK
TOPICS
4.9 DEADLOCKS
4.10 SYSTEM MODEL
4.11 DEADLOCK CHARACTERIZATION
4.12 METHODS FOR HANDLING DEADLOCKS
4.13 DEADLOCK PREVENTION
4.14 DEADLOCK AVOIDANCE
4.15 DEADLOCK DETECTION
4.16 RECOVERY FROM DEADLOCK
68
4.1 DEADLOCKS
? When processes request a resource and if the resources are not available at that time the process enters
into waiting state. Waiting process may not change its state because the resources they are requested are held
by other process. This situation is called deadlock.
? The situation where the process waiting for the resource i.e., not available is called deadlock.
4.2 SYSTEM MODEL
? A system may consist of finite number of resources and is distributed among number of processes.
There resources are partitioned into several instances each with identical instances.
? A process must request a resource before using it and it must release the resource after using it. It can
request any number of resources to carry out a designated task. The amount of resource requested may not
exceed the total number of resources available.
A process may utilize the resources in only the following sequences:
1. Request:-If the request is not granted immediately then the requesting process must wait it can acquire the
resources.
2. Use:-The process can operate on the resource.
3. Release:-The process releases the resource after using it.
Deadlock may involve different types of resources.
For eg:-Consider a system with one printer and one tape drive. If a process Pi currently holds a
printer and a process Pj holds the tape drive. If process Pi request a tape drive and process Pj request a
printer then a deadlock occurs.
Multithread programs are good candidates for deadlock because they compete for shared
resources.
4.3 DEADLOCK CHARACTERIZATION
Necessary Conditions:A deadlock situation can occur if the following 4 conditions occur simultaneously in a
system:-1. Mutual Exclusion:Only one process must hold the resource at a time. If any other process requests
for the resource, the requesting process must be delayed until the resource has been released.
1. Hold and Wait:-A process must be holding at least one resource and waiting to acquire additional
resources that are currently being held by the other process.
2. No Preemption:-Resources can’t be preempted i.e., only the process holding the resources must release it
after the process has completed its task.
3. Circular Wait:-A set {P0,P1……..Pn} of waiting process must exist such that P0 is waiting for a resource
i.e., held by P1, P1 is waiting for a resource i.e., held by P2. Pn-1 is waiting for resource held by process
Pn and Pn is waiting for the resource i.e., held by P1. All the four conditions must hold for a deadlock to
occur.
Resource Allocation Graph:
1. Deadlocks are described by using a directed graph called system resource allocation graph. The graph
consists of set of vertices (v) and set of edges (e).
2. The set of vertices (v) can be described into two different types of nodes P={P1,P2……..Pn} i.e., set
consisting of all active processes and R={R1,R2……….Rn}i.e., set consisting of all resource types in the
system
69
7. A directed edge from process Pi to resource type Rj denoted by Pi->Ri indicates that Pi requested
an instance of resource Rj and is waiting. This edge is called Request edge.
8. A directed edge Ri-> Pj signifies that resource Rj is held by process Pi. This is called
Assignment edge
Eg:
R1 R3
R2 R4
? If the graph contain no cycle, then no process in the system is deadlock. If the graph contains a cycle
then a deadlock may exist.
? If each resource type has exactly one instance than a cycle implies that a deadlock has occurred. If
each resource has several instances then a cycle do not necessarily implies that a deadlock has occurred.
4.4 METHODS FOR HANDLING DEADLOCKS
There are three ways to deal with deadlock problem x We can use a protocol to prevent deadlocks ensuring
that the system will never enter into the
deadlock state. x We allow a system to enter into deadlock state, detect it and recover from it. x We
ignore the problem and pretend that the deadlock never occur in the system. This is used by
most OS including UNIX.
? To ensure that the deadlock never occur the system can use either deadlock avoidance or a deadlock
prevention.
? Deadlock prevention is a set of method for ensuring that at least one of the necessary conditions does
not occur.
? Deadlock avoidance requires the OS is given advance information about which resource a process
will request and use during its lifetime.
? If a system does not use either deadlock avoidance or deadlock prevention then a deadlock situation
may occur. During this it can provide an algorithm that examines the state of the system to determine whether
a deadlock has occurred and algorithm to recover from deadlock.
70
? Undetected deadlock will result in deterioration of the system performance.
HANDLING DEADLOCKS
There are three ways to deal with deadlock problem x We can use a protocol to prevent deadlocks ensuring
that the system will never enter into the deadlock state. x We allow a system to enter into deadlock state,
detect it and recover from it. x We ignore the problem and pretend that the deadlock never occur in the
system. This is used by most OS including UNIX.
? To ensure that the deadlock never occur the system can use either deadlock avoidance or a deadlock
prevention.
? Deadlock prevention is a set of method for ensuring that at least one of the necessary conditions does
not occur.
? Deadlock avoidance requires the OS is given advance information about which resource a process
will request and use during its lifetime.
? If a system does not use either deadlock avoidance or deadlock prevention then a deadlock situation
may occur. During this it can provide an algorithm that examines the state of the system to determine whether
a deadlock has occurred and algorithm to recover from deadlock.
71
4.5 DEADLOCK PREVENTION
??For a deadlock to occur each of the four necessary conditions must hold. If at least one of the there
condition does not hold then we can prevent occurrence of deadlock.
1. Mutual Exclusion:This holds for non-sharable resources. Eg:-A printer can be used by only one process at a
time.
Mutual exclusion is not possible in sharable resources and thus they cannot be
involved in deadlock. Read-only files are good examples for sharable resources. A process never waits for
accessing a sharable resource. So we cannot prevent deadlock by denying the mutual exclusion condition in
non-sharable resources.
2. Hold and Wait:This condition can be eliminated by forcing a process to release all its resources held by it
when it request a resource i.e., not available.
x One protocol can be used is that each process is allocated with all of its resources before
its start execution. Eg:-consider a process that copies the data from a tape drive to the disk,
sorts the file and then prints the results to a printer. If all the resources are allocated at the
beginning then the tape drive, disk files and printer are assigned to the process. The main problem
with this is it leads to low resource utilization because it requires printer at the last and is allocated
with it from the beginning so that no other process can use it. x Another protocol that can be used
is to allow a process to request a resource when the
process has none. i.e., the process is allocated with tape drive and disk file. It performs the
required operation and releases both. Then the process once again request for disk file and the
printer and the problem and with this is starvation is possible.
3. No Preemption:To ensure that this condition never occurs the resources must be preempted. The following
protocol can be used.
x If a process is holding some resource and request another resource that cannot be immediately
allocated to it, then all the resources currently held by the requesting process are preempted
and added to the list of resources for which other processes may be waiting. The process will
be restarted only when it regains the old resources and the new resources that it is requesting.
x When a process request resources, we check whether they are available or not. If they are
available we allocate them else we check that whether they are allocated to some other
waiting process. If so we preempt the resources from the waiting process and allocate them to
the requesting process. The requesting process must wait.
4.Circular Wait:-The fourth and the final condition for deadlock is the circular wait condition. One
way to ensure that this condition never, is to impose ordering on all resource types and each process
requests resource in an increasing order.
Let R={R1,R2,………Rn} be the set of resource types. We assign each resource type
with a unique integer value. This will allows us to compare two resources and determine whether one
precedes the other in ordering. Eg:-we can define a one to one function
F:R?N as follows :-F(disk drive)=5 F(printer)=12 F(tape drive)=1
72
Deadlock can be prevented by using the following protocol:
x Each process can request the resource in increasing order. A process can
request any number of instances of resource type say Ri and it can request
instances of resource type Rj only F(Rj) > F(Ri).
x Alternatively when a process requests an instance of resource type Rj,
it has released any resource Ri such that F(Ri) >= F(Rj). If these
two protocol are used then the circular wait can’t hold.
4.6 DEADLOCK AVOIDANCE
? Deadlock prevention algorithm may lead to low device utilization and reduces system throughput.
? Avoiding deadlocks requires additional information about how resources are to be requested. With the
knowledge of the complete sequences of requests and releases we can decide for each requests whether or not
the process should wait.
? For each requests it requires to check the resources currently available, resources that are currently
allocated to each processes future requests and release of each process to decide whether the current requests
can be satisfied or must wait to avoid future possible deadlock.
? A deadlock avoidance algorithm dynamically examines the resources allocation state to ensure that a
circular wait condition never exists. The resource allocation state is defined by the number of available and
allocated resources and the maximum demand of each process.
Safe State:
? A state is a safe state in which there exists at least one order in which all the process will run
completely without resulting in a deadlock.
? A system is in safe state if there exists a safe sequence.
? A sequence of processes is a safe sequence for the current allocation state if for
each Pi the resources that Pi can request can be satisfied by the currently available resources.
? If the resources that Pi requests are not currently available then Pi can obtain all of its needed resource
to complete its designated task.
? A safe state is not a deadlock state.
? Whenever a process request a resource i.e., currently available, the system must decide whether
resources can be allocated immediately or whether the process must wait. The request is granted only if the
allocation leaves the system in safe state.
? In this, if a process requests a resource i.e., currently available it must still have to wait. Thus resource
utilization may be lower than it would be without a deadlock avoidance algorithm.
Resource Allocation Graph Algorithm:
??This algorithm is used only if we have one instance of a resource type. In addition to the request edge
and the assignment edge a new edge called claim edge is used. For eg:-A claim edge Pi?Rj indicates
that process Pi may request Rj in future. The claim edge
is represented by a dotted line.
73
x When a process Pi requests the resource Rj, the claim edge is converted to a request edge. x When resource Rj
is released by process Pi, the assignment edge Rj?Pi is replaced by the claim edge Pi?Rj.
??When a process Pi requests resource Rj the request is granted only if converting the request edge
Pi?Rj to as assignment edge Rj?Pi do not result in a cycle. Cycle detection algorithm is used to
detect the cycle. If there are no cycles then the allocation of the resource to process leave the system
in safe state
. Banker’s Algorithm:
? This algorithm is applicable to the system with multiple instances of each resource types, but this is
less efficient then the resource allocation graph algorithm.
? When a new process enters the system it must declare the maximum number of resources that it may
need. This number may not exceed the total number of resources in the system. The system must determine
that whether the allocation of the resources will leave the system in a safe state or not. If it is so resources are
allocated else it should wait until the process release enough resources.
? Several data structures are used to implement the banker’s algorithm. Let ‘n’ be the number of
processes in the system and ‘m’ be the number of resources types. We need the following data structures:
x Available:-A vector of length m indicates the number of available resources. If Available[i]=k, then k
instances of resource type Rj is available.
x Max:-An n*m matrix defines the maximum demand of each process if Max[i,j]=k, then Pi may request
at most k instances of resource type Rj.
x Allocation:-An n*m matrix defines the number of resources of each type currently allocated to each
process. If Allocation[i,j]=k, then Pi is currently k instances of resource type Rj.
x Need:-An n*m matrix indicates the remaining resources need of each process. If Need[i,j]=k, then Pi
may need k more instances of resource type Rj to compute its task. So Need[i,j]=Max[i,j]-
Allocation[i]
Safety Algorithm:
??This algorithm is used to find out whether or not a system is in safe state or not. Step 1. Let work and
finish be two vectors of length M and N respectively. Initialize work = available and Finish[i]=false for
i=1,2,3,…….n
Step 2. Find i such that both Finish[i]=false Need i <= work
If no such i exist then go to step 4
Step 3. Work = work + Allocation Finish[i]=true Go to step 2
Step 4. If finish[i]=true for all i, then the system is in safe state. This algorithm may require an order of m*n*n
operation to decide whether a state is safe.
74
Resource Request Algorithm:Let Request(i) be the request vector of process Pi. If Request(i)[j]=k,
then process Pi wants K instances of the resource type Rj. When a request for resources is made by process Pi
the following actions are taken.
x If Request(i) <= Need(i) go to step 2 otherwise raise an error condition since the process has exceeded its
maximum claim. x If Request(i) <= Available go to step 3 otherwise Pi must wait. Since the resources are not
available. x If the system want to allocate the requested resources to process Pi then modify the state
as follows. Available = Available ? Request(i) Allocation(i) = Allocation(i) + Request(i)
Need(i) = Need(i) ? Request(i)
x If the resulting resource allocation state is safe, the transaction is complete and Pi is allocated
its resources. If the new state is unsafe then Pi must wait for Request(i) and old resource
allocation state is restored.
4.7 DEADLOCK DETECTION
If a system does not employ either deadlock prevention or a deadlock avoidance algorithm then a deadlock
situation may occur. In this environment the system may provide x An algorithm that examines the state of
the system to determine whether a deadlock has occurred. x An algorithm to recover from the deadlock.
Single Instances of each Resource Type:
? If all the resources have only a single instance then we can define deadlock detection algorithm that
uses a variant of resource allocation graph called a wait for graph. This graph is obtained by removing the
nodes of type resources and removing appropriate edges.
? An edge from Pi to Pj in wait for graph implies that Pi is waiting for Pj to release a resource that Pi
needs.
? An edge from Pi to Pj exists in wait for graph if and only if the corresponding resource allocation
graph contains the edges Pi?Rq and Rq?Pj.
? Deadlock exists within the system if and only if there is a cycle. To detect deadlock the system needs
an algorithm that searches for cycle in a graph.
75
76
4.8 RECOVERY FROM DEADLOCKS
Several Instances of a Resource Types:
??The wait for graph is applicable to only a single instance of a resource type. The following algorithm
applies if there are several instances of a resource type. The following data structures are used:-
? o Available:-Is a vector of length m indicating the number of available resources of each type .
? o Allocation:-Is an m*n matrix which defines the number of resources of each type currently
allocated to each process.
? o Request:-Is an m*n matrix indicating the current request of each process. If request[i,j]=k then Pi is
requesting k more instances of resources type Rj.
Step 1. let work and finish be vectors of length m and n respectively. Initialize Work = available/expression
For i=0,1,2……….n if allocation(i)!=0 then Finish[i]=0
else Finish[i]=true
Step 2. Find an index(i) such that both Finish[i]
= false Request(i)<=work
If no such I exist go to step 4.
Step 3. Work = work + Allocation(i) Finish[i] = true Go to step 2. Step 4. If Finish[i] = false for some I where
m>=i>=1. When a system is in a deadlock state. This algorithm needs an order of m*n square operations to
detect whether the system is in deadlock state or not.
IMPORTANT QUESTIONS:
1. For the following snapshot of the system find the safe sequence (using Banker’salgorithm).
77
b. Is the system is in safe state?
c. If the process P1 request (0,4,2,0) resources cam the request be granted immediately?
3. The operating system contains three resources. The numbers of instances of each resource type are (7, 7,
10). The current allocation state is given below.
a. Is the current allocation is safe?
b. find need?
c. Can the request made by the process P1(1,1,0) can be granted?
4. Explain different methods to recover from deadlock?
5. Write advantage and disadvantage of deadlock avoidance and deadlock prevention?
Editors
Checkout our YouTube channel for video tutorials and learn more about Eduladder.
New updates
Similar Questions
Notes
10cs53 Downloadable notesRTOS - Real-Time Operating Systems soonEmbedded computing systems 10CS7210is72 Information systems unit-2Operating systemUnit 7- CLOUD VIRTUALIZATION TECHNOLOGYeyeOS06is65 information system and management vtu notes unit-1CE 2040 ECOLOGICAL ENGINEERINGGE2151 BASIC ELECTRICAL AND ELECTRONICS ENGINEERING