Volatile happens before question

[markspace]

I'm curious about the "values out of thin air" statement about hardware.
Could you give some information about how it happens?

<

>

If I understand correctly:

x & y are global integers initialized to 0. r1 and r2 are temporary
variables.

Thread 1:

int r1 = x;
y = r1;

Thread 2:

int r2 = y;
x = r2;


What happens is during the read of x, it is not found in cache. So a
bus cycle is started to read the value of x, but at the same time the
cpu has nothing to do while waiting, so it speculates as to the value of
x and continues processing. Let's say the cpu speculates that x is 42.

r1 = 42;

Now since r1 is 42, when y is written it also gets a speculative write
of the value 42;

y = 42;

This doesn't actually go on the memory bus, it's held in an output queue
of writes.

Next, Thread 2 comes along and also tries to read y. It also can't and
like thread 1 decides to speculate on the value of y while waiting for
main memory. It speculates y is 42.

r2 = 42;

Next x is written from the value of r2.

x = 42;

At this point, the internal cpu bus sees a write of 42 to the memory
location of x and thinks its speculation was correct, cancels the memory
read, and commits the value of y to memory.

That's what I understood from that talk on Vimeo. I'm starting to
wonder though exactly what sort of problem Bartosz Milewski is
describing there. I thought he was describing what could actually
happen in the absence of synchronization; possibly he is speculating on
some kind of hardware issue however.

 

[raphfrk]

If you get the old value, then no writes have occurred.  We're talking
AtomicInteger::get() here, right?  Not Map::get() or something.

Thread 1                        Thread 2
Writer                          Reader

map.put() // write
writeCounter.increment() -----> writeCounter.get() // happens before
                                 map.get()          // read

                          -----> writerCounter.get() // happens before
                                 map.get()

Yes that is correct, it is also possible that it goes:

Thread 1 Thread 2
Writer Reader

W1: map.put() // write
R1: writeCounter.get() // happens
before
R2: map.get() // read
R3: writerCounter.get() // happens
before
W2: writeCounter.increment()

So, the happens before chains are:

Thread 1:
<Start> happens before W1
W1 happens before W2

Thread 2:
<Start> happens before R1
R1 happens before R2
R2 happens before R3

Inter thread
None

So, there is no guarantee that W1 happens before R2 (and similar no
guarantee that R2 happens before W1), so they could occur at the same
time.

 

[markspace]

Yes that is correct, it is also possible that it goes:

Thread 1 Thread 2
Writer Reader

W1: map.put() // write
R1: writeCounter.get() // happens
before
R2: map.get() // read
R3: writerCounter.get() // happens
before
W2: writeCounter.increment()

That one I specifically don't see. If you get a reader and a writer
accessing the map at the same time, then the reader will detect a change
and retry the operation. There's two get's on the reader side, it might
be useful to distinguish between them.

public V get(Object key) {
int save = 0;
V value = null;
do {
while (((save = writeCounter.get()) & 1) == 1); // RA
value = map.get(key);
} while (save != writeCounter.get()); // RB
return value;
}

I'll do the same on the writer side just for clarity.

public V put(K key, V value) {
lock.lock();
try {
writeCounter.getAndIncrement(); // WA
map.put(key, value);
writeCounter.getAndIncrement(); // WB
} finally {
lock.unlock();
}
return value;
}


So here's how I parse a "failed" read.

Thread 1 Thread 2
Writer Reader

writerCounter.get() // RA
writeCounter.increment() // WA
map.put()
// 1: No happens-before here

map.get()
writerCounter.get() // RB
writerCounter.get() // RA

// 2: this repeats until...

writeCounter.increment() // WB
-----> writerCounter.get() // RA
map.get()
writerCounter.get() // RB


The ----> arrow indicates the happens-before (which is the same way the
JLS shows happens-before).

(I'm ignoring the happens-before for the writeCounter itself. That
there is such a relationship should be obvious.)

Now with the WB -> RA pair there's been happens before relationship
established and the second map.get() in the reader thread is ok.

The first map.get() is fubar but according to Patricia we should at
least expect to get back from the get call with only bad data, no other
problems. Likewise, the write should not be expected to create "out of
this air" values. If so, then the second read should be clean.

 

