Page History

...

Noncompliant Code Example

This noncompliant code example consists of an application that monitors web requests. Each request has a response time associated with it, as well as a measurement of network bandwidth. This example calculates the average bandwidth of all requests, and also calculates the avaerage reponse time of all requestsConsider a 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;
  }
}

Each request has a response time associated with it, as well as a measurement of network bandwidth required to fulfill the request.

This noncompliant code example consists of an application that monitors web requests. It calculates the average bandwidth and average response time required to service all incoming requests.

public class WebRequestAnalyzer {
  private final Vector<WebRequest> requests = new Vector<WebRequest>();
  
  public boolean addWebRequest(WebRequest request) {
    // lockLock on last element to prevent data race with the calculate methods
    synchronized (requests.lastElement()) {
      return requests// 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)) {
      numberOfPagesbandwidth += requests.get(i).getBandwidth();
      return calculateAverageBandwidth(++i, bandwidth); // Acquires locks in increasing order 
    }
  }

  publicprivate double getAverageResponseTimecalculateAverageResponseTime() { 
    return calculateAverageResponseTime( requests.size() - 1, 0);
  }

  private double calculateAverageResponseTime(int 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 maintains a list of web requests . To be thread-safe, it starts off with an empty list, and defensively copies all data fed to it. Henceforth, any 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.

These methods use The statistics perform fine-grained locking by holding locks on the individual requests' intrinsic lockselements (requests) of the vector. The locks permit new requests to be added up to when the computation is almost complete; at that point they prevent new requests from being added. Consequently, the while the computations are still underway. Consequently, the statistics reported by the methods are accurate at the time they return the methods actually return their 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 to requests.size() - 1 whereas calculateAverageResponseTime() requests them from index requests.size() - 1 to 0. Because of recursion, no previously acquired locks are released by either method. A deadlock occurs when two threads call these methods out of order in that, 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 for of WebRequest 0, the first element in the vector. Meanwhile, if a second thread calls getAverageResponseTime(), it acquires the intrinsic lock for WebRequest 19, the last element in the vector. Consequently, deadlock results , as because neither thread can acquire all of the locks and proceed with the calculationcalculations.

Compliant Solution

In this compliant solution, the two calculation methods acquire and release locks in the same order.

public class WebRequestAnalyzer {
  private final Vector<WebRequest> requests = new Vector<WebRequest>();
  
  public boolean addWebRequest(WebRequest request) {
    // initial methods are unchangedLock on last element to prevent data race with the calculate methods
    synchronized (requests.lastElement()) {
      // Defensive copying
      return requests.add(new WebRequest(request.getBandwidth(), request.getResponseTime()));
    }
  }

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

  public double getAverageBandwidthgetAverageResponseTime() { 
    return calculateAverageBandwidthcalculateAverageResponseTime( 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
      numberOfPagesbandwidth += requests.get(i).getBandwidth();
      return calculateAverageBandwidth(++i, bandwidth);  
    }
  }

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

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

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

...