In this post, we are going to learn about deadlocks in modern operating systems. We will learn what deadlocks are, mainly the resource deadlocks. We will learn about the four conditions that need to be true for deadlocks to occur.
What is a deadlock in Operating Systems?
Before discussing the technical terms, let us explain deadlocks by an analogy. Consider a scenario where you and a friend decided to eat something. Now, to serve yourselves, you picked a bowl but didn’t get a spoon, on the other hand, your friend picked a spoon and didn’t get a bowl. Now, both of you have a resource (bowl or spoon) and require exactly one more resource(spoon or bowl) to eat the dessert. And this is the scene where the “deadlock” comes into the picture. Neither you nor your friend is ready to give his resource to the other person, so both of you stand there waiting for each other infinitely and this is what we call a situation of deadlock.
The technical definition of a deadlock: A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause.
Deadlock is a situation where two or more processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process. In a local area network, most of the resources are shared. It becomes congested when more than two processes are in a deadlock state.
If you remember, the Operating System is responsible for managing resources, so it naturally becomes the responsibility of the OS when two processes fight over the same resource. That is why managing deadlocks is an integral part of an OS.
Conditions for Resource Deadlocks in an OS
There are four conditions which need to be true to cause a resource deadlock:
- Mutual Exclusion: Mutual exclusion says that a resource can be used by only one process at a time.
- Hold and Wait: This is a condition where a process is holding at least one resource and is waiting for other resources.
- No Preemption: If a process is holding a resource, it cannot be taken back from it unless the process itself releases the resource explicitly.
- Circular Wait: A set of processes are waiting for each other for the resources in a circular fashion. For example, P1 is waiting for P2, P2 is waiting for P3 and P3 is again waiting for P1.
All four of these conditions must hold true for a resource deadlock to occur. If even one of the condition is false then there is no resource deadlock.
Using graphs to visually check for deadlocks in an OS
In the above image, the squares are represented by resources and circles by processes. When a resource (square) is directed towards the process (circle) it means that the process is currently using that resource, as shown in figure 1. In figure 2, the process is directed towards the resource, this means that the process is waiting for that resource to get free. In the 3rd figure, we have arrived at a deadlock cycle.
How to deal with Deadlocks in Operating Systems?
There are four ways to deal with these resource deadlocks. They are listed below.
- Ignoring the problem. This is also called the ostrich algorithm
- Detection and Recovery. Let deadlocks occur, detect them and then recover from them.
- Dynamic avoidance using careful resource allocation.
- Prevention, by negating one of the four conditions.
We will learn more about how these four methods work in dealing with deadlocks in detail.
Make sure to check out the Operating Systems course to learn a lot about how they work.