At 09:17 AM 9/12/2003, I wrote:
>Consider two threads, where each letter represents a lock and unlock
>action on a named object's monitor.
>Thread 1 Thread 2
> X Y
>Does a total order exist here? In particular, what is the order of the
>locks on X and Y?
Since no one has picked up on this, I decided to have a look at whether or
not the absence of a total order could be visible to a program. My first
problem is in deciding how the existence of a total order interacts with
the happens before rules. I've concluded that the specification implies
that they do, and that in the example, either X hb Y, or Y hb X.
Now consider the following
Initialy, x1 = x2 = y1 = y2 = 0. None of them are volatile.
Thread 1 Thread 2
x1 = 1 x2 = 1
y1 = x2 y2 = x1
Total order implies X hb Y or Y hb X, so x1 = 1 hb y2 = x1, or x2 = 1 hb y1
So the outcome is y1 == 1 or y2 == 1 (or both). In the absence of a total
order, the X hb Y and vice versa relationships do not exist. It seems to me
that in that case the outcome y1 == y2 == 0 is possible. The absence of a
total order would be visible. There would be no justification order for
this, I think, but a justification order is also a total order.
If the existence of a total order has the ramifications I describe for the
hb rules, then it is a requirement, not merely an observation, and has an
execution cost on real mult-processor systems.
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:55 EDT