Page History

To avoid data corruption in multithreaded Java programs, one has to protect the data that is shared between multiple threads as described in detail shared data must be protected from concurrent modifications and accesses, as detailed in CON30-J. Synchronize access to shared mutable variables. This can be done at the object level by using synchronized blocks (coarse-grained locking), as a result locking out other threads from interfering. If synchronization is used judiciously, deadlocks do not usually crop up (See CON00-J. Do not invoke a superclass method or constructor from a synchronized region in the subclass) 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.

...

This noncompliant code example shows a more subtle deadlock issue caused due to incorrect implementation of synchronizationthat manifests itself when synchronization is implemented incorrectly. Assume that an attacker has two bank accounts and is capable of requesting two amount transfer operations in succession. This corresponds to two threads as shown in main(). Objects a and b are constructed where such that the amount will be transferred from a to b by first depositing the amount from a to b and then zeroing out a (and vice-versa for during the second call to withdraw b.deposit()).

An insidious deadlock condition can sometimes arise. Both the threads invoke the synchronized deposit method on objects a and b respectively and there is no interleaving of locks. However, the deposit method is designed to request a lock on object a for the first thread and object b for the second. If both threads have acquired separate locks together and the call to withdraw() requests an already held lock, there is a deadlock situation. In case Thread 1 finishes executing before Thread 2, there would not be any issues. Sequences where the threads alternate, such as, T1, T2, T1, T2 can result in a deadlock (Tx = Thread number).

class BadLocks {
  private int balance;  // totalTotal amount
	 
  private BadLocks(int balance) {
    this.balance = balance;
  }

  private synchronized void withdraw(BadLocks bl) {
    System.out.println("Withdrawing amount...");
    this.balance = 0; 
  }

  private synchronized void deposit(BadLocks bl) {
    System.out.println("Depositing amount...");
    bl.balance += this.balance;
    bl.withdraw(bl);
  }

  public static void main(String[] args) throws Exception {
    final BadLocks a = new BadLocks(5000);
    final BadLocks b = new BadLocks(6000);
		
    // These two threads correspond to two malicious requests triggered by the attacker
    Thread t1 = new Thread(new Runnable() {
      public void run() {
        a.deposit(b);
      }
    });
 
    Thread t2 = new Thread(new Runnable() {
      public void run() {
        b.deposit(a);
      }
    });
    t1.start();
    t2.start();
  }
}

...

To be compliant, do not request a lock when it is already held by another object where that object is waiting for the requesting object to release its own lock. This can be achieved by invoking the withdraw() method without qualifying it with the bl parameter.

...

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<noOfStocksn < noOfStocks; n++) {
      balances[n] = 10000;
      locks[n] = new Object();
    }
  }

  static void transfer(Transfer t) {
    int lo, hi;
    if (t.fundFrom > t.fundTo) { // acquiresAcquires 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("ActualThe 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 As it is not possible to 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 raw Objects (locks) can be used.

This compliant solution avoids deadlocks because every thread requests monitors in the same order and as a result, 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 < n<noOfStocksnoOfStocks; 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("ActualThe actual balance is " + actual);
  }
}

...

Fine-grained locking may result in deadlocks if some thread does not always request locks in the same order as others.

...