CON34-J. Avoid deadlock by requesting fine-grained locks in the proper order

To avoid data corruption in multithreaded Java programs, one has to protect the data that is shared between multiple threads as described in detail in CON30-J. Synchronize access to shared mutable variables. This can be done at the object level by using synchronized blocks (coarse-grained locking), thus locking out other threads from interfering. If synchronization is used judiciously, (See CON00-J. Use synchronization judiciously) deadlocks do not usually crop up.

If however, one follows a fine-grained locking approach by using member locks, deadlocks can still arise unless it is ensured that each and every thread always requests locks in the same order.

Noncompliant Code Example

In this noncompliant code example, a deadlock occurs if the transfer method acquires the monitors in decreasing numeric order, while the sumHelper method uses an increasing numeric order to acquire its locks.

class Stocks implements FundConstants {
  static int[] balances = new int[noOfStocks];
  static Object[] locks = new Object[noOfStocks];
  static
  {
    for (int n=0; n<noOfStocks; n++) {
      balances[n] = 10000;
      locks[n] = new Object();
    }
  }

  static void transfer(Transfer t) {
    int lo, hi;
    if (t.fundFrom > t.fundTo) {// acquires the monitors in decreasing numeric order
      lo = t.fundFrom;
      hi = t.fundTo;
     } else {
      lo = t.fundTo;
      hi = t.fundFrom;
     }
     
     synchronized (locks[lo]) {
       synchronized (locks[hi]) {
         balances[t.fundFrom] -= t.amount;
         balances[t.fundTo] += t.amount;
       }
      }
    }

  static int sumHelper (int next) {
    synchronized (locks[next]) {
      if (next == (noOfStocks-1)) {
        return balances[next];
      } else {
       return balances[next] + sumHelper(next+1);
     }
   }
 }

  static void checkSystem() {
    int actual = 0;
    actual = sumHelper(0);
    System.out.println("Actual balance is" + actual);
  }
}

Compliant Solution

To implement a fine-grained locking strategy, request a separate lock for each position in the balances array. Since one cannot lock on primitive types, a direct lock on the items in the balances array cannot be obtained. Instead, one has to create an array of Object (locks).

This compliant solution avoids deadlocks because every thread requests monitors in the same order and thus the locks are acquired (and released) correctly.

class Stocks implements FundConstants {
  static int[] balances = new int[noOfStocks];
  static Object[] locks = new Object[noOfStocks];
  
  static
  {
     for (int n=0; n<noOfStocks; n++) {
       balances[n] = 10000;
       locks[n] = new Object();
     }
  }

  static void transfer(Transfer t) {
    int lo, hi;
    if (t.fundFrom < t.fundTo) {
      lo = t.fundFrom;
      hi = t.fundTo;
    } else {
        lo = t.fundTo;
        hi = t.fundFrom;
    }
    synchronized (locks[lo]) {
      synchronized (locks[hi]) {
        balances[t.fundFrom] -= t.amount;
        balances[t.fundTo] += t.amount;
      }
    }
  }

  static int sumHelper (int next) {
    synchronized (locks[next]) {
      if (next == (noOfStocks-1)) {
        return balances[next];
      } else {
        return balances[next] +
        sumHelper(next+1);
      }
    }
  }

  static void checkSystem() {
    int actual = 0;
    actual = sumHelper(0);
    System.out.println("Actual balance is " + actual);
  }
}