Avoid synchronization
deadlocks
Tutorial Details:
Avoid synchronization deadlocks
Avoid synchronization deadlocks
By: By Brian Goetz
Use a consistent, defined synchronization ordering to keep your apps running
n my earlier article " Double-Checked Locking: Clever, but Broken " ( JavaWorld, February 2001), I described how several common techniques for avoiding synchronization are in fact unsafe, and recommended a strategy of "When in doubt, synchronize." In general, you should synchronize whenever you are reading any variable that might have been previously written by a different thread, or whenever you are writing any variable that might be subsequently read by another thread. Additionally, while synchronization carries a performance penalty, the penalty associated with uncontended synchronization is not as great as some sources have suggested, and has reduced steadily with each successive JVM implementation. So it seems that there is now less reason than ever to avoid synchronizing. However, another risk is associated with excessive synchronization: deadlock.
What is a deadlock?
We say that a set of processes or threads is deadlocked when each thread is waiting for an event that only another process in the set can cause. Another way to illustrate a deadlock is to build a directed graph whose vertices are threads or processes and whose edges represent the "is-waiting-for" relation. If this graph contains a cycle, the system is deadlocked. Unless the system is designed to recover from deadlocks, a deadlock causes the program or system to hang.
Synchronization deadlocks in Java programs
Deadlocks can occur in Java because the synchronized keyword causes the executing thread to block while waiting for the lock, or monitor, associated with the specified object. Since the thread might already hold locks associated with other objects, two threads could each be waiting for the other to release a lock; in such a case, they will end up waiting forever. The following example shows a set of methods that have the potential for deadlock. Both methods acquire locks on two lock objects, cacheLock and tableLock , before they proceed. In this example, the objects acting as locks are global (static) variables, a common technique for simplifying application-locking behavior by performing locking at a coarser level of granularity:
Listing 1. A potential synchronization deadlock
public static Object cacheLock = new Object();
public static Object tableLock = new Object();
...
public void oneMethod() {
synchronized (cacheLock) {
synchronized (tableLock) {
doSomething();
}
}
}
public void anotherMethod() {
synchronized (tableLock) {
synchronized (cacheLock) {
doSomethingElse();
}
}
}
Now, imagine that thread A calls oneMethod() while thread B simultaneously calls anotherMethod() . Imagine further that thread A acquires the lock on cacheLock , and, at the same time, thread B acquires the lock on tableLock . Now the threads are deadlocked: neither thread will give up its lock until it acquires the other lock, but neither will be able to acquire the other lock until the other thread gives it up. When a Java program deadlocks, the deadlocking threads simply wait forever. While other threads might continue running, you will eventually have to kill the program, restart it, and hope that it doesn't deadlock again.
Testing for deadlocks is difficult, as deadlocks depend on timing, load, and environment, and thus might happen infrequently or only under certain circumstances. Code can have the potential for deadlock, like Listing 1, but not exhibit deadlock until some combination of random and nonrandom events occur, such as the program being subjected to a certain load level, run on a certain hardware configuration, or exposed to a certain mix of user actions and environmental conditions. Deadlocks resemble time bombs waiting to explode in our code; when they do, our programs simply hang.
Inconsistent lock ordering causes deadlocks
Fortunately, we can impose a relatively simple requirement on lock acquisition that can prevent synchronization deadlocks. Listing 1's methods have the potential for deadlock because each method acquires the two locks in a different order. If Listing 1 had been written so that each method acquired the two locks in the same order, two or more threads executing these methods could not deadlock, regardless of timing or other external factors, because no thread could acquire the second lock without already holding the first. If you can guarantee that locks will always be acquired in a consistent order, then your program will not deadlock.
Deadlocks are not always so obvious
Once attuned to the importance of lock ordering, you can easily recognize Listing 1's problem. However, analogous problems might prove less obvious: perhaps the two methods reside in separate classes, or maybe the locks involved are acquired implicitly through calling synchronized methods instead of explicitly via a synchronized block. Consider these two cooperating classes, Model and View , in a simplified MVC (Model-View-Controller) framework:
Listing 2. A more subtle potential synchronization deadlock
public class Model {
private View myView;
public synchronized void updateModel(Object someArg) {
doSomething(someArg);
myView.somethingChanged();
}
public synchronized Object getSomething() {
return someMethod();
}
}
public class View {
private Model underlyingModel;
public synchronized void somethingChanged() {
doSomething();
}
public synchronized void updateView() {
Object o = myModel.getSomething();
}
}
Listing 2 has two cooperating objects that have synchronized methods; each object calls the other's synchronized methods. This situation resembles Listing 1 -- two methods acquire locks on the same two objects, but in different orders. However, the inconsistent lock ordering in this example is much less obvious than that in Listing 1 because the lock acquisition is an implicit part of the method call. If one thread calls Model.updateModel() while another thread simultaneously calls View.updateView() , the first thread could obtain the Model 's lock and wait for the View 's lock, while the other obtains the View 's lock and waits forever for the Model 's lock.
You can bury the potential for synchronization deadlock even deeper. Consider this example: You have a method for transferring funds from one account to another. You want to acquire locks on both accounts before performing the transfer to ensure that the transfer is atomic. Consider this harmless-looking implementation:
Listing 3. An even more subtle potential synchronization deadlock
public void transferMoney(Account fromAccount,
Account toAccount,
DollarAmount amountToTransfer) {
synchronized (fromAccount) {
synchronized (toAccount) {
if (fromAccount.hasSufficientBalance(amountToTransfer) {
fromAccount.debit(amountToTransfer);
toAccount.credit(amountToTransfer);
}
}
}
}
Even if all methods that operate on two or more accounts use the same ordering, Listing 3 contains the seeds of the same deadlock problem as Listings 1 and 2, but in an even subtler way. Consider what happens when thread A executes:
transferMoney(accountOne, accountTwo, amount);
While at the same time, thread B executes:
transferMoney(accountTwo, accountOne, anotherAmount);
Again, the two threads try to acquire the same two locks, but in different orders; the deadlock risk still looms, but in a much less obvious form.
How to avoid deadlocks
One of the best ways to prevent the potential for deadlock is to avoid acquiring more than one lock at a time, which is often practical. However, if that is not possible, you need a strategy that ensures you acquire multiple locks in a consistent, defined order.
Depending on how your program uses locks, it might not be complicated to ensure that you use a consistent locking order. In some programs, such as in Listing 1, all critical locks that might participate in multiple locking are drawn from a small set of singleton lock objects. In that case, you can define a lock acquisition ordering on the set of locks and ensure that you always acquire locks in that order. Once the lock order is defined, it simply needs to be well documented to encourage consistent use throughout the program.
Shrink synchronized blocks to avoid multiple locking
In Listing 2, the problem grows more complicated because, as a result of calling a synchronized method, the locks are acquired implicitly. You can usually avoid the sort of potential deadlocks that ensue from cases like Listing 2 by narrowing the synchronization's scope to as small a block as possible. Does Model.updateModel() really need to hold the Model lock while it calls View.somethingChanged() ? Often it does not; the entire method was likely synchronized as a shortcut, rather than because the entire method needed to be synchronized. However, if you replace synchronized methods with smaller synchronized blocks inside the method, you must document this locking behavior as part of the method's Javadoc. Callers need to know that they can call the method safely without external synchronization. Callers should also know the method's locking behavior so they can ensure that locks are acquired in a consistent order.
A more sophisticated lock-ordering technique
In other situations, like Listing 3's bank account example, applying the fixed-order rule grows even more complicated; you need to define a total ordering on the set of objects eligible for locking and use this ordering to choose the sequence of lock acquisition. This sounds messy, but is in fact straightforward. Listing 4 illustrates that technique; it uses a numeric account number to induce an ordering on Account objects. (If the object you need to lock lacks a natural identity property like an account number, you can use the Object.identityHashCode() method to generate one instead.)
Listing 4. Use an ordering to acquire locks in a fixed sequence
public void transferMo
Read
Tutorial at: Click here to view the tutorial
Rate Tutorial: Avoid synchronization
deadlocks
View Tutorial: Avoid synchronization
deadlocks
Related
Tutorials:
 Programming Java threads in the
real world, Part
2 - JavaWorld -
October 1998
Programming Java threads in the
real world, Part
2 - JavaWorld -
October 1998
|
Programming Java threads in the
real world, Part
3 - JavaWorld -
November 1998
Programming Java threads in the
real world, Part
3 - JavaWorld -
November 1998
|
Reading textual data: Fun with
streams - JavaWorld - April 1999
Reading textual data: Fun with
streams - JavaWorld - April 1999
|
Java Tip 79: Interact with garbage collector to avoid
memory leaks - JavaWorld
Java Tip 79: Interact with garbage collector to avoid
memory leaks - JavaWorld
|
Direct network
traffic of EJBs - JavaWorld November
1999
Direct network
traffic of EJBs - JavaWorld November
1999
|
Java performance programming,
Part 3: Managing collections - JavaWorld February 2000
Java performance programming,
Part 3: Managing collections - JavaWorld February 2000
|
Use the JVM
Profiler Interface for accurate timing -
JavaWorld
Use the JVM
Profiler Interface for accurate timing -
JavaWorld
|
Optimize a query on a Map - JavaWorld November 2000
Optimize a query on a Map - JavaWorld November 2000
|
Double-checked
locking: Clever, but broken - JavaWorld February
2001
Double-checked
locking: Clever, but broken - JavaWorld February
2001
|
Warning! Threading in
a multiprocessor world - JavaWorld February 2001
Warning! Threading in
a multiprocessor world - JavaWorld February 2001
|
Can double-checked locking be fixed? - JavaWorld May 2001
Can double-checked locking be fixed? - JavaWorld May 2001
|
Avoid synchronization
deadlocks
Avoid synchronization
deadlocks
|
Can ThreadLocal solve the double-checked locking
problem?
Can ThreadLocal solve the double-checked locking
problem?
|
Diagnose common runtime problems with
hprof
Diagnose common runtime problems with
hprof
|
Very
interesting
Very
interesting
|
elegant turnaround
elegant turnaround
|
Data Syncronization Tool
Data Syncronization Tool
Daffodil Replicator is a powerful Open Source data synchronization tool that allows bi-directional data synchronization between heterogeneous databases supporting JDBC drivers. Its flexible publish and subscribe model support
|
The ABCs of Synchronization, Part 1
Threads may execute in a manner where their paths of execution are completely independent of each other. Neither thread depends upon the other for assistance. For example, one thread might execute a print job, while a second thread repaints a window. And
|
Advanced Synchronization in Java Threads
In this chapter, we look at some of the more advanced issues related to data synchronization--specifically, timing issues related to data synchronization. When you write a Java program that makes use of several threads, issues related to data synchronizat
|
Using JConsole to Monitor Applications
JConsole is the Java Monitoring and Management Console, a new graphical tool shipped in J2SE JDK 5.0. This article describes how JConsole can be used to observe information about an application running on the Java platform, with an overview of the J2SE 5.
|
|
|
|
