- Big Giant Lock
- Finer Granularity
- Release When Possible
- Locking Order and Deadlocks
- Lightweight Locking
- Specialized Lock Types
- Doing Without Locks
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Locking Order and Deadlocks
The biggest problem with using locks for synchronization is deadlock. In the simplest case, you have two bits of code, each of which holds one lock, but each one needs the other one's lock in order to proceed.
If each bit of code needs only one lock at a time, deadlock will not occur, but unfortunately this isn't always possible. The simplest way of avoiding a deadlock when you need more than one lock is to enforce a locking order, in which you can acquire two locks only by doing so in a specified order.
In this situation, if you acquire one lock and fail to acquire the other, then you must release the first lock and try again. The problem with this plan is that it may not be possible to release the first lock safely. You might need the first lock to start an operation and the second lock to complete it. If you have to release the first lock, then you also have to undo the associated work. Effectively, you need to implement transactions. (We'll look at transactions in part 3 of this series.)
Although this case is the simplest, it can become arbitrarily complex. One classic example is the "dining philosophers" problem. Each philosopher has a chopstick on either side of him and requires two to eat. They all start by picking up the chopstick on their right. Now they're deadlocked—no one can proceed until someone puts down his chopstick.
You can also easily enter a livelock condition from here. If each philosopher puts down the chopstick on his right and tries to pick up the one on the left, then they're stuck that way. They may put the left one down and pick up the one on the right again, oscillating between two states without actually managing to eat.
This problem could be avoided if each chopstick had a number, and they all had to be picked up in order. In this case, all of the philosophers would try to pick up the one on their right, except for the one sitting between the chopsticks with the highest number on one side and the lowest number on the other side. He would have to wait until the person using the chopstick on his left had finished before he could pick up the one on his right. Or he would get there first. In both cases, at least one person would be able to pick up both chopsticks. Once he'd finished eating, at least one more person would be able to start.