WHAT IS DEADLOCK

• A process requests resources; if the resources are not

available at that time, the process enters a waiting
state.
• Sometimes, a waiting process is never again able to
change state, because the resources it has requested
are held by other waiting processes.
• This situation is called a deadlock.

Deadlock
Deadlock
DEADLOCK
CHARACTERIZATION
Deadlock can arise if four conditions hold simultaneously.

• Mutual exclusion: only one process at a time can use a

resource.
• 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 only voluntarily by
the process holding it, after that process has completed its task.
• Circular wait: there exists a set {P0, P1, …, P0} 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 P0 is waiting for a
resource that is held by P0.

Deadlock
• 1) Mutual exclusion: In this condition, only one
method must be non-shareable. It means only one
process can use it at a time.
• This condition ensures that a resource cannot be
simultaneously accessed or modified
• 2) Hold and wait: The process must hold at least one
resource while waiting to acquire additional
resources. This condition can lead to a situation
where processes hold some resources and wait
indefinitely for others. ocesses.

Deadlock
• 3) No pre-emption: Resources cannot be pre-empted
or forcibly taken away from a process. This means that
a resource can only be released voluntarily by the
process holding it. If a process is holding a resource
and cannot complete its task due to waiting for
another resource, it will not release its current
resource, contributing to a potential Deadlock.
• 4) Circular wait: There must be a circular chain of
one or more processes, each of which is waiting for a
resource held by another process in the chain. This
circular waiting pattern means that no process in the
cycle can make progress because another process
blocks it
Deadlock
Deadlock
OF HANDLING
DEADLOCK
SEQUENCE
• Execution Sequence

Deadlock
• 1) Deadlock prevention: Deadlock prevention
strategies aim to eliminate one or more of the
necessary conditions for Deadlock. This approach
ensures that Deadlock cannot occur in the system.
One common method involves resource allocation
graphs or resource allocation policies to track and
manage resource allocation.

Deadlock
2) DEADLOCK
DETECTION AND
RECOVERY:
• Deadlock detection is a process of periodically
checking the system for the existing Deadlocks.
Once the Deadlock is detected, the system can take
action to resolve it. Detection and recovery are
reactive approaches to managing Deadlocks after
they occur.

Deadlock
3) DEADLOCK
AVOIDANCE
• Deadlock avoidance uses resource allocation
algorithms and request protocols to dynamically
allocate resources in a way that prevents the system
from entering a Deadlock state. The key is to make
sure that resource requests do not lead to situations
where all necessary conditions for Deadlock are met.

Deadlock
4) WOUND-WAIT
SCHEMES
• Wound-wait scheme handles Deadlock situations in
the Data Management system, allowing either older
transactions to wait or younger transactions to wait
and deciding which one should be aborted based on
their age.

Deadlock
Deadlock
Deadlock
DEAD LOCK
PREVENTION
• Mutual Exclusion
In terms of resources, mutual exclusion means that
multiple processes can’t use the same resource at the
same time. However, while this is reasonable, it results in
a deadlock. There will be no process waiting for the
resource if we may use the same resource for several
processes at the same time. However, if we can prevent
the resources from acting in a mutually exclusive
manner, we can keep the system from becoming stuck.

Deadlock
HOLD AND WAIT

• A hold and wait condition occurs when a process

holds a resource while waiting for other resources to
complete its task. There is a risk of deadlock in this
case because many processes possess one resource
and cyclically wait for various other resources to
complete their tasks. As a result, we’ll need to come
up with a procedure that doesn’t hold any resources
or waits for any resources. This means that before
beginning the process, we should assign all of the
resources that it will require. The process is then
started without having to wait for any resources.

Deadlock
• In practice, we can only do so if we first identify all of
the resources that the procedure will require.
Although this sounds highly practical, we cannot do
so in a computer system because no process can
identify the required resources at the outset.

Deadlock
• A process is a series of instructions that the CPU
executes. Each instruction makes many requests for
distinct resources. The operating system, however,
cannot control the demand for resources. The
following concerns arise from the approach:
• Practically, it is not possible.
• Because the process can retain a resource for a
lengthy time in some instances, there is a risk of
starving.

Deadlock
NO PREEMPTION

