> From: Bill Pugh [mailto:pugh@cs.umd.edu]
>
> It may be that rather than fairness, we simply need a rule that some
> thread makes progress.
First point: the thread in the infinite loop *is* making progress. It's not
doing anything useful but it is progressing exactly in accordance with the
code that was written.
Second point: we don't need any rules about fairness or progression - this
is simply not in the domain of this JSR.
The basic "rule" is simple. Any transformation that results in an execution
that would have been observable under some scheduling model that is valid
according to the JLS, is itself valid.
It then comes down to quality of implementation if the transformation
changes the apparent scheduling behaviour in a way that adversely affects
application behaviour. When people chose to use VM XXX because it has
certain operating characteristics (such as scheduling behaviour), they
generally don't want those characteristics to change in a fundamental way
due to some code transformation.
Transformations that increase the number of locks held across a section of
code (other than increasing from 0 to 1) could induce deadlock. As this
would not be a valid execution under any scheduling model that obeys the
JLS, such a transformation is illegal if it would lead to deadlock.
Most of the examples for sync block fusing have implicit assumptions
regarding scheduling and synchronization behaviour that are not guaranteed
on any given system - for example, assuming that some form of lock hand-off
occurs, or requiring implicit timing relationships between threads. Consider
these two threads executing on a multi-processor:
Thread 1 Thread 2
while(true) { while(true) {
synchronized(foo) { synchronized(foo) {
System.out.println("T1"); System.out.println("T2");
} }
} }
On most VM's today we would see a mixture of "T1" and "T2" being printed. On
a VM with lock hand-off we'd see alternating "T1" and "T2"'s. However it
would be perfectly valid for a system to print either all "T1" or all "T2".
There are no guarantees of progression.
Given that I do not know how any VM implementor would be able to prove that
their transformations yielded valid executions according to the JLS. If they
have the tools to do this please share them with the rest of us. :)
> In Jeremy's example 3, this allowed the system to be hosed because thread
1
> went into an infinite loop. If, instead, we had:
>
> initially, all variables are 0
> Thread 1
> Volatile1 = 1
>
> Thread 2
> while (Volatile1 == 0);
> print "success"
>
> Then the program would be guaranteed to print "success", because once
> thread 1 terminates, thread 2 must see the change to Volatile1 and
> then terminate.
No it is not guaranteed. For that to occur we must guarantee that thread 1
gets to execute first (and presumably terminates).
> On the other hand, if we have:
> initially, all variables are 0
> Thread 1
> Volatile1 = 1
> while (Volatile2 == 0);
> print "T1 terminates"
>
>
> Thread 2
> Volatile2 = 1
> while (Volatile1 == 0);
> print "T2 terminates"
>
> then this program could fail to make progress, because thread 1 could
> spin forever without giving thread 2 a chance to set Volatile2 to 1.
Which is why, when doing a busy-wait, you should use Thread.yield (even
though that is not *guaranteed* to be effective we will one day fix the JLS
to make it so - I hope).
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:36 EDT