Page History

The Java programming language does not prevent deadlocks or require their detection \[[JLS 05|AA. Java References#JLS 05]\]. Deadlocks can occur when two or more threads request and release locks in different orders. Consequently, deadlock can be avoided by acquiring and releasing locks in the same order. 

Additionally, synchronization should be limited to cases where it is absolutely necessary. For example, the {{paint()}}, {{dispose()}}, {{stop()}}, and {{destroy()}} methods should never be synchronized in an applet because they are always called and used from dedicated threads. The {{Thread.stop()}} and {{Thread.destroy()}} methods are deprecated. For more information, see [CON24-J. Do not use Thread.stop() to terminate threads].

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 intervals, until they succeed in acquiring the resource successfully.


h2. Noncompliant Code Example (Different Lock Orders)

This noncompliant code example can deadlock because of excessive synchronization. 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 // 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}

 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 will 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 will not occur when two threads request the same two locks but one thread completes its transfer before the other thread begins. In addition, deadlock will similarly not 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 by synchronizing on a {{private static final}} lock object before performing any account transfers.

{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 be performed concurrently. 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 final longAtomicLong 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                             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 threads require a lock to write information, while other threads require the lock to concurrently read the information.


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

The following immutable class {{WebRequest}} 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}

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);
    }
  }
}