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

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

Volatile happens before question

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

Contents

  Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-17 04:04 -0800
    Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-17 08:17 -0800
      Re: Volatile happens before question markspace <-@.> - 2012-01-17 08:50 -0800
        Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-17 09:00 -0800
      Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-17 08:54 -0800
        Re: Volatile happens before question markspace <-@.> - 2012-01-17 11:24 -0800
      Re: Volatile happens before question Patricia Shanahan <pats@acm.org> - 2012-01-17 14:49 -0800
        Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 15:49 -0800
        Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-17 17:14 -0800
          Re: Volatile happens before question Patricia Shanahan <pats@acm.org> - 2012-01-17 18:17 -0800
            Re: Volatile happens before question Joshua Maurice <joshuamaurice@gmail.com> - 2012-01-19 16:45 -0800
    Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 08:18 -0800
      Re: Volatile happens before question markspace <-@.> - 2012-01-17 08:33 -0800
        Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 08:49 -0800
          Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 09:21 -0800
            Re: Volatile happens before question markspace <-@.> - 2012-01-17 10:10 -0800
              Re: Volatile happens before question Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-17 10:28 -0800
                Re: Volatile happens before question markspace <-@.> - 2012-01-17 10:41 -0800
                  Re: Volatile happens before question Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-17 11:06 -0800
                    Re: Volatile happens before question markspace <-@.> - 2012-01-17 12:09 -0800
                      Re: Volatile happens before question markspace <-@.> - 2012-01-17 12:12 -0800
                        Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-17 12:38 -0800
                          Re: Volatile happens before question markspace <-@.> - 2012-01-17 13:35 -0800
                            Re: Volatile happens before question markspace <-@.> - 2012-01-17 14:41 -0800
                      Re: Volatile happens before question Patricia Shanahan <pats@acm.org> - 2012-01-17 14:55 -0800
                        Re: Volatile happens before question markspace <-@.> - 2012-01-17 15:27 -0800
                    Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-17 17:37 -0800
                      Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-17 17:42 -0800
              Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 15:46 -0800
                Re: Volatile happens before question markspace <-@.> - 2012-01-17 16:14 -0800
                  Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 20:01 -0800
                    Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-17 20:37 -0800
                      Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 21:52 -0800
                        Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-17 23:47 -0800
                          Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-18 00:08 -0800
                            Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-18 09:04 -0800
                          Re: Volatile happens before question Steven Simpson <ss@domain.invalid> - 2012-01-18 11:22 +0000
                            Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-18 06:24 -0800
                              Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-18 07:32 -0800
                                Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-18 08:34 -0800
                                  Re: Volatile happens before question markspace <-@.> - 2012-01-18 10:12 -0800
                                    Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-18 11:15 -0800
                                      Re: Volatile happens before question markspace <-@.> - 2012-01-18 11:59 -0800
                                        Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-18 12:24 -0800
                                          Re: Volatile happens before question markspace <-@.> - 2012-01-18 13:16 -0800
                                            Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-18 15:00 -0800
                                              Re: Volatile happens before question markspace <-@.> - 2012-01-18 16:12 -0800
                                                Re: Volatile happens before question Patricia Shanahan <pats@acm.org> - 2012-01-18 16:34 -0800
                                                  Re: Volatile happens before question markspace <-@.> - 2012-01-18 17:17 -0800
                                                    Re: Volatile happens before question Patricia Shanahan <pats@acm.org> - 2012-01-18 19:03 -0800
                                            Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-18 15:30 -0800
                                              Re: Volatile happens before question markspace <-@.> - 2012-01-18 16:10 -0800
                                                Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-19 08:18 -0800
                                                  Re: Volatile happens before question markspace <-@.> - 2012-01-19 09:40 -0800
                                                    Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-19 10:10 -0800
                                                      Re: Volatile happens before question markspace <-@.> - 2012-01-19 10:39 -0800
                                                        Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-19 12:13 -0800
                                                          Re: Volatile happens before question markspace <-@.> - 2012-01-19 13:31 -0800
                                                            Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-19 16:14 -0800
                                                              Re: Volatile happens before question markspace <-@.> - 2012-01-19 21:16 -0800
                                                                Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-20 03:23 -0800
                                                                  Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-20 06:46 -0800
                                                                  Re: Volatile happens before question markspace <-@.> - 2012-01-20 08:56 -0800
                                                                    Re: Volatile happens before question Lew <noone@lewscanon.com> - 2012-01-20 11:12 -0800
                                        Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-18 17:06 -0800
                                        Re: Volatile happens before question Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-19 12:46 -0800
                                          Re: Volatile happens before question markspace <-@.> - 2012-01-19 13:38 -0800
                            Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-18 07:32 -0800
                        Re: Volatile happens before question Lew <noone@lewscanon.com> - 2012-01-18 00:06 -0800
                          Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-18 09:23 -0800
                        Re: Volatile happens before question Joshua Maurice <joshuamaurice@gmail.com> - 2012-01-19 17:07 -0800
                          Re: Volatile happens before question Joshua Maurice <joshuamaurice@gmail.com> - 2012-01-19 17:12 -0800
                          Re: Volatile happens before question Joshua Maurice <joshuamaurice@gmail.com> - 2012-01-19 19:22 -0800
    Re: Volatile happens before question Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-17 10:24 -0800

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

