JavaMemoryModel: Weak fairness in the Java memory model

From: Bill Pugh (pugh@cs.umd.edu)
Date: Mon Apr 12 2004 - 16:59:48 EDT


OK, we've adopted some language on weak fairness in
the Java memory model.

Consider:

Initially, v = 0 and v is volatile

Thread 1:
do {
   r1 = v;
   } while (r1 == 0);

Thread 2:
v = 1

OK, the new language is that for each synchronization
action, only a finite number of synchronization actions
can occur before it in the synchronization order (obviously,
this is trivially true for any finite execution).

For this example, that means that if thread 2 terminates,
thread 1 cannot loop forever.

This is a pretty weak guarantee, since this program could
run in an infinite loop if the write to v by thread 2 was never
performed and thread 2 did not terminate (perhaps thread 1 is
of a higher priority than thread 2, and thread 2 is never
scheduled).

However, it does make it pretty difficult for the compiler
to do some undesirable transformations, such as
hoisting the volatile read out of the loop.

Jerry Schwarz noted that
this property can also be described by saying that the
> synchronization order is total order
> of order type omega (or less).
> What that means without the math jargon is simply that if you put them
> into order you can count them
> with the integers.

-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:01:03 EDT