reading the JLS (17.4.5)

Discussion in 'Java' started by Andreas Leitgeb, Dec 18, 2011.

  1. 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?
    Andreas Leitgeb, Dec 18, 2011
    #1
    1. Advertising

  2. Andreas Leitgeb

    markspace Guest

    On 12/18/2011 4:10 AM, Andreas Leitgeb wrote:
    > 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.
    markspace, Dec 18, 2011
    #2
    1. Advertising

  3. markspace <-@> wrote:
    > On 12/18/2011 4:10 AM, Andreas Leitgeb wrote:
    >> 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.


    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, Dec 20, 2011
    #3
  4. Patricia Shanahan <> wrote:
    > On 12/18/2011 4:10 AM, Andreas Leitgeb wrote:
    >> How could a "read" that happens-before a particular "write" *ever*
    >> see the "write"'s value?
    >> Maybe, someone could explain, what that *really* means?

    >
    > 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.
    Andreas Leitgeb, Dec 20, 2011
    #4
  5. Andreas Leitgeb

    markspace Guest

    On 12/20/2011 9:54 AM, Andreas Leitgeb wrote:

    > 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.
    markspace, Dec 20, 2011
    #5
  6. Andreas Leitgeb

    Lew Guest

    Andreas Leitgeb wrote:
    > 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.

    --
    Lew

    > "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.
    Lew, Dec 21, 2011
    #6
  7. Lew <> wrote:
    > Andreas Leitgeb wrote:
    >> 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.


    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, Dec 21, 2011
    #7
  8. Patricia Shanahan <> wrote:
    > 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) ?
    Andreas Leitgeb, Dec 21, 2011
    #8
  9. Andreas Leitgeb

    markspace Guest

    On 12/21/2011 10:56 AM, Patricia Shanahan wrote:
    > On 12/21/2011 12:54 AM, Andreas Leitgeb wrote:
    >>
    >> 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) ?
    >>

    >
    > 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, Dec 21, 2011
    #9
  10. Andreas Leitgeb

    markspace Guest

    On 12/21/2011 12:37 AM, Andreas Leitgeb wrote:

    > *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.
    markspace, Dec 21, 2011
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mike Schilling
    Replies:
    10
    Views:
    712
    Mike Schilling
    Sep 29, 2003
  2. VisionSet

    JCert & JLS gotcha

    VisionSet, Oct 6, 2003, in forum: Java
    Replies:
    0
    Views:
    348
    VisionSet
    Oct 6, 2003
  3. Mike Schilling

    JLS 3 Errata

    Mike Schilling, Oct 2, 2005, in forum: Java
    Replies:
    3
    Views:
    452
    Mike Schilling
    Oct 2, 2005
  4. stixwix

    equals method contract in JLS

    stixwix, Dec 12, 2005, in forum: Java
    Replies:
    2
    Views:
    1,002
    Chris Smith
    Dec 12, 2005
  5. Oliver Wong
    Replies:
    9
    Views:
    401
    Roedy Green
    Feb 10, 2006
Loading...

Share This Page