DEADLOCK:

A deadlock is a situation where computer programs sharing the same resources are
permanently blocked. As a result of which, each program prevents the other from acquiring the
resources required for its completion.
Resource Allocation Graph:

• A Resource Allocation Graph (RAG) is a visual way to understand how resources are assigned
in an operating system.
• A resource allocation graph is a graph which has two different types of nodes, the process
nodes (represented by circle) and resource nodes (represented by rectangles). For different
instances of a resource, there is a dot in the resources nodes (rectangle).
• An edge from the resource to the process node denotes that it has been acquired by the
process, whereas an edge from the process node to the resource node denotes that the
process is requesting for the resource.

The following tips help us to check the resource allocation graph easily and predict the presence of
cycles.

1. If there is no cycle in the resource allocation graph, there is no deadlock.

 2. If there is a cycle in the graph and each resource has only one instance, then there is a deadlock.
In such a case, the presence of a cycle is the necessary condition in order for deadlock to occur (as
there is only one instance of the resource).

3. If there is a cycle in the graph, and each resource has more than one instance, there may or may
not be a deadlock. Therefore, we conclude that a cycle in the resource allocation graph is a necessary
but not a sufficient condition for a deadlock in the case of multiple instances of a resource

Deadlock Handling-

Deadlock Prevention:

To prevent a deadlock, we must ensure that any one of the following four conditions listed below
should not hold.

1. Mutual exclusion condition: The mutual exclusion condition means that there are some
resources (such as CD Drive, Printer, etc.) which once all cated to a process cannot be taken
back unless and until the process releases it (i.e., non-preemptable resources). So, such
resources should be allocated to only one process at a time. They cannot be shared. Although,
this does not mean that none of the resources can be shared. Certain pre-emptable
resources (such as memory, CPU) can be shared, because they will never result in a deadlock.
So, those resources which cannot be shared are mutually exclusive and this condition needs
to be taken care by OS.
2. Hold and wait condition: In order to ensure this condition never occurs in the system, we have
to devise a strategy such that a process requests all its required resources at one time and
blocks the process until all requests can be granted. This approach has its drawback that a
process cannot know what resources would be required before it actually starts execution,
and sometimes it may have to wait for a long time in order to get all its required resources;
whereas it could have used some of the already allocated resources and released them back
to the pool to be used by other processes. For example, a program may require five CDs, there
should be five free drives before the execution begins, while the program might be using only
one drive to begin with. Thus, this approach leads to serious waste of resources.
3. Non-Preemption condition: The non- preemption condition can be overcome by the following
protocol. If a process is holding some resources and requests another resource that cannot
be immediately allocated to it (which means, the process must wait), then all resources
currently being held are pre-empted (released). These pre empted resources are added to
the list of resources. For example, when a process releases resources, the process may lose
all its work to that point. The major disadvantage of this strategy is the possibility of indefinite
 postponement (starvation). However, this protocol is often applied to resource whose state
can be easily saved and restored later, such as CPU registers and memory space. It cannot
generally be applied to printers and drives.
4. Circular wait condition: A linear ordering of different resources can be used to allocate the
resources to a process, which means that if a pro cess has been allocated a resource, then it
can only be allocated a resource in the linear order.
5.
Deadlock Avoidance:

Deadlock cannot occur by denying any of the four necessary conditions of the deadlock,
whereas a `Deadlock Avoidance’ algorithm dynamically examines the resource-allocation
state to ensure that there can never be a circular wait condition. There are three basic pillars
to attain this objective:
1. Safe state algorithm
2. Resource allocation graph algorithm
3. Banker’s algorithm

1. Safe State
• A safe state can be defined as a state in which there is no deadlock.
• This can be achieved if
1. All the requested resources are allocated to the process.
2. 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 known as unsafe state.

2. Resource Allocation Graph Algorithm: The resource allocation graphs can also be used for dead
lock avoidance. The major limitation of this strategy is that it is not applicable to a resource allocation
system with multiple instances of each resource type

3. Banker’s Algorithm (Proposed by Dijkstra’s)

• Banker’s algorithm is used to avoid deadlocks

1. Basic principle:
• It is similar to a banking system, that is, to ensure that the bank never allocates its available
cash such that it can no longer satisfy the needs of all its customers.
• 2. Working: When a new process enters the system, it must declare the maximum number of
instances of each resources type it may need. This number should not exceed the total number
of resources in the system.
Time Complexity:

Banker’s algorithm considers each request as it occurs,

and checks whether it leads to a safe state or not. If it does, the request is granted; otherwise, it is
postponed for some time later. This algorithm has a time complexity of O(n2), where n is the number
of processes.
Solution: In the whole process, we have never encountered a situation where the condition Needi <
Work does not hold good. Therefore, we can execute our processes in the order [P1, P3, P4, P2, P0]
without encountering the deadlock.