Page History

"The Java programming language neither prevents nor requires detection of deadlock conditions" \[[JLS 05|AA. Java References#JLS 05]\]. Deadlocks can arise when two or more threads request and release locks in different orders. Consequently, to avoid deadlock, locks should be acquired and released in the same order, and synchronization should be limited to cases where it is absolutely necessary. For example, to avoid deadlocks in an applet, the {{paint()}}, {{dispose()}}, {{stop()}}, and {{destroy()}} methods should not be synchronized, because they are always called and used from dedicated threads. The {{Thread.stop()}} and {{Thread.destroy()}} methods are deprecated. For more information, see [CON13-J. Ensure that threads are stopped cleanly].

The advice of this guideline also applies to programs that need to work with a limited set of resources. For example, liveness issues can arise when two or more threads are waiting for each other to release resources such as database connections. These issues can be resolved by letting each waiting thread retry the operation at random time intervals, until it acquires the resource successfully.


h2. Noncompliant Code Example (Different Lock Orders)

This noncompliant code example can deadlock because of excessive synchronization. Objects of the {{BankAccount}} class represent bank accounts. The {{balanceAmount}} field represents the total balance amount available for a particular {{BankAccount}} object.  A user is allowed to initiate an operation that atomically transfers a specified amount from one account to another. 

{code:bgColor=#FFcccc}
final class BankAccount {
  private double balanceAmount;  // Total amount in bank account
		 

  BankAccount(double balance) {
    this.balanceAmount = balance;
  }

  // Deposits the amount from this object instance
  // to BankAccount instance argument ba 
  private void depositAmount(BankAccount ba, double amount) {
    synchronized (this) {
      synchronized (ba) {
        if (amount > balanceAmount) {
          throw new IllegalArgumentException(
               "Transfer cannot be completed"
          );
        }
        ba.balanceAmount += amount;
        this.balanceAmount -= amount; 
      }
    } 
  }
	  
  public static void initiateTransfer(final BankAccount first,
    final BankAccount second, final double amount) {

    Thread transfer = new Thread(new Runnable() {
        public void run() {
          first.depositAmount(second, amount);
        }
    });
    transfer.start();
  }
}
{code}

{code}
BankAccount a = new BankAccount(5000);
BankAccount b = new BankAccount(6000);
BankAccount.initiateTransfer(a, b, 1000); // starts thread 1
BankAccount.initiateTransfer(b, a, 1000); // starts thread 2

{code}

The two transfers, from instance {{a}} to {{b}} and {{b}} to {{a}}, are performed in their own threads. The first thread atomically transfers the amount from {{a}} to {{b}} by depositing it in account {{b}} and then withdrawing the same amount from {{a}}. The second thread performs the reverse operation; that is, it transfers the amount from {{b}} to {{a}}. When executing {{depositAmount()}}, the first thread acquires a lock on object {{a}}. The second thread could acquire a lock on object {{b}} before the first thread can. Subsequently, the first thread would request a lock on {{b}}, which is already held by the second thread. The second thread would request a lock on {{a}}, which is already held by the first thread. This constitutes a deadlock condition, because neither thread can proceed.

This noncompliant code example may or may not deadlock, depending on the scheduling details of the platform. Deadlock can occur when two threads request the same two locks in different orders and each thread obtains a lock that prevents the other thread from completing its transfer. Deadlock cannot occur when two threads request the same two locks but one thread completes its transfer before the other thread begins. In addition, deadlock cannot occur if the two threads request the same two locks in the same order (which would happen if they both transfer money from one account to a second account) or if two transfers involving distinct accounts occur concurrently.


h2. Compliant Solution ({{static}} Private Final Lock Object)

The deadlock can be avoided if a {{private static final}} lock object is used before any account transfers are performed.

{code:bgColor=#ccccff}
final class BankAccount {
  private double balanceAmount;  // Total amount in bank account	 
  private static final Object lock = new Object();

  BankAccount(double balance) {
    this.balanceAmount = balance;
  }

  // Deposits the amount from this object instance
  // to BankAccount instance argument ba 
  private void depositAmount(BankAccount ba, double amount) {
    synchronized (lock) {
      if (amount > balanceAmount) {
        throw new IllegalArgumentException(
            "Transfer cannot be completed");
      }
      ba.balanceAmount += amount;
      this.balanceAmount -= amount; 
    } 
  }
  
  public static void initiateTransfer(final BankAccount first,
    final BankAccount second, final double amount) {

    Thread transfer = new Thread(new Runnable() {
        @Override public void run() {
          first.depositAmount(second, amount);
        }
    });
    transfer.start();
  }
}
{code}

 performing only one transfer at a time. Two transfers involving four distinct accounts (with distinct target accounts) cannot happen concurrently. The impact of this penalty increases considerably as the number of {{BankAccount}} objects increase. Consequently, this solution does not scale well.


h2. Compliant Solution (Ordered Locks)

This compliant solution ensures that multiple locks are acquired and released in the same order. It requires that an ordering over {{BankAccount}} objects is available. The ordering is enforced by having the {{BankAccount}} class implement the {{java.lang.Comparable}} interface and override the {{compareTo()}} method.

{code:bgColor=#ccccff}
final class BankAccount implements Comparable<BankAccount> {
  private double balanceAmount;  // Total amount in bank account	 
  private final Object lock;

  private final long id; // Unique for each BankAccount
  private static longfinal AtomicLong NextIDnextID = new AtomicLong(0); // Next unused idID

  BankAccount(double balance) {
    this.balanceAmount = balance;
    this.lock = new Object();
    this.id = this.NextID++nextID.getAndIncrement();
  }

  @Override public int compareTo(BankAccount ba) {
     return (this.id > ba.id) ? 1 : (this.id < ba.id) ? -1 : 0;
  }

  // Deposits the amount from this object instance
  // to BankAccount instance argument ba 
  public void depositAmount(BankAccount ba, double amount) {
    BankAccount former, latter;
    if (compareTo(ba) < 0) {
      former = this;
      latter = ba;
    } else {
      former = ba;
      latter = this;
    }
    synchronized (former) {
      synchronized (latter) {
        if (amount > balanceAmount) {
          throw new IllegalArgumentException(
              "Transfer cannot be completed");
        }
        ba.balanceAmount += amount;
        this.balanceAmount -= amount; 
      } 
    }
  }
 
  public static void initiateTransfer(final BankAccount first,
    final BankAccount second, final double amount) {
   
    Thread transfer = new Thread(new Runnable() {
        @Override public void run() {
          first.depositAmount(second, amount);
        }
    });
    transfer.start();
  }
}
{code}

 to try acquiring both accounts' locks, but to release the locks if it fails and try again later.

{code:bgColor=#ccccff}
final class BankAccount {
  private double balanceAmount;  // Total amount in bank account
  private final Lock lock = new ReentrantLock();
  private final Random number = new Random(123L);
	 
  BankAccount(double balance) {
    this.balanceAmount = balance;
  }

  // Deposits the amount from this object instance
  // to BankAccount instance argument ba 
  private void depositAmount(BankAccount ba, double amount)
                             throws InterruptedException {
    while (true) {
      if (this.lock.tryLock()) {
        try {
          if (ba.lock.tryLock()) {
            try {
              if (amount > balanceAmount) {
                throw new IllegalArgumentException(
                    "Transfer cannot be completed");
              }
              ba.balanceAmount += amount;
              this.balanceAmount -= amount; 
              break;
            } finally {
              ba.lock.unlock();
            }
          }
        } finally {
          this.lock.unlock();
        }
      }
      int n = number.nextInt(1000);
      int TIME = 1000 + n; // 1 second + random delay to prevent livelock
      Thread.sleep(TIME);
    }
  }
  
  public static void initiateTransfer(final BankAccount first, 
    final BankAccount second, final double amount) {

    Thread transfer = new Thread(new Runnable() {
        public void run() {
          try {
            first.depositAmount(second, amount);
          } catch (InterruptedException e) {
            Thread.currentThread().interrupt(); // Reset interrupted status
          }
        }
    });
    transfer.start();
  }
}
{code}

}} class can be used when some thread requires a lock to write information, while other threads require the lock to concurrently read the information.


h2. Noncompliant Code Example (Different Lock Orders, Recursive)

Consider an immutable class {{WebRequest}} that encapsulates a web request received by a server.

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

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

  public long getBandwidth() {
    return bandwidth;
  }

  public long getResponseTime() {
    return responseTime;
  }
}
{code}

 requests. It calculates the average bandwidth and average response time required to service all incoming requests.

{code:bgColor=#FFcccc}
public final class WebRequestAnalyzer {
  private final Vector<WebRequest> requests = new Vector<WebRequest>();
  
  public boolean addWebRequest(WebRequest request) {
    return requests.add(new WebRequest(request.getBandwidth(),
                        request.getResponseTime()));
  }
  
  public double getAverageBandwidth() { 
    if (requests.size() == 0) {
      throw new IllegalStateException("The vector is empty!");   
    }  
    return calculateAverageBandwidth(0, 0);
  }

  public double getAverageResponseTime() { 
    if (requests.size() == 0) {
      throw new IllegalStateException("The vector is empty!");   
    }
    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
      return calculateAverageBandwidth(++i, bandwidth);
    }
  }

  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
    }
  }
}
{code}

{mc}
// Hidden main() methodreturn calculateAverageResponseTime(--i, responseTime);
  public static void main(String[] args) {
    final WebRequestAnalyzer wra = new WebRequestAnalyzer();
    wra.addWebRequest(new WebRequest(10,20));
    wra.addWebRequest(new WebRequest(30,60));
    new Thread(new Runnable() {
      public void run() {
        wra.getAverageResponseTime(); 
      }
    }).start();
	 
    new Thread(new Runnable() {
      public void run() {
        wra.getAverageBandwidth(); 
      }
     }).start();
  }
{mc}

The monitoring application is built around the {{WebRequestAnalyzer}} class that maintains a list of web requests using the {{requests}} vector.  That vector is suitably constructed using the {{addWebRequest()}} setter method. Any thread can get the average bandwidth or average response time of all web requests by invoking the {{getAverageBandwidth()}} and {{getAverageResponseTime()}} methods.

These methods use fine-grained locking by holding locks on individual elements (web requests) of the vector. The locks permit new requests to be added while the computations are still underway. Consequently, the statistics reported by the methods are accurate when they return the results.

Unfortunately, this implementation is prone to deadlock, because the recursive calls within the synchronized regions of these methods acquire the intrinsic locks in opposite numerical orders. That is, {{calculateAverageBandwidth()}} requests locks from index 0 up to {{requests.size()}} - 1, whereas {{calculateAverageResponseTime()}} requests them from index {{requests.size()}} - 1 down to 0. Because of recursion, no previously acquired locks are released by either method. Deadlock occurs when two threads call these methods out of order, because one thread calls {{calculateAverageBandwidth()}}, while the other calls {{calculateAverageResponseTime()}} before either method has finished executing.

For example, if there are 20 requests in the vector, and one thread calls {{getAverageBandwidth()}}, it acquires the intrinsic lock of {{WebRequest}} 0, the first element in the vector. Meanwhile, if a second thread calls {{getAverageResponseTime()}}, it acquires the intrinsic lock of {{WebRequest}} 19, the last element in the vector. Consequently, deadlock results because neither thread can acquire all of the locks and proceed with the calculations.

Note that the {{addWebRequest()}} method also has a race condition with {{calculateAverageResponseTime()}}. When the method is iterating over the vector, new elements can be added to the vector, invalidating the results of the previous computation. This race condition can be prevented by locking on the last element of the vector (when it contains at least one element) before inserting the element. However, it is likely that a programmer using a noncompliant code example such as this one has overlooked this case, because the race condition is benign.

h2. Compliant Solution 

In this compliant solution, the two calculation methods acquire and release locks in the same order, beginning with the first web request in the vector. 

{code:bgColor=#ccccff}
public final class WebRequestAnalyzer {
  private final Vector<WebRequest> requests = new Vector<WebRequest>();
  
  public boolean addWebRequest(WebRequest request) {
    return requests.add(new WebRequest(request.getBandwidth(), request.getResponseTime()));  
  }

  public double getAverageBandwidth() { 
    if (requests.size() == 0) {
      throw new IllegalStateException("The vector is empty!");   
    }
    return calculateAverageBandwidth(0, 0);
  }

  public double getAverageResponseTime() { 
    if (requests.size() == 0) {
      throw new IllegalStateException("The vector is empty!");   
    }
    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
    }
  }
}
{code}

Consequently, while one thread is calculating the average bandwidth or response time, another thread cannot interfere or induce deadlock. That is because the other thread would first need to synchronize on the first {{WebRequest}}, which is impossible until the first calculation is complete.

There is no need to lock on the last element of the vector in {{addWebRequest()}}, because locks are acquired in increasing order in all the methods and because updates to the vector are reflected in the results of the computations.

h2. Risk Assessment

Acquiring and releasing locks in the wrong order can result in deadlock.

|| Rule || Severity || Likelihood || Remediation Cost || Priority || Level ||
| CON12- J | low | likely | high | {color:green}{*}P3{*}{color} | {color:green}{*}L3{*}{color} |

h3. Automated Detection

[SureLogic Flashlight|http://www.surelogic.com/] can detect violations of this guideline. It flags both the noncompliant code examples by specifying: "potential for deadlock."

h3. Related Vulnerabilities

Any vulnerabilities resulting from the violation of this rule are listed on the [CERT website|https://www.kb.cert.org/vulnotes/bymetric?searchview&query=FIELD+KEYWORDS+contains+CON34-J].

h2. References

\[[JLS 05|AA. Java References#JLS 05]\] [Chapter 17, Threads and Locks|http://java.sun.com/docs/books/jls/third_edition/html/memory.html]
\[[Halloway 00|AA. Java References#Halloway 00]\] 
\[[MITRE 09|AA. Java References#MITRE 09]\] [CWE ID 412|http://cwe.mitre.org/data/definitions/412.html] "Unrestricted Lock on Critical Resource"

----
[!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_left.png!|CON11-J. Do not assume that declaring an object reference volatile guarantees visibility of its members]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_up.png!|11. Concurrency (CON)]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_right.png!|CON13-J. Ensure that threads are stopped cleanly]

}
  }
}

public final class WebRequestAnalyzer {
  private final Vector<WebRequest> requests = new Vector<WebRequest>();

  public boolean addWebRequest(WebRequest request) {
    return requests.add(new WebRequest(request.getBandwidth(),
                        request.getResponseTime()));
  }

  public double getAverageBandwidth() {
    if (requests.size() == 0) {
      throw new IllegalStateException("The vector is empty!");
    }
    return calculateAverageBandwidth(0, 0);
  }

  public double getAverageResponseTime() {
    if (requests.size() == 0) {
      throw new IllegalStateException("The vector is empty!");
    }
    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)) {
      // Acquires locks in increasing order
      responseTime += requests.get(i).getResponseTime();
      return calculateAverageResponseTime(++i, responseTime);
    }
  }
}