Concurrent programs is not a novelty today, almost every modern application executes in multiple threads. But as concurrency brought us better resource utilization and throughput, it also introduced a number of issues nonexistent in serial execution. One of them is deadlocks. A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does.

Suppose, as an example, two thread trying to transfer money between accounts: first one from account A to account B and the second one vice versa. First thread locks A for debiting. Second thread locks B for the same reason. Now the first thread asks for B’s lock for crediting, but the request is denied until the second thread releases it. So do the second thread will be denied for A’s lock. At this point both threads are blocked and will remain so forever. Oops, we have a deadlock.

A savvy developer should understand the causes of that liveness hazard and have a knowledge of how to prevent it. Coffman et al. (1971) showed that four conditions must hold for there to be a deadlock:

1. Mutual exclusion condition. Each resource is either currently assigned to exactly one thread or is available.
2. No preemption condition. Resources previously granted cannot be forcibly taken away from a thread. They must be explicitly released by the thread holding them.
3. Hold and wait condition. Thread currently holding resource that were granted earlier can request new resources.
4. Circular wait condition. There must be a circular chain of two or more threads, each of which is waiting for a resource held by the next member of the chain.

All four of these conditions must be present for a deadlock to occur. So, to make a program deadlock-free we must eliminate at least one of these conditions. Let’s see what we can do in a multithreaded program that protects shared resources with locks.

There is no point in attacking first two conditions, because this is what locks and synchronized blocks (Java) are all about: only one thread can hold a lock and it holds the lock until releases.

Hold and wait condition can be eliminated if all required locks can be obtained together. An immediate problem with this approach is that in many cases it is impossible to know how many lock-guarded resources will be needed until the run. Another problem is that resources will not be used optimally with this approach.

Only one condition remains — the circular wait, — which can be eliminated in several ways. One way is simply to have a rule saying that a thread can hold only one lock at any moment. If it needs a second one, it must release the first one. Of course, this is not always practical, but if you can get away with it, you are out of troubles. Another way to avoid the circular wait is to induce an ordering on the locks. Now the rule is this: threads can request locks whenever they want to, but all requests must be made in a predefined order.

Let’s see a lock ordering in action. We will secure our money transactions example by means of Java. One way to induce an ordering on objects is to use System.identityHashCode, which returns the value that would be returned by Object.hashCode. It involves a few extra lines of code, but helps us avoid deadlocking.

private static final Object tieLock = new Object();

public void transferMoney(final Account fromAcct,
                          final Account toAcct,
                          final BigDecimal amount)
        throws InsufficientFundsException {
   int fromHash = System.identityHashCode(fromAcct);
   int toHash = System.identityHashCode(toAcct);

   if (fromHash < toHash) {
       synchronized (fromAcct) {
           synchronized (toAcct) {
               new Helper().transfer();
           }
       }
   } else if (fromHash > toHash) {
       synchronized (toAcct) {
           synchronized (fromAcct) {
               new Helper().transfer();
           }
       }
   } else {
       synchronized (tieLock) {
           synchronized (fromAcct) {
               synchronized (toAcct) {
                   new Helper().transfer();
               }
           }
       }
   }

   class Helper {
       public void transfer() throws InsufficientFundsException {
           if (fromAcct.getBalance().compareTo(amount) < 0) {
               throw new InsufficientFundsException();
           } else {
               fromAcct.debit(amount);
               toAcct.credit(amount);
           }
       }
   }
}Code language: PHP (php)

We look at hash codes of the objects and lock them in the ascending order of hash values. In the rare case that two objects have the same hash code, we must use an arbitrary means of ordering the lock acquisitions, as this reintroduces the possibility of deadlock. To prevent inconsistent lock ordering in this case, a third “tie breaking” lock is used. By acquiring the tie-breaking lock before acquiring either Account lock, we ensure that only one thread at a time performs the risky task of acquiring two locks in an arbitrary order, eliminating the possibility of deadlock.

So, as a note to keep in mind, if you must acquire multiple locks, lock ordering must be a part of your design: try to minimize the number of potential locking interactions, and follow and document a lock-ordering protocol for locks that may be acquired together.