Page History

...

This noncompliant code example consists of an application to monitor a sports race. Each racer is asociated with a dedicated object instance of class Racer.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 requests.

Code Block

bgColor	ffcccc


public class WebRequest

Code Block


class Racer implements Cloneable {
  private doublelong currentSpeedbandwidth;
  private doublelong distanceresponseTime; 

  public doublelong getCurrentSpeedgetBandwidth() {
    return currentSpeedbandwidth;
  }

  public voidlong setCurrentSpeedgetResponseTime(double currentSpeed) {
    this.currentSpeed = currentSpeedreturn responseTime;
  }
 
  public double getDistanceWebRequest()long {
bandwidth, long   return distance;responseTime) {
  }

  publicthis.bandwidth void setDistance(double distance) {= bandwidth;
    this.distanceresponseTime = distanceresponseTime;
  }
}
  
public Racerclass clone()WebRequestAnalyzer {
  private final tryVector<WebRequest> {
requests =     return (Racer) super.clonenew Vector<WebRequest>();
  
  }public catchboolean addWebRequest(CloneNotSupportedExceptionWebRequest xrequest) {
    // lock on last element to prevent data /*race handlewith errorcalculate */methods
    synchronized  }(requests.lastElement()) {
      return null;
  }
}

Each racer has two statistics that can be reported about them: their current speed, and the current distance traveled. The class Racer provides methods getCurrentSpeed() and getDistance() for this purpose.

The monitoring application is built upon class Race which maintains a list of racers. To be thread-safe, it accepts a list of racers, and defensively clones them. Henceforth, any thread can change a Racer's distance or current speed, or get the average distance or average current speed of all racers. Changing a racer's statistics involves locking using the racer's intrinsic lock, while getting the average statistics for all racers involves locking all the racers' intrinsic locks until the average is calculated.

Code Block

bgColor	#FFcccc


public class Race {
  private final Racer[] racers;
 
  public Race(Racer[] racers) {
    this.racers = cloneRacers( 0, racers);
  }