#11425

Maybe some other folks would like to look too.  I've found the blog I 
was looking for, but this guy is fairly prolific in his writing and I'm 
having trouble finding the article about how CPUs can return random 
values when proper signalling is not used.

Take a search through this blog anyway, it's a real eye-opener.

<http://bartoszmilewski.wordpress.com/>



On 1/17/2012 12:09 PM, markspace wrote:

> Check Java Concurrency in Practice. "Programs with data races have no
> useful defined semantics." That's exactly what Brian Goetz says, and
> this is what he's talking about. Reads and writes no longer work if you
> obviate synchronization.
>

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

#11426

Thanks for the info.  I think the conclusion is that it would be
unsafe?  I will just use synchronized to ensure safety.

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

#11427

On 1/17/2012 12:38 PM, raphfrk@gmail.com wrote:
> Thanks for the info.  I think the conclusion is that it would be
> unsafe?  I will just use synchronized to ensure safety.


Certainly my conclusion is that it is unsafe.  "Synchronization" here 
includes use of volatiles.  As long as you write the volatile last and 
read it first, the program is properly synchronized.

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

#11431

On 1/17/2012 1:35 PM, markspace wrote:
> On 1/17/2012 12:38 PM, raphfrk@gmail.com wrote:
>> Thanks for the info. I think the conclusion is that it would be
>> unsafe? I will just use synchronized to ensure safety.
>
>
> Certainly my conclusion is that it is unsafe. "Synchronization" here
> includes use of volatiles. As long as you write the volatile last and
> read it first, the program is properly synchronized.


Here's a video by the same guy, talking to the Seattle Java Users Group.

<http://vimeo.com/3757991>

Pay special attention to the "out of thin air guarantee."

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

#11433

On 1/17/2012 12:09 PM, markspace wrote:
> On 1/17/2012 11:06 AM, Daniel Pitts wrote:
...
>> If b=1, that means a MUST be true.
>
> No, if b = 1, it could just be a random value made up by the CPU.

That is one of the few behaviors that is specifically excluded. "Each
read sees a write to the same variable in the execution.",
http://java.sun.com/docs/books/jls/third_edition/html/memory.html#17.4.7

Patricia

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

#11434

On 1/17/2012 2:55 PM, Patricia Shanahan wrote:
> On 1/17/2012 12:09 PM, markspace wrote:
>> On 1/17/2012 11:06 AM, Daniel Pitts wrote:
> ...
>>> If b=1, that means a MUST be true.
>>
>> No, if b = 1, it could just be a random value made up by the CPU.
>
> That is one of the few behaviors that is specifically excluded. "Each
> read sees a write to the same variable in the execution.",
> http://java.sun.com/docs/books/jls/third_edition/html/memory.html#17.4.7


Well, I know Java can't exclude "made up values" because it happens in 
hardware.  Java has no choice but to execute on hardware.

The section you are referring to is 17.4.7 Well Formed Executions, and 
starts thusly: "We only consider well-formed executions."  In a well 
formed execution, I believe you are right, the program only sees writes 
that another thread actually made.

However a well formed execution also requires "4. The execution is 
happens-before consistent" and I believe that's what's being violated 
here.  Once you start reading variables with out proper synchronization, 
the concept of well formed executions are no longer valid and all of 
those 5 points go out the window.

