I wanted to apply the rules of "Semantics of Multithreaded Java" and the
rules of "Improving the Java Memory Model Using CRF" to the idiom of
optimistic reading, discussed in our OOPSLA paper "Guava: A Dialect of Java
Without Data Races" (Bacon/Strom/Tarafdar)
To simplify the discussion, let's assume a single writer thread (in real
life multiple writers would execute serially via a synchronized method,
thus behaving like a single writer thread), and a second reader thread.
Assume that the first execution of the writer writes a=2, b=3; the second
execution writes a=5, b=7. The reader thread reads a and b and returns
a*b; obviously we want the reader thread to return only the value 6 or 35.
Here are the threads, with the optimistic protocol inserted in color. They
are written in "naïve Java", although as I show later, this naïve Java must
be perturbed to get the desired effect:
Writer thread:
volatile v;
/* Assume for this example that
the first write has already begun, with v=1, a=any, b=any */
...
a = 2;
b = 3;
v++;
... /* other operations between first and second write */
v++;
a=5;
b=7;
v++;
Reader thread:
t1 = v;
x = a;
y = b;
r = a*b;
t2 = v;
if (t1 == t2 && t1%2 == 0) return(r);
else /* redo */
Now, as I understand the semantics in Bill's paper, this coding will work,
with one small change. ("Work", in this context, means that whenever the "
if" statement in the reader evaluates to true, either t1=t2=2 and r=6, or
t1=t2=4 and r=35.) The tricky part is to verify that the implementation
must respect the anti-dependency between the statement t2=v when it reads
the value 2, and the writer operation v++ incrementing v from 2 to 3:
namely that no writes performed subsequently by the writer can be visible
by the reader. Although Section 3 in Bill's paper does not explicitly
state that the model respects anti-dependencies, this property follows from
the fact that reads are never re-ordered, and writes may not be moved ahead
of the read in v++. Unfortunately, no rule prevents writes from being
moved into the space between the read and the write in v++, so to prevent
this, in Bill's model that particular v++ must be replaced by v++; int
bogus = v. This is a little counter-intuitive, and the compiler must be
aware that the computation of the dead variable bogus may not be thrown
away, since it is performed for the sake of the side effect of forcing a
read of a volatile, and the suppression of moves of the following writes!
Now let's look at the same algorithm in CRF. First I write it as if I were
a code-generator knowing that this is supposed to be an optimistic
implementation of a logically synchronized read and write operation (e.g.
as if there were a direct Guava-to-CRF translator):
Writer thread:
reconcile v
...
storeL a,2
storeL b,2
commit a
commit b
fence_ww a,v
fence_ww b,v
t1 = readL v
storeL v, t1++
commit v
...
t1 = readL v
storeL v, t1++
commit v
fence_ww v,a
fence_ww v,b
storeL a,5
storeL b,7
commit a
commit b
fence_ww a,v
fence_ww b,v
storeL v, t1++
commit v
Read thread:
reconcile v
t1 = readL v
fence_rr v,a
fence_rr v,b
reconcile a
reconcile b
tempa = readL a
tempb = readL b
storeL r,a*b
fence_rr a,v
fence_rr b,v
reconcile v
t2 = readL v
if (t1==t2 && t1%2 == 0) commit r
This program inserts exactly the fences we want: stores by the writer (and
reads if there had been any) are corralled between the two increments of
the volatile; reads by the reader are corralled between the two reads of
the volatile; this plus global ordering guarantee that the dependencies and
the anti-dependencies are respected.
Having written a correct CRF program, how can I safely "reverse-compile" it
to the Java code I need to write, using the translation rules of the
Maessen/Arvind/Shen paper?
There are several problems, assuming the naïve algorithm. First of all, the
second v++ statement still does not prevent the moving of subsequent writes
to a and b to before the v++, since neither the load nor the store
generates a ww-fence from v to a and b. But unlike the case in Bill's
paper, here inserting a bogus read of v doesn't fix the problem, since a
bogus read only suppresses the motion of subsequent reads, not writes. We
need either a bogus lock-enter operation (which I'm not sure in Java can be
performed without a corresponding lock-exit), or else we need an endcon
(which fences too much). So this means that the v++ must be followed
either by synchronized(bogus) {} or Bogus bogus = new Bogus(). That's not
very auspicious!
Now, there's still the problem in the reader thread. The first read of v
is OK --- it inserts a fence to prevent subsequent reads from being
reordered in front of it. But what prevents the second read of v from
being reordered in front of these reads? Nothing. We need another bogus
lock-enter operation just before the second read of v.
Unless I am reading one or both documents wrong, I find that the optimistic
reader idiom (a) requires different Java code in the two proposals; (b)
requires the insertion of non-intuitive operations that look like nonsense
(a read of a volatile into a dead variable, an empty synchronize block on a
non-shared variable, a bogus allocation).
Comments? Have I misunderstood anything?
Rob Strom
-------------------------------
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