Deadlocks

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 System Model
• A system consists of a finite number of resources to be distributed among a
number of competing processes.

• If a system has two CPUs, then the resource type CPU has two instances.

• A process must request a resource before using it and must release the resource
after using it.

• Each process utilizes a resource as follows:

-- Request: The process requests the resource. If the request cannot be granted
immediately then the requesting process must wait until it can acquire the resource.
– Use : The process can operate on the resource.
– Release : The process releases the resource.
Radhika A D, Asst. Prof. Dept. of CSE, BMSCE
 Deadlock Example
• Deadlock : It is a situation when a process in the system has acquired some
resources and waiting for more resources acquired by some other process
which in turn is waiting for the resources acquired by this process. None of
them can process and operating system cant do any work.

• Different resource type : P1 DVD and P2 Printer

P1 requests printer and P2 requests DVD
P1 waiting for the release of printer(P2) and P2 is waiting for the release of
DVD(P1).

• Same resource type : P1,P2,P3 having three CD RW drives.

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

Deadlock Characterization

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Deadlock Characterization
Four conditions for a deadlock to occur

• Mutual exclusion: Only one process at a time can use a resource. If a process requests that resource, the
requesting process must be delayed until the resource has been released.

• Hold and wait: A process holding at least one resource is waiting to acquire additional resources held by
other processes.

• No preemption: A resource can be released voluntarily by the process holding it, after that process has
completed its task.

• Circular wait: there exists a set {P0, P1, …, Pn} of waiting processes such that P0 is waiting for a resource
that is held by P1, P1 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 P0.

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Resource-Allocation Graph
• It consists of set of vertices V and a set of edges E.

• V is partitioned into two types:

– P = {P1, P2, …, Pn}, the set consisting of all the processes in the system
R = {R1, R2, …, Rm}, the set consisting of all resource types in the system

• Request edge – Directed edge Pi  Rj , process Pi has requested an instance of

resource type Rj and is currently waiting for that resource.

• Assignment edge – Directed edge Rj  Pi, instance of resource

type Rj has been allocated to process Pi.

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Resource-Allocation Graph (Cont.)
• Process

• Resource Type with 4 instances

• Pi requests instance of Rj Pi
Rj

• Pi is holding an instance of Rj Pi
Rj

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Resource-Allocation Graph (Cont.)

Resource Allocation Graph with no deadlock Resource Allocation Graph with a Deadlock

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Resource-Allocation Graph (Cont.)

• Resource allocation graph with cycle but no deadlock.

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Process states:
• Process P1 is holding an instance of resource type R2 and is waiting for an instance of
resource type R1 .
• Process P2 is holding an instance of R1 and an instance of R2 and is waiting for an instance
of R3.
• Process P3 is holding an instance of R3 .

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

Methods of Handling Deadlock

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Methods for Handling Deadlocks :
• Ensure that the system will never enter a deadlock state:
– Deadlock prevention
– Deadlock avoidance
• Allow the system to enter a deadlock state and then recover.
• Ignore the problem and pretend that deadlocks never occur in the system;

• Deadlock prevention provides a set of methods to ensure that at least one of the
necessary cannot hold.
• Deadlock avoidance requires that the operating system be given additional
information in advance concerning which resources a process will request and use
during its lifetime

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

Deadlock Prevention

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Deadlock Prevention
 Mutual Exclusion –
• The mutual exclusion condition must hold. That is, at least one resource
must be non-sharable.
• Sharable resources, in contrast, do not require mutually exclusive access and
thus cannot be involved in a deadlock.
• Read-only files are a good example of a sharable resource.
• If several processes attempt to open a read-only file at the same time, they
can be granted simultaneous access to the file.
 It must hold for non-sharable resources. We cannot prevent deadlocks by
denying the mutual-exclusion condition, because some resources are
intrinsically non sharable.