[raphfrk]

So here's how I parse a "failed" read.

I did a re-ordering again. This is synchronization ordering (in
theory W-write and R-read shouldn't even be included, as they are non-
volatile). From a synchronization ordering it looks like a successful
read, as both operations are separate.

Thread 1                        Thread 2
Writer                          Reader

                               writerCounter.get()  // RA
                               map.get() // R-read
                               writerCounter.get()  // RB
writeCounter.increment() // WA
map.put(); // W-write
writeCounter.increment() // WB


RB will return the safe/stable value for writeCounter, so the read
loop returns successfully on the first attempt.

RA happens-before R-read happens-before RB
WA happens-before W-write happens-before WB

However, you can't say that RB happens-before WA. Therefore, there is
no happens before path between W-write and R-read. They are
effectively concurrent.

The rule would need to be "A read from a volatile variable happens-
before the write to that volatile that overwrites the value", but that
rule isn't in the spec.

 

[markspace]

However, you can't say that RB happens-before WA. Therefore, there is
no happens before path between W-write and R-read. They are
effectively concurrent.

There doesn't need to be a happens-before here, however. It's a *read*,
and doesn't create a data race. The only thing you care about is that
writes happen-before reads.

If the reads and writes you show *actually were* executed concurrently,
it would have been caught by the RB read, like I showed in my earlier trace.

The rule would need to be "A read from a volatile variable happens-
before the write to that volatile that overwrites the value", but that
rule isn't in the spec.

Doesn't need to be. Reads don't make data races. You need an
unprotected write for that, followed by a read. There could be any
number of reads, or no reads, before the write and it won't matter.
Reads don't alter state, so there's nothing to protect.

 

[raphfrk]

There doesn't need to be a happens-before here, however.  It's a *read*,
and doesn't create a data race.  The only thing you care about is that
writes happen-before reads.

The point is that the read has to happen before the write, since the
read is checking if a write lock happened.

In reality, something like this is allowed

writeCounter.increment()
-> update stored in memory
map.put()
-> written immediately

Seeing that writeCounter is still the old value doesn't mean that
map.put hasn't been committed to memory yet.

 

[Daniel Pitts]

Looking at his code a bit more carefully, I think it has problems, but
not the same one. I guess the extra variables in his code that you're
looking at are local variables. So those are safe, they don't figure
into multi-threading concerns.

The bit that confuses me is that he "protects" his map with a write
counter:

writeCounter.getAndIncrement();
map.put(key, value);
writeCounter.getAndIncrement();

And then allows the reader(s) into the critical section whenever the
writeCounter is even (why not just decrement the counter after a write
access?).

Because the reads need to be restarted if there has been any write.
Therefore its not enough to protect with just an "is zero".

while (((save = writeCounter.get()) & 1) == 1);
value = map.get(key);

So if a reader starts "first" and passes the first test
(writeCounter==0), and then starts to access the map, and then a writer
comes in and also begins to access the map... yeah you have two threads
accessing the map at the same time. This doesn't seem to work at all.

That's why he has "save". If the write happens and then the read
attempts to read, the read needs to retry.

(Hint: ConcurrentHashMap

Agreed, if you need this behavior. On the other hand, if you are
experimenting with concurrency code, rather than trying to write
concurrent applications, then this thread is more useful than knowing
about CHM.

 

[markspace]

The point is that the read has to happen before the write, since the
read is checking if a write lock happened.

In reality, something like this is allowed

writeCounter.increment()
-> update stored in memory
map.put()
-> written immediately

I'm pretty sure that's the exact opposite of what is allowed. Remember
that AtomicInteger::increment() is documented to have the same semantics
as both reading and writing a volatile. I.e., from the perspective of a
given execution order, the write from increment() is guaranteed to
happen first. Writes and reads may not be reordered around it. I don't
think write are allowed to be interleaved with other writes this way.

Seeing that writeCounter is still the old value doesn't mean that
map.put hasn't been committed to memory yet.

It's seeing writes from the future I'm most worried about right now.
The read in the reader thread could see (perhaps) a write from the
future, the map.put(). I'm looking around for something like "a read
that happens before a a volatile read may not be reordered beyond a a
write to that same volatile."

 

[markspace]

Agreed, if you need this behavior. On the other hand, if you are
experimenting with concurrency code, rather than trying to write
concurrent applications, then this thread is more useful than knowing
about CHM.

Yes, this thread is excellent for learning stuff and making me look
stuff up and justify what I think I know about concurrency.

However, I'd like to point out that M. Bartosz Milewski says that
developing lock-free algorithms are the subject of P.h.D. dissertations
that take years of peer review before they're finally deemed correct.
There's no way I'd put any of the code on this thread into production!

Please stick to the Java API for production code, that's stuff is
already debugged! ;-)

 

