Improperly accessing resources
Consider the following example in which the class “guarantees” that it will always deliver an even number when you call getValue( ). However, there’s a second thread named “Watcher” that is constantly calling getValue( ) and checking to see if this value is truly even. This seems like a needless activity, since it appears obvious by looking at the code that the value will indeed be even. But that’s where the surprise comes in. Here’s the first version of the program:
//: c13:AlwaysEven.java
// Demonstrating thread collision over resources by
// reading an object in an unstable intermediate state.
public class AlwaysEven {
private int i;
public void next() { i++; i++; }
public int getValue() { return i; }
public static void main(String[] args) {
final AlwaysEven ae = new AlwaysEven();
new Thread("Watcher") {
public void run() {
while(true) {
int val = ae.getValue();
if(val % 2 != 0) {
System.out.println(val);
System.exit(0);
}
}
}
}.start();
while(true)
ae.next();
}
} ///:~
In main( ), an AlwaysEven object is created—it must be final because it is accessed inside the anonymous inner class defined as a Thread. If the value read by the thread is not even, it prints it out (as proof that it has caught the object in an unstable state) and then exits the program.
This example shows a fundamental problem with using threads. You never know when a thread might be run. Imagine sitting at a table with a fork, about to spear the last piece of food on your plate, and as your fork reaches for it, the food suddenly vanishes (because your thread was suspended and another thread came in and stole the food). That’s the problem that you’re dealing with when writing concurrent programs.
Sometimes you don’t care if a resource is being accessed at the same time you’re trying to use it (the food is on some other plate). But for multithreading to work, you need some way to prevent two threads from accessing the same resource, at least during critical periods.
Preventing this kind of collision is simply a matter of putting a lock on a resource when one thread is using it. The first thread that accesses a resource locks it, and then the other threads cannot access that resource until it is unlocked, at which time another thread locks and uses it, etc. If the front seat of the car is the limited resource, the child who shouts “Dibs!” asserts the lock.
A resource testing
framework
Before going on, let’s try to simplify things a bit by creating a little framework for performing tests on these types of threading examples. We can accomplish this by separating out the common code that might appear across multiple examples. First, note that the “watcher” thread is actually watching for a violated invariant in a particular object. That is, the object is supposed to preserve rules about its internal state, and if you can see the object from outside in an invalid intermediate state, then the invariant has been violated from the standpoint of the client (this is not to say that the object can never exist in the invalid intermediate state, just that it should not be visible by the client in such a state). Thus, we want to be able to detect that the invariant is violated, and also know what the violation value is. To get both of these values from one method call, we combine them in a tagging interface that exists only to provide a meaningful name in the code:
//: c13:InvariantState.java
// Messenger carrying invariant data
public interface InvariantState {} ///:~
In this scheme, the information about success or failure is encoded in the class name and type to make the result more readable. The class indicating success is:
//: c13:InvariantOK.java
// Indicates that the invariant test succeeded
public class InvariantOK implements InvariantState {} ///:~
To indicate failure, the InvariantFailure object will carry an object with information about what caused the failure, typically so that it can be displayed:
//: c13:InvariantFailure.java
// Indicates that the invariant test failed
public class InvariantFailure implements InvariantState {
public Object value;
public InvariantFailure(Object value) {
this.value = value;
}
} ///:~
Now we can define an interface that must be implemented by any class that wishes to have its invariance tested:
//: c13:Invariant.java
public interface Invariant {
InvariantState invariant();
} ///:~
Before creating the generic “watcher” thread, note that some of the examples in this chapter will not behave as expected on all platforms. Many of the examples here attempt to show violations of single-threaded behavior when multiple threads are present, and this may not always happen.[69] Alternatively, an example may attempt to show that the violation does not occur by attempting (and failing) to demonstrate the violation. In these cases, we’ll need a way to stop the program after a few seconds. The following class does this by subclassing the standard library Timer class:
//: c13:Timeout.java
// Set a time limit on the execution of a program
import java.util.*;
public class Timeout extends Timer {
public Timeout(int delay, final String msg) {
super(true); // Daemon thread
schedule(new TimerTask() {
public void run() {
System.out.println(msg);
System.exit(0);
}
}, delay);
}
} ///:~
The delay is in milliseconds, and the message will be printed if the timeout expires. Note that by calling super(true), this is created as a daemon thread so that if your program completes in some other way, this thread will not prevent it from exiting. The Timer.schedule( ) method is given a TimerTask subclass (created here as an anonymous inner class) whose run( ) is executed after the second schedule( ) argument delay (in milliseconds) runs out. Using Timer is generally simpler and clearer than writing the code directly with an explicit sleep( ). In addition, Timer is designed to scale to large numbers of concurrently scheduled tasks (in the thousands), so it can be a very useful tool.
Now we can use the Invariant interface and the Timeout class in the InvariantWatcher thread:
//: c13:InvariantWatcher.java
// Repeatedly checks to ensure invariant is not violated
public class InvariantWatcher extends Thread {
private Invariant invariant;
public InvariantWatcher(Invariant invariant) {
this.invariant = invariant;
setDaemon(true);
start();
}
// Stop everything after awhile:
public
InvariantWatcher(Invariant invariant, final int timeOut){
this(invariant);
new Timeout(timeOut,
"Timed out without violating invariant");
}
public void run() {
while(true) {
InvariantState state = invariant.invariant();
if(state instanceof InvariantFailure) {
System.out.println("Invariant violated: "
+ ((InvariantFailure)state).value);
System.exit(0);
}
}
}
} ///:~
The constructor captures a reference to the Invariant object to be tested, and starts the thread. The second constructor calls the first constructor, then creates a Timeout that stops everything after a desired delay—this is used in situations where the program may not exit by violating an invariant. In run( ), the current InvariantState is captured and tested, and if it fails, the value is printed. Note that we cannot throw an exception inside this thread, because that would only terminate the thread, not the program.
Now AlwaysEven.java can be rewritten using the framework:
//: c13:EvenGenerator.java
// AlwaysEven.java using the invariance tester
public class EvenGenerator implements Invariant {
private int i;
public void next() { i++; i++; }
public int getValue() { return i; }
public InvariantState invariant() {
int val = i; // Capture it in case it changes
if(val % 2 == 0)
return new InvariantOK();
else
return new InvariantFailure(new Integer(val));
}
public static void main(String[] args) {
EvenGenerator gen = new EvenGenerator();
new InvariantWatcher(gen);
while(true)
gen.next();
}
} ///:~
When defining the invariant( ) method, you must capture all the values of interest into local variables. This way, you can return the actual value you have tested, not one that may have been changed (by another thread) in the meantime.
In this case, the problem is not that the object goes through a state that violates invariance, but that methods can be called by threads while the object is in that intermediate unstable state.
