Colliding over resources
The worst thing that happens with EvenGenerator is that a client thread might see it in an unstable intermediate state. The object’s internal consistency is maintained, however, and it eventually becomes visible in a good state. But if two threads are actually modifying an object, the contention over shared resources is much worse, because the object can be put into an incorrect state.
Consider the simple concept of a semaphore, which is a flag object used for communication between threads. If the semaphore’s value is zero, then whatever it is monitoring is available, but if the value is nonzero, then the monitored entity is unavailable, and the thread must wait for it. When it’s available, the thread increments the semaphore and then goes ahead and uses the monitored entity. Because incrementing and decrementing are atomic operations (that is, they cannot be interrupted), the semaphore keeps two threads from using the same entity at the same time.
If the semaphore is going to properly guard the entity that it is monitoring, then it must never get into an unstable state. Here’s a simple version of the semaphore idea:
//: c13:Semaphore.java
// A simple threading flag
public class Semaphore implements Invariant {
private volatile int semaphore = 0;
public boolean available() { return semaphore == 0; }
public void acquire() { ++semaphore; }
public void release() { --semaphore; }
public InvariantState invariant() {
int val = semaphore;
if(val == 0 || val == 1)
return new InvariantOK();
else
return new InvariantFailure(new Integer(val));
}
} ///:~
The core part of the class is straightforward, consisting of available( ), acquire( ), and release( ). Since a thread should check for availability before acquiring, the value of semaphore should never be other than one or zero, and this is tested by invariant( ).
But look what happens when Semaphore is tested for thread consistency:
//: c13:SemaphoreTester.java
// Colliding over shared resources
public class SemaphoreTester extends Thread {
private volatile Semaphore semaphore;
public SemaphoreTester(Semaphore semaphore) {
this.semaphore = semaphore;
setDaemon(true);
start();
}
public void run() {
while(true)
if(semaphore.available()) {
yield(); // Makes it fail faster
semaphore.acquire();
yield();
semaphore.release();
yield();
}
}
public static void main(String[] args) throws Exception {
Semaphore sem = new Semaphore();
new SemaphoreTester(sem);
new SemaphoreTester(sem);
new InvariantWatcher(sem).join();
}
} ///:~
The SemaphoreTester creates a thread that continuously tests to see if a Semaphore object is available, and if so acquires and releases it. Note that the semaphore field is volatile to make sure that the compiler doesn’t optimize away any reads of that value.
In main( ), two SemaphoreTester threads are created, and you’ll see that in short order the invariant is violated. This happens because one thread might get a true result from calling available( ), but by the time that thread calls acquire( ), the other thread may have already called acquire( ) and incremented the semaphore field. The InvariantWatcher may see the field with too high a value, or possibly see it after both threads have called release( ) and decremented it to a negative value. Note that InvariantWatcher join( )s with the main thread to keep the program running until there is a failure.
On my machine, I discovered that the inclusion of yield( ) caused failure to occur much faster, but this will vary with operating systems and JVM implementations. You should experiment with taking the yield( ) statements out; the failure might take a very long time to occur, which demonstrates how difficult it can be to detect a flaw in your program when you’re writing multithreaded code.
This class emphasizes the risk of concurrent programming: If a class this simple can produce problems, you can never trust any assumptions about concurrency.