  // Defensively clone the racers array, but only after all racers are locked
  private Racer[] cloneRacers(int i, Racer[] racers) {
    if (i > racers.length - 1) {
      Racer[] result = new Racer[i];
      for (int j = 0; j < this.racers.length; j++) {requests.add(new WebRequest( request.getBandwidth(), request.getResponseTime()));
    }
  }
  
  public double getAverageBandwidth() { 
    return calculateAverageBandwidth( 0, 0);
  }

  private double calculateAverageBandwidth(int i, long bandwidth) { 
    if (i > requests.size()) {
      return bandwidth / requests.size();
    }
    synchronized (requests.elementAt(i)) {
      numberOfPages += requests.get(i).getBandwidth();
      return calculateAverageBandwidth(++i, bandwidth);  
    }
  }

  public double getAverageResponseTime() { 
    return calculateAverageResponseTime( requests.size() - 1, 0);
  }

  private double calculateAverageResponseTime(int i, long responseTime) { 
    if (i <= -1) {		 
      return responseTime result[j] = racers[j].clone/ requests.size();
      }
      return result;
    }

    synchronized(racers[i]synchronized (requests.elementAt(i)) {
      return cloneRacers( ++i, racersresponseTime += requests.get(i).getResponseTime();
    }
  }


  public void setCurrentSpeed(int index, double currentSpeed) {
    synchronized( racers[index]) {
      racers[index].setCurrentSpeed( currentSpeed)return calculateAverageResponseTime(--i, responseTime);
    }
  }

  public void setDistance(int index, double distance) {
    synchronized( racers[index]) {
      racers[index].setDistance( distance);
    }
  }


  double getAverageCurrentSpeed() {
    return averageCurrentSpeedCalculator(0, 0.0);
  }

  double averageCurrentSpeedCalculator(int i, double currentSpeed) {
    // Acquires locks in increasing order
    if (i > racers.length - 1) {
      return currentSpeed / racers.length;
    }

    synchronized(racers[i]) {
      currentSpeed += racers[i].getCurrentSpeed();
      return averageCurrentSpeedCalculator(++i, currentSpeed);
    }	 
  }


  double getAverageDistance() {
    return averageDistanceCalculator(racers.length - 1, 0.0);
  }

  double averageDistanceCalculator(int i, double distance) {
    // Acquires locks in decreasing order
    if (i <= -1) {		 
      return distance / racers.length;
    } 

    synchronized(racers[i]) {
      distance += racers[i].getDistance();
      return averageDistanceCalculator(--i, distance);
    }
  }
}

Consequently, the statistics reported by the methods are accurate at the time the methods actually return their results.

This implementation is prone to deadlock because the recursive calls occur within the synchronized regions of these methods and acquire locks in opposite numerical orders. That is, averageCurrentSpeedCalculator() requests locks from index 0 to MAX - 1 (19) whereas averageDistanceCalculator() requests them from index MAX - 1 (19) 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 averageSpeedCalculator() while the other calls averageTimeCalculator() before either method has finished executing.

For example, if one thread calls getCurrentSpeed(), it acquires the intrinsic lock for Racer 0, the first in the array. Meanwhile if a second thread calls getCurrentDistance(), it acquires the intrinsic lock for Racer 19, the last in the array. Consequently, deadlock results, as neither thread can acquire all of the locks and proceed with the calculation.

Compliant Solution

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

Code Block

bgColor	#ccccff


public class Race {
  double averageCurrentSpeedCalculator(int i, double currentSpeed) {
    // Acquires locks in increasing order
    if (i > racers.length - 1) {
      return currentSpeed / racers.length;
    }

    synchronized(racers[i]) {
      currentSpeed += racers[i].getCurrentSpeed();
      return averageCurrentSpeedCalculator(++i, currentSpeed);
    }	
  }


  double averageDistanceCalculator(int i, double distance) {
    // Acquires locks in increasing order
    if (i > racers.length - 1) {
      return distance / racers.length;
    } 

    synchronized(racers[i]) {
      distance += racers[i].getDistance();
      return averageDistanceCalculator(++i, distance);
    }
  }
}

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

Noncompliant Code Example

Code Block


// Immutable Racer
public final class Racer {
  private final double currentSpeed;
  private final double distanceTraveled; 

  public Racer(double speed, double distance) {
    currentSpeed = speed;
    distanceTraveled = distance;
  }
  
  public double getCurrentSpeed() {
    return currentSpeed;
  }
  
  public double getDistance() {
    return distanceTraveled;
  }
}

Code Block

bgColor	#FFcccc


public final class Race {
  private final Vector<Racer> racers;
  private final Object lock = new Object();
  
  public Race(Vector<Racer> racer) {
    racers = (Vector<Racer>) racer.clone(); 
  }
  
  public boolean addRacer(Racer racer){	  
    synchronized(racers.elementAt(racers.size() - 1)) {
      return racers.add(racer);
    }
  }
  
  public boolean removeRacer(Racer racer) {
    synchronized(racers.elementAt(racers.indexOf(racer))) { 
      return racers.remove(racer);      
    }
  }
  
  private double getAverageCurrentSpeed(int i, double currentSpeed) { 
    if (i > racers.size()) {
      return currentSpeed / racers.size();
    }
    synchronized(racers.elementAt(i)) {
      currentSpeed += racers.get(i).getCurrentSpeed();
      return getAverageCurrentSpeed(++i, currentSpeed);  
    }
  }

  private double getAverageCurrentDistance(int i, double distance) { 
    if (i <= -1) {		 
      return distance / racers.size();
    }     
    synchronized(racers.elementAt(i)) {
      distance += racers.get(i).getDistance();
      return getAverageCurrentDistance(--i, distance);
    }
  }
  
  public void getStatisticsAtSomePointInRace() {
    synchronized(lock) {
      getAverageCurrentSpeed(0, 0.0);
      getAverageCurrentDistance(racers.size()-1, 0.0);
    }
  }
}

Compliant Solution

Code Block

bgColor	#ccccff


public final class Race {
  private final Vector<Racer> racers;
  private final Object lock = new Object();
  
  public Race(Vector<Racer> racer) {
    racers = (Vector<Racer>) racer.clone(); 
  }
  
  public boolean addRacer(Racer racer){	  
    return racers.add(racer);
  }
  
  public boolean removeRacer(Racer racer) {
    synchronized(racers.elementAt(racers.indexOf(racer))) { 
      return racers.remove(racer);      
    }
  }
  
  private double getAverageCurrentSpeed(int i, double currentSpeed) { 
    if (i > racers.size()) {
      return currentSpeed / racers.size();
    }
    synchronized(racers.elementAt(i)) {
      currentSpeed += racers.get(i).getCurrentSpeed();
      return getAverageCurrentSpeed(++i, currentSpeed);  
    }
  }

  private double getAverageCurrentDistance(int i, double distance) { 
    if (i > racers.size()) {		 
      return distance / racers.size();
    }     
    synchronized(racers.elementAt(i)) {
      distance += racers.get(i).getDistance();
      return getAverageCurrentDistance(++i, distance);
    }
  }
  
  public void getStatisticsAtSomePointInRace() {
    synchronized(lock) {
      getAverageCurrentSpeed(0, 0.0);
      getAverageCurrentDistance(0, 0.0);
    }
  }
}

Noncompliant Code Example

The monitoring application is built upon class WebRequestAnalyzer which maintains a list of requests. To be thread-safe, it starts off with an empty list, and defensively copies all data fed to it. Henceforth, any thread can get the average bandwidth or average response time of all web requests.

The statistics perform fine-grained locking on the individual requests' intrinsic locks. 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 statistics reported by the methods are accurate at the time 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 WebRequest 0, the first in the vector. Meanwhile if a second thread calls getAverageResponseTime(), it acquires the intrinsic lock for WebRequest 19, the last in the vector. Consequently, deadlock results, as neither thread can acquire all of the locks and proceed with the calculation.

Compliant Solution

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

Code Block

bgColor	#ccccff


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

  private double calculateAverageBandwidth(int i, long bandwidth

Code Block

bgColor	FFcccc


public class Book {
  private String title;
  private double width;
  private double weight;

  public String getTitle() {
    return title;
  }
  public double getWidth() {
    return width;
  }
  public double getWeight() {
    return weight;
  }
 
  public Book(String title, double width, double weight) {
    this.title = title;
    this.width = width;
    this.weight = weight;
  }
}

public class Bookshelf {
  private final Vector<Book> books = new Vector<Book>();
  
  public boolean addBook(Book book) {
    // lock on last element to prevent race cond with calculation methods
    synchronized(books.lastElement()) {
      return books.add(new Book( book.getTitle(), book.getWidth(), book.getWeight()));
    }
  }
  
  // only one remove can happen at a time
  public final synchronized boolean removeBook(String title) {
    for (int i = 0; i < books.size(); i++) {
      if (books.getTitle().equals( title)) {
        // lock on book to prevent race cond with calculation routines
        synchronized (books.elementAt(i)) {
          return books.remove( i);
        }
      }
    }
    return false; // book not on bookshelf
  }

  
  private double getTotalWidth(int i, double width) { 
    if (i > booksrequests.size()) {
      return width bandwidth / requests.size();
    }
    synchronized (booksrequests.elementAt(i)) {
      numberOfPages += booksrequests.get(i).getWidthgetBandwidth();
      return getTotalWidthcalculateAverageBandwidth(++i, widthbandwidth);  
    }
  }

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

  private double getTotalWeightcalculateAverageResponseTime(int i, doublelong weightresponseTime) { 
    if (i <= -1> requests.size()) {		 
      return weight responseTime / requests.size();
    }     
    synchronized (booksrequests.elementAt(i)) {
      weightresponseTime += booksrequests.get(i).getWeightgetResponseTime();
      return getTotalWeightcalculateAverageResponseTime(--++i, weightresponseTime);
    }
  }
}

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.

Risk Assessment

Acquiring and releasing locks in the wrong order may result in deadlocks.

...

Space shortcuts

Page tree

Versions Compared

Old Version 86

New Version 87

Key

Compliant Solution

Noncompliant Code Example

Compliant Solution

Noncompliant Code Example

Compliant Solution

Risk Assessment