Avoid synchronization deadlocks

In 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 transferMoney(Account fromAccount, 
                            Account toAccount, 
                            DollarAmount amountToTransfer) { 
    Account firstLock, secondLock;
    if (fromAccount.accountNumber() == toAccount.accountNumber())
      throw new Exception("Cannot transfer from account to itself");
    else if (fromAccount.accountNumber() < toAccount.accountNumber()) {
      firstLock = fromAccount;
      secondLock = toAccount;
    }
    else {
      firstLock = toAccount;
      secondLock = fromAccount;
    }
    synchronized (firstLock) {
      synchronized (secondLock) { 
        if (fromAccount.hasSufficientBalance(amountToTransfer) { 
          fromAccount.debit(amountToTransfer); 
          toAccount.credit(amountToTransfer);
        }
      }
    }
  }

Now the order in which the accounts are specified in the call to transferMoney() doesn’t matter; the locks are always acquired in the same order.

The most important part: Documentation

A critical — but often overlooked — element of any locking strategy is documentation. Unfortunately, even in cases where much care is taken to design a locking strategy, often much less effort is spent documenting it. If your program uses a small set of singleton locks, you should document your lock-ordering assumptions as clearly as possible so that future maintainers can meet the lock-ordering requirements. If a method must acquire a lock to perform its function or must be called with a specific lock held, the method’s Javadoc should note that fact. That way, future developers will know that calling a given method might entail acquiring a lock.

Few programs or class libraries adequately document their locking use. At a minimum, every method should document the locks that it acquires and whether callers must hold a lock to call the method safely. In addition, classes should document whether or not, or under what conditions, they are thread safe.

Focus on locking behavior at design time

Because deadlocks are often not obvious and occur infrequently and unpredictably, they can cause serious problems in Java programs. By paying attention to your program’s locking behavior at design time and defining rules for when and how to acquire multiple locks, you can reduce the likelihood of deadlocks considerably. Remember to document your program’s lock acquisition rules and its use of synchronization carefully; the time spent documenting simple locking assumptions will pay off by greatly reducing the chance of deadlock and other concurrency problems later.

Source: www.infoworld.com