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 1 of 4  [1] 2 3 4  Next page →

#11400 — Volatile happens before question

The spec says that all writes to volatiles can be considered to happen
before all subsequent reads.  What does "subsequent" mean, is that
with regards to real time?

So,

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

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

Since the setting of a to true happens before the reading of a as
true, the println must happen after b is set to 1.

This means that either nothing will be printed or "The value of b is
1" will be printed.

Does this work in reverse too?

For example,

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.

(bStore = b) happens before (read a as false)
(read a as false) happens before (set a = true) [is this valid?]
(set a = true) happens before (set b = 1)

So, bStore = b happens before set b = 1, so bStore = 0.

Effectively, the rule would be "A read to a volatile happens before
the write to that volatile that overwrites the value that was read".

However, that wasn't clear from the spec.  I think since read/writes
to volatiles are synchronization actions, then when running the
program, they can be considered to have happened in some ordering
(consistent with program order in the threads).  As long as the
program works no matter what the ordering is picked, then it is fine.

[toc] | [next] | [standalone]

#11402

On Tue, 17 Jan 2012 04:04:52 -0800 (PST), raphfrk@gmail.com wrote:

> The spec says that all writes to volatiles can be considered to happen
> before all subsequent reads.  What does "subsequent" mean, is that
> with regards to real time?

Essentially, yes.  I believe the exact language talks about synchronization
order" or something, but the basic idea is the order in which program
statements are effectively executed.

Without volatile, the program statements may be effectively reordered
according to the needs of optimization (by the JIT compiler, runtime,
hardware, etc.) as long as the same outcome occurs for a given thread.

With volatile, this strengthens the requirements slightly by also requiring
the same outcome for certain parts of the code even across multiple threads
(i.e. those parts that use fields marked "volatile").  (And in particular,
in the way that the spec describes using the "happens before" language).

> So,
> 
> Thread 1
> int b = 0;
> volatile boolean a = false;
> ...
> ...
> b = 1;
> a = true;
> 
> Thread 2
> if (a) {
>   System.out.println("The value of b is " + b);
> }
> 
> Since the setting of a to true happens before the reading of a as
> true, the println must happen after b is set to 1.

Yes, that's precisely the typical usage of "volatile".  A sentinel value
like "a" is set to some new value that a different thread will see.
Everything else that was written before that write to the "volatile" field
is guaranteed to have actually taken place before some other thread reads
from the "volatile" field.

> This means that either nothing will be printed or "The value of b is
> 1" will be printed.

Right.

> Does this work in reverse too?
> 
> For example,
> 
> 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.

No, I don't think that you get the opposite guarantee.

Using "volatile" creates a "synchronizes-with" relationship between the
assignment "a = true" and the read "if (!a)".

Within a thread, you're guaranteed statements happen in program order.
With "volatile", you also get the guarantee that the write to the variable
"a" synchronizes with the read from variable "a".  That is, that everything
that happens before the write to "a" also must happen before the read from
"a".

But there's not a "happens-after" guarantee, just a "happens-before".  The
specification assures you that anything that happened before the write,
will be seen by another thread after it reads from the same volatile
variable.  But since the assignment "b = 1" occurs after the assignment "a
= true", and since "b" is not volatile, the specification offers no
guarantees about what "happens-before" the write to "b" (such as the
assignment "a = true").

Without this guarantee, the write to "b" is allowed to be reordered, and
could move ahead of the write to "a".

If you want a more robust synchronization, then you have "synchronized" and
the concurrency-related objects to provide stronger guarantees.

> (bStore = b) happens before (read a as false)
> (read a as false) happens before (set a = true) [is this valid?]
> (set a = true) happens before (set b = 1)

It's this last assertion that fails.  It's only valid when looking only at
the thread in which those statements appear.  You can be sure that in the
first thread, the variable "b" will not be seen to be set to "1" before the
variable "a" is set to "true".  But from the point of view of other
threads, there's nothing that guarantees "a = true" happens before "b = 1".

The change to variable "a" could get published late or the change to
variable "b" could get published earlier, and either would invalidate the
apparent order of execution.

> So, bStore = b happens before set b = 1, so bStore = 0.
> 
> Effectively, the rule would be "A read to a volatile happens before
> the write to that volatile that overwrites the value that was read".

I'm not aware of any such rule or its equivalent appearing in the
specification.

