Sarita gave a couple of examples of loops and raised some issues
related to them.
Clearly, this is an area we need to do some work on, although I don't
think it requires a substantial rethinking of what has been discussed
so far.
Among other issues, we need to have the semantics specify in some
what that if you have a loop that spin waits on a volatile variable,
you can't move the read of the volatile variable out of the loop.
There is a general rule in compilers that no program should be able
to detect the reordering done by a compiler. A similar rule holds for
the multithreaded case. For example,
At 4:07 PM -0500 6/29/01, Sarita Adve wrote:
>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.
If the actions in thread 1 are reordered, then the program could
detect a reordering that is not possible an execution of the original
program. Of course, since we have multithreaded programs, we have to
consider some of the strangeness that arises due to incorrectly
synchronized programs.
At 4:07 PM -0500 6/29/01, Sarita Adve wrote:
>Example 1:
>----------
>Initially all variables are 0
>Thread 1
>Volatile1 = 1
>while (A == 0) {;}
>
>Thread 2
>while (Volatile1 != 1) {;}
>print "Success"
This example is a little different. An execution in which Thread 2
never printed "Success" could be explained by an execution in which
Thread 1 never got any time slices. To fix this, I think we need to
add something like weak fairness to the formal semantics: that if a
thread has a infinite number of opportunities to make progress, it
will make progress.
For example, that means in the following code:
Example 3:
Thread 1
while (true)
synchronized(A) {
print "Thread 1"
}
Thread 2
while (true)
synchronized(A) {
print "Thread 2"
}
it would be illegal to hoist the synchronization out of the loop
(which would result in only one thread printing messages).
I believe this also handles cases such as code spin waiting on a
volatile variable.
Note, however, that finite loops could be transformed. For example,
in example 3, if the while loops were instead for loops that counted
to one million, it would be legal to hoist the synchronization out of
the loop. We discussed this a while back; while there are some
quality of service issues, I think it would be far too nasty to have
specific trip counts embedded in the formal semantics (e.g., "if a
thread is able to make progress 100,000 times, it will make progress
by no later than the 100,000th time it is able to make progress").
Bill
-------------------------------
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