Deadlock

Deadlocks
 System Model

 Deadlock Characterization

 Methods for Handling Deadlocks

 Deadlock Prevention

 Deadlock Avoidance

 Deadlock Detection

 Recovery from Deadlock

 The Deadlock Problem
 A deadlock is a situation where a

set of processes are blocked

because each process is holding a
resource and waiting for another
resource acquired by some other
process.
 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.
Deadlock Characterization
 Necessary Conditions
 Deadlock can arise if the following four conditions hold simultaneously

Mutual Exclusion: Two or more resources are non-shareable (Only one process

can use at a time).

Hold and Wait: A process is holding at least one resource and waiting for

resources.

No Preemption: A resource cannot be taken from a process unless the process

releases the resource.

Circular Wait: A set of processes waiting for each other in circular form.
 Mutual Exclusion
 There should be a resource
that can only be held by one
process at a time. In the
diagram below, there is a
single instance of Resource 1
and it is held by Process 1
only.
 Hold and Wait
 A process can hold multiple

resources and still request more

resources from other processes
which are holding them. In the
diagram given below, Process 2
holds Resource 2 and Resource
3 and is requesting the Resource
1 which is held by Process 1.
 No Preemption
 A resource cannot be preempted

from a process by force. A process

can only release a resource

voluntarily. In the diagram below,

Process 2 cannot preempt

Resource 1 from Process 1. It will

only be released when Process 1

relinquishes it voluntarily after its

execution is complete.
 Circular Wait
 A process is waiting for the resource held

by the second process, which is waiting for

the resource held by the third process and

so on, till the last process is waiting for a

resource held by the first process. This

forms a circular chain. For example:

Process 1 is allocated Resource2 and it is

requesting Resource 1. Similarly, Process 2

is allocated Resource 1 and it is requesting

Resource 2. This forms a circular wait loop.

 System Model
 The systems model is a process-oriented representation
that emphasizes the influences, or flow, of information
between modules. A systems model describes how processes
interact and what operations these processes perform.
 Make it a requirement that all processes request all resources at
the same time. Processes that hold resources must.

Request : The process requests the resource. If the request cannot be granted
immediately (for example, if the resource is being used by another process),the
requesting process must wait until it can acquire the Resource.

Use: The process can operate on the resource (for example, if the resource is
a printer, the process can print on the printer)

Release: The process releases the resource.

 Resources − The system has a set of resources that are shared among processes.

These resources can be hardware or software components, such as memory, files,

printers, or network connections. Each resource is identified by a unique name or

identifier.

 Processes − The system has a set of processes that request and release

resources. Processes are units of execution that can be started, suspended,

resumed, and terminated. Each process is identified by a unique process ID.

 Resource Allocation − Each resource can be in one of two states , allocated or

available. A resource that is allocated to a process cannot be used by any other

process until it is released.

 Request and Release − A process can request a resource by sending a request to the system.

If the resource is available, it will be allocated to the process. When a process is finished using

a resource, it must release it so that it can be used by other processes.

 Resource Dependency − Some processes may require multiple resources to complete their

tasks. A resource dependency graph can be used to represent the relationships between

processes and resources and to detect potential deadlocks.

 Deadlock Detection − A deadlock can occur when two or more processes are waiting for

resources that are being held by other processes, creating a circular dependency. Deadlock

detection algorithms can be used to detect when a deadlock has occurred, so that corrective

action can be taken.

 Deadlock Resolution − Once a deadlock has been detected, it can be resolved by

breaking the circular dependency between the processes. This can be done by

releasing one or more resources that are being held by a process, or by preempting

one or more processes that are holding resources.

 Resource preemption is a technique used to break the circular wait condition of a

deadlock. The operating system can preempt resources from one or more processes

involved in the deadlock and allocate them to the processes that need them.

Preemption can be done either selectively or globally. In selective preemption, only

the resources that are required to resolve the deadlock are preempted, while in

global preemption, all the resources held by the deadlocked processes are

preempted.
  When a process is terminated, all the resources held by the process are

released, and other processes can proceed. However, this approach can

lead to data loss and inconsistency if the terminated process was in the

middle of a critical task.

 Deadlock Avoidance − Deadlock avoidance is a technique used to

prevent the occurrence of deadlocks in a computer system. The goal of

deadlock avoidance is to ensure that all resources required by a process are

available before the process starts execution, thereby avoiding the

possibility of deadlock.
 Resource-Allocation Graph
A set of vertices V and a set of
edges E.

 In Resource allocation graph, the process is represented

by a Circle while the Resource is represented by a
rectangle. Let's see the types of vertices and edges in
detail.
 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

 assignment edge – directed edge Rj  Pi

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
Resource-Allocation Graph
Single and multiple instance without deadlock
 Methods for Handling Deadlocks
 Generally speaking, we can deal with the deadlock problem in one of
three ways:
 We can use a protocol to prevent or avoid deadlocks, ensuring that the

 system will never enter a deadlocked state.

 We can allow the system to enter a deadlocked state, detect it, and
recover.
 We can ignore the problem altogether and pretend that deadlocks never

 occur in the system.

Ignore the problem and pretend that deadlocks never occur in the
system; used by most operating systems, including UNIX.
 Deadlock ignorance

 Deadlock Prevention

 Deadlock Avoidance

 Deadlock detection and recovery

 Deadlock Detection
 A deadlock can be detected by a resource scheduler as
it keeps track of all the resources that are allocated to
different processes. After a deadlock is detected, it can
be resolved using the following methods −
 All the processes that are involved in the deadlock are
terminated. This is not a good approach as all the
progress made by the processes is destroyed.
 Resources can be preempted from some processes and
given to others till the deadlock is resolved.
 Deadlock Prevention and Deadlock Avoidance

Deadlock Prevention
 It is very important to prevent a deadlock before it can occur. So,

the system checks each transaction before it is executed to

make sure it does not lead to deadlock. If there is even a slight
chance that a transaction may lead to deadlock in the future, it
is never allowed to execute.

Deadlock Avoidance
 It is better to avoid a deadlock rather than take measures after

the deadlock has occurred. The wait for graph can be used for
deadlock avoidance. This is however only useful for smaller
databases as it can get quite complex in larger databases.
 Deadlock Detection and Recovery
 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.
Deadlock Detection and Recovery