> However, that wasn't clear from the spec.  I think since read/writes
> to volatiles are synchronization actions, then when running the
> program, they can be considered to have happened in some ordering
> (consistent with program order in the threads).  As long as the
> program works no matter what the ordering is picked, then it is fine.

I think the key is that you get "happens-before" guarantees but not
"happens-after" guarantees.  If you want a guarantee about what happens
before a write to a variable, such as in "b = 1", then "b" is what needs to
be volatile.

All that said, this question highlights the caution one must use when using
"volatile".  Fact is, for most of us, using full synchronization always is
likely the best approach, as it's a much simpler concept to understand (and
frankly is not all that simple itself).  "volatile" exists and can be used
when absolutely needed, but one should be prepared to really dig in and
make sure one understands exactly how the memory model is defined, to
carefully validate any concurrent code in the program, and to do rigorous
performance testing to make sure that the weakened memory guarantees really
are providing the performance benefit over simpler synchronized code that
is hoped for when one uses "volatile".

That's a pretty tall order, and most often probably not worth the cost.

Pete

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

#11406

On 1/17/2012 8:17 AM, Peter Duniho wrote:

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

>> (set a = true) happens before (set b = 1)
>
> It's this last assertion that fails.


I believe the original assertion is true, but in code he was assuming 
the converse. (*)  That is a is true before b is 1, but just because a 
is true doesn't mean that b has been set to 1 yet.  There is a physical 
time gap in between those events. (**)

In other words, the JLS does not say that:

a is true iff b is 1.

(iff = "if and only if").

The JLS does say:

If b is 1, then a has also been set to true. (a happens before b.)

The JLS does not say:

If a is true, then b has been also set to 1.

That last statement could be false and there could still be a valid 
happens-before relationship between write(a<-true) and write(b<-1). 
There is a time gap between a being written and b being written where 
you could see a==true but b==0.

As a general rule of thumb, you always read the volatile FIRST and write 
the volatile LAST.  Here in the 2nd example, a was read first and the 
volatile (b) was read after, so that's why it didn't work.



(*) I'm wondering if the proper word is reflexive rather than converse. 
  That is, just because

(b=1) therefore (a=true) is true, does not mean

(a=true) therefore (b=1) is true (it's not).

Any help here?


(**) These are terrible variable names for discussion a problem in 
English.  "a" looks like the article a and b is just as bad.  Use 
something longer and more obvious next time.  I can scarcely follow my 
own writing, sheesh.

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

#11408

On Jan 17, 4:50 pm, markspace <-@.> wrote:
> On 1/17/2012 8:17 AM, Peter Duniho wrote:
>
> >> int b = 0;
> >> volatile boolean a = false;
> >> ...
> >> ...
> >> a = true;
> >> b = 1;
> >> (set a = true) happens before (set b = 1)
>
> > It's this last assertion that fails.
>
> I believe the original assertion is true, but in code he was assuming
> the converse. (*)  That is a is true before b is 1, but just because a
> is true doesn't mean that b has been set to 1 yet.  There is a physical
> time gap in between those events. (**)

No, I was assuming that if a = false, then b must be 0.

Effectively, "if a read of a volatile gives the old value, then that
read happens before the write that overwrites that value"

If thread 2 is
a = true;
b = 1;

then if a == false, then b must not yet be set to 1.

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

#11407

On Jan 17, 4:17 pm, Peter Duniho <NpOeStPe...@NnOwSlPiAnMk.com> wrote:
> > Effectively, the rule would be "A read to a volatile happens before
> > the write to that volatile that overwrites the value that was read".
>
> I'm not aware of any such rule or its equivalent appearing in the
> specification.

The spec says that there is an ordering of the synchronisation
actions.

So, this means that the JVM must order all synchronization actions in
some ordering that is consistent with the program ordering in each
thread.

However, if it places a sync actions later than another sync action,
that still doesn't mean that the later one "happens after" the first
one?

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

#11422

On 1/17/2012 8:54 AM, raphfrk@gmail.com wrote:

> However, if it places a sync actions later than another sync action,
> that still doesn't mean that the later one "happens after" the first
> one?


Specifically, no.

It wasn't clear to me that was the question you where asking. (Sorry 
about that!)  Your program was a little hard to read.  But the answer is 
that there is are no semantics for multi-threaded reads and rights if 
there is no happens-before relationship.

