Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #10849 > unrolled thread

reading the JLS (17.4.5)

Back to article view | Back to comp.lang.java.programmer

Contents

  reading the JLS (17.4.5) Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-12-18 12:10 +0000
    Re: reading the JLS (17.4.5) markspace <-@.> - 2011-12-18 06:57 -0800
      Re: reading the JLS (17.4.5) Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-12-20 17:54 +0000
        Re: reading the JLS (17.4.5) markspace <-@.> - 2011-12-20 10:50 -0800
          Re: reading the JLS (17.4.5) Patricia Shanahan <pats@acm.org> - 2011-12-20 12:12 -0800
            Re: reading the JLS (17.4.5) Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-12-21 08:54 +0000
              Re: reading the JLS (17.4.5) Patricia Shanahan <pats@acm.org> - 2011-12-21 10:56 -0800
                Re: reading the JLS (17.4.5) markspace <-@.> - 2011-12-21 12:02 -0800
    Re: reading the JLS (17.4.5) Patricia Shanahan <pats@acm.org> - 2011-12-18 09:21 -0800
      Re: reading the JLS (17.4.5) Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-12-20 18:35 +0000
        Re: reading the JLS (17.4.5) Lew <lewbloch@gmail.com> - 2011-12-20 19:08 -0800
          Re: reading the JLS (17.4.5) Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-12-21 08:37 +0000
            Re: reading the JLS (17.4.5) Patricia Shanahan <pats@acm.org> - 2011-12-21 10:46 -0800
            Re: reading the JLS (17.4.5) markspace <-@.> - 2011-12-21 12:09 -0800

#10849 — reading the JLS (17.4.5)

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?

[toc] | [next] | [standalone]

#10850

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.

[toc] | [prev] | [next] | [standalone]

#10907

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.

[toc] | [prev] | [next] | [standalone]

#10909

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.

[toc] | [prev] | [next] | [standalone]

#10911

On 12/20/2011 10:50 AM, markspace wrote:
...
> 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.

I just wanted to construct one specific case, and picked a fairly
arbitrary combination of operations and events. Producing the sort of
effect I was aiming for does require a happens-before relationship
between two actions in different threads.

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. If the reordering produces results consistent with a
legal execution, it is not illegal."

Prohibiting a read R from seeing the result of a write W if R "must
appear to happen before" W, but may in fact have happened after W, is
quite reasonable.

Patricia

[toc] | [prev] | [next] | [standalone]

#10926

Patricia Shanahan <pats@acm.org> 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) ?

[toc] | [prev] | [next] | [standalone]

#10932

On 12/21/2011 12:54 AM, Andreas Leitgeb wrote:
> Patricia Shanahan<pats@acm.org>  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) ?
>

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.

In a small, simple system, with a sequentially consistent hardware
memory model, it may be as simple as writing out any values that are
being held in registers to the appropriate memory locations.

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.

Patricia

[toc] | [prev] | [next] | [standalone]

#10935

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.

[toc] | [prev] | [next] | [standalone]

#10854

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. 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?

Patricia

[toc] | [prev] | [next] | [standalone]

#10908

Patricia Shanahan <pats@acm.org> 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.

[toc] | [prev] | [next] | [standalone]

#10924

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.

[toc] | [prev] | [next] | [standalone]

#10925

Lew <lewbloch@gmail.com> 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.

[toc] | [prev] | [next] | [standalone]

#10931

On 12/21/2011 12:37 AM, Andreas Leitgeb wrote:
> Lew<lewbloch@gmail.com>  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.
>

I think we need to distinguish between two things. I'm going to copy
some notation from Lew. /happens-before/, printed in italics in the JLS,
is not an observation about what really happened, but a requirement of
the form "X must appear to happen before Y", with a definition of what
that means in terms e.g. of the results of read operations.

That is entirely distinct from the actual order of operations. If a read
sees the result of a write, that write must have really happened before
(no slashes, no italics) the read, but that does not prove the existence
of a /happens-before/ relationship between them.

However, the volatile reads and writes are synchronization actions, so
they are ordered by the synchronization order, and whichever comes first
in the synchronization order /happens-before/ the other. I agree with
your assertion.

Patricia

[toc] | [prev] | [next] | [standalone]

#10936

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web