> From: owner-javamemorymodel@cs.umd.edu
> [mailto:owner-javamemorymodel@cs.umd.edu]On Behalf Of Jeremy Manson
> Sent: Monday, 22 October 2001 3:43 AM
> To: javamemorymodel@cs.umd.edu
> Subject: JavaMemoryModel: Fairness Guarantees in the Memory Model?
>
> I have a question for the list...
> Has the issue of fairness in the JMM been thrashed out?
I don't think the discussions on fusing sync blocks really thrashed things
out beyond an informal agreement that the compiler folk want to be able to
do it and the programmers are willing to let the compilers do it as long as
it doesn't "break" anything they very carefully constructed.
There was the issue of source-compile-time versus some later time
modifications and I think the general understanding there was that
transforming source to bytecode should preserve the intent of the source.
Otherwise you would preclude, for example, running the modified bytecode in
a real-time JVM.
For the later time transformations (JIT/AOT etc), the general consensus
seemed to be that for a given VM, the transformation should preserve a
minimal fairness property relevant to that VM.
Considering the examples:
> Example 1:
>
> Can this:
>
> while (true)
> synchronized (foo)
> { ... }
>
> Become this:
>
> synchronized (foo)
> while (true)
> { ... }
If the transformation does not cause indefinite postponement in a thread
that otherwise would not have encountered indefinite postponement *on that
VM*, then it is allowed.
If the transformation merely delays a thread, where it would not have been
delayed originally, then the transformation is allowed, but the length of
the delay becomes a quality-of-service issue in the VM.
I think the important thing is that the validity of the transformation has
to be considered with regard to the specific VM in question. For example, on
a VM with a user level threading model (ie doesn't utilise multi-processors)
without time-slicing, and assuming there are no implicit scheduling points
within the ... block, then the transformation is undetectable and so is
allowed.
However, on a VM that supports, for example, a threading model that utilises
multi-processors, the transformation would be observable and so should be
disallowed if it causes indefinite postponement. (I'm assuming a simple
scenario where another thread wants to acquire the lock of foo and the
infinite loop really is infinite).
> Example 2:
>
> Can this:
>
> for (i = 0; i < 1 quadrillion; i++)
> synchronized (foo)
> { ... }
>
> Become this:
>
> synchronized (foo)
> for (i = 0; i < 1 quadrillion; i++)
> { ...}
The question here is whether a quadrillion iterations is "indefinite" for
all practical intents and purposes.
> 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.
> There are other examples out there... The basic question is what kind of
> fairness guarantees need to be included in the spec. I am not asking if
> these are good transformations to make, I am just asking whether or not
> the JMM should allow them (or even make mention of them).
I'd be happier if the compiler would just leave my sync/threading code
alone. If my program performs badly because of poor
synchronization/concurrency strategies then profiling will reveal it and the
code will be improved. But that's a battle I've already lost .... so I think
the only thing we can reasonably say is that these types of transformation
should never remove a fairness property that would have been present without
the transformation - it may weaken it, but not remove it. This basically
means no introduction of "indefinite" postponement, where "indefinite" is
likely to be a very subjective term.
Just my $2 worth.
David Holmes
-------------------------------
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