This is what Brian Goetz means when he says "Programs with data races 
have no useful defined semantics."  Data races mean your code is no 
longer well formed.  Nice things like "you don't see made up values" 
don't work.  Things are just a mess.

Check that Vimeo link I posted, esp. the part about "out of thin air" 
values.  It's hard to get your head around but important, I think, to 
understand what happens when executions are not well-formed.  It 
provides good incentive to make sure your code really is synchronized in 
all cases.

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

#11442

On Tue, 17 Jan 2012 11:06:10 -0800, Daniel Pitts wrote:

> On 1/17/12 10:41 AM, markspace wrote:
>> On 1/17/2012 10:28 AM, Daniel Pitts wrote:
>>
>>> a was volatile, so it does cause the happens-before relationships with
>>> the reads/writes of b.
>>
>>
>> I messed up again, but I'm still right. :)
>>
>> He's reading "b" first. He stores b in bStore, and then checks "a".
> He is reading b first.  If b=1, that means a MUST be true. 

Why?  As "markspace" points out, "b" is not volatile, so we don't get any
cross-thread guarantees with respect to its value.  Marking "a" as volatile
only provides us with guarantees about writes that "happen-before" a write
to "a" and any reads that a read from "a" "happens-before", nothing more .

With "a" marked as volatile, we know that if thread #2 sees thread #1's
assignment "a = true", that thread #2 also sees thread #1's assignment "b =
1".  This is due to the happens-before guarantee "volatile" gives us for
"a".

But there's nothing I see in the specification that says that if thread #2
sees thread #1's assignment "b = 1" that thread #2 also sees thread #1's
assignment "a = true".  Without that guarantee, it is possible for thread
#2 to see "b = 1" but not "a = true", and thus find "a" to be false while
"b" is set to 1.

In fact, if we did have this guarantee we wouldn't need "volatile" at all.
If a write to a non-volatile variable could guarantee visibility of a
preceding write to a variable, then we'd have volatile semantics without
"volatile" already.

Even if we looked for something more strict, expecting that guarantee to be
present only for visibility of a preceding write to a volatile variable, I
just don't see where in the spec you might get that.

By definition (in this context), the lack of a guarantee is the same as
acknowledging the possibility of the opposite.

I believe in practice it would be rare (especially on x86 hardware) to ever
observe the exception.  But as far as I can tell, the Java specification
does not allow one to _know_ they will never observe the exception.

> [...]
>>> Thread 1
>>> int b = 0;
>>> volatile boolean a = false;
>>> ...
>>> ...
>>> a = true;
>>> b = 1;
>>>
>>> Thread 2
> // bStore = 0 or 1.
>>> int bStore = b;
> // if a is true bStore is either 0 or 1, 

Correct, but not the interesting bit.  :)

> but if a is false, b=1 hasn't 
> happened yet (since it a=true happens-before b=1).

"volatile" applied to "a" tells us nothing about other writes that writes
to "a" happen-before, and more importantly it also tells us nothing about
writes to "a" that happen-before other writes.  It only tells us about
other writes that happen-before writes to "a" and of course the write to
"a" itself.

Pete

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

#11444

On Tue, 17 Jan 2012 17:37:24 -0800, Peter Duniho wrote:

> [...]
> With "a" marked as volatile, we know that if thread #2 sees thread #1's
> assignment "a = true", that thread #2 also sees thread #1's assignment "b =
> 1".  This is due to the happens-before guarantee "volatile" gives us for
> "a".

I should clarify: in the above I am referring to the first example given,
where the assignment "b = 1" actually _does_ occur in program order before
the assignment "a = true".

> But there's nothing I see in the specification that says that if thread #2
> sees thread #1's assignment "b = 1" that thread #2 also sees thread #1's
> assignment "a = true".  Without that guarantee, it is possible for thread
> #2 to see "b = 1" but not "a = true", and thus find "a" to be false while
> "b" is set to 1.

Likewise the above refers to the _second_ example.

Sorry if I didn't make that clear enough originally.

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

#11437

