Deadlock

If you're working with a moderately complex multithreaded program, then sooner or later, you'll hit the problem of deadlock¹:

Deadlock is the phenomenon when, typically, two threads each hold an exclusive lock that the other thread needs in order to continue;
in principle, there could actually be more threads and locks involved;
it is generally liable to occur when threads acquire the same locks in different orders.

Deadlock can occur with any locking primitive. It notably occurs with the synchronized keyword, but it's liable to occur with locks, Semaphores, blocking queues etc.

When does deadlock occur?

Examples in textbooks always make deadlock seem more unlikely than it really is, because on a simple system with just two locks, it takes quite contrived code to occur. But in a complex application with many locks held and released all over the code, deadlock is a real-life problem. A couple of quite realistic example scenarios, that require related but subtly different solutions for reasons we'll discuss in a minute:

You have a single read-write database connection and also a lock used to control the consistency of some group of tables. For example, imagine you have a Users table and a Subscriptions table, and whenever you add an item to the Subscriptions table, you set a LastSubscriptionAdded field on the corresponding row in the Users table. To make sure the two tables remain in a consistent state, your server application keeps a lock, which is always acquired around modifications to the two tables. Now, imagine method 1 acquires the database connection first then attemps to acquire the lock; meanwhile, method 2 acquires the lock, before wanting to acquire the database connection. Deadlock will now ensue: method 2 is waiting for the database connection, which method 1 is sitting hogging. Meanwhile, method 1 is waiting for the lock, which method 2 is hogging. Neither will ever be able to proceed. If there are several connections available, then a milder form of temporary deadlock may occur, while method 2 waits for a connection to become available.
Your application manages resources (bank accounts, remote documents etc) that allow data to be transferred from one resource to the other. Each resource has a lock associated with it, and to perform a transfer, you must acquire the lock for each resource involved in the transfer. Now, two threads initiate transfers involving the same two resources. If the two threads are unlucky and attempt to grab the two resources in different oders, they are liable to deadlock.

Avoiding deadlock

Usually, the simplest and most efficient way to avoid deadlock is to ensure that resources are always acquired in some well-defined order.

Now, in an example such as our database locking example (1), this ordering could boil down to a programming policy. So long as all programmers know and apply the policy of acquiring the locks in some well-defined order, you'll avoid deadlock. For hopefully obvious reasons, we must release locks in the opposite order to that in which we acquired them, and should release them in a finally clause:

DbConnection conn = ConnectionPool.getConnection();
try {
  acquireUserTableLock();
  try {
    // ... update user tables ...
  } finally {
    releaseUserTableLock();
  }
} finally {
  ConnectionPool.release(conn);
}

The obvious problem is that everybody must remember to use the correct behaviour. A better strategy is generally to provide a method that combines acquisition and release of the two locks in the correct way:

DbConnection conn = ConnectionPool.getConnectionAndUsersLock();
try {
  // ... update user tables ...
} finally {
  ConnectionPool.releaseConnectionAndUsersLock(conn);
}

A clear advantage of the explicit Java Lock classes is they allow lock management code to be delegated to a different method in this way. The synchronized keyword has the restriction that lock acquisition has to be coded "there and then"; if you're working with synchronized-based locking, then programmers will just have to remember which order to acquire the locks in.

Avoiding deadlock with arbitrary locks

Our second example of data transfer between two documents/resources introduces another problem: the locks in question are for two arbitrary resources. In the the example we just looked at, it is presumably relatively straightforward to define "the user table lock" and "the connection pool" in our code, and thus define a lock ordering simply in the code. But what about two arbitrary lock objects, that may even be created on the fly?

Well, the answer is that we have to explicitly define some way of ordering them. If locking will only exist for the lifetime of the application, then one way of doing this is simply to use the identity hash code of the two objects. The identity hash code is an internal number that the JVM assigns to each object. It never changes for the lifetime of the application, and since it is just an integer, we can define an ordering by comparing hash codes:

public void acquireBothLocks(Resource r1, Resource r2) {
  Lock l1, l2;
  if (System.identityHashCode(r1) <
      System.identityHashCode(r2)) {
    l1 = r1.getLock(); l2 = r2.getLock();
  } else {
    l1 = r2.getLock(); l2 = r1.getLock();
  }
  l1.lock();
  l2.lock();
}

Otherwise, we can use other comparable data that is fixed for a particular resource, such as database primary keys.

1. In Spanish, deadlock is usually termed interbloqueo; in French, interblocage. For reasons that will become clear, another term sometimes used in English is "deadly embrace".

If you enjoy this Java programming article, please share with friends and colleagues. Follow the author on Twitter for the latest news and rants. Follow @BitterCoffey