Page History

...

This noncompliant code example consists of an application to monitor a sports race. It maintains a list of racers. Each racer has two statistics that can be reported about them: their current speed, and their current distance travelled. This example provides methods to report on the average current speed of the racers, and the average distance of the racers. To be thread-safe, it locks each racer before it reads her statistics until after it reports the average. Consequently, the statics reported by the methods are accurate at the time the methods actually return their results.Each racer is asociated with a dedicated object instance of class Racer:

public class Racer {public class Racer {
  double currentSpeed;
  double distanceTraveled; 

  public double getCurrentSpeed() {
    // ...return currentSpeed;
  }

  public double getDistance() {
    return distanceTraveled;
  }
}

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 locks each racer before it reads her statistics until after it reports the average.

 double getDistance() {
    // ...
  }

  //...
}

public class Race {
  final static int MAX = 20;
  static Racer[] racers = new Racer[MAX];
 
  public Race() {
    for (int i = 0; i < MAX; i++) {
      racers[i] = new Racer(/* initialize racer */);
    }
  }

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

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

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


  double getAverageDistance() {
    return averageDistanceCalculator(MAX - 1, 0.0);
  }

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

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

Consequently, the statics 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 will first acquire acquires the intrinsic lock for Racer 0, the first in the array. Meanwhile if a second thread calls getCurrentDistance(), and it will first acquire 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.

...

In this compliant solution, the two calculation methods use acquire and release locks in the same ordering for locking the racer objectsorder.

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

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

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


  double getAverageDistance() {
    return averageDistanceCalculator(0, 0.0);
  }

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

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

Consequently, while one thread is producing a calculation, no other thread can produce a calculationcalculating 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.

...