Page History

To avoid data corruption in multithreaded Java programs, shared data must be protected from concurrent modifications and accesses. Locking can be performed at the object level using synchronized methods, synchronized blocks, or the java.util.concurrent dynamic lock objects. However, excessive use of locking can result in deadlocks.

Java doesneither not preventprevents deadlocks ornor requirerequires their detection \[[JLS 2005|AA. Bibliography#JLS 05]\]. Deadlock can occur when two or more threads request and release locks in different orders. Consequently, programs deadlockare required canto beavoid avoideddeadlock by acquiring and releasing locks in the same order.

...

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 Users are allowed to initiate an operation that atomically transfers a specified amount from one account to another.

...

Objects of this class are prone to deadlock. An attacker that who has two bank accounts can construct two threads that initiate balance transfers from two different BankAccount object instances a and b. For example, consider the following code:

...

This noncompliant code example may or may not deadlock, depending on the scheduling details of the platform. Deadlock will occur when (a) two threads request the same two locks in different orders, and (b) each thread obtains a lock that prevents the other thread from completing its transfer. Deadlock will not occur be avoided when two threads request the same two locks but one thread completes its transfer before the other thread begins. Similarly, deadlock will not occur be avoided 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.

Compliant Solution (Private Static Final Lock Object)

The deadlock can be avoided This compliant solution avoids deadlock by synchronizing on a private static final lock object before performing any account transfers.

...

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

This solution comes with imposes a performance penalty because a private static lock restricts the system to performing only one transfer at a timetransfers sequentially. 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 fails to scale well.

Compliant Solution (Ordered Locks)

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

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 long NextID = 0; // Next unused ID

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

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

Whenever a transfer occurs, the two BankAccount objects are ordered so that the first object's lock is acquired before the second object's lock. Consequently, if when two threads attempt transfers between the same two accounts, they will both each try to acquire the first account's lock before the acquiring the second account's lock. As a resultConsequently, one thread will acquire both locks, complete the transfer, and release both locks before the other thread can proceed.

Unlike in the previous compliant solution, this solution permits multiple concurrent transfers can happen concurrently, as long as they the transfers involve distinct target accounts.

...

In this compliant solution, each BankAccount has a java.util.concurrent.locks.ReentrantLock. This design permits the depositAmount() method to try attempt to acquire the locks of both accounts and , to release the locks if it fails, and to try again later if necessary.

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

Deadlock is impossible in this compliant solution because no method grabs a lock and holds it locks are never held indefinitely. If the current object's lock is acquired but the second lock is unavailable, the first lock is released and the thread sleeps for some specified amount of time before attempting to reacquire the lock.

Code that uses this lock locking strategy has behavior similar to that of synchronized code that uses the traditional monitor lock. ReentrantLock also provides several other capabilities. For example, the tryLock() method does not block never blocks waiting, if when another thread is already holding holds the lock. The Further, the java.util.concurrent.locks.ReentrantReadWriteLock class can be used .locks.ReentrantReadWriteLock class multiple-reader/single-writer semantics, and is useful when some threads require a lock to write information, while other threads require the lock to concurrently read the information.

...

This noncompliant code example monitors web requests and provides routines for calculating the average bandwidth and response time required to service serve incoming requests.

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();
      // 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();
      // Acquires locks in decreasing order
      return calculateAverageResponseTime(--i, responseTime); 
    }
  }
}

The monitoring application is built around the WebRequestAnalyzer class that , which maintains a list of web requests using the requests vector and includes the addWebRequest() setter method. Any thread can request the average bandwidth or average response time of all web requests by invoking the getAverageBandwidth() and getAverageResponseTime() methods.

...

Unfortunately, this noncompliant code example 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 never 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 when there are 20 requests in the vector, and one thread calls getAverageBandwidth(), the thread 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 web request 19, the last element in the vector. Consequently, deadlock results because neither thread can acquire all of the locks and required to proceed with the its calculations.

Note that the addWebRequest() method also has a race condition with calculateAverageResponseTime(). While 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.

...

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 first needs to Each thread thread must first synchronize on the first web request, which cannot happen before the first until any prior calculation completes.

There is no need to lock Locking on the last element of the vector in addWebRequest() is unnecessary for two reasons: (1) because locks are acquired in increasing order in all the methods and (2) because updates to the vector are reflected in the results of the computations.

...

...