Page History

To avoid data corruption in multithreaded Java programs, shared data must be protected from concurrent modifications and accesses. This can be performed at the object level by using synchronized methods or blocks, or by using dynamic lock objects. However, excessive use of locking may result in deadlocks (See CON08-J. Do not call alien methods that synchronize on the same objects as any callers in the execution chain).

To avoid deadlock, locks should be acquired and released in the same order and synchronization should be limited to where it is absolutely necessary. For instance, to avoid deadlocks, the paint(), dispose(), stop(), destroy() methods in an applet should not be synchronized because they are always called and used from dedicated threads.

...

class BankAccount {
  private int balanceAmount;  // Total amount in bank account
	 
  private BankAccount(int balance) {
    this.balanceAmount = balance;
  }

  // Deposits the amount from this object instance to BankAccount instance argument ba 
  private void depositAllAmount(BankAccount ba) {
    synchronized (this) {
      synchronized(ba) {
        ba.balanceAmount += this.balanceAmount;
        this.balanceAmount = 0; // withdrawWithdraw all amount from this instance
        ba.displayAllAmount();  // Display the new balanceAmount in ba (may cause deadlock)
      }
    } 
  }
  
  private synchronized void displayAllAmount() {
    System.out.println(balanceAmount);
  }

  public static void initiateTransfer(final BankAccount first, final BankAccount second) {
    Thread t = new Thread(new Runnable() {
      public void run() {
        first.depositAllAmount(second);
      }
    });
    t.start();
  }
}

...

The threads in this program request monitors in varying order different orders depending on the interleaving of method calls. If Thread T1 finishes executing before Thread T2, or T2 before T1, there are no issues because in these cases, locks are acquired and released in the same order. Sequences where the threads alternate, such as, T1, T2, T1, T2 may cause a deadlock.

Compliant Solution (

...

static internal private lock)

The deadlock can be avoided by using a single lock to acquire before doing private static final internal lock object before performing any account transfers.

class BankAccount {
  private int balanceAmount;  // Total amount in bank account
	 
  private static final Object lock;

  private BankAccount(int balance) {
    this.balanceAmount = balance;
    this.lock = new Object();
  }

  // Deposits the amount from this object instance to BankAccount instance argument ba 
  private void depositAllAmount(BankAccount ba) {
    synchronized (lock) {
      ba.balanceAmount += this.balanceAmount;
      this.balanceAmount = 0; // withdrawWithdraw all amount from this instance
      ba.displayAllAmount();  // Display the new balanceAmount in ba (may cause deadlock)
    } 
  }
  
  private void displayAllAmount() {
    synchronized (lock) {
      System.out.println(balanceAmount);
    }
  }

  public static void initiateTransfer(final BankAccount first, final BankAccount second) {
    Thread t = new Thread(new Runnable() {
      public void run() {
        first.depositAllAmount(second);
      }
    });
    t.start();
  }
}

In this scenario, if two threads with two different BankAccount objects try to tranfer transfer to each others' accounts simultaneously, deadlock cannot occur. One thread will acquire the private lock, complete its transfer, and release the lock, before the other thread may can proceed.

This solution comes with a performance penalty , as because a private static lock restricts the system to performing only performing one transfer at a time. Two transfers involving four distinct accounts (and with distinct target accounts) may not happen concurrently. The impact of this penalty increases considerably as the number of BankAccount objects increase. Consequently, this solution does not scale very well.

...

class BankAccount implements Comparable {
  private int balanceAmount;  // Total amount in bank account	 
  private final Object lock;

  private BankAccount(int balance) {
    this.balanceAmount = balance;
    this.lock = new Object();
  }

  // Deposits the amount from this object instance to BankAccount instance argument ba 
  private void depositAllAmount(BankAccount ba) {
    BankAccount former, latter;
    if (compareTo(ba) < 0) {
      former = this;
      latter = ba;
    } else {
      former = ba;
      latter = this;
    }
    synchronized (former) {
      synchronized (latter) {
        ba.balanceAmount += this.balanceAmount;
        this.balanceAmount = 0; // withdraw all amount from this instance
        ba.displayAllAmount(); // Display the new balanceAmount in ba (may cause deadlock)
      } 
    }
  }
 
  private synchronized void displayAllAmount() {
    System.out.println(balanceAmount);
  }

  public static void initiateTransfer(final BankAccount first, final BankAccount second) {
    Thread t = new Thread(new Runnable() {
      public void run() {
        first.depositAllAmount(second);
      }
    });
    t.start();
  }

  public int compareTo(BankAccount ba) {
   if(this.balanceAmount < ba.balanceAmount) {
     return -1;
   } else if(this.balanceAmount > ba.balanceAmount) {
     return 1;
   } else {
     return 0;
   }
  }
}