• The reason for the deadlock is that once the process

starts, it cannot be stopped. However, we can avoid
deadlock by removing resources from the process
that could cause it. However, this is not an
appropriate technique because bringing out a
resource that is used by the process will be
inconsistent with the previous effort.

Deadlock
• Example – Let’s say we have a printer that is now
being used by a process, and we want to assign the
printer to another process. As a result, the data
produced by the printer becomes both inaccurate
and ineffective. Furthermore, the operation would not
resume printing from where it stopped off, resulting
in inefficient performance.

Deadlock
CIRCULAR WAIT

• A circular wait occurs when one or more processes

wait in a circular order for the resources they require.
The problem of a cyclic wait can be solved by
assigning a priority number to each resource. A
resource with a lower priority value cannot be
requested by the process. It ensures that no process
can demand a resource that is already in use by
another. As a result, no cycle will form.

Deadlock
Deadlock
DEADLOCK
AVOIDANCE
• A deadlock avoidance policy grants a resource
request only if it can establish that granting the
request cannot lead to a deadlock either immediately
or in the future. The kernal lacks detailed knowledge
about future behavior of processes, so it cannot
accurately predict deadlocks. To facilitate deadlock
avoidance under these conditions, it uses the
following conservative approach: Each process
declares the maximum number of resource units of
each class that it may require. The kernal permits a
process to request these resource units in stages

Deadlock
• Resource Allocation Graph
• Banker’s Algorithm

Deadlock
LIMIT RESOURCE
UTILISATION
• This method involves limiting the huge number of
resources that can be allocated to a process. By
restricting resource usage, the system reduces the
likelihood of Deadlock occurrence. However, this
approach may impact system efficiency and resource
utilisation, so it should be used judiciously.

Deadlock
Consider there are n
processes in the system P1,
P2, P3, …… , Pn where-
Process P1 requires x1 units of
resource R
Process P2 requires x2 units of
resource R
Process P3 requires x3 units of
resource R and so on.
Deadlock
Deadlock
MAXIMUM NUMBER OF
UNITS THAT ENSURES
DEADLOCK-
• (x1-1) + (x2-1) + (x3-1) + …. + (xn-1)
• = ( x1 + x2 + x3 + …. + xn ) – n
• = ∑xi – n
• = Sum of max needs of all n processes – n

Deadlock
MINIMUM NUMBER OF
UNITS THAT ENSURES
NO DEADLOCK
• Minimum number of units of resource R that ensures no
deadlock
• = One more than maximum number of units of resource R
that ensures deadlock
• = (∑xi – n) + 1

Deadlock
QUESTION

A system is having 3 user processes each requiring 2 units of

resource R. The minimum number of units of R such that no
deadlock will occur-
•n worst case,
•The number of units that each process holds = One less than its maximum demand So,
•Process P1 holds 1 unit of resource R
•Process P2 holds 1 unit of resource R
•Process P3 holds 1 unit of resource R
Thus,
•Maximum number of units of resource R that ensures deadlock = 1 + 1 + 1 = 3
•Minimum number of units of resource R that ensures no deadlock = 3 + 1 = 4

Deadlock
DEADLOCK AVOIDANCE
• The deadlock Avoidance method is used by the
operating system in order to check whether the
system is in a safe state or in an unsafe state and in
order to avoid the deadlocks, the process must need
to tell the operating system about the maximum
number of resources a process can request in order
to complete its execution.

Deadlock
• In this method, the request for any resource will be
granted only if the resulting state of the system
doesn't cause any deadlock in the system. This
method checks every step performed by the
operating system. Any process continues its
execution until the system is in a safe state. Once
the system enters into an unsafe state, the operating
system has to take a step back.

Deadlock
SAFE STATE

• A state is safe if the system can allocate resources to

each process( up to its maximum requirement) in
some order and still avoid a deadlock. Formally, a
system is in a safe state only, if there exists a safe
sequence. So a safe state is not a deadlocked state
and conversely a deadlocked state is an unsafe state.

Deadlock
• In an Unsafe state, the operating system cannot
prevent processes from requesting resources in such
a way that any deadlock occurs. It is not necessary
that all unsafe states are deadlocks; an unsafe state
may lead to a deadlock.

