reading the JLS (17.4.5)

[Andreas Leitgeb]

http://java.sun.com/docs/books/jls/third_edition/html/memory.html#17.4

Finally I got time to read and (attempt to) understand the JLS
about concurrency. There's a couple of wordings that appear
strange to me - maybe because of some insufficiency of my
English-language skills.

But in section 17.4.5 right after "Trace 17.5" there's this
paragraph:

" A set of actions A is happens-before consistent if for all
" reads r in A, it is not the case that either hb(r, W(r)),
" where W(r) is the write action seen by r or that there
" exists a write win A such that w.v = r.v and hb(W(r), w)
" and hb(w, r).

If ever "hb(r, W(r)), where W(r) is the write action seen by r"
then I couldn't help but consider the particular JVM-imple-
mentation utterly broken. How can this "either"-branch not
be empty?

How could a "read" that happens-before a particular "write" *ever*
see the "write"'s value?

Maybe, someone could explain, what that *really* means?

 

[markspace]

How could a "read" that happens-before a particular "write" *ever*
see the "write"'s value?

I think you have read it correctly. To elaborate:

" A set of actions A is happens-before consistent if for all
" reads r in A, it is not the case that either hb(r, W(r)),

Note that it says "it is NOT the case that ... hb(r, W(r))". The write
DOES have to happen before the read, or you won't see it. That's what
they're saying.

 

[Andreas Leitgeb]

I think you have read it correctly. To elaborate:
Note that it says "it is NOT the case that ... hb(r, W(r))". The write
DOES have to happen before the read, or you won't see it. That's what
they're saying.

Yeah, I was aware of the negation. As I've realized since, my mistake
was taking Java's behaviour as a pre-requisite for describing Java's
behaviour. ;-)

Maybe, however, my mistake was even a bit more complicated. The JLS
defines properties (like "happens-before", "happens-before-consistency")
on certain entities (pairs of actions, sets of actions).

Sometimes, the *non*-applicability of a particular property implies
essentially a "flaw" in some program's design (insufficient synchro-
nization), but some other times the fulfilment of some other property
is meant as a requisite for a conforming JVM-implementation.
I guess, I got confused about the implications of the property,
based on that it was defined as a property of a set of actions,
rather than as a property of a conforming JVM-implementation.

 

[Andreas Leitgeb]

Think about a large, high-performance server, with many out-of-order
processors, many memory modules, and a complicated network with as few
choke points as possible linking them. Everything has to be done as much
in parallel as possible, with as little synchronization as possible, to
get performance. Broadcasts to all memory modules or to all processors
must be very, very rare.

Suppose processor P sees in its pipeline instruction R, a read of
location X. It does not have the cache line containing X, so it sends
out a message asking for it.

To make as much progress as possible, P goes on to another instruction,
U, in the same thread as R, but that does not need X. U is an unlock
action, such as the end of a synchronized region. P immediately
afterwards gets a message from processor Q asking to be notified when U
happens, and responds to it.

Meanwhile, Q has the cache line containing X, and the right to modify
it. Because of delays in one path through the process-memory network,
the unlock action U reaches Q before the request for the cache line
containing X. Q executes an action V such that U synchronizes-with V,
followed in the same thread by a write W that changes the value of X.

Some time later, Q gets P's request for read access to the cache line
containing X, and sends it over with the W value written in to it.

R happens-before U, because they are actions of the same thread and R
comes before U in program order. U happens-before V, because U
synchronizes-with V. V happens-before W, because they are actions in the
same thread and V comes before W in program order.

R happens-before W, because happens-before is a transitive relation, but
R sees the value of X that W wrote.

The rule you are asking about requires a Java implementation to prevent
this scenario.

This is the point where I say: "phew". Up to this point, I feared
you'd describe some legal behaviour based on that, while reads can
happen-after writes with obvious meaning, writes happening-after
reads might still be allowed to be seen by reads... Well, I'm glad
it isn't so. I was confused enough to not be beyond doubt, though.

Why is a rule for a Java implementation phrased as a property
of/on a "set of actions"?

For example, P might be prevented from doing an action
such as U that synchronizes-with activity in other threads until it has
completed all actions, such as R, that precede it in program order.

You can think of section 17 as defining "as possible" in the first
paragraph of this article. How parallel and out-of-order can a Java
implementation afford to be? What ordering can a Java programmer depend on?

Given some (simplified) sample code:
class Test {
/*non-vol*/ int n1;
volatile int v1;

void t1() {
n1 = 1;
v1 = n1; // v1 uses n1
}

void t2() {
int r1=v1, r2=r1*n1; // r2 uses r1
assert ! (r1 == 1 && r2 != 1) : "huh?";
}
}
Two threads T1 and T2 may at some point run t1() and t2()
respectively, then I should expect, per transitivity of
"happens-before" that if r1 == 1, then r2 would *have to*
== 1, too. Is there a happens-before relation between
between setting n1 and reading n1 via write&read on the
volatile v1 and each intra-thread ordering?

