Re: JavaMemoryModel: fusing synch blocks

From: Doug Lea (dl@cs.oswego.edu)
Date: Sun Feb 04 2001 - 07:52:05 EST


> If you want to give another thread a chance to run, you can always
> do so using wait and notify. Well written multithreaded programs generally
> work this way.

But there are many situations where polling is essentially mandated.
Thread interruption is the most common one.

> I don't even know how you could tell whether 257 iterations of a loop
> were getting fused

Arriving at a particular value for this bound is a matter of providing
helpful guidance to compiler writers. But having a bound also allows
you to at least test for lack of infinite fusing in a finite amount of
time, which I think is important enough to make up for the inelegance
of hard-wiring a constant here.

The JSR process requires ("TCK") compliance tests, although they need
not (and for the JMM JSR usually cannot) be exhaustive or exact. We
cannot guarantee to detect whether a JVM actually uses a bound of 257
instead of 256, but we can figure out, for any given JVM, a worst case
time limit for completion of programs with indeterminate loops like my
original example: Find out the spec rate and multiply by a huge factor
for the sake of minimizing false positives. For simplicity you could
make this factor so big that it wipes out all conceivable JVM speed
differences. For example, a test can conservatively claim that a JVM
that doesn't complete that 10 line program in an hour doesn't comply.
There will still be an infinitessimal probablity that the test will
give false positives, but there is an appeal process for TCK tests
that could be applied. (There are surely many other JCK/TCK tests
with this halting-problem based property that you cannot with
certainty distinguish an error causing a test not to ever complete vs
a very slow JVM.)

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



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