On 1/17/2012 10:10 AM, markspace wrote:
> On 1/17/2012 9:21 AM, Knute Johnson wrote:
>
>> And if b = 1 could be reordered before a = true then b would be flopping
>> all over the place because as soon as a = true b would again have to
>> be 0.
>
>
> But those reads and writes could be reordered, couldn't they? The read
> of "a" could happen after the read of "b", because there's no
> happens-before relationship there (a is not volatile, nor synchronized
> in any way).
>
> Or is that what you are saying? The actual problem is worse. (And I did
> in fact fubar my explanation and the my reading of the code. It *is*
> broken though.) I'm still looking for references, and I might be close.
> Uno momento....


In his case b cannot be anything but 0 in thread 2 when a is read in the 
if statement.  That doesn't mean it is going to stay that way very long.

And to quote Goetz "When a field is declared volatile, the compiler and 
runtime are put on notice that this variable is shared and that 
operations on it should not be reordered with other memory operations."

-- 

Knute Johnson

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

#11439

On 1/17/2012 3:46 PM, Knute Johnson wrote:

> And to quote Goetz "When a field is declared volatile, the compiler and
> runtime are put on notice that this variable is shared and that
> operations on it should not be reordered with other memory operations."


To get that behavior, you have to actually read from the volatile after 
writing to it.  Check the JLS.  Both threads must participate in the 
happens-before operation, or this *is no* happens-before behavior.

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

#11450

On 1/17/2012 4:14 PM, markspace wrote:
> On 1/17/2012 3:46 PM, Knute Johnson wrote:
>
>> And to quote Goetz "When a field is declared volatile, the compiler and
>> runtime are put on notice that this variable is shared and that
>> operations on it should not be reordered with other memory operations."
>
>
> To get that behavior, you have to actually read from the volatile after
> writing to it. Check the JLS. Both threads must participate in the
> happens-before operation, or this *is no* happens-before behavior.

Assigning a value to a is a write.  Using it in the if test is a read.

-- 

Knute Johnson

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

#11451

On Tue, 17 Jan 2012 20:01:08 -0800, Knute Johnson wrote:

> On 1/17/2012 4:14 PM, markspace wrote:
>> On 1/17/2012 3:46 PM, Knute Johnson wrote:
>>
>>> And to quote Goetz "When a field is declared volatile, the compiler and
>>> runtime are put on notice that this variable is shared and that
>>> operations on it should not be reordered with other memory operations."

While the quoted text may assist in comprehending the Java specification,
it should not be confused with the Java specification.  And "should not be
reordered with" is not the kind of unambiguous language that one finds in
the specification (i.e. it's consistent with either interpretation).

>> To get that behavior, you have to actually read from the volatile after
>> writing to it. Check the JLS. Both threads must participate in the
>> happens-before operation, or this *is no* happens-before behavior.
> 
> Assigning a value to a is a write.  Using it in the if test is a read.

Correct. And "volatile" ensures that all writes that happen-before the
write to the volatile variable are visible in any thread that reads the
same variables _after_ a read from the volatile variable.

There's nothing about that requirement that implies anything whatsoever
about writes that occur _after_ the write to the volatile variable.  Those
writes are not even mentioned.

If you have a different place of the specification that explicitly
addresses that scenario, or you have some way to logically manipulate (i.e.
akin to a mathematical proof) the guarantees that _are_ described in the
memory-model and volatile parts of the specification such that there's a
conclusion that does address that scenario, then I'm sure we would all be
very interested to see that.

But the parts of the specification we're referring to at the moment do not
appear to lead to the conclusion you're stating.  They don't even address
the scenario in question.

Or put another way: let's assume for the moment that you're right, and that
I (and possibly others) are misinterpreting the specification.  Parse the
relevant portion of the spec for us step-by-step, rather than assuming
we're able to do that ourselves (since we've clearly failed to).

Pete

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

#11453

Let's start over here:

Thread 1
int b = 0;
volatile boolean a = false;
...
...
a = true;
b = 1;

Thread 2
int bStore = b;
if (!a) {
   System.out.println("The value of b is " + bStore);
}

Will this always print either "The value of b is 0" or nothing.

+++++++++++++++

I'm not even sure what we are discussing any more so I will make a 
statement that I don't think can be false.

If a is false at the if in thread 2 then b must be 0 in thread 2.

In thread 1, b = 0 happens before a = false happens before a = true 
happens before b = 1.

