Page History

...

The two transfers are performed in their own threads, from instance a to b and b to a. The first thread atomically transfers the amount from a to b by depositing the balance from a to b and withdrawing the entire balance from a. The second thread performs the reverse operation, that is, it transfers the balance from b to a and withdraws the balance from b. When executing depositAllAmount(), the first thread might acquire acquires a lock on object a while the second thread may acquire acquires a lock on object b. Subsequently, the first thread requests a lock on b which is already held by the second thread and the . The second thread requests a lock on a which is already held by the first thread. This constitutes a deadlock condition, as neither thread can proceed.

Deadlock can occur when two threads request the same two locks in different orders. 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 simultaneous transfers occur involving distinct accounts.

Compliant Solution (static internal private lock)

...

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 class BankAccount extend implement the java.lang.Comparable interface and overriding the compareTo() method.

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

    // other fields, which can help make this class Comparable

  public int compareTo(BankAccount ba) {
    // compare bank accounts
  }


  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) {
    Thread t =  return -1;new Thread(new Runnable() {
   }  else if(this.balanceAmount > ba.balanceAmountpublic void run() {
      return 1  first.depositAllAmount(second);
    } else {}
     return 0});
   } t.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 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, with the result that one thread will acquire both locks, complete the transfer, and release both locks before the other thread may proceed.

...

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

public class WebRequestAnalyzer {
  private final Vector<WebRequest> requests = new Vector<WebRequest>();
  
  public boolean addWebRequest(WebRequest request) {
    // No need to lock on the last element because locks are 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
    }
  }
}

...