DEADLOCK

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.

Examples Of Deadlock

1. The system has 2 tape drives. P1 and P2 each hold one tape drive and each needs
another one.
2. Semaphores A and B, initialized to 1, P0, and P1 are in deadlock as follows:
 P0 executes wait(A) and preempts.
 P1 executes wait(B).
 Now P0 and P1 enter in deadlock.

P0 P1

wait(A); wait(B)

wait(B); wait(A)

3. Assume the space is available for allocation of 200K bytes, and the following sequence of
events occurs.

P0 P1

Request 80KB; Request 70KB;

Request 60KB; Request 80KB;

Deadlock occurs if both processes progress to their second request.

CHARACTERISTICS OF DEADLOCK
1. Mutual Exclusion: Processes contend for exclusive control over resources. Only one
process can use a resource at a time.
2. Hold and Wait: Processes hold resources already allocated to them while waiting for
additional resources. A process may request additional resources while holding onto its
current resources.
3. No Preemption: Resources cannot be forcibly taken away from a process; a process must
voluntarily release resources it holds.
4. Circular Wait: A circular chain of processes exists, where each process holds a resource that
the next process in the chain needs. This creates a cycle of dependencies.
RESOURCE ALLOCATION GRAPH
 A resource allocation graphs shows which resource is held by which process and
which process is waiting for a resource of a specific kind. It is amazing and
straight – forward tool to outline how interacting processes can deadlock.
 Therefore, resource allocation graph describe what the condition of the system
as far as process and resources are concern like what number of resources are
allocated and what is the request of each process.
 Everything can be represented in terms of graph. One of the benefit of having
a graph is, sometimes it is conveivable to see a deadlock straight forward by
utilizing RAG and however you probably won’t realize that by taking a glance at
the table.

RAG also contains vertices and edges. In RAG vertices are two types :

1. Process Vertex: Every process will be represented as a process vertex. Generally,

the process will be represented with a circle.
2. Resource Vertex: Every resource will be represented as a resource vertex. It is
also two types:
 Single instance type resource: It represents as a box, inside the box, there
will be one dot.So the number of dots indicate how many instances are
present of each resource type.
 Multi-resource instance type resource: It also represents as a box, inside
the box, there will be many dots present.

How many Types of Edges are there in RAG?

Now coming to the edges of RAG.There are two types of edges in RAG –
 Assign Edge: If you already assign a resource to a process then it is called
Assign edge.
 Request Edge: It means in future the process might want some resource to
complete the execution, that is called request edge.

DEADLOCK PREVENTION
 Eliminate Mutual Exclusion: It is not possible to dis-satisfy the mutual
exclusion because some resources, such as the tape drive and printer, are
inherently non-shareable.
 Eliminate Hold and wait: Allocate all required resources to the process before
the start of its execution, this way hold and wait condition is eliminated but it
will lead to low device utilization. for example, if a process requires a printer at
a later time and we have allocated a printer before the start of its execution
printer will remain blocked till it has completed its execution. The process will
make a new request for resources after releasing the current set of resources.
This solution may lead to starvation.
  Eliminate No Preemption : Preempt resources from the process when
resources are required by other high-priority processes.
 Eliminate Circular Wait : Each resource will be assigned a numerical number. A
process can request the resources to increase/decrease. order of
numbering. For Example, if the P1 process is allocated R5 resources, now next
time if P1 asks for R4, R3 lesser than R5 such a request will not be granted, only
a request for resources more than R5 will be granted.
 Detection and Recovery: Another approach to dealing with deadlocks is to
detect and recover from them when they occur. This can involve killing one or
more of the processes involved in the deadlock or releasing some of the
resources they hold.

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- i.e. a
few resource units at a time- subject to the maximum number declared by it
and uses a worst case analysis technique to check for the possibility of future
deadlocks.

DEADLOCK DETECTION
1. If resources have a single instance –
In this case for Deadlock detection, we can run an algorithm to check for the cycle in
the Resource Allocation Graph. The presence of a cycle in the graph is a sufficient
condition for deadlock.

In the above diagram, resource 1 and resource 2 have single instances. There is a
cycle R1 → P1 → R2 → P2. So, Deadlock is Confirmed.

2. If there are multiple instances of resources –

Detection of the cycle is necessary but not a sufficient condition for deadlock
detection, in this case, the system may or may not be in deadlock varies according
to different situations.
3. Wait-For Graph Algorithm –
The Wait-For Graph Algorithm is a deadlock detection algorithm used to detect
deadlocks in a system where resources can have multiple instances. The algorithm
works by constructing a Wait-For Graph, which is a directed graph that represents
the dependencies between processes and resources.

