RE: JavaMemoryModel: Fairness Guarantees in the Memory Model?

From: Jerry Schwarz (jschwarz@us.oracle.com)
Date: Mon Oct 22 2001 - 16:08:39 EDT


At 11:08 AM 10/22/2001, Bill Pugh wrote:
>At 10:59 AM +1000 10/22/01, David Holmes wrote:
>> > Example 3:
>> >
>> > Is this
>> >
>> > Initially all variables are 0
>> > Thread 1
>> > Volatile1 = 1
>> > while (A == 0) {;}
>> >
>> > Thread 2
>> > while (Volatile1 != 1) {;}
>>> print "Success"
>>>
>>> guaranteed to print "success"?
>>
>>There is no suggested transformation here and the answer is obviously no.
>>There is no requirement from the JLS that thread 2 (assuming it runs first)
>>ever relinquishes the CPU and gives thread 1 a chance to write to Volatile1.
>>Hence the loop in thread 2 is not guaranteed to terminate.
>
>It is not required that thread 2 print "success" in any finite amount of
>time. But if the code is allowed to run for an infinite amount of time, it
>must eventually print "true".

I do not believe there is currently any such requirement in either the JLS
or JVMS and I would strongly oppose adding one. Oracle's RDBMS Server VM
has entirely non-preemptive scheduling. Once Thread 2 gets into its loop
that is all the VM does. Thread 1 never runs.

>Otherwise, the compiler could hoist the read of Volatile1 out of the loop
>in thread 2, or move the write to Volatile1 after the loop in thread 1.

In terms of my earlier email on modelling semantics (to which no one ever
responded), the semantics of thread 2 require repeated memory operations
(reads) of Volatile1 until a read returns a value not equal to 1. The
system is free to avoid those reads when it can determine that doing so
will not violate the semantics of the overall program. For example, a
compiler that knew it was acting in the context of a non-preemptive
scheduler would be free to hoist the read in Thread 2. But a compiler that
is acting without context (such as a java to bytecode compiler) is not free
to make that transformation.

>Essentially, the rule is that if a thread is given an infinite number of
>opportunities to make progress, it must make progress.

Since there are no scheduling events in the body of thread 2's loop, in
Oracle's VM there are no opportunities for Thread 1 to make progress.

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

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



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