What you have there is called a data race.  Those are completely broken. 
  The reason is that hardware involved will optimize reads and writes 
aggressively.  (The same problem would occur even if you wrote this code 
in assembly language.  This is not a Java problem, it's a system 
problem.  The JLS actually just tells you how modern CPUs work.)

In this case, by creating a data race and reading b before you create 
the happens-before relationship, Thread 2 could see any value for b, 
even values that are neither 1 nor 0.  It's a random number generator. 
(And the more complete story is even worse.  I'm still looking for some 
sources to back that up though.)

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

#11432

On 1/17/2012 8:17 AM, Peter Duniho wrote:
> On Tue, 17 Jan 2012 04:04:52 -0800 (PST), raphfrk@gmail.com wrote:
>
>> The spec says that all writes to volatiles can be considered to happen
>> before all subsequent reads.  What does "subsequent" mean, is that
>> with regards to real time?
>
> Essentially, yes.  I believe the exact language talks about synchronization
> order" or something, but the basic idea is the order in which program
> statements are effectively executed.
...

Even before analyzing the entire thread so far, I'm going to disagree
with this comment, because it can lead to an incorrect intuition.

Real time order is a total order, or can be made into one by adding a
tie breaker using the processor number for events that happen on the
same cycle in different processors.

The potential incorrect intuition is that there is a total order of all
events in a Java program. There isn't.

There are a number of important partial orders: synchronization order,
happens-before, and program order within a thread. The behavior of reads
and writes must be consistent with the relevant partial orders, but do
not have to be consistent with any one total order.

The problem with imposing a total order is the amount of inter-processor
communication and coordination it would require.

Patricia

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

#11438

On 1/17/2012 2:49 PM, Patricia Shanahan wrote:
> On 1/17/2012 8:17 AM, Peter Duniho wrote:
>> On Tue, 17 Jan 2012 04:04:52 -0800 (PST), raphfrk@gmail.com wrote:
>>
>>> The spec says that all writes to volatiles can be considered to happen
>>> before all subsequent reads. What does "subsequent" mean, is that
>>> with regards to real time?
>>
>> Essentially, yes. I believe the exact language talks about
>> synchronization
>> order" or something, but the basic idea is the order in which program
>> statements are effectively executed.
> ...
>
> Even before analyzing the entire thread so far, I'm going to disagree
> with this comment, because it can lead to an incorrect intuition.
>
> Real time order is a total order, or can be made into one by adding a
> tie breaker using the processor number for events that happen on the
> same cycle in different processors.
>
> The potential incorrect intuition is that there is a total order of all
> events in a Java program. There isn't.
>
> There are a number of important partial orders: synchronization order,
> happens-before, and program order within a thread. The behavior of reads
> and writes must be consistent with the relevant partial orders, but do
> not have to be consistent with any one total order.
>
> The problem with imposing a total order is the amount of inter-processor
> communication and coordination it would require.
>
> Patricia

And part of the problem with analyzing the OPs code is that we are 
assuming that thread 1 is actually running before thread 2 (or at least 
I was) which in reality may not be the case.

-- 

Knute Johnson

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

#11441

On Tue, 17 Jan 2012 14:49:58 -0800, Patricia Shanahan wrote:

> On 1/17/2012 8:17 AM, Peter Duniho wrote:
>> On Tue, 17 Jan 2012 04:04:52 -0800 (PST), raphfrk@gmail.com wrote:
>>
>>> The spec says that all writes to volatiles can be considered to happen
>>> before all subsequent reads.  What does "subsequent" mean, is that
>>> with regards to real time?
>>
>> Essentially, yes.  I believe the exact language talks about synchronization
>> order" or something, but the basic idea is the order in which program
>> statements are effectively executed.
> ...
> 
> Even before analyzing the entire thread so far, I'm going to disagree
> with this comment, because it can lead to an incorrect intuition.

I have to admit, I didn't think my statement was specific enough for you to
disagree on the point with which you chose to disagree.

> Real time order is a total order, or can be made into one by adding a
> tie breaker using the processor number for events that happen on the
> same cycle in different processors.
> 
> The potential incorrect intuition is that there is a total order of all
> events in a Java program. There isn't. [...]

I think I understand what you're saying and I don't disagree, but the fact
remains that it is reasonable to consider the order of execution of
statements within the program relative to each other, as if it _were_
possible to identify a total order.  After all, any time there's a conflict
(e.g. two different threads writing atomically to the same memory location
at once), the CPU does pick a winner, even if non-deterministically.

