Deadlock in Operating System
What is Deadlock in Operating System
Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.
It is a situation that occurs in OS when any process enters a waiting state because another waiting process is holding the demanded resource.
When Deadlock Arise
Deadlock can arise if the following four conditions hold simultaneously (Necessary Conditions)
Mutual Exclusion: One or more than one resource are non-shareable (Only one process can use at a time). Mutual Exclusion is a full form of Mutex. It is a special type of binary semaphore which used for controlling access to the shared resource. It includes a priority inheritance mechanism to avoid extended priority inversion problems. It allows current higher priority tasks to be kept in the blocked state for the shortest time possible. Resources shared such as read-only files never lead to deadlocks, but resources, like printers and tape drives, needs exclusive access by a single process.
There should be a resource that can only be held by one process at a time. In the diagram below, there is a single instance of Resource 1 and it is held by Process 1 only.
Hold and Wait: A process is holding at least one resource and waiting for resources. In this condition, processes must be stopped from holding single or multiple resources while simultaneously waiting for one or more others.
A process can hold multiple resources and still request more resources from other processes which are holding them. In the diagram given below, Process 2 holds Resource 2 and Resource 3 and is requesting the Resource 1 which is held by Process 1.
No Preemption: A resource cannot be taken from a process unless the process releases the resource. A resource cannot be preempted from a process by force. A process can only release a resource voluntarily. In the diagram below, Process 2 cannot preempt Resource 1 from Process 1. It will only be released when Process 1 relinquishes it voluntarily after its execution is complete.
Circular Wait: A set of processes are waiting for each other in circular form. It imposes a total ordering of all resource types. Circular wait also requires that every process request resources in increasing order of enumeration.
A process is waiting for the resource held by the second process, which is waiting for the resource held by the third process and so on, till the last process is waiting for a resource held by the first process. This forms a circular chain. For example: Process 1 is allocated Resource2 and it is requesting Resource 1. Similarly, Process 2 is allocated Resource 1 and it is requesting Resource 2. This forms a circular wait loop.
Real Life Example of Deadlock
- A real-world example would be traffic, which is going only in one direction.
- Here, a bridge is considered a resource.
- So, when Deadlock happens, it can be easily resolved if one car backs up (Preempt resources and rollback).
- Several cars may have to be backed up if a deadlock situation occurs.
- So starvation is possible.
Advantages of Deadlock
- This situation works well for processes which perform a single burst of activity
- No preemption needed for Deadlock.
- Convenient method when applied to resources whose state can be saved and restored easily
- Feasible to enforce via compile-time checks
- Needs no run-time computation since the problem is solved in system design
Disadvantages of Deadlock method
- Delays process initiation
- Processes must know future resource need
- Pre-empts more often than necessary
- Dis-allows incremental resource requests
- Inherent preemption losses.
Deadlock Detection
A deadlock can be detected by a resource scheduler as it keeps track of all the resources that are allocated to different processes. After a deadlock is detected, it can be resolved using the following methods;
- All the processes that are involved in the deadlock are terminated. This is not a good approach as all the progress made by the processes is destroyed.
- Resources can be preempted from some processes and given to others till the deadlock is resolved.
Difference Between Deadlock, Starvation, and Livelock
- A deadlock is a situation that occurs in OS when any process enters in a waiting state because the demanded resource is being held by another waiting process.
- A livelock, on the other hand, is almost similar to a deadlock, except that the states of the processes which are involved in a livelock always keep on changing to one another, none progressing.
- So, Livelock is a unique case of resource starvation.