DEADLOCKS,DETECTING AND

RECOVERING FROM
DEADLOCKS
Presented by: group 3 (Muskan 32, Alishfa 10, Haseeb 29,
Amir saleem 26, Saqlain 31, Rayan 14)
Submitted to: Mam Hamna Khalid
Context:
■ Introduction to Deadlock
■ Necessary Conditions for Deadlock
■ Methods for Handling Deadlock (Prevention and Avoidance)
■ Methods for Handling Deadlock (Detection and Recovery)
■ Recovery from Deadlock (Process Termination)
■ Recovery from Deadlock (Resource Preemption) and
Deadlock Ignorance
Introduction to Deadlock:

A process in operating system uses resources in the following way:

1. Requests a resource
2. Use the resource
3. Releases the resource
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.
 Introduction to Deadlock:

Consider an example when two trains are coming toward each

other on the same track and there is only one track, none of the
trains can move once they are in front of each other. A similar
situation occurs in operating systems when there are two or more
processes that hold some resources and wait for resources held by
other(s). 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.
Examples Of Deadlock

• The system has 2 tape drives. P0 and

P1 each hold one tape drive and each
P0 P1
needs another one.
• Semaphores A and B, initialized to 1,
P0, and P1 are in deadlock as follows: wait(A);
wait(B)
1. P0 executes wait(A) and preempts.
2. P1 executes wait(B).
3. Now P0 and P1 enter in deadlock. wait(B); wait(A)
 Necessary Conditions for Deadlock

Deadlock can arise if the following four conditions hold

simultaneously (Necessary Conditions) .

1. No Preemption
2. Circular Wait
3. Hold and Wait
4. Mutual Exclusion
 Necessary Conditions for Deadlock

No Preemption

Preemption in an operating system means the system can

pause a task to let another one run. But using preemption to solve
deadlocks, where processes are stuck waiting for resources, can be
risky. It might make the system unstable or treat processes unfairly.
Instead, operating systems use other methods like deadlock
detection, avoidance, or prevention. These techniques try to either
find and fix deadlocks when they happen or set up rules to stop
them from occurring. So, while preemption can be helpful, it's not
the best fix for deadlocks in operating systems because it can cause
more problems than it solves.
 Necessary Conditions for Deadlock

Circular Wait

Circular wait is a deadlock situation in an operating system where

two or more processes are each waiting for a resource held by another
process in a circular chain. For example, Process A is waiting for a resource
held by Process B, which in turn is waiting for a resource held by Process C,
and so on until one process in the chain is waiting for a resource held by
Process A, completing the circle. This situation prevents any of the
processes involved from progressing, resulting in a deadlock. Circular wait
is one of the four necessary conditions for deadlock, along with mutual
exclusion, hold and wait, and no preemption. To prevent circular wait and
avoid deadlocks, operating systems implement various strategies such as
resource allocation graphs, which help identify and break potential circular
wait scenarios before they lead to deadlock.
 Necessary Conditions for Deadlock

Hold and Wait

Hold and wait is one of the conditions that can lead to deadlock in an
operating system. It occurs when a process holds at least one resource
and is waiting to acquire additional resources that are currently held by
other processes. This situation creates the potential for deadlock
because processes may end up waiting indefinitely for resources to
become available, while still holding onto resources they have
acquired.
 Necessary Conditions for Deadlock

Mutual Exclusion

Mutual exclusion is a fundamental concept in operating systems that ensures only

one process at a time can access a shared resource or critical section. This principle
prevents concurrent access to the resource, which could lead to data corruption or
inconsistency.
For example, if one process is writing to a file, mutual exclusion ensures that no other
process can simultaneously write to the same file, avoiding conflicts and maintaining
data integrity.
Operating systems implement mutual exclusion using techniques such as locks,
semaphores, or mutexes, which allow processes to request exclusive access to resources
and synchronize their execution. By enforcing mutual exclusion, operating systems
facilitate safe and orderly resource sharing among concurrent processes, improving
system reliability and stability.
 Methods for Handling Deadlock (Prevention and Avoidance)

Prevention:

The idea is to not let the system into a deadlock state. This system will make
sure that above mentioned four conditions will not arise. These techniques are very
costly so we use this in cases where our priority is making a system deadlock-free.
One can zoom into each category individually, Prevention is done by negating one of
the above-mentioned necessary conditions for deadlock. Prevention can be done in
four different ways:

1. Eliminate mutual exclusion 3. Allow preemption

2. Solve hold and Wait 4. Circular wait Solution

Methods for Handling Deadlock (Prevention and Avoidance)
Avoidance:

Avoidance is kind of futuristic. By using the strategy

of “Avoidance”, we have to make an assumption. We need to
ensure that all information about resources that the process will
need is known to us before the execution of the process. We use
Banker’s algorithm (Which is in turn a gift from Dijkstra) to
avoid deadlock.

In prevention and avoidance, we get the correctness of data but

performance decreases.
 Methods for Handling Deadlock (Detection and Recovery)

If Deadlock prevention or avoidance is not applied to the

software then we can handle this by deadlock detection and recovery.
which consist of two phases:
1. In the first phase, we examine the state of the process and check
whether there is a deadlock or not in the system.
2. If found deadlock in the first phase then we apply the algorithm for
recovery of the deadlock.
In Deadlock detection and recovery, we get the correctness of data but
performance decreases.
Methods for Handling Deadlock (Detection and Recovery)

Recovery from Deadlock

1. Manual Intervention:

When a deadlock is detected, one option is to inform the operator and let
them handle the situation manually. While this approach allows for human
judgment and decision-making, it can be time-consuming and may not be
feasible in large-scale systems.

2. Automatic Recovery:

An alternative approach is to enable the system to recover from deadlock

automatically. This method involves breaking the deadlock cycle by either
aborting processes or preempting resources. Let’s delve into these
strategies in more detail.
 Recovery from Deadlock (Process Termination)
1. Abort all deadlocked processes:

This approach breaks the deadlock cycle, but it comes at a

significant cost. The processes that were aborted may have executed for
a considerable amount of time, resulting in the loss of partial
computations. These computations may need to be recomputed later.
2. Abort one process at a time:

Instead of aborting all deadlocked processes simultaneously, this

strategy involves selectively aborting one process at a time until the
deadlock cycle is eliminated. However, this incurs overhead as a
deadlock-detection algorithm must be invoked after each process
termination to determine if any processes are still deadlocked.
Recovery from Deadlock (Process Termination)

Factors for choosing the termination order:

– The process’s priority

– Completion time and the progress made so far
– Resources consumed by the process
– Resources required to complete the process
– Number of processes to be terminated
– Process type (interactive or batch)
 Recovery from Deadlock (Resource Preemption)
and Deadlock Ignorance
1. Selecting a victim:
Resource preemption involves choosing which resources and processes
should be preempted to break the deadlock. The selection order aims to
minimize the overall cost of recovery. Factors considered for victim selection
may include the number of resources held by a deadlocked process and the
amount of time the process has consumed.
2. Rollback:
If a resource is preempted from a process, the process cannot continue its
normal execution as it lacks the required resource. Rolling back the process
to a safe state and restarting it is a common approach. Determining a safe
state can be challenging, leading to the use of total rollback, where the
process is aborted and restarted from scratch.
Recovery from Deadlock (Resource Preemption)
and Deadlock Ignorance
3. Starvation prevention:

To prevent resource starvation, it is essential to ensure that the same

process is not always chosen as a victim. If victim selection is solely
based on cost factors, one process might repeatedly lose its resources
and never complete its designated task. To address this, it is advisable to
limit the number of times a process can be chosen as a victim, including
the number of rollbacks in the cost factor.
 Recovery from Deadlock (Resource Preemption)
and Deadlock Ignorance
Deadlock ignorance:
If a deadlock is very rare, then let it happen and reboot the system. This is the approach
that both Windows and UNIX take. we use the ostrich algorithm for deadlock ignorance.
In Deadlock, ignorance performance is better than the above two methods but the
correctness of data is not there.
Safe State:
A safe state can be defined as a state in which there is no deadlock. It is
achievable if:
If a process needs an unavailable resource, it may wait until the same has been released
by a process to which it has already been allocated. if such a sequence does not exist, it
is an unsafe state.
All the requested resources are allocated to the process.
Any Question ?
Thank You !