Some statements may occur concurrently, and of course directly germane to
this discussion is the fact that the apparent order of execution (i.e. the
observable results) for any given thread is dependent on what's observing
that thread (i.e. without synchroniation, the observable data may mutate in
a different way in one thread than it does in another).  Synchronization is
all about removing these ambiguities.

IF you feel my statement was not specific enough to avoid confusing
someone, that's fine with me.  But outright disagreement?  Seems like you
have to infer too much to get that far.  :)

Pete

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

#11446

On 1/17/2012 5:14 PM, Peter Duniho wrote:
> On Tue, 17 Jan 2012 14:49:58 -0800, Patricia Shanahan wrote:
...
>> The potential incorrect intuition is that there is a total order of all
>> events in a Java program. There isn't. [...]
>
> I think I understand what you're saying and I don't disagree, but the fact
> remains that it is reasonable to consider the order of execution of
> statements within the program relative to each other, as if it _were_
> possible to identify a total order.  After all, any time there's a conflict
> (e.g. two different threads writing atomically to the same memory location
> at once), the CPU does pick a winner, even if non-deterministically.

I agree that total ordering is a reasonable model of single processor
operations, where there is such a thing as "the" CPU.

Patricia

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

#11508

On Jan 17, 6:17 pm, Patricia Shanahan <p...@acm.org> wrote:
> On 1/17/2012 5:14 PM, Peter Duniho wrote:
>
> > On Tue, 17 Jan 2012 14:49:58 -0800, Patricia Shanahan wrote:
> ...
> >> The potential incorrect intuition is that there is a total order of all
> >> events in a Java program. There isn't. [...]
>
> > I think I understand what you're saying and I don't disagree, but the fact
> > remains that it is reasonable to consider the order of execution of
> > statements within the program relative to each other, as if it _were_
> > possible to identify a total order.  After all, any time there's a conflict
> > (e.g. two different threads writing atomically to the same memory location
> > at once), the CPU does pick a winner, even if non-deterministically.
>
> I agree that total ordering is a reasonable model of single processor
> operations, where there is such a thing as "the" CPU.

To expound on this a bit, there is no such naive "total order" for
some multi-core processors. Consider the pseudo-code:

//initial
a=0; //shared
b=0; //shared

//thread 1
a=1;
b=2;

//threads 2-5
local_a = a;
local_b = b;
print(local_a + local_b + "\n");

An allowed execution is:
00
02
10
12

Moreover, that execution can happen on some real hardware, and it's
not because the compiler is antagonistic and makes thread 2 execute
different compiled code than thread 3 or convolutes the code. It's
because core specific caches.
http://en.wikipedia.org/wiki/Cache_coherence
It would be easiest to explain this in terms of the infamous DEC Alpha
and its split cache. For the purposes of this conversation, let's say
each core of the DEC Alpha has two caches, one for even numbered
addresses, and one for odd numbered addresses. Let's suppose that
(global) a is an odd address, and (global) b is an even address. It's
quite possible that due to earlier code executed, or perhaps from OS
swapping, or a variety of other reasons, for the core of thread 2,
(global) a is still in cache but (global) b is not. Thus, it will
reuse the cached value of a, and possibly read a new value of b,
resulting in "02". You can use the same reasoning for the core of
thread 3 to show it's possible /in the same execution/ to get "10"
from thread 3.

tl;dr Real programs on real processors can have one core see some
assembly write X but not some assembly write Y, and another core can
see assembly write Y but not assembly write X /in the same execution/.

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

#11403

On 1/17/2012 4:04 AM, raphfrk@gmail.com wrote:
> The spec says that all writes to volatiles can be considered to happen
> before all subsequent reads.  What does "subsequent" mean, is that
> with regards to real time?
>
> So,
>
> Thread 1
> int b = 0;
> volatile boolean a = false;
> ...
> ...
> b = 1;
> a = true;
>
> Thread 2
> if (a) {
>    System.out.println("The value of b is " + b);
> }
>
> Since the setting of a to true happens before the reading of a as
> true, the println must happen after b is set to 1.

Yes

> This means that either nothing will be printed or "The value of b is
> 1" will be printed.

Yes

> Does this work in reverse too?
>
> For example,
>
> 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.

Yes