In thread 2, bStore = b happens before the test of a.  Therefore bStore 
must be 0 in the print statement if a is false.

And if a is true at the test in thread 2 then b could be either 0 or 1.

Do we disagree on this?

-- 

Knute Johnson

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

#11454

On Tue, 17 Jan 2012 21:52:00 -0800, Knute Johnson wrote:

> Let's start over here:
> 
> Thread 1
> int b = 0;
> volatile boolean a = false;
> ...
> ...
> a = true;
> b = 1;
> 
> Thread 2
> int bStore = b;
> if (!a) {
>    System.out.println("The value of b is " + bStore);
> }
> 
> Will this always print either "The value of b is 0" or nothing.
> 
> +++++++++++++++
> 
> I'm not even sure what we are discussing any more so I will make a 
> statement that I don't think can be false.
> 
> If a is false at the if in thread 2 then b must be 0 in thread 2.
> 
> In thread 1, b = 0 happens before a = false happens before a = true 
> happens before b = 1.
> 
> In thread 2, bStore = b happens before the test of a.  Therefore bStore 
> must be 0 in the print statement if a is false.
> 
> And if a is true at the test in thread 2 then b could be either 0 or 1.
> 
> Do we disagree on this?

Yes.  Sorry.  :)

Here are the excerpts of the specification that seem relevant to me:

  17.4.2 Actions
    An inter-thread action is an action performed by one thread
    that can be detected or directly influenced by another thread.
    There are several kinds of inter-thread action that a program
    may perform:

    * Synchronization actions, which are: 
      - Volatile read. A volatile read of a variable. 
      - Volatile write. A volatile write of a variable. 

Defines the write to and the read from "a" as a "synchronization action".

  17.4.4 Synchronization Order
    Every execution has a synchronization order. A synchronization
    order is a total order over all of the synchronization actions
    of an execution. For each thread t, the synchronization order
    of the synchronization actions (§17.4.2) in t is consistent
    with the program order (§17.4.3) of t. 

    Synchronization actions induce the synchronized-with relation
    on actions, defined as follows: 

    * A write to a volatile variable (§8.3.1.4) v synchronizes-with
      all subsequent reads of v by any thread (where subsequent is
      defined according to the synchronization order). 

Tells us that the program statement "a = true" "synchronizes-with" the
program statement "if (!a)".

  17.4.5 Happens-before Order
    Two actions can be ordered by a happens-before relationship. If
    one action happens-before another, then the first is visible to
    and ordered before the second. 

    If we have two actions x and y, we write hb(x, y) to indicate
    that x happens-before y. 

    * If an action x synchronizes-with a following action y, then
      we also have hb(x, y). 
    * If hb(x, y) and hb(y, z), then hb(x, z).

Tells us that any program statement _before_ "a = true" must
"happen-before" any program statement _after_ "if (!a)".  Notably it, this
part at least, does not tell us anything about statements that come after
"a = true" in thread #1, nor statements that come before "if (!a)" in
thread #2.


The problem as I see it is that while your statements about the
intra-thread order of the program statements are correct, the original
question doesn't pertain to the intra-thread order.  It pertains to the
inter-thread order, which is defined only insofar as the memory model
defines it.

And as far as I can tell, the memory model leaves the question open
(undefined) as to what happens when you read a non-volatile field _before_
reading a volatile field.

Reading the volatile field induces synchronization between the threads,
such that whatever happened up to the point of the write to the volatile
field is visible to whatever happens _after_ the point of the read of the
volatile field.  Until the thread reads the volatile field, all bets are
off.

The thread that will eventually read the volatile field is permitted to see
any unsynchronized state from the thread writing the field, including a
write that in the first thread occurs after a write to the volatile field
that the second thread hasn't seen yet.

Because the memory model doesn't stipulate what must happen, compilers and
run-times are permitted to allow the write to "b" to be reordered to occur
before the write to "a".  This reordering then can cause the early-written
value of "1" to be observed in thread #2, even as it just one program
statement later observes the still-unwritten variable "a", seeing a value
of "false".

And even if the compiler (javac or JIT) doesn't reorder the writes, without
a full memory barrier enforced by the runtime, the hardware could reorder
them.

