Volatile happens before question

[Knute Johnson]

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]

...

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.

 

[markspace]

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.

 

[Knute Johnson]

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]

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?

 

[Lew]

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.

I'm going to go out on a limb here.

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

No. Thread 2 could observe the write 'b = 1;' prior to observing the write 'a
= true;'.

"observes" means "thread 2 observes from thread 1:".

«(observes 'a == false') implies (observes 'b = 0')».
This is clearly true because
'b = 0' /hb/ 'a = false' /hb/ if (!a) true

«(observes 'b = 1') implies (observes 'a = true')»
«(observes 'a = true') implies (observes 'b = 1')»

Neither is true. There is no /hb/ between the two writes. Thread 2 can observe
them in either order.

«(observes 'a == false') implies (!observes 'b = 1')».

There is no /hb/ between these two writes. Ergo thread 2 could view them in
either order.

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

Yes, but thread 2 does not have this /hb/ order. There is no inter-thread /hb/
that orders the writes 'a = false;', 'a = true;' and 'b = 1;'. T2 can see 'b
= 1;' prior to either write to 'a'.

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

No. T2 can observe 'b = 1;' because no promise or prevention applies to writes
that happen after the observed write to 'a'.

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

Do we disagree on this?

There is no /hb/ among the writes to 'a' and the 'b = 1;' write that T2 can
observe. T2 can see consecutive writes of zero and one to 'b' before it sees
any of the writes to 'a', or it could never see the 'b = 1;' write, or
anything in between.

 

[Steven Simpson]

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

 

[raphfrk]

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.

 

[raphfrk]

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.

 

[Knute Johnson]

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

I'm going to go out on a limb here.


No. Thread 2 could observe the write 'b = 1;' prior to observing the
write 'a = true;'.

"observes" means "thread 2 observes from thread 1:".

«(observes 'a == false') implies (observes 'b = 0')».
This is clearly true because
'b = 0' /hb/ 'a = false' /hb/ if (!a) true

«(observes 'b = 1') implies (observes 'a = true')»
«(observes 'a = true') implies (observes 'b = 1')»

Neither is true. There is no /hb/ between the two writes. Thread 2 can
observe them in either order.

«(observes 'a == false') implies (!observes 'b = 1')».

There is no /hb/ between these two writes. Ergo thread 2 could view them
in either order.


Yes, but thread 2 does not have this /hb/ order. There is no
inter-thread /hb/ that orders the writes 'a = false;', 'a = true;' and
'b = 1;'. T2 can see 'b = 1;' prior to either write to 'a'.


No. T2 can observe 'b = 1;' because no promise or prevention applies to
writes that happen after the observed write to 'a'.


There is no /hb/ among the writes to 'a' and the 'b = 1;' write that T2
can observe. T2 can see consecutive writes of zero and one to 'b' before
it sees any of the writes to 'a', or it could never see the 'b = 1;'
write, or anything in between.

I woke up at 5 this morning thinking about this and I think I agree with
you now. The more I think about this the less sense it makes. Or maybe
it's the less sense I make .

 

[markspace]

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?

Yeah, it's a trick. Or at least isn't great documentation. To figure
it out, you have to read the introduction to the AtomicInteger
documentation, which tells you that you need to read the package
documentation for "the properties of atomic variables."

In the package documentation, it eventually explains that:

"get has the memory effects of reading a volatile variable.
"set has the memory effects of writing (assigning) a volatile variable. "

So you are synchronizing here just as if you were reading and writing to
a volatile. I don't think the implementation uses volatile, I think it
uses native methods which have the same effect, but you can think of the
internal values as using a volatile to hold the atomic values.

Voila!

 

[raphfrk]

Yeah, it's a trick.

You mean yeah, it has the same problem, so won't work either?

 

[markspace]

You mean yeah, it has the same problem, so won't work either?

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

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.

(Hint: ConcurrentHashMap

<http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentHashMap.html>)

 

[raphfrk]

Looking at his code a bit more carefully, I think it has problems, but not the same one.

I would be interested in his basic locking principle.

I think it has the same problem. He is assuming that if he .gets() an
even number, then no write lock has happened.

However, that isn't guaranteed.

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

This is to handle the case where the reader reads the counter before
and after a write. It needs to be able to tell something changed.

     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.

