RE: JavaMemoryModel: Fairness Guarantees in the Memory Model?

From: Bill Pugh (pugh@cs.umd.edu)
Date: Mon Oct 22 2001 - 21:26:11 EDT


At 3:55 PM -0700 10/22/01, Boehm, Hans wrote:
> It's not at all clear to me
>that the semantics needs to talk about any of this; hoisting the volatile
>was legal only because it was invisible. I think this needs to be reflected
>in the semantics only in that runnable threads are not guaranteed to make
>progress, at least not if there is another runnable thread.

I would not expect the semantics to explicitly state whether it is
legal to hoist volatile reads out of loops. However, if doing so
cannot be observed, (because you can't distinguish between hoisting
volatile reads out of loops and a non-preemptive scheduler) then it
is legal.

It may be that rather than fairness, we simply need a rule that some
thread makes progress. In Jeremy's example 3, this allowed the system
to be hosed because thread 1 went into an infinite loop. If, instead,
we had:

initially, all variables are 0
Thread 1
   Volatile1 = 1

Thread 2
   while (Volatile1 == 0);
   print "success"

Then the program would be guaranteed to print "success", because once
thread 1 terminates, thread 2 must see the change to Volatile1 and
then terminate.

On the other hand, if we have:
initially, all variables are 0
Thread 1
   Volatile1 = 1
   while (Volatile2 == 0);
   print "T1 terminates"

Thread 2
   Volatile2 = 1
   while (Volatile1 == 0);
   print "T2 terminates"

then this program could fail to make progress, because thread 1 could
spin forever without giving thread 2 a chance to set Volatile2 to 1.

We will think about it some more. I suspect that the rule "some
thread makes progress if possible" may be enough to rule out
ill-advised compiler transformations, at least in the common cases.

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



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