Amity School of Engineering & Technology

Deadlock
 Amity School of Engineering & Technology

Objectives
– describe deadlock, and forms of prevention,
avoidance, detection, and recovery
 Amity School of Engineering & Technology

• A process in operating systems uses different

resources and uses resources in following way.

1) Requests a resource
2) Use the resource
2) Releases the resource
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

For example, in the below diagram, Process 1 is holding

Resource 1 and waiting for resource 2 which is acquired by
process 2, and process 2 is waiting for resource 1.
 Amity School of Engineering & Technology

Example of Deadlock
A real-world example would be traffic, which is going only in
one direction. Here, a bridge is considered a resource. So, when
Deadlock happens, it can be easily resolved if one car backs up
(Preempt resources and rollback).Several cars may have to be
backed up if a deadlock situation occurs.So starvation is possible.
 Amity School of Engineering & Technology

Deadlocks are a set of blocked processes each holding a

resource and waiting to acquire a resource held by another
process.
 Amity School of Engineering & Technology

Difference between Starvation and Deadlock

Sr. Deadlock Starvation
1 Deadlock is a situation where Starvation is a situation where the low
no process got blocked and no priority process got blocked and the high
process proceeds priority processes proceed.

2 Deadlock is an infinite waiting. Starvation is a long waiting but not

infinite.
3 Every Deadlock is always a Every starvation need not be deadlock.
starvation.
4 The requested resource is The requested resource is continuously be
blocked by the other process. used by the higher priority processes.

5 Deadlock happens when Mutual It occurs due to the uncontrolled priority

exclusion, hold and wait, No and resource management.
preemption and circular wait
occurs simultaneously.
 Amity School of Engineering & Technology

What is a Livelock?
• There is a variant of deadlock called livelock. This is a
situation in which two or more processes continuously
change their state in response to changes in the other
process(es) without doing any useful work. This is similar
to deadlock in that no progress is made but differs in that
neither process is blocked or waiting for anything.

• A human example of livelock would be two people who

meet face-to-face in a corridor and each moves aside to
let the other pass, but they end up swaying from side to
side without making any progress because they always
move the same way at the same time.
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Strategies for handling Deadlock

1. Deadlock Ignorance
Deadlock Ignorance is the most widely used
approach among all the mechanism. This is
being used by many operating systems mainly
for end user uses. In this approach, the
Operating system assumes that deadlock never
occurs. It simply ignores deadlock. This
approach is best suitable for a single end user
system where User uses the system only for
browsing and all other normal stuff.
 Amity School of Engineering & Technology

• There is always a tradeoff between Correctness and

performance. The operating systems like Windows
and Linux mainly focus upon performance. However,
the performance of the system decreases if it uses
deadlock handling mechanism all the time if
deadlock happens 1 out of 100 times then it is
completely unnecessary to use the deadlock
handling mechanism all the time.
• In these types of systems, the user has to simply
restart the computer in the case of deadlock.
Windows and Linux are mainly using this approach.
Amity School of Engineering & Technology
Amity School of Engineering & Technology
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Deadlock Prevention
• If we simulate deadlock with a table which is
standing on its four legs then we can also
simulate four legs with the four conditions which
when occurs simultaneously, cause the deadlock.

• However, if we break one of the legs of the table

then the table will fall definitely. The same
happens with deadlock, if we can be able to
violate one of the four necessary conditions and
don't let them occur together then we can
prevent the deadlock.
 Amity School of Engineering & Technology

1. Mutual Exclusion

• Mutual section from the resource point of view is

the fact that a resource can never be used by
more than one process simultaneously which is
fair enough but that is the main reason behind
the deadlock. If a resource could have been used
by more than one process at the same time then
the process would have never been waiting for
any resource.
• However, if we can be able to violate resources
behaving in the mutually exclusive manner then
the deadlock can be prevented.
 Amity School of Engineering & Technology