[raphfrk]

I'm pretty sure that's the exact opposite of what is allowed.  Remember
that AtomicInteger::increment() is documented to have the same semantics
as both reading and writing a volatile.  I.e., from the perspective of a
given execution order, the write from increment() is guaranteed to
happen first.  Writes and reads may not be reordered around it.  I don't
think write are allowed to be interleaved with other writes this way.

However, that only applies to volatile read/writes themselves, I
think.

There has to be a happens-before chain from W-write to R-read, in the
example. Otherwise, you can't say they happen separately.

 

[Joshua Maurice]

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

 

[Joshua Maurice]

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.

Let's try it like this:
"[initial] a=false" < "[t1] a=true" < "[t1] b=1"
"[initial] b=0" < "[t1] a=true" < "[t1] b=1"
"[initial] a=false" < "[t2] bStore=b" < "[t2] test of a"
"[initial] b=0" < "[t2] bStore=b" < "[t2] test of a"

Let's consider the case that the volatile read "[t2] test of a" reads
the value of the volatile write "[t1] a=true". Then, according to the
rules for volatile, we can conclude:
"[initial] a=false" < "[t1] a=true" < "[t2] test of a"
We also know that "[t2] test of a" reads true.

On the other case, if the volatile read "[t2] test of a" does not read
the value of the volatile write "[t1] a=true", then we can conclude
nothing further about "happens-before" relationships. We do know that
"[t2] test of a" reads false.

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

