Deadlocks are another common problem with multithreading. I’ll explain how you can get into this situation and how to change your code to avoid the problem.
This is a case where diagnosis is a lot harder than the cure. You have two options.
- Change how fine-grained your locks are by using fewer locks to encompass more resources.
- Keep the locks on individual resources and make sure to always acquire locks in the same order.
I sometimes ask a question about deadlocks during interviews and have heard some creative answers over the years. You don’t need anything complicated to handle deadlocks. Just make sure to acquire locks in the same order.
This works even if threads are asking for different numbers of locks. Let’s say that one thread wants to lock resources A, B, and C. And another thread only needs B and C. As long as both threads follow the same order for whatever locks they try to obtain, then you’ll avoid deadlocks.
Listen to the full episode for more explanation, or you can also read the full transcript below.
Transcript
In the previous episode 94, I described how you can use critical sections to make sure that you have sole access to some variables when making changes. A critical section is really just a lock. And I even used the analogy of locking a room before changing a number written on a whiteboard.
This works great. You can have many different locks available and all you need to do is remember to acquire the appropriate lock before making any changes.
Proper multithreading requires that all the threads in a process follow the same rules. It won’t do you any good if most of your threads make sure to get locks while just one thread proceeds to modify objects as if it was the only thread remaining.
But this brings up an interesting question. Why do you need multiple locks in the first place. Why not have only a single lock for everything?
Have you ever went bowling. Your typical bowling alley has multiple lanes and when a group of people want to play, the group will have sole access to their lane for a couple hours. Imagine the confusion that would result if anybody was allowed to grab a ball and throw it down any lane at any time. You could think of this as if the group of people locked their lane while they’re using it.
This works out well for the bowling alley because each lane can be locked separately for different teams. Individual locks allow your code to be more fine-grained whenever multiple resources are involved. Your code only needs to lock what it wants to change.
The alternative would be for the bowling alley to lock their main doors and not let anybody else enter the whole building while a team occupies just one lane. This is a waste because normally resources like this can act independently of each other.
Whenever you have multiple variables, or objects, or anything that needs multithreaded access control, you need to decide which are independent. Then you create a lock for each of these independent pieces. Just like how the bowling alley allows each lane to be locked while in use.
If this was the whole story, then there wouldn’t be any deadlocks. Sometimes though you might need to do something that requires more than just one lock. Let’s say you gather a large group of friends to go bowling and need two lanes. This is where you can run into problems. Just that simple extra requirement to get multiple locks can bring your whole application to a complete stop.
Have you ever used an application on your computer when it just froze? It just stopped working? Well, that in itself doesn’t mean there was a deadlock. But that’s the kind of devastation that deadlocks can bring down on your application.
I’ll describe what causes a deadlock and how you can avoid them right after this message from our sponsor.
( Message from Sponsor )
Okay, you need two lanes now at the bowling alley. To simplify things, let’s pretend this is a really small bowling alley that only has two lanes.
The simple case happens when you get to the bowling alley and find it empty. You lock both lanes and enjoy your games.
What happens if you get to the bowling alley and one lane is already being used? You could wait until both lanes are available. But this puts the bowling alley in a difficult spot. Should it let another group have the single available lane in the hope that both lanes will become free at the same time? Or should it hold the available lane for your group? This is bad for the bowling alley because it can’t charge you for a lane you’re not using and it can’t let another team use the lane because who knows how long they’ll keep using it. What normally happens is the bowling alley will ask you if you want to start playing on the single available lane and then move into the second lane when it becomes available.
In other words, you place a lock on just part of what you need and wait for a second lock to complete your requirements. Maybe you can do some warmup exercises on the lane you have but your group won’t be able to make full use of the facilities until you have both locks. Eventually, when the other team finishes, you get both locks and enjoy your games.
So far, there’s been no deadlock. That’s going to change right now with this scenario. In this case, your large group still needs two lanes and you happen to arrive at the bowling ally just as another large group arrives. Both groups are going to need two lanes.
You walk up to the counter and request lane one and lane two for your group. The clerk checks on lane one first and finds it available. You now have half of what you need. But at the same time, the other group has been talking with another clerk and that other group just locked lane 2. They also have half of what they need. When your clerk tries to lock lane 2 for you, it’s no longer available and the clerk tells you that you’ll just have to wait. The problem is that’s almost the same story that the other group was told. You have lane one and are waiting on lane two. The other group has lane two and is waiting on lane one. You’re both waiting on something that the other has. And because you’re both waiting, neither one is going to give up the piece already in possession. This is a deadlock.
This is a simple case of a deadlock and is not that hard to spot the potential and fix it. Not all deadlocks are this simple though. Maybe there’s more than just two threads involved. Or maybe the resources locked by each thread are far apart in your code making it harder to detect. Like a lot of multithreading problems, deadlocks don’t always happen. This makes them hard to spot through testing.
You’re best chance of finding potential deadlocks before your customers complain is to use code analysis tools and good ol’design reviews.
What do you do when you find a potential deadlock? What changes do you make to your code to fix the problem so it won’t happen again?
The answer is actually very simple. This is a case where diagnosis is a lot harder than the cure. You have two options. The heavy-handed approach involves changing your lock levels. I mean, go back to using fewer locks. For the bowling alley with just two lanes, this effectively means that anytime somebody rents one lane, they get the whole building. While this option works, it’s probably not going to solve your needs.
The second option allows you to keep your fine-grained locks. All it adds is one requirement that anytime multiple locks are needed, they all have to be obtained in the same order.
That was the ultimate cause of the bowling alley deadlock. Your clerk gave you lane one first while the other clerk gave the other team lane two first. Because the clerks weren’t following the same order, a deadlock occurred.
Had the other clerk instead started with lane one just like your clerk did, then the scenario just becomes a race to see who can get the lock on lane one first. Whoever gets the first lock, then goes on to get the second lock.
This doesn’t mean that the second lane will always be available. What it means is that there won’t be somebody holding the second lane who also wants the first lane. There could easily be a lock on the second lane by a small team who will soon finish their game and leave. Does that mean you’ll then get the second lane? Well, maybe not. It’s possible that yet another small team will get the second lane ahead of you and you have to again wait for them to complete.
This is just normal waiting. Avoiding deadlocks doesn’t suddenly speed up your application or give your threads some super ability to get all their locks on the first attempt. All it does is make sure that you avoid the scenario where multiple threads each have only part of what they need and are waiting on other threads that also have only part of what they need.