True, he is assuming that a .get() on an unstable map won't do
anything dangerous, like cause an infinite loop.

Also, a .get() might be setup so that it makes some housekeeping
changes to the map.

(Hint: ConcurrentHashMap

<http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Concurr...>)

I was just wondering about his basic method.

 

[markspace]

I would be interested in his basic locking principle.

I think it has the same problem. He is assuming that if he .gets() an
even number, then no write lock has happened.

Well, he assumes no write is in progress. A write would have definitely
happened if writeCounter was 2, for example.

However, that isn't guaranteed.

I don't see how it isn't guaranteed. get() and set() on an
AtomicInteger create a happens-before relationship, just like a
volatile. Both the variable itself and the map should be protected on a
"good" read. I'm concerned about what happens when there's a write (a
reader could be in there too) and what happens on a "bad" read.

I didn't see where he creates/publishes writeCounter and lock. I assume
they're safely published as final instance fields somewhere. That
shouldn't be a problem.

This is to handle the case where the reader reads the counter before
and after a write. It needs to be able to tell something changed.

Good point, I realized this after I posted.

True, he is assuming that a .get() on an unstable map won't do
anything dangerous, like cause an infinite loop.

That's what I was thinking. With folks like Brian Goetz and Bartosz
saying the system can simply invent values, it's hard to analyze the
resulting code for any kind of deterministic behavior. Esp. because
Java is a step away from the machine, and I don't know exactly what sort
of operations are going to be executed.

In particular, during the write, if a reader is also present, I wonder
if the writer could "see" a bad read due to the reader present, and then
"finalize" that bad read and write it to memory. Stuff like this is
hard to analyze.

*IF* you assume that the read operation actually returns, and doesn't
throw an exception, or melt some other part of the code (like the
writer), *then* I think you can say that the update will be detected by
the reader, and the operation will be re-tried. This does seem to
eventually guarantee an uncontended read of the map, provided writes
don't happen "too frequently," which must be the case for this sort of
lock-free code, or it isn't going to work.

So, yes I think it works if you're prepared to make some assumptions
about the behavior of the JVM. However, I don't think anyone on this
list should be making those assumptions. Better safe than sorry.

I was just wondering about his basic method.

ConcurrentHashMap uses a totally different technique. It "stripes" the
map into several smaller maps, each of which has its own lock.
Therefore the chance that two threads will "collide" and need the same
lock is reduced. Striping locks is a much easier technique, easier to
analyze and very effective afaik. Java Concurrency in Practice talks
about this in some detail. It's worth checking out.

After you're done with striping, check out ConcurrentSkipListMap, and
look up some of the basic info on the skip list algorithm (Sedgewick is
good). More crazy techniques.

 

[Knute Johnson]

That's what I was thinking. With folks like Brian Goetz and Bartosz
saying the system can simply invent values, it's hard to analyze the
resulting code for any kind of deterministic behavior. Esp. because Java
is a step away from the machine, and I don't know exactly what sort of
operations are going to be executed.

I know that the JLS says that variables can have values out of thin air
but Goetz says on page 36 "When a thread reads a variable without
synchronization, it may see a stale value, but at least it sees a value
that was actually placed there by some thread rather then some random
value. This safety guarantee is called out-of-thin-air safety."

 

[raphfrk]

I don't see how it isn't guaranteed.  get() and set() on an
AtomicInteger create a happens-before relationship, just like a
volatile.

The issue is that the .get() doesn't have a happens before the next
write.

So, if the write .increments() the counter and the .get() reads the
updated value, then the .get() is guaranteed to happen after
the .increment().

However, if the .get() gets the old value then it isn't guaranteed to
happen before the increment, i.e. there is no guarantee.

 

[markspace]

However, if the .get() gets the old value then it isn't guaranteed to
happen before the increment, i.e. there is no guarantee.

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()

 

[markspace]

I know that the JLS says that variables can have values out of thin air
but Goetz says on page 36 "When a thread reads a variable without
synchronization, it may see a stale value, but at least it sees a value
that was actually placed there by some thread rather then some random
value. This safety guarantee is called out-of-thin-air safety."

That's a good find. I can't reconcile that statement with other things
I'm seeing. Since real world hardware seems to be able to produce
values out of thin air, I don't see how Java could prevent this. It
seems that one or the other statement is incorrect.