Deadlock between threads competing for the same set of locks is the hardest problem to solve in any threaded program. It’s a hard enough problem, in fact, that we will not solve it—or even attempt to solve it. Instead, we’ll try to offer a good understanding of deadlock and some guidelines on how to prevent it. Preventing deadlock is completely the responsibility of the Java developer—the Java virtual machine will not do deadlock prevention or deadlock detection on your behalf.
We’ll look at deadlock in conjunction with the following code, which emulates how a kitchen might operate. When a cook wants to make cookies, she grabs the measuring cup to measure ingredients into the bowl; when a cook wants to make an omelette, he grabs a bowl, beats some eggs, and then measures out the eggs for each individual omelette. This is the order a typical cook uses to make these items, and as long as we have only one cook, everything is fine with these procedures. If we have two cooks, however, and one wants to make cookies while the other wants to make omelettes, we have a deadlock situation: the omelette maker needs the measuring cup to measure out the eggs that are in the mixing bowl; the cookie maker needs the bowl to put in the flour that is in the measuring cup:[11]
public class Kitchen { static MeasuringCup theCup; static Bowl theBowl; public void makeCookie() { synchronized(theCup) { theCup.measureOut(1, theFlour); synchronized(theBowl) { theBowl.putIngredients(theCup); theBowl.mix(); } } } public void makeOmelette() { synchronized(theBowl) { Eggs e[] = getBrokenEggs(); theBowl.putIngredients(e); theBowl.mix(); synchronized(theCup) { theCup.measureOut(theBowl); } } } }
Like previous examples of deadlock we’ve seen, this example is simple, but more complicated conditions of deadlock follow the same principles outlined here: they’re harder to detect, but nothing more is involved than two or more threads attempting to acquire each other’s locks.
Deadlock
is difficult to detect because it can involve many classes that call
each other’s synchronized sections (that is, synchronized
methods or synchronized blocks) in an order that isn’t
apparently obvious. Say we have 26 classes, A to Z, and that the
synchronized methods of class A call those of class B, those of class
B call class C, and so on, until those of class Z call those of class
A. This leads us into the same sort of deadlock situation that we had
between our makeCookie() and
makeOmelette() methods, but it’s unlikely
that a programmer examining the source code would detect that
deadlock.
Nonetheless, a close examination of the source code is the only option presently available to determine if deadlock is a possibility. Java virtual machines do not detect deadlock at runtime, and while it is possible to develop tools that examine the source code to detect potential deadlock situations, no such tools exist yet for Java.
The simplest way to avoid deadlock is to follow the rule that a synchronized method should never call a synchronized method. That’s a good rule, often advocated, but it’s not the ideal rule for two reasons:
It’s impractical: many useful Java methods are synchronized, and you’ll want to call them from your synchronized method. As an example, we’ve called the
addElement()method of Java’s Vector class from several of our synchronized methods.It’s overkill: if the synchronized method you’re going to call does not in turn call another synchronized method, there’s no way that deadlock can occur (which is why we always got away with calling the
addElement()method from a synchronized method; theaddElement()method makes no further synchronization calls). Generically, the synchronized method can call other synchronized methods in ways we’ll explore later.
Nonetheless, if you can manage to obey this rule, there will be no deadlock in your program.
Another often-used technique to avoid deadlock is to lock some higher-order object that is related to the many lower-order objects we’ll need to use: in our example, that means locking the kitchen instead of locking the individual utensils as we use them. This makes our methods synchronized as follows:
public class Kitchen {
public synchronized void makeCookie() { ... }
public synchronized void makeOmelette() { ... }
}Of course, we don’t need to lock everything. We could create a BusyFlag for the measuring cup and bowl combination and just acquire that lock whenever we needed one or the other utensil. We also could make it a programmatic rule that to use either the measuring cup or mixing bowl, you must acquire the lock only for the mixing bowl. All these variations of locking multiple objects suffer from the same lock granularity problem that we’re about to discuss.
The problem with this technique is that it often leads to situations where the locking granularity is not ideal. By synchronizing the methods of the Kitchen class, we are essentially preventing more than one cook from using the kitchen at a time; the purpose of having multiple threads is to allow more than one cook to use the kitchen. If we’ve done our program design correctly, there was probably a reason why we attempted to acquire multiple locks rather than a single global lock. Solving deadlock issues by violating this design becomes somewhat counterproductive.
The most practical rule to avoid deadlock is to make sure that locks are always acquired in the same order. In the case of our deadlock example, this would mean making sure that the mixing bowl lock is always acquired before the measuring cup lock (or vice versa, as long as we’re consistent). This implies the need for a lock hierarchy among classes. The lock hierarchy is unrelated to the Java class hierarchy: it is a hierarchy of objects rather than of classes. Furthermore, the hierarchy of the locks is unrelated to the hierarchy of the classes: the MeasuringCup and Bowl classes are probably sibling classes in the class hierarchy, but in the lock hierarchy, we must place one object above the other. The lock hierarchy is a queue rather than a tree: each object in the hierarchy must have one and only one parent object (as in the Java class hierarchy), but it must have one and only one descendant as well.
If you’re developing a complex program in Java, it’s a good idea to develop a lock hierarchy when you develop your class hierarchy; sample hierarchies are shown in Figure 8.1. But since there is no mechanism to enforce the lock hierarchy, it’s up to your good programming practices to make sure that the lock hierarchy is followed.
We can use this rule to prevent deadlock in our kitchen by requiring
that all methods acquire the bowl before the measuring cup even if
they intend to use the measuring cup first. We’d rewrite the
makeCookie() method like this:
public void makeCookie() {
synchronized(theBowl) {
synchronized(theCup) {
theCup.measureOut(1, theFlour);
theBowl.putIngredients(theCup);
theBowl.mix();
}
}
}Following this lock acquisition hierarchy is the best way to guarantee that deadlock will not occur in your Java program when you use the standard synchronization techniques of the Java language.
What about the BusyFlag class that we’ve developed; could that be useful in preventing deadlock? The answer is yes, to a point. Using the BusyFlag class adds a certain complexity to a Java program, and it introduces the possibility of a new kind of deadlock that standard Java synchronization techniques don’t allow. But the BusyFlag class also allows us to build more complicated deadlock recovery into our program, which may be useful in certain circumstances.
The feature in the BusyFlag class that helps us avoid deadlock is the
tryGet-BusyFlag() method. In standard Java
synchronization calls, there is no such concept as testing the
acquisition of a lock: standard Java threads attempt to acquire the
lock and block until the lock is acquired. The BusyFlag class allows
us to see if we can acquire the lock and also attempts some sort of
recovery if the flag is busy.
Let’s rewrite our kitchen example to use the BusyFlag:
public class Kitchen { static MeasuringCup theCup; static Bowl theBowl; static BusyFlag theCupFlag, theBowlFlag; public void makeCookie() { theCupFlag.getBusyFlag(); theCup.measureOut(1, theFlour); theBowlFlag.getBusyFlag(); theBowl.putIngredients(theCup); theBowl.mix(); theBowlFlag.freeBusyFlag(); theCupFlag.freeBusyFlag(); } public void makeOmelette() { theBowlFlag.getBusyFlag(); Eggs e[] = getBrokenEggs(); theBowl.putIngredients(e); theBowl.mix(); theCupFlag.getBusyFlag(); theCup.measureOut(theBowl); theCupFlag.freeBusyFlag(); theBowlFlag.freeBusyFlag(); } }
So far we’ve just substituted the BusyFlag class for
Java’s standard synchronized blocks, with the effect that we
can still have deadlock. But we could go further and rewrite the
makeCookie() method like this:
public void makeCookie() {
theCupFlag.getBusyFlag();
theCup.measureOut(1, theFlour);
if (theBowlFlag.tryGetBusyFlag()) {
theBowl.putIngredients(theCup);
theBowl.mix();
theBowlFlag.freeBusyFlag();
}
else {
// ... Do something else ...
}
theCupFlag.freeBusyFlag();
}Here we’ve prevented deadlock by testing to see if the bowl’s BusyFlag is free as we grab it. If the flag is free, we’ll grab the lock and continue to make our cookies. Even if, at this point, another cook thread comes along to make an omelette, we won’t have deadlock, because that thread blocks until we’ve released the locks for both the bowl and the cup.
Whether or not we’ve achieved anything by preventing deadlock
depends on what logic we could put into the else
clause of the makeCookie() method. Perhaps there
is another bowl we could use in the else clause,
but that doesn’t do us any good: what if that bowl is being
used by a cook thread executing the makeTrifle()
method? The logic in the else statement must do
one of two things: it must do either something that requires no
utensils to be locked or something that allows the measuring
cup’s BusyFlag to be released. If we have a square of waxed
paper available, we could put the flour onto the waxed paper and then
wait for the bowl:
public void makeCookie() {
theCupFlag.getBusyFlag();
theCup.measureOut(1, theFlour);
if (theBowlFlag.tryGetBusyFlag()) {
theBowl.putIngredients(theCup);
theBowl.mix();
theBowlFlag.freeBusyFlag();
theCupFlag.freeBusyFlag();
}
else {
WaxedPaper thePaper = new WaxedPaper();
thePaper.emptyOnto(theCup);
theCupFlag.freeBusyFlag();
theBowlFlag.getBusyFlag();
theBowl.putIngredients(thePaper);
theBowl.mix();
theBowlFlag.freeBusyFlag();
}
}This type of logic would not have been possible with the
synchronized keyword
since we cannot release the lock at will. To use Java’s
synchronized keyword, we would always have had to
use waxed paper:
public void makeCookie() {
WaxedPaper thePaper = new WaxedPaper();
synchronized(theCup) {
theCup.measureOut(1, theFlour);
thePaper.emptyOnto(theCup);
}
synchronized(theBowl) {
theBowl.putIngredients(thePaper);
theBowl.mix();
}
}The code using the synchronized keyword is
certainly cleaner, easier to understand, and easier to maintain. But
in a world where waxed paper is a rare commodity, the BusyFlag code
has the advantage of not using scarce resources unless it is
necessary to do so. In real-world programs, the scarce resource might
be a slow but always available implementation of a particular
algorithm, a very memory-intensive operation, or something similar.
Using the BusyFlag is also more complex than the technique of using the lock hierarchy. But here again, there is an advantage to the BusyFlag code: there is a larger degree of parallelism in the BusyFlag example than in the ordered lock acquisition example. In the BusyFlag example, one cook thread could be measuring the flour at the same time another cook thread is whisking the eggs for the omelette, whereas in the ordered lock acquisition example, the omelette maker must wait to whisk the eggs until the cookie maker has released both utensils.
You must decide whether these types of benefits outweigh the added complexity of the code when you design your Java program. If you start by creating a lock hierarchy, you’ll have simpler code at the possible expense of the loss of some parallelism. We think that it’s easier to write the simpler code first and then address the parallelism problems if they become a performance bottleneck.
In our last example of the
kitchen with the BusyFlag, we introduced the possibility of another
type of deadlock that could not have occurred had we used only
Java’s synchronized keyword. At issue is
what happens if a thread should die unexpectedly when it is holding a
lock.
Let’s simplify our example somewhat by changing the class so that it has only a single synchronized method. The class definition would look something like this:
public class Kitchen {
public synchronized void makeCookie() { ... }
}Now we have two cook threads, one that is executing the
makeCookie() method and another that is blocked
attempting to enter the makeCookie() method.
Under normal circumstances, the first thread completes the
makeCookie() method and exits the method, at
which time the second thread has the opportunity to enter the
makeCookie() method and make its own cookies.
What happens instead if the first thread encounters a runtime exception and terminates? Under many threading systems, this leads to a type of deadlock, because the thread that terminates does not automatically release the locks it held. Under those systems, the second thread would wait forever trying to make its batch of cookies because it can’t acquire the lock. In Java, however, locks are always given up when the thread leaves the scope of the synchronized block, even if it leaves that scope due to an exception. So in Java, this type of deadlock never occurs.
But if we use the BusyFlag class instead of Java’s
synchronized keyword, we’ve introduced the
possibility of this type of deadlock. In this case, our methods look
like this:
public void makeCookie() {
flag.getBusyFlag();
// ... Do some work ...
flag.freeBusyFlag();
}If in the process of doing some work we encounter a runtime exception, the BusyFlag will never be freed. This means that our second cook thread would never be able to make its batch of cookies. Note that this problem applies only to runtime exceptions, since Java requires you to catch all other types of exceptions. Often a runtime exception is a catastrophic error that you can’t recover from anyway, so it may not matter if you didn’t release the BusyFlag, but we wouldn’t make that assumption.
There is a way around this: we can use Java’s
finally clause to make sure the BusyFlag is
freed no matter what happens during the execution of our method. To
use the BusyFlag so that it has the same lock semantics as the
synchronized keyword, you need to do something
like this:
public void makeCookie() {
try {
flag.getBusyFlag();
// ... Do some work ...
} finally {
flag.freeBusyFlag();
}
}Now our BusyFlag behaves the same as if we’d used the
synchronized keyword. Clearly, in the examples
we’ve used in this chapter, we can always arrange our
try/finally clauses so that the
locks are released even when an exception is encountered. But in
other examples we’ve seen, this is not always possible. One
technique that is possible with the BusyFlag class is to release the
lock in a method other than the one in which the lock was acquired.
If you use that technique, you have to be aware that this new type of
deadlock is still possible.
By the way, the fact that Java’s
synchronized keyword does not allow this type of
deadlock is not necessarily a good thing. When a thread encounters a
runtime exception while it is holding a lock, there’s the
possibility—indeed, the expectation—that it will leave
the data it was manipulating in an inconsistent state. If another
thread is then able to acquire the lock, it may encounter this
inconsistent data and proceed erroneously. In our example, if the
first thread was in the middle of making chocolate-chip cookies when
the runtime exception occurred, it would have left a bunch of
ingredients in the bowl. Under normal circumstances, the
makeCookie() method would have cleaned out the
bowl, but when the exception occurred, that didn’t happen. So
now our second thread comes along attempting to make oatmeal-raisin
cookies; the end result is chocolate-chip-oatmeal-raisin cookies.
We could put the logic that cleans the bowl into the
finally clause in an attempt to prevent this
problem, but what happens if that method throws an exception? Given
Java’s semantics, this problem is impossible to solve. In fact,
it’s exactly this problem that led to the deprecation of the
stop() method: the stop()
method works by throwing an exception, which has the potential to
leave key resources in the Java virtual machine in an inconsistent
state.
Hence, we cannot solve this problem completely. In many cases, it’s better to use the BusyFlag and risk deadlock if a thread exits unexpectedly than to allow a second thread to use that inconsistent data. Consider a stock trading system in which a thread is in the process of updating the current price information when it encounters the runtime exception: if another thread accesses the incorrect current price and a trade is made on the wrong price, the exposure of the firm executing that trade could be in the millions of dollars. In cases like this, it’s really better to use some sort of back-end database that has transactional integrity built into it so that you’re protected against an unexpected thread termination. The logic to solve this problem is standard in every database package that implements a two-phase commit. You could write such logic into your Java program directly, but it’s difficult to get right.
[11] Obviously, the code examples in this section are not complete examples. In addition to lacking all the methods and classes to which we refer, we’re missing some other useful methods as well. For example, our class does not include a recipe for soup, since a multithreaded recipe would spoil the broth.