Now, I admit that I do not know the Java specification inside and out.
It's possible I've overlooked something in the specification that provides
the requirement that would lead to the interpretation of the code you're
suggesting.  So if you know of such a section of the specification, I
welcome being shown the error of my ways.  :)

Pete

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

#11456

On Tue, 17 Jan 2012 23:47:38 -0800, Peter Duniho wrote:

> [...]
>     If we have two actions x and y, we write hb(x, y) to indicate
>     that x happens-before y. 
> 
>     * If an action x synchronizes-with a following action y, then
>       we also have hb(x, y). 
>     * If hb(x, y) and hb(y, z), then hb(x, z).
> 
> Tells us that any program statement _before_ "a = true" must
> "happen-before" any program statement _after_ "if (!a)".  Notably it, this
> part at least, does not tell us anything about statements that come after
> "a = true" in thread #1, nor statements that come before "if (!a)" in
> thread #2.

Sorry, I seem to be making a habit of leaving out important clarification
lately.  To wit: in the above, I am assuming that the statement "a = true"
actually does execute before the statement "if (!a)".  Obviously, that
doesn't have to happen...thread #2 could complete before thread #1 ever
executes, or any variation on that theme.  But the scenario the
specification addresses is when that does happen.

If program statement "if (!a)" occurs before "a = true", then the
specification doesn't tell us anything specific about the other statements
around those statements.  Thus my interpretation that allows "bStore" to
wind up with the value of 1 even if the statement "if (!a)" observes "a" as
having the value of "false" instead of "true".

Pete

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

#11468

On 1/18/2012 12:08 AM, Peter Duniho wrote:
> On Tue, 17 Jan 2012 23:47:38 -0800, Peter Duniho wrote:
>
>> [...]
>>      If we have two actions x and y, we write hb(x, y) to indicate
>>      that x happens-before y.
>>
>>      * If an action x synchronizes-with a following action y, then
>>        we also have hb(x, y).
>>      * If hb(x, y) and hb(y, z), then hb(x, z).
>>
>> Tells us that any program statement _before_ "a = true" must
>> "happen-before" any program statement _after_ "if (!a)".  Notably it, this
>> part at least, does not tell us anything about statements that come after
>> "a = true" in thread #1, nor statements that come before "if (!a)" in
>> thread #2.
>
> Sorry, I seem to be making a habit of leaving out important clarification
> lately.  To wit: in the above, I am assuming that the statement "a = true"
> actually does execute before the statement "if (!a)".  Obviously, that
> doesn't have to happen...thread #2 could complete before thread #1 ever
> executes, or any variation on that theme.  But the scenario the
> specification addresses is when that does happen.
>
> If program statement "if (!a)" occurs before "a = true", then the
> specification doesn't tell us anything specific about the other statements
> around those statements.  Thus my interpretation that allows "bStore" to
> wind up with the value of 1 even if the statement "if (!a)" observes "a" as
> having the value of "false" instead of "true".
>
> Pete

Pete:

I woke up in the middle of the night thinking about this again :-).

I made some assumptions that I'm not sure you did and that was that a 
and b were safely published in thread 1 before the ... and that 
execution of both threads started at that point (probably not a good 
assumption but that was it).  If that were not the case then b is up for 
grabs until a is read in thread 2.

The other question, can b = 1 be reordered before the a = true as seen 
by thread 2, I'm not really sure.  I am sure that once a is read in 
thread 2 b must again be 0 whether it was reordered or not.  That is the 
one guarantee of volatile that the memory model will be up to date for 
all writes to all variables written before the write to the volatile is 
subsequently read in the other thread.

So I think that my original answer to the OP is not correct.  I'm not 
sure how to answer the reordering question.  As best I can read the JLS 
there is no special case for thread with volatile assignments other than 
a read following a write.

I did find a good quote for the day however, "Don't rely on clever 
reasoning about why you don't need to synchronize", Brian Goetz.

-- 

Knute Johnson

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

#11457

On 18/01/12 07:47, Peter Duniho wrote:
> Because the memory model doesn't stipulate what must happen, compilers and
> run-times are permitted to allow the write to "b" to be reordered to occur
> before the write to "a".  This reordering then can cause the early-written
> value of "1" to be observed in thread #2, even as it just one program
> statement later observes the still-unwritten variable "a", seeing a value
> of "false".

