RE: JavaMemoryModel: Fairness Guarantees in the Memory Model?

From: Boehm, Hans (hans_boehm@hp.com)
Date: Mon Oct 22 2001 - 15:54:14 EDT


Now, I'm confused. If you require that "Success" must eventually be
printed, even when running on a single processor, that requires that the
scheduler cannot just run thread 1 forever. My understanding (which may be
obsolete, but agrees with David's) was that there was no such requirement.
And old Sun JVMs did not obey such a requirement.

Are we proposing to change this? Or did you mean to say that if you have an
infinite amount of time on an infinite number of available processors, then
"Success" must eventually be printed? Or was there already a change that I
missed?

(I personally would consider such a change as both (a) desirable and (b)
probably outside the charter of our group. My impression is that
programmers rely on the fact that implementations either time slice or use a
round-robin scheduler at each priority level, so that you can effectively
force them to time-slice with a high-priority thread that sleeps for short
periods in an infinite loop. But neither is guaranteed.)

Hans

> -----Original Message-----
> From: Bill Pugh [mailto:pugh@cs.umd.edu]
> Sent: Monday, October 22, 2001 11:08 AM
> To: David Holmes; Jeremy Manson; javamemorymodel@cs.umd.edu
> Subject: RE: JavaMemoryModel: Fairness Guarantees in the Memory Model?
>
>
> 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".
>
> 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.
>
> Essentially, the rule is that if a thread is given an infinite number
> of opportunities to make progress, it must 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