EJCP Top 10: Nested monitor lockout
Posted by Peter Veentjer in the early evening: January 22, 2008
Concurrent programming is going to be even more important with the introduction of the multi-core cpu's. Running the complete application on a single cpu's (single threaded) is going to lead to less effective usage of hardware. Luckily in most cases, applications are inherently concurrent (like a standard request/response web-application) so a developer doesn't need to deal often with explicit concurrency control. But it doesn't mean that even such simple applications are free of concurrency problems. In this Enterprise Java Concurrency Problems (EJCP) Top 10, I'm going to list my 10 most important issues I look at, when I need to find concurrency problems within Enterprise Java applications.
So, without further ado, let's start at the bottom: number 10.
Nested Monitor Lockout
It is very easy to cause liveness problems with conditions (aka condition variables) but it is not just the direct usage that can cause problems, also techniques like object composition can be quite dangerous.
A condition is a very low level synchronization structure that makes it possible for threads to wait for an event to occur, e.g. the return of a license in a semaphore or the placement of an item on a queue. So a lot of higher order concurrency structures are build on top of conditions and this makes them one of the most fundamental concurrency abstractions. The big question is: how can the usage of a condition cause a deadlock? When a thread is going to wait for a notification, it blocks, it is added to a wait-set (a set of blocking threads that wait for that condition) and the associated lock is released. Releasing and reacquiring the lock is done behind the screens and luckily is not a task developers need to deal with. But if the waiting thread never receives the notification it is waiting for, the thread won't wake-up and therefore is in a deadlock.
Imagine there is a fridge with room for beer. If someone wants to grab a beer from the fridge, he opens the door (other people are not able to access the fridge while it is opened) and checks if one is available. If there is, he takes it, closes the door and returns. If there isn't, he closes the door and waits next to the fridge. When the delivery guy wants to put something in the fridge, he opens the door, places the item, shouts that a new item has been put and closes the door. The guy that is waiting heard the delivery guy, he opens the door, sees that a beer is available, takes it and closes the door.
class Fridge{
final Object monitor = new Object();
final List<Beer> itemList = new LinkedList<Beer>();
void put(Beer beer){
synchronized(monitor){
itemList.add(beer);
monitor.notify();
}
}
Beer take()throws InterruptedException{
synchronized(monitor){
while(itemList.isEmpty())
monitor.wait();
return itemList.remove(0);
}
}
}
The Fridge class is an implementation of the example. It uses a Java monitor, a combination of a condition (wait-set) and its corresponding (intrinsic) lock:
- the lock is used to synchronize between threads (providing exclusive access)
- the condition is used to communicate between threads (the waiting and shouting part)
Lets enhance our example and place the fridge in a very small kitchen; a kitchen with room for just a single person. We can prevent multiple people from accessing the small room by adding a door to the kitchen.
class Kitchen{
final Object monitor = new Object();
final Fridge fridge = new Fridge();
void put(Beer beer){
synchronized(monitor){
fridge().put(beer);
}
}
Beer take()throws InterruptedException{
synchronized(monitor){
return fridge.take();
}
}
}
In this Kitchen class, the kitchen-door is implemented by a monitor (only the lock is used b.t.w.). When someone wants to access the fridge he sees that the kitchen-door is open and enters the kitchen, he closes the kitchen-door (he acquires the lock of the kitchen-monitor), he opens the fridge-door (he acquires the lock of the fridge-monitor) and looks inside. When he realizes that the fridge is empty, he waits in the kitchen. When this happens, the lock on the fridge-door is released, but because he stays in the kitchen the kitchen-door remains closed (locked). The consequence is that everybody who want to access the kitchen is going to deadlock:
- someone that wants to take something from the fridge or wants to refill the fridge is going to deadlock because he can't enter the kitchen (the kitchen-door is closed) and keeps waiting.
- the person that is waiting in the kitchen, is going to deadlock because nobody is able to refill the fridge because he has locked out everybody from the kitchen.
This problem is called: 'nested monitor lockout'. Composing larger structures (e.g. kitchens) from smaller structures (e.g. fridges) is a technique all object oriented developers use on a daily basis (dependency injection, object composition, decorators, template methods, proxies, strategies, etc). But as soon as these structures block and are wrapped within other concurrent structures, you can get in serious liveness problems. So one of the first things I look at is if synchronized structures are wrapped in other synchronized structures and possible do blocking calls (if you are lucky, the methods throw an InterruptedException). But this can be a very challenging task if the concurrent code isn't localized but scattered all over the place or when the InterruptedExceptions aren't handled correctly. Maybe in the future techniques like STM (Software Transactional Memory) can help us, but for the moment we need to keep paying extra attention to concurrency control.
For more information about this subject I recommend "Concurrent Programming in Java: Design Principles and Pattern (2nd Edition)" from Doug Lea, Chapter 3.3.4 "Confinement and nested monitors".
Filed under: Concurrency Control, Java
February 12th, 2008 at 1:57 pm
[…] Continuing the Enterprise Java Concurrency Problem Top 10 countdown, it’s time to talk about number 9 ‘Stopping threads’. […]
February 20th, 2008 at 3:59 pm
[…] Nested monitor lockout […]