Deadlock
Deadlock
A SYSTEM MODEL
• A system model or structure consists of a fixed number of
resources to be circulated among some opposing processes. The
resources are then partitioned into numerous types, each consisting
of some specific quantity of identical instances. Memory space,
CPU cycles, directories and files, I/O devices like keyboards,
printers and CD-DVD drives are prime examples of resource types.
When a system has 2 CPUs, then the resource type CPU got two
instances.

Deadlock
SYSTEM MODEL

• Under the standard mode of operation, any process may use a

resource in only the below-mentioned sequence:
[Link]: When the request can't be approved immediately (where
the case may be when another process is utilizing the resource),
then the requesting job must remain waited until it can obtain the
resource.
[Link]: The process can run on the resource (like when the resource is
a printer, its job/process is to print on the printer).
• Release: The process releases the resource (like, terminating or
exiting any specific process).

Deadlock
DEADLOCK SYSTEM
MODEL
• Resource types R1, R2, . . ., Rm
CPU cycles, memory space, I/O devices
• Each resource type Ri has Wi instances.
• Each process utilizes a resource as follows:
• request
• use
• release

Deadlock
Deadlock
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. Let's see the
types of vertices and edges in detail.
•

Deadlock
RESOURCE-ALLOCATION
GRAPH
A 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 P1  Rj
• assignment edge – directed edge Rj  Pi

Deadlock
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

Deadlock
•The resource can be of two types:
[Link] Instance - It contains the single instance of the
resource, and is represented by a single dot inside the rectangle
which is the resource vertex.
[Link] Instance - It contains the multiple instances of the
resource, and is represented by multiple (more than one) dots
inside the rectangle.

Deadlock
RULE-01:
•In a Resource Allocation Graph where all the resources are single
instance,
•If a cycle is being formed, then system is in a deadlock state.
•If no cycle is being formed, then system is not in a deadlock
state.

Deadlock
RULE-02:
• In a Resource Allocation Graph where all the resources
are NOT single instance,
• If a cycle is being formed, then system may be in a deadlock state.
• Banker’s Algorithm is applied to confirm whether system is in a
deadlock state or not.
• If no cycle is being formed, then system is not in a deadlock state.
• Presence of a cycle is a necessary but not a sufficient condition for
the occurrence of deadlock.

Deadlock
Deadlock
BANKERS ALGORITHM

Deadlock
Deadlock
MULTI-INSTANCE

• It means that resource has multiple instances.

• In simple words we can say that a particular resource can fulfil the
need of multiple process requests.

Deadlock
MULTIPLE INSTANCE

Deadlock
EXPLANATION
• Current availability: (0,0)
• With the current availability we can fulfil the request of P3, because P3 is demanding nothing. So, P3
will get terminated after executing completely. Now the availability has changed as resource allocated to
P3 has been released by P3.
• Current availability: (0,1)
• Now, with the current availability we can fulfil the request of P1, because it requires 1 resource of R2
and we have it. So, P1 will get terminated after getting executed completely and the resource allocated to
P1 will be released.
• Current availability: (1,1)
• With this availability we can fulfil the request of P2.
• So, no deadlock is present in the system.
• This example contains circular wait but no deadlock is present, because this is multi-instance that only
happen in the case of single-instance.

Deadlock
EXAMPLE OF A RESOURCE
ALLOCATION GRAPH

Deadlock
RESOURCE ALLOCATION GRAPH
WITH A DEADLOCK

Deadlock
RESOURCE ALLOCATION GRAPH WITH A CYCLE BUT NO
DEADLOCK

Deadlock
BASIC FACTS
• If graph contains no cycles  no deadlock.
• If graph contains a cycle 
• if only one instance per resource type, then deadlock.
• if several instances per resource type, possibility of
deadlock.

Deadlock
METHODS FOR HANDLING
DEADLOCKS
• Ensure that the system will never enter a deadlock state.
• Allow the system to enter a deadlock state and then recover.
• Ignore the problem and pretend that deadlocks never occur in the
system; used by most operating systems, including UNIX.

