For reference, here's the example (sanitized by Bill Pugh) that I shows
how moving a volatile store (*) down into a synchronized region can
result in deadlock:
Initially:
volatile boolean stop = false;
Thread 1:
synchronized(this) {
while (!stop) work();
}
Thread 2:
stop = true; // ***
synchronized(this) {
consumeWork();
}
Unless we're willing to allow optimizations to induce deadlock, the
extra fences after a volatile store are needed.
I was wondering if the CRF proposal needs further strengthening for
volatile loads. Does the proposal allow a volatile load to move up into
a synchronized region?
Here's a variant of the same krufty example:
Initially:
volatile boolean stop = false;
Thread 1:
do synchronized(this) { work(); }
while (!stop);
Thread 2:
synchronized(this) {
stop = true;
consumeWork();
}
Might a CRF-based optimizer try to expand the synch region in thread 1
to include the entire do-while, including the volatile load? If so,
deadlock will result. And extra fences before the load would be needed
to prevent this.
-- Joe Bowbeer----- Original Message ----- From: "Jan-Willem Maessen" <jmaessen@MIT.EDU> To: <javamemorymodel@cs.umd.edu> Sent: Monday, October 30, 2000 11:00 AM Subject: JavaMemoryModel: The Optimistic Read Idiom and the new Java Memory Model
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++
file://NEED A FENCE HERE!!
StL a,2 StL b,3
file://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; file://*** 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
------------------------------- 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