Re: JavaMemoryModel: Dropping coherence is more complicated than we thought

From: Adalberto Castelo (
Date: Mon Nov 08 1999 - 18:28:27 EST

Bill Pugh wrote:
> However, consider the following single-check idiom example:
> int v;
> int getValue() {
> if (v != 0)
> v = computeValue();
> return v;
> }
> Assume that computeValue has no side-effects, and always returns the same
> non-zero value.

Let me try to rewrite this example as:

        T1 T2
w0: int v=0; w3: int v=0;
w1: int v=non-zero value;
    call getValue; call getValue;
r1: if (v!=0) r3: if(v!=0);
w2: v=compValue(); w4: v=compValue();
r2: return v; r4: return v;

Because there are no synchronizations between T1 and T2, according to
Location Consistency (LC), the set of possible values for r3 is
V(r3)={w0, w1, w2, w3}. If r3 sees w2, as Bill proposes, and w4 is
issued, then the set of values for r4 is V(r4)={w0, w1, w2, w4} (notice
that w3 is not in this set). These are the legal sets of values for r3
and r4 according to LC. So it is legal for r4 to return v=0, even with
the if block being executed. The point is: will it ever happen?

Answer: not in the architectures we know today.

If we assume that T2's r3 saw the last write in location v by T1 (w2),
it means that T1 has already written back to main memory its latest
value for v. If T1 did so, it means that there's no copy left of the
former writes w1 and w0 in the system. Not even in T1's cache (or
working memory). So, *in the architectures that we have today (that I
know of)*, T2 wouldn't be able to return a value of v=0, for this
example--where the if block gets executed.

An example of architecture (Dr. Amaral from CAPSL had this idea) where
the example above could have V(r3)!=0 and V(r4)==0 both true would
provide more than one main memory. A system with several mirrors for its
main memory, where r3 would get w2 from one mirror and r4 would get w0
from another.

Adalberto Castelo
Computer Architecture and Parallel Systems Lab (CAPSL)
University of Delaware
JavaMemoryModel mailing list -

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