DEADLOCK RECOVERY
A traditional operating system such as Windows doesn’t deal with deadlock
recovery as it is a time and space-consuming process. Real-time operating systems
use Deadlock recovery.

1. Killing the process –

Killing all the processes involved in the deadlock. Killing process one by
one. After killing each process check for deadlock again and keep repeating
the process till the system recovers from deadlock. Killing all the processes
one by one helps a system to break circular wait conditions.
 2. Resource Preemption –
Resources are preempted from the processes involved in the deadlock, and
preempted resources are allocated to other processes so that there is a
possibility of recovering the system from the deadlock. In this case, the
system goes into starvation.
3. Concurrency Control – Concurrency control mechanisms are used to
prevent data inconsistencies in systems with multiple concurrent
processes. These mechanisms ensure that concurrent processes do not
access the same data at the same time, which can lead to inconsistencies
and errors. Deadlocks can occur in concurrent systems when two or more
processes are blocked, waiting for each other to release the resources they
need. This can result in a system-wide stall, where no process can make
progress. Concurrency control mechanisms can help prevent deadlocks by
managing access to shared resources and ensuring that concurrent
processes do not interfere with each other.

Advantages of Deadlock Detection and Recovery in Operating Systems:

1. Improved System Stability: Deadlocks can cause system-wide stalls, and

detecting and resolving deadlocks can help to improve the stability of the
system.
2. Better Resource Utilization: By detecting and resolving deadlocks, the
operating system can ensure that resources are efficiently utilized and that
the system remains responsive to user requests.
3. Better System Design: Deadlock detection and recovery algorithms can
provide insight into the behavior of the system and the relationships
between processes and resources, helping to inform and improve the
design of the system.

Disadvantages of Deadlock Detection and Recovery in Operating Systems:

1. Performance Overhead: Deadlock detection and recovery algorithms can

introduce a significant overhead in terms of performance, as the system
must regularly check for deadlocks and take appropriate action to resolve
them.
2. Complexity: Deadlock detection and recovery algorithms can be complex
to implement, especially if they use advanced techniques such as the
Resource Allocation Graph or Timestamping.
3. False Positives and Negatives: Deadlock detection algorithms are not
perfect and may produce false positives or negatives, indicating the
 presence of deadlocks when they do not exist or failing to detect deadlocks
that do exist.
4. Risk of Data Loss: In some cases, recovery algorithms may require rolling
back the state of one or more processes, leading to data loss or corruption.

LIVELOCK & STARVATION IN DEADLOCK

 Livelock is a situation in concurrent computing where two or more processes or
threads continually change their state in response to the actions of the others,
without making any progress.
 In other words, processes in a livelock are not stuck like in a deadlock, but they
are unable to move forward because they are too responsive to each other's
actions.

 Starvation and deadlock are related concepts in the context of concurrent

computing, but they refer to different issues. Starvation happens when a
process is perpetually denied access to a resource it needs to complete its
execution.
 It occurs in scenarios where other processes consistently acquire and release
resources, preventing a particular process from making progress.

BANKER ALGORITHM
 The Banker's algorithm is a resource allocation and deadlock avoidance
algorithm used in operating systems. It was developed by Edsger Dijkstra and
named after the concept of a banker who safely lends out money only if it
ensures that the borrower can repay.
 Similarly, the Banker's algorithm ensures that the system does not enter an
unsafe state where deadlock might occur.

The key components and steps of the Banker's algorithm:

1. Available Resources: The system maintains information about the number of

available instances of each type of resource.
 2. Maximum Claim Matrix: A matrix that defines the maximum number of
resources of each type that a process may request. It indicates the maximum
demand of each process.
3. Allocation Matrix: A matrix that represents the number of resources of each
type currently allocated to each process.
4. Need Matrix: A matrix indicating the remaining resource need of each process
(Maximum Claim - Allocation).
5. Request: When a process requests additional resources, the system checks if
the requested resources can be safely allocated without causing deadlock. If
the request is granted, the allocation and need matrices are updated
accordingly.
6. Safety Algorithm: The system employs a safety algorithm to determine if a
particular resource allocation request leaves the system in a safe state,
meaning that it can avoid deadlock. The algorithm simulates the allocation of
resources and checks if there is a safe sequence in which processes can
complete.

The safety algorithm typically works as follows:

a. Initialize a work vector to the available resources.

b. Find a process whose maximum resource needs can be satisfied with the available
resources.

c. Simulate the allocation of resources to that process and update the work vector.

d. Repeat the process until all processes can complete, or it is determined that no
safe sequence exists.