Re: JavaMemoryModel: Total orders

From: Sylvia Else (sylviae@optushome.com.au)
Date: Wed Dec 10 2003 - 18:11:40 EST


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
> A
> A
> X Y
> B
> B
>
>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
X Y
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
= x2.

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.

Sylvia.

-------------------------------
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