JavaMemoryModel: The Optimistic Read Idiom and the new Java Memory Model

From: Jan-Willem Maessen (jmaessen@MIT.EDU)
Date: Mon Oct 30 2000 - 14:00:55 EST


I took me a while to understand Rob Strom's example, but I think I
have a clear high-level handle on what's going on here.

Writer-lock support:
--------------------

The real question here, it seems, is not whether the models should
support this approach to reader locks, but whether there is some
reasonable approach to reader locking that can be expressed in the
models.

Here we see a vivid example of our simple high-level rule: "Volatile
reads act like Enter, Volatile stores act like Exit". This leads to
two high-level problems.

First, we can't ensure that the increment is visible before the writes
occur. Here's one writer block:

v++;
...
a=2;
b=3;
...
v++;

Here's it's translation, omitting commit and reconcile (which do not
have a strong impact on this particular question):

// Here's the volatile increment
LoadV v
Fence_r* v, *
StL v, v++

//NEED A FENCE HERE!!

StL a,2
StL b,3

//no real problem down here
Fence_wr V, v
LoadV v
Fence_r* v, *
StL v, v++

We can fix the writer side using the same trick as in Bill's model, if
I read correctly:

v++;
tmp = v; // conceptually begins the "writer locked" region
a = 2;
b = 3;
v = tmp+1; // conceptually ends the "writer locked" region

In CRF:

// The increment as before
LoadV v
Fence_r* v, *
StL v, v++
// Our semantics will allow the succeeding read to be fetch-elminated,
// but the following fence will then become Fence_w* v, *
Fence_wr V,v
tmp = LoadL v;
Fence_r* v, *
...
a=2
b=3
...
Fence_*w *,v;
StoreL v,(tmp+1)

However, the reason this doesn't help is that *symmetrical
synchronization is required in the reader*. Thus:

* We must do something exit-like in the reader in order to obtain
  meaningful semantics.

This leads to a truly warty solution:

t1 = v;
...
x = a;
y = b;
...
hasBeenRead = true; //*** UGLY!!!
t2 = v;
if (t1==t2 %% t1%2==0) return(r);
else /* redo, lock, etc. */

// CRF translation
t1 = LoadL v;
Fence_r* v, *
...
x = a;
y = b;
...
// store to hasBeenRead...
Fence_*w *, hasBeenRead
StoreL hasBeenRead, true
// Then we fetch t2!
Fence_wr V, v
t2 = LoadL v
Fence_r* v, *

I don't like the look of this at all--- yet it's a simple consequence
of our decision to make volatile loads behave like MonitorEnter.

If we want to strongly order volatile reads with respect to all read
operations, we should just do it. Note that this will make monotonic
uses of volatiles (set a volatile flag in the writer, do a check in
the reader and then read) a little bit less open to compiler
reordering, but it might be worth it.

Bill, if Rob's interpretation of your model is correct, you already
are doing this. I had thought, though, that one could still obtain
later-written values in your model and that the guarantees were
therefore weaker than what Rob suggests. Could you clarify? This
changes my "informal model" of your semantics quite a bit.

I don't want MonitorEnter to have stronger ordering semantics; I don't
want the possibility of using monitors for fence-like tricks such as
these.

There's already a stong argument out there for forcing volatile
operations and monitor enters/exits to be strongly ordered (the model
I presented at OOPSLA does not do this):

    synchronized (a) { while (!flag) ;
      do some writes synchronized(a) {
      flag = true; do some reads
    } }

This can deadlock if the while loop move into the synchronization
region! If we want to allow busy waiting, we really need to add
ordering constraints here.

Implementors may want to squawk loudly before committing to a more
strongly-ordered semantics, however. I'd love to hear opinions from
folks with a real stake in compilation (Sun, IBM, Compaq, Intel...).

Alternatively, is there a cleaner way to implement reader locks given
the volatile discipline we describe in the CRF paper (reads like
enter, writes like exit)? Examples like this are really valuable in
deciding where the semantic boundaries go. Volatile operations, being
"roll-your-own", are of course open to debate even in fixing an
informal Java semantics, much less encoding that model formally.

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



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