There is a slightly similar example later in the JLS about
a final and a non-final set in a constructor, but that is
different, in that the non-final is set after the final.
I don't know for sure, if the ordering of the assignments
was relevant in that example.

 

[markspace]

I guess, I got confused about the implications of the property,
based on that it was defined as a property of a set of actions,
rather than as a property of a conforming JVM-implementation.

I'm not sure why those exceptions are there, but that little paragraph
is a pretty common sense, cya exception. You wont see a write if it
hasn't happened yet, and you wont see the effect of a write if someone
else wrote something there subsequently, before your read.

"Conforming JVM" is a pretty good guess, I think, but personally I
couldn't say.

Patricia had some thoughts on reordering by hardware, but that involved
synchronization and memory barriers, and I don't recall seeing those
discussed in the small JLS section in question. I think this JLS
section applies more generally than a read or write getting moved out of
a synchronization block. I think it applies absolutely everywhere.

 

[Lew]

Given some (simplified) sample code:
class Test {
/*non-vol*/ int n1;
volatile int v1;

void t1() {
n1 = 1;
v1 = n1; // v1 uses n1
}

void t2() {
int r1=v1, r2=r1*n1; // r2 uses r1
assert ! (r1 == 1 && r2 != 1) : "huh?";
}
}
Two threads T1 and T2 may at some point run t1() and t2()
respectively, then I should expect, per transitivity of

You have to establish a /happens-before/ between the invocations of t1() an t2().

If two threads begin to execute the methods, you cannot guarantee that t1() will /happen-before/ t2(), so the read of 'v1' in the latter could result in the default value.

 

[Andreas Leitgeb]

You have to establish a /happens-before/ between the invocations
of t1() an t2().
If two threads begin to execute the methods, you cannot guarantee
that t1() will /happen-before/ t2(), so the read of 'v1' in the
latter could result in the default value.

Perhaps you found the/a sore spot of my (mis?)understanding.

*iff* a *volatile* read gets to see the result of a *volatile*
write, then doesn't that say anything about that the write must
have "happened-before" the read?

In my example, I didn't mean to imply, that r1 would always
turn out to be 1. But *if* it does, then could anything be
assumed about r2 ?

If the write to v1 (but not to n1) in t1() were in a
synchronized(this)-block, and so were the read of v1
(but not n1) in t2(), then would anything be implied
about r2 *if* observing r1 == 1 in T2?

In practice, I think that establishing a happens-before
based on observation of a read's value is quite essential,
but I may of course be wrong here. I don't even see how one
could determine the order in which synchronized blocks for
a common monitor are actually passed through by different
threads, other than by observing reads.

 

[Andreas Leitgeb]

I think "happens-before" should be thought of as short for "must appear
to happen before". As the JLS says "It should be noted that the presence
of a happens-before relationship between two actions does not
necessarily imply that they have to take place in that order in an
implementation.

The JLS even explicitly spells out, that to an unrelated thread these
synchronized-with actions may even appear out of order. This is, what
confuses me:

T1: hb(A,B) - not necessarily observed so by T2
T1,T2: hb(B,C)

How would T2 "know" about hb(A,C), if it doesn't know hb(A,B) ?

 

[markspace]

T2 does not necessarily "know", but must see the appropriate results
e.g. from its reads. Making that happen is the Java implementation's
problem. How it happens varies depending on the system.

I think Andreas is asking "If a transitive relationship exists, how does
T2 'know' that?"

The JLS doesn't require a reading thread like T2 to be aware of any
other thread's entire set of write actions. It's just that once
synchronized, those write actions are available to be observed, and the
order they are observed doesn't matter.

Let's say T1 and T2 are both accessing a circular queue, and A, B and C
are the head, tail and count variables. T1 does some operation and
updates A, B and C. Then T2 accesses the queue, observes C to be 0, and
decides it doesn't want to preform any further updates on an empty
queue. It could, and would be able to observe A and B safely, but it
just chose not to based on its own program logic. This is an example
where T2 doesn't "know" about A or B, but only observes C. The point
however is that A and B are visible to T2 and could be observed safely,
even if T2 did not elect to observe them.

I guess another way of saying this is that the compiler "knows" about A,
B and C and makes sure they are visible to T2, even if T2 doesn't use
them explicitly.

In other situations, it may be necessary to use special instructions,
such as the SPARC membar, to ensure that prior memory operations are
globally visible.

Most of the Java synchronization is guaranteed to make all writes
visible to another thread, even those writes that don't explicitly
participate in the synchronization action (i.e. the variable or object
lock). Thus they work a lot like the membar opcode, flushing all writes
to whomever might want to observe them. No one has to observe anything,
but the write flush occurs just the same.

 

[markspace]

*iff* a *volatile* read gets to see the result of a *volatile*
write, then doesn't that say anything about that the write must
have "happened-before" the read?

Maybe you know this, but just in case: yes, if a volatile like v1 is
written and then read, ALL WRITES before the write of v1 are made
visible, including the write of n1 which is not declared volatile.

Brian Goetz calls this "piggy-backing," where non-synchronized writes
are made visible by piggy-backing on synchronized writes.