Deadlock
DEADLOCK PREVENTION
Restrain the ways request can be made.
• Mutual Exclusion – not required for sharable resources;
must hold for non sharable resources.
• Hold and Wait – must guarantee that whenever a process
requests a resource, it does not hold any other resources.
• To avoid this, the process can acquire all the resources that it needs, before
starting its execution and after that, it starts its execution. In this way, the process
need not wait for some resources during its execution. But this method is not
practical because we can't know the resources required by a process in advance,
before its execution. So, another way of avoiding hold and wait can be the "Do
not hold" technique. For example, if the process needs 10 resources R1, R2,
R3,...., R10. At a particular time, we can provide R1, R2, R3, and R4. After
performing the jobs on these resources, the process needs to release these
resources and then the other resources will be provided to the process. In this
way, we can avoid the hold and wait condition.

Deadlock
DEADLOCK PREVENTION
(CONT.)
• No Preemption –
• If a process that is holding some resources requests another resource
that cannot be immediately allocated to it, then all resources
currently being held are released.
• Preempted resources are added to the list of resources for which the
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.
• Circular Wait – impose a total ordering of all resource types, and
require that each process requests resources in an increasing order
of enumeration.

Deadlock
DEADLOCK AVOIDANCE
•
• In the deadlock avoidance technique, we try to avoid
deadlock to happen in our system. Here, the system
wants to be in a safe state always. So, the system
maintains a set of data and using that data it decides
whether a new request should be entertained or not.
If the system is going into the bad state by taking
that new request, then the system will avoid those
kinds of request and will ignore the request. So, if a
request is made for a resource, from a system, then
that request should only be approved if the resulting
state of the system is safe i.e. not going into
deadlock.

Deadlock
STATE
• What is the state?
• The state of the system informs that if resources are allocated to
different processes then the system undergoes deadlock or not.
• What is a safe state? Describe how a safe state helps to avoid
deadlock
• If the system can allocate resources to the process in such a way
that it can avoid deadlock. Then the system is in a safe state.
• What is an unsafe state?
• If the system can’t allocate resources to the process safely, then
the system is in an unsafe state.
• Note: Unsafe state not always cause deadlock.

Deadlock
PREVENTION VS
• The main
AVOIDANCE
difference between deadlock prevention and deadlock
avoidance is that deadlock prevention ensures that at least one of the
necessary conditions to cause a deadlock will never occur while
deadlock avoidance ensures that the system will not enter an unsafe
state.
• Information
• In deadlock prevention, the system does not require information of
the existing resources, resource availability and resource requests
whereas, in deadlock avoidance, the system requires information on
the existing resources, resource availability and resource requests to
find whether the system is in a safe or unsafe state. Hence, this is
another difference between deadlock prevention and deadlock
avoidance.

Deadlock
DEADLOCK AVOIDANCE
Requires that the system has some additional a priori information
available.
• Simplest and most useful model requires that each process
declare the maximum number of resources of each type
that it may need.
• The deadlock-avoidance algorithm dynamically examines
the resource-allocation state to ensure that there can never
be a circular-wait condition.
• Resource-allocation state is defined by the number of
available and allocated resources, and the maximum
demands of the processes.

Deadlock
SAFE STATE
• When a process requests an available resource, system must decide
if immediate allocation leaves the system in a safe state.
• System is in safe state if there exists a safe sequence of all processes.
• Sequence <P1, P2, …, Pn> is safe if for each Pi, the resources that Pi
can still request can be satisfied by currently available resources +
resources held by all the Pj, with j<I.
• 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.

Deadlock
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.

Deadlock
SAFE, UNSAFE , DEADLOCK
STATE SPACES

Deadlock
RESOURCE-ALLOCATION
GRAPH ALGORITHM
• if we have one instace of each resource we use a variant of RAG
for deadlock avoidance
• Claim edge Pi  Rj indicated that process Pj may request resource
Rj; represented by a dashed line.
• when a process makes a request Rj then
• Claim edge converts to request edge when a process requests a
resource.
• When a resource is released by a process, assignment edge
reconverts to a claim edge.
• Resources must be claimed a priori in the system.

Deadlock
RESOURCE-ALLOCATION GRAPH FOR DEADLOCK
AVOIDANCE

Deadlock
BANKER’S ALGORITHM
• RAG not applicable with multiple instances

• Applicable to Multiple instances.

