Deadlock Study Notes for GATE & Computer Science Engineering Exams : GATE & PSU CS

Deadlock may be defined as a permanent blocking of processes in a multi-programming operating system, when a set of processes either compete for the same system resources or communicate with each other and wait for each other to complete their task first. Generally, deadlock problem involves conflicting needs of same resources by two or more processes.

Necessary Conditions for Deadlock: If the following four conditions occur simultaneously in a system, then a deadlock may occur

Mutual Exclusion: Resources must be allocated to processes at any time in an exclusive manner and not on a shared basis for a deadlock to be possible. If another process requests that resource, the requesting process must be delayed until the resource has been released.
Hold and Wait Condition: Even if a process holds certain resources at any moment, it should be possible for it to request for new ones. It should not give up (release) the already held resources to be able to request for new ones. If it is not true, a deadlock can never take place.
No Preemption Condition: Resources can't be preempted. A resource can be released only voluntarily by the process holding it, after that process has completed its task.
Circular Wait Condition: There must exist a set = {P_o, P₁, P₂, ... , P_n} of waiting processes such that Po is waiting for a resource that is held by P₁, P₁ is waiting for a resource that is held by P₂, ... , P_{n -}₁ is waiting for a resource that is held by P_n and P_n is waiting for a resource that is held by P₀.

Resource Allocation Graph: The resource allocation graph consists of a set of vertices V and a set of edges E. Set of vertices V is partitioned into two types

P = {P_l, P₂, ... ,P_n}, the set consisting of all the processes in the system.
R = {R_l, R₂, ... , R_m}, the set consisting of all resource types in the system.

Directed Edge P_i → P_j is known as request edge.
Directed Edge P_j → P_i is known as assignment edge.

Resource Instance

One instance of resource type R₁.
Two instances of resource type R₂.
One instance of resource type R₃.
Three instances of resource type R₄

Process States

Process P₁ is holding an instance of resource type R₂ and is waiting for an instance of resource type R₁.
Process P₂ is holding an instance of R₁ and R₂ is waiting for an instance of resource type R₃.
Process P₃ is holding an instance of R₃.
Basic facts related to resource allocation graphs are given below

Note: If graph consists no cycle it means there is no deadlock in the system. If graph contains cycle

If only one instance per resource type, then deadlock.
If several instances per resource type, then there may or may not be deadlock.

Deadlock Handling Strategies In general, there are four strategies of dealing with deadlock problem:

The Ostrich Approach: Just ignore the deadlock problem altogether.
Deadlock Detection and Recovery: Detect deadlock and, when it occurs, take steps to recover.
Deadlock Avoidance: Avoid deadlock by careful resource scheduling.
Deadlock Prevention: Prevent deadlock by resource scheduling so as to negate at least one of the four conditions.

Deadlock Prevention Deadlock prevention is a set of methods for ensuring that atleast one of the necessary conditions can't hold.

Elimination of “Mutual Exclusion” Condition
Elimination of “Hold and Wait” Condition
Elimination of “No-preemption” Condition
Elimination of “Circular Wait” Condition

Deadlock Avoidance This approach to the deadlock problem anticipates deadlock before it actually occurs. A deadlock avoidance algorithm dynamically examines the resource allocation state to ensure that a circular wait condition can never exist. The resource allocation state is defined by the number of available and allocated resources and the maximum demands of the processes. Safe State: A state is safe, if the system can allocate resources to each process and still avoid a deadlock.

A system is in safe state, if there exists a safe sequence of all processes. A deadlock state is an unsafe state. Not all unsafe states cause deadlocks. It is important to note that an unsafe state does not imply the existence or even the eventual existence a deadlock. What an unsafe state does imply is simply that some unfortunate sequence of events might lead to a deadlock. Banker's Algorithm: Data structures for Banker's algorithm available. Vector of length m. If available [j] = k, there are k instances of resource type R_j available.

Max n x m matrix. If max [i, j] = k, then process P_i may request at most k instances of resource type R_j.
Allocation n x m matrix. If allocation [i, j] = k, then P_i is currently allocated k instances of R_j.
Need n x m matrix. If need [i, j] = k, then P_i may need k more instances of R_j to complete its task.

Need [i, j] = max [i, j] - allocation [i, j]

Safety Algorithm

Step 1 Let work and finish be vectors of length m and n, respectively. Initialize

Work = Available

Finish [i] = False (for i = 1, 2, ... ; n)

Step 2 Find i such that both

Finish [i] = False
Need<= Work

If no such i exists, go to step 4.

Step 3 Work = Work + Allocation Finish [i] = True Go to step 2. Step 4 Finish [i] = True (for all i) Then, the system is in a safe system

Deadlock Detection

Allow system to enter deadlock state and then there is (i) Detection algorithm (ii) Recovery scheme Single instance of each resource type

Maintain wait for graph.
Nodes are processes.
P_i → P_j if P_i is waiting P_j
Periodically invoke an algorithm that searches for a cycle in the graph.
An algorithm to detect a cycle in a graph requires an order of n² operations, where n is the number of vertices in the graph.

Recovery Scheme

Temporarily prevent resources from deadlocked processes.
Back off a process to some check point allowing preemption of a needed resource and restarting the process at the checkpoint later.
Successively kill processes until the system is deadlock free.

You can go with the detailed champion study plan for GATE CS 2021 from the following link:

Detailed GATE CSE 2021 Champion Study Plan

Candidates can also practice 110+ Mock tests for exams like GATE, ISRO, DRDO, BARC, NIELIT, etc. with the Gradeup Green Card check the following link: