In an 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.
For example, in the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is acquired by process 2, and process 2 is waiting for resource 1. Hence both process 1 and process 2 are in deadlock.
Necessary conditions :
There are four necessary conditions for a deadlock to occur, known as the Coffman conditions from their first description in a 1971 article by E. G. Coffman. Deadlock can arise if four conditions hold simultaneously :
- Mutual Exclusion :
One or more than one resource are non-sharable (Only one process can use at a time) - Hold and Wait :
A process is holding at least one resource and waiting for resources. - No Preemption :
A resource cannot be taken from a process unless the process releases the resource. - Circular Wait :
A set of processes are waiting for each other in circular form.
Deadlocks can be avoided by avoiding at least one of the four conditions, because all this four conditions are required simultaneously to cause deadlock.
While these conditions are sufficient to produce a deadlock on single-instance resource systems, they only indicate the possibility of deadlock on systems having multiple instances of resources.
Methods for Handling Deadlock :
There are three ways to handle deadlock :
- Deadlock prevention or avoidance –
The idea is to not let the system into deadlock state. - Deadlock detection and recovery –
Let deadlock occur, then do preemption to handle it once occurred. - Ignore the problem all together –
If deadlock is very rare, then let it happen and reboot the system. This is the approach that both Windows and UNIX take.
Notes :
- Circular waiting happens when one process is waiting for the resource, which is held by the second process, which is also waiting for the resource held by the third process etc.
- Deadlocks can be prevented by preventing at least one of the four required conditions : Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait.
- Using Resource Allocation Graph, it can be easily detected whether system is in a Deadlock state or not.
- If Resource Allocation Graph (RAG) contains no cycles Þ no deadlock.
- If graph contains a cycle :
- (i). If only one instance per resource type, then deadlock.
- (ii). If several instances per resource type, possibility of deadlock (in this case, we use Banker’s Algorithm to check whether deadlock occurs or not.).
- If only one instance per resource type: Presence of a cycle is a necessary and sufficient condition for the occurrence of deadlock.
- If several instances per resource type: Presence of a cycle is a necessary but not a sufficient condition for the occurrence of deadlock.
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.