Deadlock in Operating System

In this tutorial, we will learn about deadlock in Operating System , necessary conditions for deadlock to occur. Further, we will see how to detect and avoid deadlocks.

What is Deadlock in Operating System :

Deadlock is a situation where a process or a thread waits for an event/task that won’t occur. When one or more processes are in deadlock, we call it a system deadlock.

Necessary Conditions for Deadlock in Operating System :

Deadlock in an Operating System can occur, if a situation satisfy the following four conditions simultaneously.

Mutual exclusion condition – We can give resource exclusively to only one process at a time.

Wait-for condition (hold-and-wait condition) – Process that has acquired an exclusive resource may hold that resource, whereas the process waits to get different resources.

No-preemption condition – Once a process has obtained a resource, the system cannot take away it from the process’s control till the process has finished using the resource.

Circular-wait condition – Two or additional processes are locked in a “circular chain” where each of them is waiting for one or additional resources that the next process within the chain is holding.

Deadlock Solutions :

1. Deadlock prevention :

We can prevent deadlock ,if we can deny any one of those four necessary conditions. Among those four conditions, we cannot break mutual exclusion. Although we can deny wait-for, No-preemption and Circular-wait conditions.

2. Deadlock avoidance : 

Dijkstra’s Banker’s Algorithm helps to avoid deadlocks. As we use this algorithm in banking systems, we name it as Banker’s Algorithm. It assures that the system would never allocate its resources in such a way that it can no longer satisfy the needs of all its processes. The system would try to be in safe state always. We cannot implement this algorithm in real systems, because it needs to the know requirements of each processes beforehand. Moreover it works if there is constant number of processes and resources .

3. Deadlock detection :

Deadlock detection is basically determining if deadlock has occurred. It also identifies the processes and resources get deadlocked. Resource Allocation Graph(RAG) helps to detect deadlocks. In RAG the squares represent the processes and the circles represent the resources. If we can reduce a RAG by all its processes, there is no deadlock.

4. Deadlock recovery :

This means clearing deadlocks from the system so the processes can complete their executions and give up the allocated resources. A system can recover from deadlock with the help of suspend/resume mechanism or checkpoint/rollback technique.

Nowadays in most of the OS, either we prevent deadlocks using basic methods or we simply ignore them.