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 = {Po, P1, P2, ... , Pn} of waiting processes such that Po 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 Pn is waiting for a resource that is held by P0.

- P = {Pl, P2, ... ,Pn}, the set consisting of all the processes in the system.
- R = {Rl, R2, ... , Rm}, the set consisting of all resource types in the system.
- Directed Edge Pi → Pj is known as request edge.
- Directed Edge Pj → Pi is known as assignment edge.
- One instance of resource type R1.
- Two instances of resource type R2.
- One instance of resource type R3.
- Three instances of resource type R4

- Process P1 is holding an instance of resource type R2 and is waiting for an instance of resource type R1.
- Process P2 is holding an instance of R1 and R2 is waiting for an instance of resource type R3.
- Process P3 is holding an instance of R3.
- Basic facts related to resource allocation graphs are given below
- If only one instance per resource type, then deadlock.
- If several instances per resource type, then there may or may not be deadlock.
- 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.
- Elimination of “Mutual Exclusion” Condition
- Elimination of “Hold and Wait” Condition
- Elimination of “No-preemption” Condition
- Elimination of “Circular Wait” Condition

- Max n x m matrix. If max [i, j] = k, then process Pi may request at most k instances of resource type Rj.
- Allocation n x m matrix. If allocation [i, j] = k, then Pi is currently allocated k instances of Rj.
- Need n x m matrix. 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]
- Safety Algorithm
Work = Available
Finish [i] = False (for i = 1, 2, ... ; n)
Step 2 Find i such that both- Finish [i] = False
- Need<= Work
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.
- Pi → Pj if Pi is waiting Pj
- 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 n2 operations, where n is the number of vertices in the graph.

- 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 Test Series check the following link:
Click Here to Avail GATE CSE Test Series!(110+ Mock Tests)
Get unlimited access to 21+ structured Live Courses all 110+ mock tests with Online Classroom Program for GATE CS & PSU Exams:
Click here to AvailOnline Classroom Program for Computer Science
Thanks
Comments
write a comment