Re: JavaMemoryModel: Total orders

From: Jeremy Manson (jmanson@cs.umd.edu)
Date: Wed Dec 10 2003 - 20:57:46 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.

I'm afraid this is not quite right. The happens-before relationships are
defined in Section 5 of the community draft. Nowhere is it stated that a
happens-before relationship can be inferred if one action happens to
preceed another in the total order over synchronization actions.

The way in which happens-before interacts with the synchronization order
is that unlocks happen before subsequent locks on the same monitor in the
SO, and that volatile writes happen before subsequent volatile reads of
the same variable in the SO. This assumes we are forgetting for the
moment about thread start / join / isalive stuff.

In the case you mention above, I am not sure what X and Y are supposed to
be. Let's assume that they are locks on variables X and Y. In that case,
you have hb relationships

lock A (T1) hb unlock A (T2)
lock B (T1) hb unlock B (T2)

No other hb relationships are implied.

I apologize for not answering your previous message; it got lost in the
shuffle.

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