|
Important
Capture important notes from internet using arusaquotes.
Today we will discuss Deadlock in OS. Deadlock is the most important topic in the operating system. There are many reasons to occur deadlock, and various techniques of deadlock prevention in the operating system.
Definition of Deadlock with Example
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 they both P1 and P2 are into the waiting state. There is no work progress for process P1 and P2. It is a deadlock too. Resource Allocation Graph (RAG) can represent deadlock.
|
| Resource Allocation Graph |
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 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.
|
| No Deadlock |
Necessary conditions for deadlock
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 n 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 do not release in the middle of the work, they release only after the process has completed its task.
Circular Wait
|
| 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.
|
| Circular Wait |
Recovery from Deadlock in OS
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 the 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 print out. Initially, the process consisting of the tape drive and disk file, now the process to request the printer applying 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, Each process to request and be 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 of 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 by in the middle of the processing. To ensure that this condition does not hold if 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.
Practice MCQ Questions of Operating System
Practice Now