Name: akC45999 Date: 10/27/98



The JLS 17.9 reads:

The rules for volatile variables effectively require that main memory
be touched exactly once for each use or assign of a volatile variable
by a thread, and that main memory be touched in exactly the order
dictated by the thread execution semantics.

However, following test shows that the main memory is touched
in different order than that dictated by the thread execution,
when the jitted test program is run on a multy-processor machine
on different platforms (sparc/2.7, x86/2.7, and win32).
JDK version was 1.2fscO.

Such behaviour contradicts the specification and affects all usage
of volatile variables.
 
In the test, two threads repeatedly perform procedure "action" which:
a) performs lock on an imaginable resource using Dekker's algorithm
b) checks in a long loop that the other thread cannot lock the resource
c) unlocks the resource

At each step of execution, variable "step" is incremented.

The Dekker's algorithm uses variables for synchronization, so it is critical
that variables be read and written without delays.

The fact that the algorithm fails to lock a resource proves that
variables are read and/or written incorrectly. To show the incorrectness in more detail, the threads print values of each other's fields
read in different steps of execution.

The following dump:
Thread 0: step-1: 709-->669
Thread 1: step-1: 673-->709
Thread 0: step/a: 710-->672
Thread 1: step/a: 674-->709
Thread 0: step/b: 710-->674
Thread 1: step/b: 674-->710

must be read as follows:
Thread0 at step 709 sees that thread1 is at step 669
Thread1 at step 673 sees that thread1 is at step 709
and so on.

If we sort the messages according to the steps of tread1,
then we can see an inconsistency:

709<--674
710-->672

The thread1 at its step 674 sees that thread0 is at step 709.
Some time later, at thread0's step 710, thread0 sees thread1 is at step
672, which is evidently wrong since we know that thread1 already entered
its step 674.

------------------------------------- file thrd02301.java
// modified version of the jck1.2b test
// lang/THRD/thrd023/thrd02301/thrd02301.html;
// in JCK12a, test also indicates the bug but not prints trace.
// More recent versions does not catch the bug

import java.io.PrintStream;

public class thrd02301 extends Thread {
  static final int timeout=30000;
  static final int actionLimit=100000;
  static final int failureLimit=4;
  long endTime;
  PrintStream out;

  boolean threadNum;
  thrd02301 common, other;
  volatile boolean want=false, turn; // variables used in Dekker's algorithm
  volatile boolean locked=false; // true when this thread owns the lock
  volatile int counter // counts actions
, step // counter*4
, failures;

  thrd02301(boolean threadNum, PrintStream out, long endTime) {
this.threadNum=threadNum;
this.out=out;
this.endTime=endTime;
  }

  void log(String message) {
out.println("Thread "+(threadNum?"1: ":"0: ")+message);
  }

  void action() {
want=true;
step++; // 1
// lock phase of Dekker's algorithm
int otherstep1=other.step;
while (other.want) {
if (common.turn!=threadNum) {
want=false;
while (common.turn!=threadNum) {
Thread.yield();
}
want=true;
}
}
step++; //2
locked=true;
int otherstep2=other.step;
// check that the other thread cannot gain the lock
for (int k=0; k<10000; k++) {
if (other.locked) {
int otherstep3=other.step;
log("failure on counter "+counter+" k="+k);
log("step-1: "+(step-1)+"-->"+otherstep1);
log("step/a: "+step+"-->"+otherstep2);
log("step/b: "+step+"-->"+otherstep3);
common.failures++;
break;
}
}

locked=false;
step++; //3
// unlock phase of Dekker's algorithm
common.turn=other.threadNum;
want=false;
step++; //0
  }

  public void run() {
for (counter=0; counter<actionLimit; counter++) {
action();
if (counter%10==0) {
if (System.currentTimeMillis()>=endTime) {
break;
} else if (common.failures>failureLimit) {
break;
} else if (!other.isAlive()) {
break;
}
}
}
log("counters performed:"+counter);
  }

//=========================
  public static int run(String args[], PrintStream out) {
long curTime=System.currentTimeMillis();
long endTime=curTime+timeout;
thrd02301 thread0=new thrd02301(false, out, endTime)
, thread1=new thrd02301(true, out, endTime);
thread0.common=thread1.common=thread0;
thread0.other=thread1; thread1.other=thread0;
thread0.start();
thread1.start();
try {
thread0.join();
thread1.join();
} catch (InterruptedException e) {
out.println("InterruptedException in join()");
return 2;
}
if (thread0.failures==0) {
return 0;
} else {
out.println("failures:"+thread0.failures);
return 2;
}
  }

  public static void main(String args[]) {
System.exit(run(args, System.out) + 95/*STATUS_TEMP*/);
  }

} // end class thrd02301

------------------------------------- end of file thrd02301.java

Running the test:
novo70% javac thrd02301.java
novo64% setenv CLASSPATH .
novo70% java -native -verify thrd02301
Thread 0: failure on counter 177 k=17
Thread 1: failure on counter 168 k=8
Thread 0: step-1: 709-->669
Thread 1: step-1: 673-->709
Thread 0: step/a: 710-->672
Thread 1: step/a: 674-->709
Thread 0: step/b: 710-->674
Thread 1: step/b: 674-->710
Thread 0: failure on counter 368 k=3
Thread 1: failure on counter 356 k=0
Thread 0: step-1: 1473-->1425
Thread 1: step-1: 1425-->1469
Thread 0: step/a: 1474-->1425
Thread 1: step/a: 1426-->1474
Thread 0: step/b: 1474-->1426
Thread 1: step/b: 1426-->1474
Thread 0: failure on counter 430 k=3
Thread 1: failure on counter 417 k=4
Thread 0: step-1: 1721-->1669
Thread 1: step-1: 1669-->1717
Thread 0: step/a: 1722-->1669
Thread 1: step/a: 1670-->1720
Thread 0: step/b: 1722-->1670
Thread 1: step/b: 1670-->1722
Thread 0: counters performed:430
Thread 1: counters performed:420
failures:6

======================================================================