> -----Original Message-----
> From: Boehm, Hans [mailto:hans_boehm@hp.com]
> Sent: Wednesday, July 11, 2001 5:23 PM
> Getting back to the question here, I think there are two distinct, though
> related issues, and I want to make sure we're talking about the
> same thing:
> (Of course, I may already be confused.)
>
> 1) Can a volatile write be reordered with a following volatile read as in
> TSO. I think this is basically the same question as whether monitor exit
> and a following volatile read can be reordered. I currently think this is
> observable (in spite of earlier messages to the contrary), but
> it's probably
> not critical either way. Allowing the reordering is cheaper on
> Itanium, at
> least for volatiles.
>
> 2) If two threads write two different volatile locations, and if there are
> several observer threads, do all the observer threads see the
> writes in the
> same order? To what extent is there a global total order among all the
> volatile accesses?
I'll respond to Hans' discussion of the two questions in separate messages.
>
> Question 1:
>
> I think you can observe if a volatile read is moved before an unlock
> operation. Let y be volatile. Initially x and y are zero.
>
> Thread 1:
> x = 1;
> unlock;
> z = y; //volatile read
>
> Thread 2:
> y = 1;
> <barrier, e.g. assignment of another volatile to itself>
> x = 2;
>
> Can this end with x = 1 and z = 0?
>
> If the reordering of the read is not allowed, then all actions in each
> thread are ordered. x = 1 precedes the read of y. Since x = 1
> at the end,
> it must have followed the x = 2 assignment. Thus the read of y must have
> followed the assignment to y.
>
> If we allow the reordering, then we can rewrite thread 1 as x = 1; z = y;
> unlock . Sinze z = y is only an acquire barrier, this can be
> reordered as z
> = y; x = 1; unlock . Thus x = 1 and z = 0 becomes a possible outcome.
>
> Did I miss something?
My claim:
---------
(1) In the context of Java and Bill's proposed semantics so far, it is not
possible to see reordering between unlock and a following volatile or
anything else (unless the reordered accesses are in a potentially infinite
loop - but there are other issues with infinite loops that need to be
handled separately as addressed in an earlier message I sent).
(2) It is possible to see reordering between volatile write and volatile
read.
Proof:
------
There are various examples to prove (2) - the simplest is Dekker's
algorithm.
Proof of (1) is very involved. If anyone is interested, please send me an
email and I'll provide references. If you have a counter-example, I would be
really interested in seeing it.
For Hans' example above, note again that volatiles are NOT barriers. I tried
to explain this in a previous message and will be happy to try again. Here
is how Bill put it in a recent message:
> Perhaps a better way to describe a property of acquire/release
> volatiles is that they are one-way-always-permeable. In other words,
> it is always possible to reorder a normal memory access and a
> following volatile read. However, in the other direction, they are
> sometimes-permeable: it depends on the details, such as whether any
> other thread has written to the volatile variable.
>
In the context of the example above, we are seeing a violation because we
are using the writes on x to order the accesses to y. So the writes on x are
being used as communicators or synchronizers between the threads. Then we
are reordering Thread 1's write on x and read of y, so of course, we see a
violation. The fact that this reordering of x and y also results in
reordering the unlock and the read of y is somewhat incidental. The real
reason we are seeing the violation is because we are assuming Thread 2's
volatiles are barriers, which they are not.
In other words, by Bill's semantics so far, it would be perfectly legal for
the compiler to remove the volatile barrier in Thread 2, and we'd get the
violation without any reordering in Thread 1.
Hence my suggestion - do not use the term "barrier" for volatiles - it leads
to more confusion than anything else.
And just to complete that argument. Bill's response to my previous message
on this issue was:
> -----Original Message-----
> From: Bill Pugh [mailto:pugh@cs.umd.edu]
> Sent: Friday, July 13, 2001 9:56 AM
>
> At 3:11 PM -0500 7/10/01, Sarita Adve wrote:
> >I would like to point out that based on Bill's proposal so far, volatiles
> >cannot be treated as one-way barriers (for non-volatile accesses), leave
> >alone as two-way barriers. Let me specify the tradeoffs here a little
> >differently from what Bill said in his last message.
> >
> >I think we have to make a fundamental choice between whether we
> would like
> >programmers to think about the memory model in terms of per-thread
> >orderings, or if we are ok with thinking in terms of
> inter-thread orderings.
>
> I just wanted to point out again that at the moment, I'm trying to
> discuss/propose _properties_ of the Java Memory Model, not the
> _specification_ of the Java Memory Model.
>
> Even if we have a more complicated formal specification of the
> semantics, we can derive per-thread ordering properties that may
> prove useful to some programmers and VM implementors.
The fact that volatiles may be some form of per-thread barriers is neither
part of the spec proposed so far, nor its property. Yes, we can derive
per-thread properties, but these are only the reorderings that are allowed,
not orderings that are ensured (or reorderings that are prohibited). When we
say "barrier", we are implying ensured orderings (or prohibited
reorderings).
>
> >But if we choose to use inter-thread spec (Bill's current proposal),
> >volatiles can neither be interpreted as one-way nor two-way barriers.
> >(Therefore, the programmability argument for two-way barriers
> seems moot.)
>
>
> Perhaps a better way to describe a property of acquire/release
> volatiles is that they are one-way-always-permeable. In other words,
> it is always possible to reorder a normal memory access and a
> following volatile read. However, in the other direction, they are
> sometimes-permeable: it depends on the details, such as whether any
> other thread has written to the volatile variable.
>
> If we follow this logic/terminology, then there isn't much to say
> about the strengthened version of volatiles: they are
> two-way-sometimes-permeable, which doesn't provide any information.
>
I agree completely. In other words, we can talk about intra-thread allowed
reorderings, but not intra-thread ensured orderings.
Back to Hans' message:
> -----Original Message-----
> From: Boehm, Hans [mailto:hans_boehm@hp.com]
> Sent: Wednesday, July 11, 2001 5:23 PM
>
> This seems to be eseentially equivalent to reordering a volatile write
> followed by a volatile read.
Volatile write -> volatile read is different from unlock -> X because unlock
has special properties in Java: An unlock is always preceded by another lock
in the same thread, all threads follow monitor semantics, a location
accessed by lock/unlock is not accessible by any other type of variable,
etc. All of these put together make unlocks special. Volatiles don't have
these properties and so have to be reasoned about differently when
considering which reorderings are visible.
>
> That having been said, I'm still leaning towards allowing the reordering.
> Disallowing the ordering seems to require an extra memory barrier on at
> least X86 and Itanium. Was there a natural example for which it actually
> matters? It sounds like the specification would be simpler if we allowed
> it.
>
But you also said in the same message:
> There should be safe usage rules that are as simple as possible, at the
> expense of some performance. But those should be derived from our
> specification; they won't be the specification. They will
> probably require
> that volatiles be used at most in very stylized ways. e.g. to publish an
> object, and that all other shared accesses be synchronized. For this the
> details of the spec hopefully won't matter. If they prevent us
> from writing
> a simple collection of safe usage rules that's a problem. If
If we allow reordering between volatile writes and reads, I believe it will
be difficult to come up with "safe usage" rules that are also simple (within
the constraints of Java). At least I haven't seen any in the literature
myself ...
Sarita
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:33 EDT