You've lost me already. You cannot conclude that. There's no
transitivity to the above happens-before relationships that let you
conclude that. Specifically, you cannot conclude that:
"[t1] b=1" < "[t2] bStore=b"
and thus you have a non-volatile read and a non-volatile write that
are not ordered by happens-before, and thus you have a race condition,
and thus the read can read any write it wants (but not a "out of thin
air" value).

In short, The rule you need to know is: (Without race conditions) if a
volatile-read (acquire-read) reads the side effect, the value, of a
volatile-write (release-write), then all reads after the volatile-read
(acquire-read) see all writes before the volatile-write (release-
write) (or the reads read the values of later writes). (Of course, you
can strengthen my paraphrase, but it's a useful paraphrase.)

In your example, you have it backwards - a read X before an acquire-
read, and a write Y after a release-write. You can use the volatile
semantics to conclude anything about X and Y.

 

[Joshua Maurice]

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

You've lost me already. You cannot conclude that. There's no
transitivity to the above happens-before relationships that let you
conclude that. Specifically, you cannot conclude that:
"[t1] b=1"  <  "[t2] bStore=b"
and thus you have a non-volatile read and a non-volatile write that
are not ordered by happens-before, and thus you have a race condition,
and thus the read can read any write it wants (but not a "out of thin
air" value).

Typo. If you want to argue that the read "[t2] bStore=b" must read 0,
then you must argue that
"[t2] bStore=b" < "[t1] b=1"
which you cannot conclude either.

 

[Joshua Maurice]

In your example, you have it backwards - a read X before an acquire-
read, and a write Y after a release-write. You can use the volatile
semantics to conclude anything about X and Y.

Ack. Typos abound.
'You **can't** use the volatile semantics to conclude anything about X
and Y."

Ugg. I did do a quick review. Apparently I need to reread my stuff
better before hitting submit.

 

[markspace]

However, that only applies to volatile read/writes themselves, I
think.

There has to be a happens-before chain from W-write to R-read, in the
example. Otherwise, you can't say they happen separately.

No, and this is where a lot of folks mess up. For locks (monitors),
volatile variables, and other syncrhonization actions, there's
specifically a transitive relationship. ALL writes prior to a
synchronization action happen-before all subsequent reads.

So if you do this:

int a = 1;
int b = 2;
int volatile v = 3;

Then a, b, and v all synchronize "together" and code like this:

x = v;
y = b;
z = a;

Reads correctly when the read of v happens after the write of v. (Note
I'm specifically ignoring the case where the read of v does NOT happen
after the write of v. I think everyone agrees all bets are off in that
case.)

What you did was a little different.

y = b;
x = v;

This can't synchronize, because even when the read of v does come after
the write of v, b is still read before that, so it's value is really
free to be anything.

 

[raphfrk]

This can't synchronize, because even when the read of v does come after
the write of v, b is still read before that, so it's value is really
free to be anything.

The issue is that a read of the old value doesn't guarantee that no
update has happened.

From my example:

Thread 1 Thread 2
Writer Reader

writerCounter.get() // RA
map.get() // R-read
writerCounter.get() // RB
writeCounter.increment() // WA
map.put(); // W-write
writeCounter.increment() // WB

Even though WA happens after RB in the synchronization ordering, there
is no relationship between R-read and W-write. The reason is that WA
and RB have no happens-before relationship.

The map.put could be in progress while map.get() is in progress.

It would work if you change it to:

Thread 1 Thread 2
Writer Reader

writerCounter.get() // RA
map.get() // R-read
writerCounter.getAndAdd(0) // RB
writeCounter.increment() // WA
map.put(); // W-write
writeCounter.increment() // WB

The write component of RB then happens-before the read component of
WA.

Thus the ordering is

RA -> R-read -> RB -> WA -> W-write -> WB

Thus, R-read will be completed before W-write starts.

 

[raphfrk]

It would work if you change it to:
<remove>

An improved way of doing it was given on the concurrent-interest
mailing list.

Thread 1 Thread 2
Writer Reader

int seq = writerCounter.get() // RA
map.get() // R-read
boolean success =
writerCounter.compareAndSet(seq, seq) // RB

writeCounter.increment() // WA
map.put(); // W-write
writeCounter.increment() // WB

compareAndSet also counts as a read and a write.

 

[markspace]

The issue is that a read of the old value doesn't guarantee that no
update has happened. ....
Even though WA happens after RB in the synchronization ordering,
there is no relationship between R-read and W-write. The reason is
that WA and RB have no happens-before relationship.

I don't think this is quite correct. No update is in progress in your
trace. What I think they're talking about is causality, or the idea
that map.get() might see a write from the future. That is, a write from
the map.put(). I don't see anywhere in the JLS where it says that reads
can't be reordered across this type memory barrier.

I'll have to dig out JCIP since at this point I think trying to read the
math heavy sections of the JLS have defeated me. The read from the
future thing kinda makes sense, since I don't recall anything that
prevents it. Maybe there is though...

Note I already mentioned this about 4 posts ago... ;-)

 

[Lew]

I don't think this is quite correct. No update is in progress in your trace.

There is no happens-before between what raphfrk marked as "R-read" and
"W-write". He is quite correct.

What I think they're talking about is causality, or the idea that map.get()

No, about visibility.

might see a write from the future. That is, a write from the map.put(). I
don't see anywhere in the JLS where it says that reads can't be reordered
across this type memory barrier.

That's not different from what raphfrk said.

I'll have to dig out JCIP since at this point I think trying to read the math
heavy sections of the JLS have defeated me. The read from the future thing
kinda makes sense, since I don't recall anything that prevents it. Maybe there
is though...

Note I already mentioned this about 4 posts ago... ;-)

When there are more than one read and more than one write, you have to look at
the entire picture. Many in this conversation have made the mistake of looking
at only the first of a series of reads or writes and trying to reason about
the visible value, while ignoring later, possibly reordered actions.

Bottom line - the read from thread 2 (T2) before the write to a volatile in T1
does not impose a happens-before ("/hb/" or "<") between those two actions.
Does not. All bets are off. Done.

If the T2 read follows a different T1 write with which there is a /hb/
relationship that's a red herring.