JavaMemoryModel: Roach motel ordering: Do we have consensus?

From: Bill Pugh (pugh@cs.umd.edu)
Date: Sat Jul 07 2001 - 19:10:00 EDT


At 3:25 PM -0400 7/6/01, Bill Pugh wrote:
>Making volatile read/write be full two directional memory barriers
>will likely at least double the cost of volatile reads on IA-64 and
>Alpha SMPs.

Actually, I didn't make the case strong enough. Making volatile
read/write be full two directional memory barriers will also at least
double the cost of volatile reads on x86 and Sparc, in addition to
IA-64 and Alpha processors, as well as just about any other processor.

The problem is that almost all SMP's will allow a write to be
reordered with a following read (both TSO and x86 allow this).

The problem is then a non-volatile write, followed by a volatile
read. To prevent these from being reordered, you need to have a
memory barrier instruction immediately before the volatile read. And
this will at least double the cost of the volatile read.

On a Sparc or x86, the naive implementation of volatiles would be to
generate a memory barrier instruction immediately after each volatile
write, which would prevent that volatile write from being reordered
with any following volatile read. In some cases, you could skip the
barrier instruction (for example, if you could determine that after
the volatile write, the next volatile/monitor action is another
volatile write).

At 1:09 PM +1000 6/29/01, David Holmes wrote:
> If volatiles are to be useful as flags in
>wait-free/non-blocking algorithms then it seems to me that ordering is
>critical and so volatile accesses should act as code motion barriers in both
>directions.

As I mentioned previously, you can get this semantics by adding a
dummy volatile write before each volatile read, and a dummy volatile
read after each volatile write (so long as the dummy volatile is
shared). However, adding these semantics in general will make
volatile more expensive, and is only needed/useful in rare
circumstances.

I would like to try to get this settled so we can move on to other
fun topics (like object initialization and final fields). David
Holmes expressed some reservations, but generally people seem to be
OK with "roach motel" ordering:

> * accesses to normal variables can be reordered with
> - a following volatile read or monitor enter
> - a preceding volatile write or monitor exit

The corresponding formal part of the semantics are below. Note that I
have clarified something: in order for a "happens before"
relationship to be established, the release action must precede the
acquire action.

> * volatile writes and monitor exits are treated as synchronization releases.
>
> * volatile reads and monitor enters are treated as synchronization acquires.
>
>A synchronization release action and _a matching and following_
>synchronization acquire action establish a "happens before"
>relationship between the two threads. Program order within a thread
>also establishes a happens before relationship, and "happens before"
>is transitive.
>
>If two threads access the same normal field or array element, and one
>of those accesses is a write, the accesses conflict. For any two
>conflicting accesses, there should be a "happens before" relationship
>between the two accesses. If all sequentially consistent executions
>of a program are correctly synchronized (i.e., all conflicting
>accesses are ordered), then the program is correctly synchronized and
>follows sequentially consistent semantics.

If anyone thinks we need to further consider alternatives to this,
_please_ speak up now.

Don't worry at the moment about having a well articulated argument to
consider alternatives; I just want to get a feeling for whether we
have consensus on this issue, or if people are still uncertain as to
whether this is the direction we should go. If we reach consensus, we
could still reopen it later but I would like to get this issue
settled before we move on.

        Bill
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:32 EDT