Deadlock in Operating System

A process enters the waiting state when another process holds the required resource. This situation is called a deadlock. It is common in multi-processing OS where multiple processes share a specific type of resource known as soft lock or software. This resource is mutually exclusive.

One of the examples of deadlock is one-directional traffic, where a bridge is a resource.

 

Deadlock Detection

The resource scheduler detects a deadlock occurrence and helps the OS to track all the resources’ activities. Following methods can help resolve deadlock:

• The OS terminates all the processes involved in deadlock. But this results in the destruction of all the progress made by processes.
• The OS preempts resources from one process and gives it to other processes until the deadlock resolves.

Deadlock Prevention

To prevent a deadlock before it occurs the system checks every transaction before execution. This way if there is even a small chance for deadlock to occur, a process is not allowed to execute.

Deadlock Avoidance

Deadlock avoidance is better than deadlock prevention. As once the deadlock occurs additional information is required, like how the OS should use resources. Thus, deadlock avoidance is a simple and useful model in which each process declares the amount and type of resources that it may need.

Coffman Conditions

For a deadlock to occur following four Coffman conditions need to hold true.

1. Mutual Exclusion: Mutex (Mutual Exclusion) is a type of binary semaphore that helps control access to the shared resources. It also has a priority inheritance mechanism that avoids extended priority inversion problems and allows tasks with higher priority to execute first. Shared resources don’t lead to deadlocks, but resources, like printers and tape drives, need exclusive access.

2. Hold and Wait: Processes hold one or more resources all the while waiting for the one they have requested.

3. Circular Wait: When a process waits for a resource held by another process, which is also waiting for a resource held by a third process, and so on, a circular chain is created. This ordeal is known as circular wait. It forms a circular loop where it is necessary that every process requests resources in increasing order of enumeration.

For example, Process A has Resource B but it needs Resource A and requests it. Similarly, another process, Process B has Resource A but it is requesting Resource B. This situation creates a circular wait loop.

4. No preemptive action: No Preemption means that a resource can only be free when the process holding it finishes execution. If a process requests a resource that is already allocated to another process, the OS frees all resources.

The preempted resources need the list of waiting resources for a process and the process restarts only when it regains the old resource or the one that it is requesting. If the requested resource is available, then it is immediately allocated to the process. If not available then the OS releases the requesting resource from its current process and gives it to the requesting process.

Avoidance Algorithms

A deadlock-avoidance algorithm helps the user assess the resources and their allocation dynamically in order to avoid the situation of circular-wait.

Single instance of a resource type:

• Makes use of a resource-allocation graph.
• It is necessary to have cycles and they are sufficient for Deadlock.

Multiple instances of a resource type:

• Though cycles are necessary they are insufficient for Deadlock.
• Maks use of the banker’s algorithm

Starvation vs Deadlock

Deadlock	Starvation
Occurs when a process gets blocked	The OS blocks low priority processes and allows the high priority processes to execute.
An infinite process	Not an infinite process
Has starvation	Not every starvation has a deadlock
Mutual exclusion and hold and wait happen after deadlock. Preemption and circular wait don’t occur simultaneously.	Happens due to resource management and uncontrolled priority.

Advantages of Deadlock

Following are the advantages of deadlock:

• Advantageous to the processes that perform a single burst of activity.
• No preemption is required.
• Convenient to apply to resources that can save and restore their states easily.
• Compile-time checks help apply it feasibly
• The system design solves problems so no run-time computation is required.

Disadvantages of Deadlock

Following are the limitations of deadlock in OS:

• Delay in process initiation.
• Knowledge of future resources is necessary.
• Frequent preemptions.
• Doesn’t allow incremental resource requests.
• There are inherent preemption losses.

Summary

Deadlock occurs in an OS when a process enters the waiting state as another waiting process is holding its demanded resource. Circular wait occurs when a process waits for a resource that is in possession of another process, and this cycle continues on to form a loop. Methods to resolve deadlocks are prevention, non-preemptive action, mutual exclusion, hold and wait, and circular wait.