Let's see if I've followed this...

In the first case, thread 1 writes 'b', then volatile-writes 'a'.  
Thread 2 volatile-reads 'a', then reads 'b'.  We only care when the read 
of 'a' happens after the write of 'a', as otherwise we don't use the 
value of 'b':

0    1     2     3     4     5
      |     |
      V     V
--------------------------------1
      b     a
            *     *
                  a     b
--------------------------------2
                  |     |
                  V     V

'volatile' guarantees that the write to 'b' at time 1 is not optimized 
in any way to happen after t2.  If it were not guaranteed, it might 
happen after t4, which we assert won't happen.

So, 'volatile' prevents the write to 'b' from jumping into the future of 
the write to 'a'.


In the second case, thread 1 volatile-writes 'a' (as true), then writes 
'b'.  Thread 2 reads 'b', then volatile-reads 'a'.  Thread 2 copies 'b', 
but only uses the copied value if 'a' is later found to be (still) 
false, so we only care when the read of 'a' happens before the write of 'a':

0    1     2     3     4     5
                  |     |
                  V     V
--------------------------------1
                  a     b
            *     *
      b     a
--------------------------------2
      |     |
      V     V

This time, 'volatile' does not guarantee anything for the write to 'b'.  
It could be optimized to happen as early as t0, so we cannot assert that 
thread 2 will always use the initial value of 'b'.

So, 'volatile' does not prevent the write to 'b' from jumping back into 
the past of the write to 'a'.



-- 
ss at comp dot lancs dot ac dot uk

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

#11461

So, is there a way to do a basic read-write lock without using the
synchronized keyword?

Would the lock from this page work?

http://mailinator.blogspot.com/2007/05/readerwriter-in-java-in-nonblocking.html

He has an atomic integer as a counter.

The write operation is

incrementcounter() -> set to odd number = unstable
<perform update>
incrementCounter() -> set to even number = stable

The write operation uses a standard lock so writes are in the right
sequence.

The read operation is

do {
  while ((save = counter.get()) & 1 == 1);  // loop while unstable
  value = <read value>
  if (counter.get() == save) {
     return value;
  }
} while (true);

So, a read confirms that the read value is stable (even) at the start
and doesn't change while the read happens.  If it changes, then repeat.

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

#11463

On Wed, 18 Jan 2012 06:24:54 -0800 (PST), raphfrk@gmail.com wrote:

> So, is there a way to do a basic read-write lock without using the
> synchronized keyword?
> 
> Would the lock from this page work?
> 
> http://mailinator.blogspot.com/2007/05/readerwriter-in-java-in-nonblocking.html
> [...]

It looks correct to me.

However, note that even now, almost five years later, the author has not
posted any conclusive performance analysis.

Lock-free algorithms _can_ greatly outperform locking algorithms, but
sometimes they don't.  The key is to match the implementation with the
expected user scenarios and the acceptable cost/benefit trade-offs for the
project (though the latter is of course eased if one is not actually
writing one's own lock-free algorithm but instead using a published and
vetted one, such as that seen in the article above).

I would, pretty much every time, start with a basic locking strategy and
investigate fancier synchronization only when I have proven that the code
is too slow and that the synchronization is what is causing that.

Pete

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

#11467

On Jan 18, 3:32 pm, Peter Duniho <NpOeStPe...@NnOwSlPiAnMk.com> wrote:
> On Wed, 18 Jan 2012 06:24:54 -0800 (PST), raph...@gmail.com wrote:
> >http://mailinator.blogspot.com/2007/05/readerwriter-in-java-in-nonblo...
> > [...]
>
> It looks correct to me.

I don't understand why it is ok.  Doesn't it suffer from the same
issue as my example?

Thread 1:

atomicInteger.increment()
nonVolatile.someUpdateMethod();
atomicInteger.increment()


Thread 2:
int temp;
if (isEven(temp = atomicInteger.get())) {
  System.out.println("nonVolatile is" +
nonVolatile.someReadingMethod());
  if (atomicInteger.get() != temp) {
    System.out.println("Read error");
  }
}

Incrementing the atomicInteger is a write, but there is no guarantee
that if the write hasn't happened that the nonVolatile was stable for
the duration.

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

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

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

csiph-web