E.g.: Printer cannot be simultaneously shared by several process(non sharable).

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE
 Deadlock Prevention
 Hold and Wait – To ensure that this condition does not occurs in the system, we must
guarantee that whenever a process requests a resource, it does not hold any other
resources.

– One protocol requires process to request and be allocated all its resources before it
begins execution.

– Another protocol allows process to request resources only when the process has
none allocated to it.

– Disadvantages
• Low resource utilization
• Starvation Radhika A D, Asst. Prof. Dept. of CSE, BMSCE
 Deadlock Prevention (Cont.)
• No Preemption : To ensure that this condition does not hold, use the following
protocol.
– If a process is holding some resources, requests another resource that cannot be
immediately allocated to it, then all resources the process is currently holding
are preempted.

– Preempted resources are added to list of resources for which process is waiting.

– Process will be restarted only when it can regain its old resources, as well as the
new ones that it is requesting.

– This protocol is used whose state can be easily saved and restored later.

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Deadlock Prevention (Cont.)
• Circular Wait
- Impose a total ordering of all resource types, and require that
each process requests resources in an increasing order of
enumeration.

- Initially process requests any number of instances of resource

type Ri. After that process can request instance of resource type Rj
if and only if F(Rj) >F(Ri).

- E.g.: We define a one-to-one function F: R N, where N is the

set of natural numbers, R is the set of resource types includes tape
drives, disk drives, and printers.

- Alternatively, we can require that a process requesting an instance

of resource type Rj must have released any resources Ri; such that
Radhika A D, Asst. Prof. Dept. of CSE, BMSCE
F(Ri) >=F(Rj).
 Deadlock Avoidance
• Simplest and most useful model requires that each process
declare the maximum number of resources of each type that it
may need.

• Given this a priori information, it is possible to construct an

algorithm which ensures that the system will never enter a
deadlocked state.

• Resource-allocation state is defined by the number of available

and allocated resources, and the maximum demands of the
processes.

• The deadlock-avoidance algorithm dynamically examines the

resource-allocation state to ensure that there can never be a
circular-wait condition.
Radhika A D, Asst. Prof. Dept. of CSE, BMSCE
 Safe State
• A state is in safe if the system can allocate resources to a process in some
order and still avoid a deadlock.

• System is in safe state if there exists a sequence <P1, P2, …, Pn> of all the
processes in the system such that if Pi resource needs are not immediately
available, then Pi can wait until all Pj have finished.

– When Pj is finished, Pi can obtain needed resources, execute, return

allocated resources, and terminate.
– When Pi terminates, Pi +1 can obtain its needed resources, and so on .

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Basic Facts
• If a system is in safe state  no deadlocks
If a system is in unsafe state  possibility of deadlock.
• Avoidance  ensure that a system will never enter an unsafe
state.

Avoidance Algorithms :
• Single instance of a resource type
Use a resource-allocation graph algorithm
• Multiple instances of a resource type
Use the banker’s algorithm
Radhika A D, Asst. Prof. Dept. of CSE, BMSCE
 Resource-Allocation Graph Algorithm
• Claim edge Pi  Rj indicates that process Pj may request resource Rj
at sometime in the future; represented by a dashed line.

• Claim edge converts 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

reconverts to a claim edge.

• Resources must be claimed a priori in the system.

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Deadlock Avoidance

Unsafe State In Resource-Allocation Graph

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Banker’s Algorithm
• It is applicable to resource allocation system with multiple instances
of each resource type.

• The name was chosen because the algorithm could be used in a

banking system to ensure that the bank never allocated its available
cash in such a way that it could no longer satisfy the needs of all its
customers.

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Banker’s Algorithm
Let n = number of processes, and m = number of resources types.

• Available: Vector of length m. If available [j] = k, there are k

instances of resource type Rj 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 Pi is currently

allocated k instances of Rj

• Need: n x m matrix. If Need[i,j] = k, then Pi may need k more

instances of Rj to complete its task

Need [i,j] = Max[i,j] –Asst.