> (bStore = b) happens before (read a as false)
> (read a as false) happens before (set a = true) [is this valid?]
> (set a = true) happens before (set b = 1)
>
> So, bStore = b happens before set b = 1, so bStore = 0.

Only if a is false

> Effectively, the rule would be "A read to a volatile happens before
> the write to that volatile that overwrites the value that was read".

I don't think so but I'm not really sure what you mean.

> However, that wasn't clear from the spec.  I think since read/writes
> to volatiles are synchronization actions, then when running the
> program, they can be considered to have happened in some ordering
> (consistent with program order in the threads).  As long as the
> program works no matter what the ordering is picked, then it is fine.

Not sure what you really mean here.  There is also a side effect of 
writing a volatile variable and that is that all other variable writes 
that happened before in that thread are visible to any other thread that 
subsequently reads the volatile variable.  "Locking can guarantee both 
visibility and atomicity; volatile variables can only guarantee 
visibility" Java Concurrency in Practice, Brian Goetz.  You should buy a 
copy of that book if you are going to get serious about concurrent 
programming.

-- 

Knute Johnson

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

#11404

On 1/17/2012 8:18 AM, Knute Johnson wrote:

>> Does this work in reverse too?
>>
>> For example,
>>
>> 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.
>
> Yes


I'm pretty sure Peter got the correct answer which is "no."  I want to 
stick my answers in a separate reply, so I'll just add that this is an 
easy mistake to make and if both Peter and you hadn't already provided 
some insights I probably would have flubbed it up myself.

Reasoning about synchronization can be pretty hard.  Make sure you 
consider carefully all possibilities when analyzing multi-threaded 
programs for bugs.

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

#11405

On 1/17/2012 8:33 AM, markspace wrote:
> On 1/17/2012 8:18 AM, Knute Johnson wrote:
>
>>> Does this work in reverse too?
>>>
>>> For example,
>>>
>>> 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.
>>
>> Yes
>
>
> I'm pretty sure Peter got the correct answer which is "no." I want to
> stick my answers in a separate reply, so I'll just add that this is an
> easy mistake to make and if both Peter and you hadn't already provided
> some insights I probably would have flubbed it up myself.
>
> Reasoning about synchronization can be pretty hard. Make sure you
> consider carefully all possibilities when analyzing multi-threaded
> programs for bugs.

OK, I'll bite, if a is false how can b be anything but 0?

-- 

Knute Johnson

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

#11410

On 1/17/2012 8:49 AM, Knute Johnson wrote:
> On 1/17/2012 8:33 AM, markspace wrote:
>> On 1/17/2012 8:18 AM, Knute Johnson wrote:
>>
>>>> Does this work in reverse too?
>>>>
>>>> For example,
>>>>
>>>> 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.
>>>
>>> Yes
>>
>>
>> I'm pretty sure Peter got the correct answer which is "no." I want to
>> stick my answers in a separate reply, so I'll just add that this is an
>> easy mistake to make and if both Peter and you hadn't already provided
>> some insights I probably would have flubbed it up myself.
>>
>> Reasoning about synchronization can be pretty hard. Make sure you
>> consider carefully all possibilities when analyzing multi-threaded
>> programs for bugs.
>
> OK, I'll bite, if a is false how can b be anything but 0?
>


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.

-- 

Knute Johnson

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

#11415

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

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

#11417

On 1/17/12 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).
a was volatile, so it does cause the happens-before relationships with 
the reads/writes of b.
>
> 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....
>
>
>

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

#11420

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

Thread 2
int bStore = b;      <--- DON'T MISS THIS BIT
if (!a) {
   System.out.println("The value of b is " + bStore);
}

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

#11421

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.  So, The 
original assertion that either nothing gets printed, or "The value of b 
is 0" gets printed is true.
>> 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, but if a is false, b=1 hasn't 
happened yet (since it a=true happens-before b=1).
>> if (!a) {
>>   System.out.println("The value of b is " + bStore);
>> }

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

#11424

On 1/17/2012 11:06 AM, Daniel Pitts wrote:

> On 1/17/12 10:41 AM, markspace wrote:
>> He's reading "b" first. He stores b in bStore, and then checks "a".

> He is reading b first.


Right.  "b" is not volatile.  So we can't say anything at all about the 
value of "b".  Full stop.


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


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]

Page 1 of 4  [1] 2 3 4  Next page →

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

csiph-web