• Each process must declare the maximum number of instance of each
resource type that it may need. But should not exceed the total number
of resources.
• When a process requests a resource it must determine whether the
allocation would lead the sytsem into safe or unsafe .
• If the system will be in safe state the resources will be allocated (only),
otherwise not (unsafe)
• When a process gets all its resources it must return them in a finite
amount of time.

Deadlock
DATA STRUCTURES FOR THE 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. Defines the max demand of each process If
Max [i,j] = k, then process Pi may request at most k instances of
resource type Rj.
• Allocation: n x m matrix. Defines the currently available
resources. If Allocation[i,j] = k then Pi is currently allocated k
instances of Rj.
• Need: 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].

Deadlock
SAFETY ALGORITHM
Finding out whether the system is safe or not
Let Work and Finish be vectors of length m and n, respectively. Initialize:
Work := Available (keeps track of available resources)
Finish [i] = false for i - 1,3, …, n.
This means, initially, no process has finished and the number of available resources is represented by
the Available array.

2. Find an i such that both:

(a) Finish [i] = false
(b) Needi  Work
• If there is no such i present, then proceed to step 4.
• It means, we need to find an unfinished process whose needs can be satisfied by the available resources. If no such
process exists, just go to step 4.

3. Work := Work + Allocationi

Finish[i] := true
When an unfinished process is found, then the resources are allocated and the process is marked finished.
And then, the loop is repeated to check the same for all other processes.
go to step 2.
4. If Finish [i] = true for all i, then the system is in a safe state.
5. That means if all processes are finished, then the system is in safe state.
• This algorithm may require an order of mxn² operations in order to determine whether a state is safe or not.

Deadlock
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

Deadlock
Deadlock
DEADLOCK DETECTION
• If a system does not employ either a deadlock-prevention or
deadlock-avoidance algorithm, then there are chances of
occurrence of a deadlock.
• In this case, the system may provide two things:
• An algorithm is used to examines the state of the system in order
to determine whether a deadlock has occurred.
• An algorithm that is used to recover from the deadlock

Deadlock
DEADLOCK DETECTION

• A deadlock detection algorithm is a technique used

by an operating system to identify deadlocks in the
system. This algorithm checks the status of
processes and resources to determine whether any
deadlock has occurred and takes appropriate actions
to recover from the deadlock.

Deadlock
DEADLOCK DETECTION
• Deadlock detection algorithms work by regularly
checking the current state of resource usage in the
system. They often use a visual tool called a resource
allocation graph. This graph shows which processes
are using which resources and which resources each
process is waiting for

Deadlock
SINGLE INSTANCE OF
EACH RESOURCE TYPE
• If each resource category has a single instance, then we can use a
variation of the resource-allocation graph known as a wait-for
graph.
• A wait-for graph can be constructed from a resource-allocation
graph by eliminating the resources and collapsing the associated
edges, as shown in the figure below.
• An arc from Pi to Pj in a wait-for graph indicates that process Pi is
waiting for a resource that process Pj is currently holding.

Deadlock
(A) RESOURCE
ALLOCATION GRAPH. (B)
CORRESPONDING WAIT-
FOR GRAPH

Deadlock
SAFETY ALGORITHM
• The above scheme that is a wait-for graph is not applicable to the
resource-allocation system having multiple instances of each
resource type. Now we will move towards a deadlock detection
algorithm that is is applicable for such systems.
• This algorithm mainly uses several time-varying data structures
that are similar to those used in Banker's Algorithm and these are
as follows:

Deadlock
DATA STRUCTURES
USED
• 1. Available

• It is an array of length m. It represents the number of available resources of each type.

• 2. Allocation
• It is an n x m matrix which represents the number of resources of each type currently allocated to each process.

• 3. Request
• It is an n*m matrix that is used to indicate the request of each process; if Request[i][j] equals to k, then process Pi is
requesting k more instances of resource type Ri.

• Allocation and Request are taken as vectors and referred to as Allocation and Request. The Given detection algorithm is
simply used to investigate every possible allocation sequence for the processes that remain to be completed.

• [Link] Work and Finish be vectors of length m and n, respectively. Initialize :

