Deadlock and Deadlock Detection
Let's talk about deadlock and how to detect it. We'll have a simulation to help us understand the concepts. We have two processes, “Alice” and “Bob”, and two resources, “Pan” and “Whisk”. In our example, we have a familiar analogy to the real world, but our resources could be anything that gets grabbed by a process and then released, and while one process has a resource, other processes that want it have to wait.
So like locks in OS/161?
Exactly!
Simulator and Visualization
Deadlock Status:
Exercise 1: Requesting Resources
In the simulator above, do the following (reset the simulation before you start if you've been playing around with it):
- Use the dropdown boxes to give both the Pan and the Whisk to Alice (or give them both to Bob if you prefer) by setting them to “Allocated”.
- In the graph display, you'll see that the Pan and Whisk resources now have a solid green edge pointing from them to the process they were allocated to.
- Now, set the dropdown boxes for the other process to “Request” one of the resources already held by the first process.
- In the graph display, you'll see a new dashed purple edge from the process to the resource.
- If the process can't get the resource, it will be blocked, which means the process will be put to sleep while it's waiting for the resource. The simulator greys out all the dropdown boxes for the resource while it sleeps.
- If you make the first process release the resource the second resource requested, the second process will wake up and acquire the resource.
- The graph and table will update to show the new state where the second process has the resource.
Exercise 2: More Things
I always want MORE!
-
You can click the following buttons to add some more processes and resources to the simulation.
That said, you can see most deadlock phenomena with just two processes and two resources.
-
If you want to go back to just two processes and two resources, you can refresh the page.
Exercise 3: Creating Deadlock
Try to create a series of allocations and requests such that every process ends up stuck waiting. When you succeed, you'll see the status change to “Deadlock Detected”.
There's clearly a cycle in the graph. That's a deadlock, right?
-
Right, deadlock is a circular wait. Each process is waiting for a resource that's held by another process in the cycle.
-
I'm sad. Now that it's deadlocked, it doesn't work anymore because everything is stuck. I guess I should reload the page to reset it.
-
Actually, don't do that. We can try to fix the situation without starting from scratch!
Conditions for Deadlock
We've already seen one condition for deadlock, circular wait. But for deadlock to be a problem, we need four conditions to be met:
- Mutual Exclusion: Resources must be held in a mutually exclusive way. That is, only one process can use a resource at a time.
- Hold and Wait: Processes must hold resources while waiting for others.
- No Preemption: Resources cannot be forcibly taken from a process.
- Circular Wait: There must be a circular wait chain of processes.
Here are two checkboxes to allow us to turn off the second and third conditions. If the simulator above is in a deadlocked state, changing these conditions will allow us to break the deadlock.
-
- If you turn off hold and wait, you can make a process give up on waiting for a resource (by switching to “Uninterested”) which will release the resource and the deadlock will disappear.
-
- If you turn on resource preemption, you can take a resource away from a process that's asleep (by switching it to “Uninterested”) which will allow another process to get the resource and continue, so the deadlock will disappear.
-
So, if we don't have all four conditions, we can't have deadlock?
-
Exactly.
Deadlock Prevention
We can prevent deadlock by attacking any of the four conditions.
Eliminate Mutual Exclusion
Suppose several processes want to print pages to the printer. One approach is to give processes exclusive access to the printer. But perhaps they don't really need an interactive conversation with the printer; maybe they just need something to receive the print job and then the printer can print that job when it's ready. With this approach, any process can create print jobs at any time, and the printer can print them in whatever order it wants.
Coming up with designs that don't require mutual exclusion is one way to prevent deadlock.
Meh. So just get rid of all the locks and hope for the best! Everyone for themselves!
-
No, that's not what we're saying. We're saying that sometimes you can design things so that you don't need locks.
Eliminate Hold and Wait
Normally, when we try to acquire a lock, our process sleeps until it can get the lock. But if we can't get the lock, we're stuck. Rather than wait indefinitely, we could instead have processes give up on waiting after some time has passed.
POSIX provides
pthread_mutex_timedlockfor this purpose. If you can't get the lock in a certain amount of time, you can give up.
So just put that in a loop and keep trying?
-
No. That would be no better than just sleeping. If we had a circular wait, we'd still be stuck. It wouldn't technically be deadlock, but it's the same issue. We call that livelock.
-
Instead we have to do something different, such as releasing all the resources we have and then trying to request all the things we need from scratch.
Eliminate No Preemption
Preempting resources is rarely a good idea. If a process is in the middle of writing to a file, we don't want to take the file away from it. But if we're stuck in a deadlock situation, killing one of the processes (and thus releasing its resources) is one way to break the deadlock.
-
So we just kill a process and hope for the best?
-
That's one way to do it. But it's a bit like using a sledgehammer to crack a nut. It's a bit heavy-handed.
Eliminate Circular Wait
If we can prevent a circular wait, we can prevent deadlock. One way would be to assign an order to resources and require processes to request resources in that order.
-
So we just have to make sure that everyone requests resources in the same order?
-
That's the goal, but it's trickier than you might think. Sometimes when you thought you only needed one resource, you later find you need another one. In those cases, the order you're supposed to request resources in may not be the same as the order you actually find that you need them.
Deadlock Detection
-
So how do we detect deadlock?
We can use a graph to represent the resources and processes and the requests and allocations between them. If we find a cycle in the graph, we have a deadlock.
Unfortunately, the graph algorithm for detecting cycles has time complexity \(\mathrm{O}(V + E)\), where \(V\) is the number of vertices and \(E\) is the number of edges. That's not terrible, but we probably don't want to run it all the time.
-
Unix-like systems tend not to bother with deadlock detection. They just hope for the best.
That's not very reassuring.
-
Meh. If you have a deadlock, you'll know about it because everything will be stuck.
(When logged in, completion status appears here.)