Conditions for Deadlock in Operating System

What is the Condition for Deadlock?

In the system, the deadlock occurs when the system has these four conditions simultaneously that are as follows:

• Mutual Exclusion
• No-preemption
• Hold & wait
• Circular wait

For a deadlock to occur, all four conditions must be met. The impasse is broken if any one of them is averted or resolved.

Mutual Exclusion

When two people meet on the landings, they cannot just stroll through since there is only enough room for one person. The first prerequisite for the occurrence of the deadlock is to enable only one person (or process) to utilize the step between them (or the resource).

• The resource has to be allocated to only one process, which is freely available.
• There should be a one-to-one relationship between the resource and process.

No-preemption

To overcome the deadlock, just cancel one of the processes and let the others continue. However, the Operating System does not. It provides resources to the processors for as long as the job requires till it is accomplished. As a result, there is no need for a temporary reallocation of resources. It's the third deadlock condition.

• The resource has to be voluntarily released by the process after completing the execution.
• It is not allowed to preempt the resource from the process forcefully.

Hold & wait

Holding occurs when two individuals refuse to retreat and defend their territory. This is the next condition that must be met in order to break the deadlock.

• A process acquires resources piecemeal. While it awaits allocation and assignment of other resources, it holds on to its acquired resources.
• In other words, a process waits for some resources while holding another resource simultaneously.

Circular wait

Circular wait occurs when two persons refuse to retreat and wait for each other to recede so that they can finish their work. It's the final thing that can cause a deadlock. Processes waiting for resources from the others form a circular chain. In that chain, each process holds at least one unit resource, which is demanded by the next process in the chain.

Suppose there exists a set {P₀, P₁,..., P₀} of waiting processes such that the process P₀ is waiting for a resource that P1 holds, and the process P₁ is waiting for a resource that P2 holds. The resource allocation graph is:

Symbol and Representation of Condition for Deadlock

The circle will represent the process as

Resources will be represented with rectangle blocks as

If the process P₁ is requested a resource, then it is represented as

If the process P₁ is holding an instance, then it is represented as

Condition for Deadlock Prevention

• 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
  1. Finish [i] = False
  2. 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 the system to enter a 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 checkpoint allowing preemption of a needed resource and restarting the process at the checkpoint later.
• Successively kill processes until the system is deadlock-free.

Condition for Deadlock Example

The examples of deadlock conditions are mentioned below.

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

• Assume the space is available for allocation of 200Kbytes, and the following sequence of events occurs.

Deadlock occurs if both processes progress to their second request.