Deadlock
DETECTION-ALGORITHM
USAGE
• When, and how often, to invoke depends on:
• How often a deadlock is likely to occur?
• How many processes will need to be rolled back
• 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.

Deadlock
ADVANTAGES OF DEADLOCK
DETECTION ALGORITHMS
• Improved System Stability: Deadlocks are a major
concern in operating systems , and detecting and
resolving deadlocks can help to improve the stability
of the system.
• Better Resource Utilization: By detecting deadlocks
and freeing resources, the operating system can
ensure that resources are efficiently utilized and that
the system remains responsive to user requests.

Deadlock
• Easy Implementation: Some deadlock detection
algorithms, such as the Wait-For Graph , are
relatively simple to implement and can be used in a
wide range of operating systems and systems with
different resource allocation and synchronization
requirements.

Deadlock
DISADVANTAGES OF DEADLOCK
DETECTION ALGORITHMS
• Performance Overhead: Deadlock detection
algorithms can introduce a significant overhead in
terms of performance, as the system must regularly
check for deadlocks and take appropriate action.
• Complexity: Some deadlock detection algorithms,
such as the Resource Allocation Graph or
Timestamping, are more complex to implement and
require a deeper understanding of the system and its
behavior

Deadlock
Deadlock
RECOVERY FROM
DEADLOCK
• Deadlock recovery performs when a deadlock is detected.
• When deadlock detected, then our system stops working, and after
the recovery of the deadlock, our system start working again.
• Therefore, after the detection of deadlock, a method/way must
require to recover that deadlock to run the system again. The
method/way is called as deadlock recovery.
• Here are various ways of deadlock recovery that we will discuss
briefly in this tutorial.
• Deadlock recovery through preemption
• Deadlock recovery through rollback
• Deadlock recovery through killing processes

Deadlock
CONTINUED

• There one possibility and that is to inform the operator about the
deadlock and let him deal with this problem manually.
• Another possibility is to let the system recover from the deadlock
automatically. These are two options that are mainly used to break
the deadlock.

Deadlock
RECOVERY FROM
DEADLOCK

Deadlock
RECOVERY FROM DEADLOCK: PROCESS
TERMINATION
• Abort all deadlocked processes.
• Abort one process at a time until the deadlock cycle is eliminated.
• In which order should we choose to abort?
• Priority of the process.
• How long process has computed, and how much longer to
completion.
• Resources the process has used.
• Resources process needs to complete.
• How many processes will need to be terminated.
• Is process interactive or batch?

Deadlock
ABORTING ALL
DEADLOCKED PROCESSES
Clearly, this method is helpful in breaking the cycle of deadlock, but
this is an expensive approach. This approach is not suggestable but
can be used if the problem becomes very serious. If all the processes
are killed then there may occur insufficiency in the system and all
processes will execute again from starting.

Deadlock
ABORT ONE PROCESS AT A TIME UNTIL THE
ELIMINATION OF THE DEADLOCK CYCLE
This method can be used but we have to decide which process to kill
and this method incurs considerable overhead. The process that has
done the least amount of work is killed by the Operating system
firstly.

Deadlock
RECOVERY FROM DEADLOCK: RESOURCE PREEMPTION

• In order to eliminate the deadlock by using resource preemption,

we will successively preempt some resources from processes and
will give these resources to some other processes until the
deadlock cycle is broken and there is a possibility that the system
will recover from deadlock. But there are chances that the system
goes into starvation.
• Selecting a victim – minimize cost.
• Rollback – return to some safe state, restart process fro that state.
• Starvation – same process may always be picked as victim,
include number of rollback in cost factor.

Deadlock
COMBINED APPROACH TO
DEADLOCK HANDLING
• Combine the three basic approaches
• prevention
• avoidance
• detection
allowing the use of the optimal approach for each of resources in
the system.
• Partition resources into hierarchically ordered classes.
• Use most appropriate technique for handling deadlocks within each
class.

Deadlock
QUESTION

Deadlock
QUESTIONS

Deadlock
QUESTION

Deadlock
QUESTIONS

Deadlock
BANKERS ALGORITHM
• Banker's algorithm is a deadlock avoidance algorithm.
It is named so because this algorithm is used in
banking systems to determine whether a loan can be
granted or not.

• Consider there are n account holders in a bank and

the sum of the money in all of their accounts is S.
Every time a loan has to be granted by the bank, it
subtracts the loan amount from the total money the
bank has. Then it checks if that difference is greater
than S. It is done because, only then, the bank would
have enough money even if all the n account holders
draw all their money at once.

Deadlock
DATA STRUCTURES OF
BANKER'S ALGORITHM
1. Available
•It is an array of length m. It represents the number of
available resources of each type. If Available[j] = k,
then there are k instances available, of resource type
Rj.

Deadlock
2. MAX
• It is an n x m matrix which represents the maximum
number of instances of each resource that a process can
request. If Max[i][j] = k, then the process Pi can request
atmost k instances of resource type Rj.

Deadlock
3. ALLOCATION
• It is an n x m matrix which represents the number of
resources of each type currently allocated to each
process. If Allocation[i][j] = k, then process Pi is currently
allocated k instances of resource type Rj.

Deadlock
4. NEED
• It is a two-dimensional array. It is an n x m matrix
which indicates the remaining resource needs of each
process. If Need[i][j] = k, then process Pi may need k
more instances of resource type Rj to complete its
task.

Deadlock
• Need[i][j] = Max[i][j] - Allocation [i][j]

Deadlock
BANKERS ALGORITHM
NUMERICAL
• Consider a system that contains five processes P1,
P2, P3, P4, P5 and the three resource types A, B and
C. Following are the resources types: A has 10, B has
5 and the resource type C has 7 instances.

Deadlock
Deadlock
• Context of the need matrix is as follows:

• Need [i] = Max [i] - Allocation [i]

• Need for P1: (7, 5, 3) - (0, 1, 0) = 7, 4, 3
• Need for P2: (3, 2, 2) - (2, 0, 0) = 1, 2, 2
• Need for P3: (9, 0, 2) - (3, 0, 2) = 6, 0, 0
• Need for P4: (2, 2, 2) - (2, 1, 1) = 0, 1, 1
• Need for P5: (4, 3, 3) - (0, 0, 2) = 4, 3, 1

Deadlock
Deadlock
• Hence, we created the context of need matrix.

• Ans. 2: Apply the Banker's Algorithm:

• Available Resources of A, B and C are 3, 3, and 2.

• Now we check if each type of resource request is available for each

process.

• Step 1: For Process P1:

• Need <= Available

• 7, 4, 3 <= 3, 3, 2 condition is false.

Deadlock
• So, we examine another process, P2.

• Step 2: For Process P2:

• Need <= Available

• 1, 2, 2 <= 3, 3, 2 condition true

• New available = available + Allocation

• (3, 3, 2) + (2, 0, 0) => 5, 3, 2

Deadlock
• Similarly, we examine another process P3.

• Step 3: For Process P3:

• P3 Need <= Available

• 6, 0, 0 < = 5, 3, 2 condition is false.

• Similarly, we examine another process, P4.

Deadlock
• Step 4: For Process P4:

• P4 Need <= Available

• 0, 1, 1 <= 5, 3, 2 condition is true

• New Available resource = Available + Allocation

• 5, 3, 2 + 2, 1, 1 => 7, 4, 3

Deadlock
• Similarly, we examine another process P5.

• Step 5: For Process P5:

• P5 Need <= Available

• 4, 3, 1 <= 7, 4, 3 condition is true

• New available resource = Available + Allocation

• 7, 4, 3 + 0, 0, 2 => 7, 4, 5

• Now, we again examine each type of resource request for processes P1 and
P3.

Deadlock
• Step 6: For Process P1:

• P1 Need <= Available

• 7, 4, 3 <= 7, 4, 5 condition is true

• New Available Resource = Available + Allocation

• 7, 4, 5 + 0, 1, 0 => 7, 5, 5

Deadlock
• So, we examine another process P2.

• Step 7: For Process P3:

• P3 Need <= Available

• 6, 0, 0 <= 7, 5, 5 condition is true

• New Available Resource = Available + Allocation

• 7, 5, 5 + 3, 0, 2 => 10, 5, 7

Deadlock
• Hence, we execute the banker's algorithm to find
the safe state and the safe sequence like P2, P4, P5,
P1 and P3.

Deadlock