Today we will discuss Deadlock in OS. Deadlock is the most important topic in the operating system. There are many reasons for deadlock and various techniques of deadlock prevention in the operating system.
Table of Content
What is Deadlock in OS?
If P1 and P2 are two processes, R1 and R2 are two resources. P1 requests the resource R1, R1 is held by process P2, P2 requests the resource R2, R2 is held by process P1, and both P1 and P2 are in the waiting state. There is no work progress for processes P1 and P2. It is a deadlock too. Resource Allocation Graph (RAG) can represent deadlock.
Resource Allocation Graph
A resource allocation graph is a directed graph; it is used to represent the deadlocks. There are two types of nodes in the graph. One for the process, it is represented by a circle, and the second, for the resource, is represented by a square. There are two types of edges in the graph. One is the requesting edge (Pi to Rj), and another is the assignment edge (Rj to Pi).
Conditions for Deadlock
- Condition 1: If the resource allocation graph contains no cycle, then there is no deadlock.
- Condition 2: If the resource allocation graph contains cycles, then the system may or may or may not be in deadlock. But, if the system is in a deadlock state, the resource allocation graph must consist of cycles.
A deadlocked system must satisfy the following four conditions
- Mutual Exclusion
- Hold and Wait
- No Pre-emption
- Circular Wait
Mutual Exclusion
Mutual exclusion means resources are (at least one) in non-sharable mode only. It means only one process at a time can use a resource. For example, If process P1 requests the resource R1 then process P2 must wait til resource R1 has been released by process P1.
For example, line printers, the line printers are always in non-sharable mode only, only one process can use the resource at a time.
Hold and Wait
Each process in the deadlock state must hold at least one resource and wait for additional resources that are currently being held by another process.
No Pre-emption
No pre-emption means resources are not released in the middle of the work, they release only after the process has completed its task.
Circular Wait
In the above figure, P1 is waiting for the resource R1, R1 is held by process P2, P2 is waiting for the resource R2, R2 is held by process P3, P3 is waiting for the resource R4, R4 is held by process P2, P2 is waiting for resource R3, R3 is held by P1, it is said to be a circular wait.
Deadlock Prevention
Deadlock prevention refers to the methods used to prevent deadlocks before they occur. For a deadlock to occur, all four necessary conditions must hold.
By ensuring that at least one of these conditions cannot hold, we can prevent the occurrence of deadlocks. Therefore, we can apply prevention techniques to each of the four necessary conditions separately.
Mutual Exclusion
Mutual exclusion means only one process can access the resource at a time. In other words, the number of processes does not share the resources at the same time. Hence, resources are non-sharable mode only.
We can deny this condition with a simple protocol, i.e., Connect all non-sharable resources to sharable resources. Therefore, this condition is not satisfied by the deadlock.
There is a small correction; the number of processes does not share a printer at a time. Therefore, we cannot connect the printer from non-sharable to sharable mode. Hence, we cannot apply this prevention method if the system consists of printers.
Hold and Wait
Hold and wait means, each process in the deadlock state must hold and wait for at least one resource. We can deny this condition with a small protocol, i.e., A process requests the resources only, when the process has none. This protocol is very expensive and time-consuming.
For example, a person wants to copy from a tape drive to a disk file and then take a printout. Initially, the process consisted of the tape drive and disk file, now the process to request the printer to apply the above-said protocol, the process should release the tape and disk file before the request of the printer. Therefore, it is time-consuming. The second protocol is that each process requests and is allocated all its resources before it begins execution.
There are two main disadvantages- first, resource utilization is very poor. Second, starvation is possible. A process that needs several resources may have to wait indefinitely because at least one of the resources it needs is always allocated to some other process.
No Pre-emption
The third necessary condition “No Pre-emption” means resources are not released in the middle of the processing. To ensure that this condition does not hold we use the following protocol.
When a process requests some resources, we first check whether they are available. If they are available, we allocate them.
If not, we check whether they are allocated to some other process that is waiting for additional resources. If so, we pre-empt the resources from the waiting process and allocate them to the requesting process.