Spooling
For a device like printer, spooling can work. There
is a memory associated with the printer which
stores jobs from each of the process into it. Later,
Printer collects all the jobs and print each one of
them according to FCFS. By using this mechanism,
the process doesn't have to wait for the printer and
it can continue whatever it was doing. Later, it
collects the output when it is produced.
•
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Although, Spooling can be an effective approach to

violate mutual exclusion but it suffers from two kinds
of problems.

1.This cannot be applied to every resource.

2.After some point of time, there may arise a race
condition between the processes to get space in that
spool.

We cannot force a resource to be used by more than

one process at the same time since it will not be fair
enough and some serious problems may arise in the
performance. Therefore, we cannot violate mutual
exclusion for a process practically.
 Amity School of Engineering & Technology

2. Hold and Wait

•Hold and wait condition lies when a process holds a resource
and waiting for some other resource to complete its task.
Deadlock occurs because there can be more than one process
which are holding one resource and waiting for other in the
cyclic order.
•However, we have to find out some mechanism by which a
process either doesn't hold any resource or doesn't wait. That
means, a process must be assigned all the necessary
resources before the execution starts. A process must not
wait for any resource once the execution has been started.
 Amity School of Engineering & Technology

!(Hold and wait) = !hold or !wait (negation of hold and

wait is, either you don't hold or you don't wait)
•This can be implemented practically if a process declares all
the resources initially. However, this sounds very practical but
can't be done in the computer system because a process can't
determine necessary resources initially.
•Process is the set of instructions which are executed by the
CPU. Each of the instruction may demand multiple resources
at the multiple times. The need cannot be fixed by the OS.
•The problem with the approach is:
1.Practically not possible.
2.Possibility of getting starved will be increases due to the fact
that some process may hold a resource for a very long time.
 Amity School of Engineering & Technology

3. No Preemption
•Deadlock arises due to the fact that a process can't be stopped
once it starts. However, if we take the resource away from the
process which is causing deadlock then we can prevent deadlock.
•This is not a good approach at all since if we take a resource
away which is being used by the process then all the work which
it has done till now can become inconsistent.
•Consider a printer is being used by any process. If we take the
printer away from that process and assign it to some other
process then all the data which has been printed can become
inconsistent and ineffective and also the fact that the process
can't start printing again from where it has left which causes
performance inefficiency.
 Amity School of Engineering & Technology

4. Circular Wait
•To violate circular wait, we can assign a priority
number to each of the resource. A process can't
request for a lesser priority resource. This ensures
that not a single process can request a resource
which is being utilized by some other process and
no cycle will be formed.
 Amity School of Engineering & Technology

Deadlock avoidance

In deadlock avoidance, the request for any resource

will be granted if the resulting state of the system
doesn't cause deadlock in the system. The state of
the system will continuously be checked for safe
and unsafe states.
In order to avoid deadlocks, the process must tell
OS, the maximum number of resources a process
can request to complete its execution.
 Amity School of Engineering & Technology

The simplest and most useful approach states that

the process should declare the maximum number of
resources of each type it may ever need. The
Deadlock avoidance algorithm examines the
resource allocations so that there can never be a
circular wait condition.
 Amity School of Engineering & Technology

Resources Assigned

Process Type 1 Type 2 Type 3 Type 4

A 3 0 2 2
B 0 0 1 1
C 1 1 1 0
Resources Assigned
D 2 1 4 0

Resources still needed

Process Type 1 Type 2 Type 3 Type 4

A 1 1 0 0
B 0 1 1 2
C 1 2 1 0
D 2 1 1 2
 Amity School of Engineering & Technology

E = (7 6 8 4)  
P = (6 2 8 3)  
A = (1 4 0 1)   
 Amity School of Engineering & Technology

A state of the system is called safe if the system can allocate

all the resources requested by all the processes without
entering into deadlock.

If the system cannot fulfill the request of all processes then

the state of the system is called unsafe.

The key of Deadlock avoidance approach is when the request

is made for resources then the request must only be approved
in the case if the resulting state is also a safe state.
 Amity School of Engineering & Technology

Resource Allocation Graph

• The resource allocation graph is the pictorial

