Joe's example brings up a subtle issue. It shows that a potentially
*infinite* number of volatile reads cannot be reordered before a monitor
exit. This example has a lot to do with "infinite" and perhaps not as much
to do with "volatile" for reasons below, and has repurcussions beyond the
context of reordering volatiles and monitors:
(1) I believe that it is possible to reorder a finite number of volatile
reads before a monitor exit without breaking SC. I'd be very interested in a
counter-example. (For that matter, I think a monitor exit followed by a
volatile write can also be safely reordered.) When I say "finite," I mean
"finite" for *any* execution, not just sequentially consistent executions.
(2) Here are some examples with potentially unbounded loops that can give
trouble similar to Joe's example, but don't violate the ordering
restrictions discussed so far:
Example 1:
----------
Initially all variables are 0
Thread 1
Volatile1 = 1
while (A == 0) {;}
Thread 2
while (Volatile1 != 1) {;}
print "Success"
This is a "correct" program and should see SC results; i.e., Thread 1 will
loop forever and Thread 2 will print Success.
But if the statements of Thread 1 are reordered, then the write of Volatile1
will not occur and Thread 2 will never print Success. Note that this
reordering is analogous to the reordering that breaks Joe's example. But the
above does not violate any of the ordering restrictions considered so far
(it reorders volatile write with respect to a following ordinary read which
could even be a local read). The commonality between Joe's example and this
is that they both involve reordering a potentially unbounded loop.
[One difference is that Joe's loop will terminate in all SC executions and
the above loop won't. In theory, we may be able to exploit the difference,
but in practice, the compiler may not be able to determine if a loop will
terminate.]
Example 2:
----------
Thread 1:
while (some condition that is always true) {;}
Volatile1 = 1
Thread 2:
if (Volatile1 == 1)
print "Error"
If statements of Thread 1 are reordered, Thread 2 prints Error, which is not
SC.
Comments and questions
-----------------------
(1) Is there existing compiler work/convention on reordering with respect to
potentially unbounded loops?
(2) These examples show a subtle difference between reordering optimizations
in hardware and compiler. It is easy to tell hardware what to do to not
break both examples, without restricting common optimizations:
For example 1: Permit reordering of X and Y (where X before Y by program
order) with the restriction that if Y is issued, then X will *eventually* be
issued. This is easy for (current) hardware, since it does not "skip over"
instructions for infinite time.
For example 2: Prohibit speculative writes. Again, this is easy for current
hardware since speculative writes are too difficult regardless of this
issue.
For the compiler, for example 2, a reasonable restriction would be: if a
loop cannot be proven to terminate, then don't reorder writes following it.
My thesis work showed that it is sufficient to consider only loops that
cannot be proven to terminate in any sequentially consistent execution.
For the compiler, for example 1, I am not sure of the right answer. For this
example, we have a loop that will not terminate and so again we can say that
reordering is not allowed across loops that can be proven to not terminate.
I think it should be sufficient to restrict this to reordering of writes,
but I haven't proven it.
Another point for example 1 is that this loop is non-terminating in an SC
execution. Joe's example was for a loop that was terminating in all SC
executions. It is possible that for loops that terminate in all SC
executions, we will only need to restrict reordering across
volatiles/monitors. I don't have a proof of this yet though. In practice, I
am not sure how much difference this makes, unless the programmer tells the
compiler or unless the compiler is smart enough to figure out if a loop such
as Joe's example will terminate.
Sarita
> -----Original Message-----
> From: owner-javamemorymodel@cs.umd.edu
> [mailto:owner-javamemorymodel@cs.umd.edu]On Behalf Of Joseph Bowbeer
> Sent: Thursday, June 28, 2001 2:52 AM
> To: Bill Pugh
> Cc: javamemorymodel@cs.umd.edu
> Subject: Re: JavaMemoryModel: Ordering of volatile and monitor actions
>
>
> PS - Here's a slightly simpler version (showing that reordering
> monitor exit
> and volatile read can lead to deadlock).
>
> Initially:
>
> volatile boolean consumed = true;
>
> Thread 1:
>
> while (true) {
> synchronized(this) {
> work();
> consumed = false;
> }
> while (!consumed) { /* wait */ }
> }
>
> Thread 2:
>
> while (true) {
> synchronized(this) {
> if (!consumed) {
> consumeWork();
> consumed = true;
> }
> }
> }
>
>
> As before, thread 2 is using the volatile flag 'consumed' to
> signal thread 1
> to stop waiting and do some more work. If the read of 'consumed'
> in thread 1
> is moved into the synchronized block, then the program deadlocks.
>
>
>
> -------------------------------
> 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:32 EDT