In this compliant solution, whenever Whenever a transfer occurs, the two BankAccount objects are ordered , with so that the first object's lock being is acquired before the second object's lock. Consequently, if two threads attempt transfers between the same two accounts, they will both try to acquire the first account's lock before the second account's lock first, with the result that one thread will acquire both locks, complete the transfer, and release both locks before the other thread may proceed.

Unlike the previous compliant solution, this solution incurs no performance penalty , as because multiple transfers can occur concurrently as long as the transfers involve distinct target accounts.

...

In this compliant solution, each BankAccount has a java.util.concurrent.locks.ReentrantLock associated with it. This permits the depositAllAmount() method to try acquiring both accounts' locks, but releasing its the locks if it fails, and trying again later.

...

Deadlock is impossible in this code, compliant solution because no method grabs a lock and holds it indefinitely. If a the current object's lock is acquired, but the system cannot proceed immediately, it releases the lock and sleeps before requesting the lock againthe second lock is unavailable, the first lock is released and the thread sleeps for some specified time before retrying.

Code that uses this lock behaves similar to synchronized code that uses the traditional monitor lock. ReentrantLock provides several other capabilities, for instance, the tryLock() method does not block waiting if another thread is already holding the lock. The class java.util.concurrent.locks.ReentrantReadWriteLock can be used when some thread requires a lock to write information while other threads require the lock to concurrently read the information.

Noncompliant Code Example

Consider a an immutable class WebRequest that encapsulates a web request to a server.

// Immutable WebRequest
public final class WebRequest {
  private final long bandwidth;
  private final long responseTime;

  public long getBandwidth() {
    return bandwidth;
  }

  public long getResponseTime() {
    return responseTime;
  }
 
  public WebRequest(long bandwidth, long responseTime) {
    this.bandwidth = bandwidth;
    this.responseTime = responseTime;
  }
}

...

public class WebRequestAnalyzer {
  private final Vector<WebRequest> requests = new Vector<WebRequest>();
  
  public boolean addWebRequest(WebRequest request) {
    // Lock on last element to prevent data race with the calculatecalculateAverageResponseTime() methodsmethod
    synchronized (requests.lastElement()) {
      // Defensive copying
      return requests.add(new WebRequest(request.getBandwidth(), request.getResponseTime()));
    }
  }
  
  public double getAverageBandwidth() { 
    return calculateAverageBandwidth(0, 0);
  }

  public double getAverageResponseTime() { 
    return calculateAverageResponseTime(requests.size() - 1, 0);
  }

  private double calculateAverageBandwidth(int i, long bandwidth) { 
    if (i > requests.size()) {
      return bandwidth / requests.size();
    }
    synchronized (requests.elementAt(i)) {
      bandwidth += requests.get(i).getBandwidth();
      return calculateAverageBandwidth(++i, bandwidth); // Acquires locks in increasing order 
    }
  }

  private double calculateAverageResponseTime(int i, long responseTime) { 
    if (i <= -1) {		 
      return responseTime / requests.size();
    }     
    synchronized (requests.elementAt(i)) {
      responseTime += requests.get(i).getResponseTime();
      return calculateAverageResponseTime(--i, responseTime); // Acquires locks in decreasing order
    }
  }
}

The monitoring application is built upon class WebRequestAnalyzer which that maintains a list of web requests using vector requests. The vector requests is suitably initialized after defensively copying the requests. Any thread can get the average bandwidth or average response time of all web requests by invoking the getAverageBandwidth() and getAverageResponseTime() methods.

...

public class WebRequestAnalyzer {
  private final Vector<WebRequest> requests = new Vector<WebRequest>();
  
  public boolean addWebRequest(WebRequest request) {
    // Lock on last elementNo need to prevent data race withlock on the calculatelast methods
element because locks are synchronized (requests.lastElement()) {
      // Defensive copying
  acquired in increasing order
    return requests.add(new WebRequest(request.getBandwidth(), request.getResponseTime()));
    }
  }

  public double getAverageBandwidth() { 
    return calculateAverageBandwidth(0, 0);
  }

  public double getAverageResponseTime() { 
    return calculateAverageResponseTime(0, 0);
  }

  private double calculateAverageBandwidth(int i, long bandwidth) { 
    if (i > requests.size()) {
      return bandwidth / requests.size();
    }
    synchronized (requests.elementAt(i)) { // Acquires locks in increasing order
      bandwidth += requests.get(i).getBandwidth();
      return calculateAverageBandwidth(++i, bandwidth);  
    }
  }

  private double calculateAverageResponseTime(int i, long responseTime) { 
    if (i > requests.size()) {		 
      return responseTime / requests.size();
    }     
    synchronized (requests.elementAt(i)) {
      responseTime += requests.get(i).getResponseTime();
      return calculateAverageResponseTime(++i, responseTime); // Acquires locks in increasing order
    }
  }
}

...