representation of the state of a system. As its
name suggests, the resource allocation graph is
the complete information about all the processes
which are holding some resources or waiting for
some resources.
• It also contains the information about all the
instances of all the resources whether they are
available or being used by the processes.
• In Resource allocation graph, the process is
represented by a Circle while the Resource is
represented by a rectangle.
 Amity School of Engineering & Technology

Example
•Let’s consider 3 processes P1, P2 and P3, and two types of
resources R1 and R2. The resources are having 1 instance each.
•According to the graph, R1 is being used by P1, P2 is holding R2
and waiting for R1, P3 is waiting for R1 as well as R2.
•The graph is deadlock free since no cycle is being formed in the
graph.
 Amity School of Engineering & Technology

Deadlock Detection using RAG

• If a cycle is being formed in a Resource allocation graph where
all the resources have the single instance then the system is
deadlocked.
• In Case of Resource allocation graph with multi-instanced
resource types, Cycle is a necessary condition of deadlock but
not the sufficient condition.
• The following example contains three processes P1, P2, P3 and
three resources R2, R2, R3. All the resources are having single
instances each.
 Amity School of Engineering & Technology

• If we analyze the graph then we can find out that there is a

cycle formed in the graph since the system is satisfying all
the four conditions of deadlock.

Allocation Matrix
Allocation matrix can be formed by using the Resource
allocation graph of a system. In Allocation matrix, an entry
will be made for each of the resource assigned. For Example,
in the following matrix, en entry is being made in front of P1
and below R3 since R3 is assigned to P1.

Process R1 R2 R3

P1 0 0 1
P2 1 0 0
P3 0 1 0
 Amity School of Engineering & Technology

Request Matrix
In request matrix, an entry will be made for each of the
resource requested. As in the following example, P1 needs R1
therefore an entry is being made in front of P1 and below R1.

Process R1 R2 R3

P1 1 0 0
P2 0 1 0
P3 0 0 1

Avial = (0,0,0)
 Amity School of Engineering & Technology

Neither we are having any resource available in the

system nor a process going to release. Each of the
process needs at least single resource to complete
therefore they will continuously be holding each
one of them.
We cannot fulfill the demand of at least one process
using the available resources therefore the system
is deadlocked as determined earlier when we
detected a cycle in the graph.
 Amity School of Engineering & Technology

Deadlock Detection and Recovery

• In this approach, The OS doesn't apply any mechanism to
avoid or prevent the deadlocks. Therefore the system
considers that the deadlock will definitely occur. In order to
get rid of deadlocks, The OS periodically checks the system
for any deadlock. In case, it finds any of the deadlock then
the OS will recover the system using some recovery
techniques.

• The main task of the OS is detecting the deadlocks. The OS

can detect the deadlocks with the help of Resource
allocation graph.
 Amity School of Engineering & Technology

In single instanced resource types, if a cycle is being formed in

the system then there will definitely be a deadlock. On the
other hand, in multiple instanced resource type graph, detecting
a cycle is not just enough. We have to apply the safety
algorithm on the system by converting the resource allocation
graph into the allocation matrix and request matrix.

In order to recover the system from deadlocks, either OS

considers resources or processes.
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

For Resource
Preempt the resource
We can snatch one of the resources from the owner of the
resource (process) and give it to the other process with the
expectation that it will complete the execution and will release
this resource sooner. Well, choosing a resource which will be
snatched is going to be a bit difficult.

Rollback to a safe state

System passes through various states to get into the deadlock
state. The operating system canrollback the system to the
previous safe state. For this purpose, OS needs to implement
check pointing at every state.
The moment, we get into deadlock, we will rollback all the
allocations to get into the previous safe state.
 Amity School of Engineering & Technology

For Process
Kill a process
Killing a process can solve our problem but the
bigger concern is to decide which process to kill.
Generally, Operating system kills a process which
has done least amount of work until now.

Kill all process

This is not a suggestible approach but can be
implemented if the problem becomes very serious.
Killing all process will lead to inefficiency in the
system because all the processes will execute
again from starting.