Radhika A D, Allocation
Prof. Dept. of CSE,[i,j]
BMSCE
 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 + Allocation
Finish [i] = true .
Go to step 2.

4. If Finish [i] == true for all i, then the system is in a safe state
Radhika A D, Asst. Prof. Dept. of CSE, BMSCE
 Resource-Request Algorithm for Process Pi
Requesti = request vector for process Pi. If Requesti [j] = k then
process Pi wants k instances of resource type Rj

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 safe  the resources are allocated to Pi
 If unsafe  Pi must wait, and the old resource-allocation
state is restored
Radhika A D, Asst. Prof. Dept. of CSE, BMSCE
Problems on Bankers Algorithm

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

Problems on Bankers Algorithm

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

Problems on Bankers Algorithm

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

Problems on Bankers Algorithm

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Deadlock Detection

• Allow system to enter deadlock state

• Detection algorithm

• Recovery scheme

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Single Instance of Each Resource Type
• If all the resources have single instance then we use a variant of
resource allocation graph called wait for graph.

• We obtain this graph by removing the resource nodes and

collapsing the appropriate edges.

• Maintains wait-for graph

– Nodes are processes
– Pi  Pj means Pi is waiting for Pj to release a resource that
Pi needs.

• Periodically invoke an algorithm that searches for a cycle in the

graph. If there is a cycle, there exists a deadlock.

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Resource-Allocation Graph and Wait-for Graph

Resource-Allocation Graph Corresponding wait-for graph

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Several instances of resource type :Detection Algorithm
Let Work and Finish be vectors of length m and n, respectively
Initialize:
(a) Work = Available
(b) For i = 1,2, …, n, if Allocationi  0, then
Finish[i] = false; otherwise, Finish[i] = true

2. Find an index i such that both:

(a) Finish[i] == false
(b) Requesti  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] == false, for some i, 1  i  n, then the system is in
deadlock state. Moreover, if Finish[i] == false, then Pi is
deadlocked
Radhika A D, Asst. Prof. Dept. of CSE, BMSCE
 Detection-Algorithm Usage
• When, and how often, to invoke depends on:
– How often a deadlock is likely to occur?
– How many processes will be affected by deadlock when it
happens?

• If detection algorithm is invoked arbitrarily, there may be many

cycles in the resource graph and so we would not be able to tell
which of the many deadlocked processes “caused” the deadlock.

• Recovery from Deadlock :

• Inform the operator that a deadlock has occurred and to let the
operator deal with the deadlock manually.
• Let the system recover from the deadlock automatically.

Radhika A D, Asst. Prof. Dept. of CSE, BMSCE

 Recovery from Deadlock: Process Termination
• Abort all deadlocked processes :The deadlocked processes may have
computed for a long time, and the results of these partial
computations must be discarded and probably will have to be
recomputed later.
• Abort one process at a time until the deadlock cycle is eliminated
:each process is aborted, a deadlock-detection algorithm must be
invoked to determine whether any processes are still deadlocked.

• In which order should we choose to abort?

1. Priority of the process.
2. How long process has computed, and how much longer to
completion.
3. How many resources that the process has used.
4. How many resources that process needs in order to complete.
5. How many processes will need to be terminated.
Radhika A D, Asst. Prof. Dept. of CSE, BMSCE
 Recovery from Deadlock: Resource Preemption
 Resource Preemption : We successively preempt some resources
from processes and give these resources to other processes till
the deadlock cycle is broken.

• Selecting a victim – Which resources and which processes are to

be preempted? As in process termination, we must determine
the order of preemption to minimize cost.

• Rollback – If we preempt a resource from a process, what

should be done with that process? If it is missing some needed
resource. We must roll back the process to some safe state and
restart it from that state.

• Starvation – How can we guarantee that resources will not

always be preempted from the same process?
Radhika A D, Asst. Prof. Dept. of CSE, BMSCE