Conditions for Deadlock in Operating System

By Mona Kumari|Updated : August 26th, 2022

Conditions for Deadlock in Operating System is a scenario known as a deadlock that includes the interaction of multiple resources and processes. A deadlock condition occurs in the system when a process cannot proceed because it needs to obtain a resource that is held by another process, but it itself is holding a resource that the other process needs.

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, a deadlock problem involves conflicting needs of the same resources by two or more processes. Here, we will see all the necessary 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 {P0, P1,..., P0} of waiting processes such that the process P0 is waiting for a resource that P1 holds, and the process P1 is waiting for a resource that P2 holds. The resource allocation graph is:

Circular wait

Symbol and Representation of Condition for Deadlock

The circle will represent the process as

Condition for Deadlock

Resources will be represented with rectangle blocks as

Condition for deadlock 2

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

Condition for dead lock 3

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

Condition for deadlock 3

Condition for Deadlock Prevention

Deadlock Handling Strategies In general, there are four strategies for dealing with the deadlock problem:
  1. The Ostrich Approach: Just ignore the deadlock problem altogether.
  2. Deadlock Prevention: Prevent deadlock by resource scheduling so as to negate at least one of the four conditions.
  3. Deadlock Avoidance: Avoid deadlock by careful resource scheduling.
  4. Deadlock Detection and Recovery: Detect deadlock and, when it occurs, take steps to recover.

Deadlock Prevention

Deadlock prevention is a set of methods for ensuring that at least 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 a 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 of 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 are available. Vector of length m. If available [j] = k, there are k instances of resource type Rj available.
  • 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

  • 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.
  • 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.
deadlock condition 2323

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. P0 and P1 are in deadlock as follows:
    (a) P0 executes wait (A) and preempts.
    (b) P1 executes wait (B).
    (c) Now, P0 and P1 enter in deadlock.

P0

P1

wait(A);

wait(B);

wait(B);

wait(A);

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

P0

P1

Request 80KB;

…;

Request 60KB;

Request 70KB;

Request 80KB;

Deadlock occurs if both processes progress to their second request.

Important Topics for Gate Exam
Brittle MaterialCapacitors in Parallel
Capacitors in SeriesCarnot Cycle
Cement TestClamping Circuit
Clipping CircuitCMOS Fabrication
CMOS ConverterColumn Base

Comments

write a comment

FAQs on Conditions for Deadlock

  • A deadlock is a condition where each of the computer processes waits for a resource that is being assigned to some other process. In this situation, none of the processes gets executed since the resource it needs is held by some other process which is also waiting for some other resource to be released.

  • The four conditions that say the deadlock occurs in the system are:

    • Mutual Exclusion
    • No-preemption
    • Hold & wait
    • Circular wait
  • Yes, all these 4 conditions must hold simultaneously for the deadlock occur. If any of these conditions fail, the system can be ensured deadlock-free.

  • No. This follows directly from the hold-and-wait condition. With a single process, it is impossible that the hold and wait condition exists.

  • A resource can only be shared in a mutually exclusive manner. It implies that two processes cannot use the same resource simultaneously.

Follow us for latest updates