39

I'd like to clarify how happens-before relation works with volatile variables. Let we have the following variables:

public static int i, iDst, vDst;
public static volatile int v;

and thread A:

i = 1;
v = 2;

and thread B:

vDst = v;
iDst = i;

Are the following statements correct in accordance with Java memory model (JMM)? If not, what would be correct interpretation?

  • i = 1 always happens-before v = 2
  • v = 2 happens-before vDst = v in JMM only if it's actually happens before in time
  • i = 1 happens-before iDst = i in JMM (and iDst will be predictably assigned 1) if v = 2 actually happens before vDst = v in time
  • Otherwise order between i = 1 and iDst = i is undefined and resulting value of iDst is undefined as well

Mistake in the logic:

There is no "wall clock time" concept in JMM, and we should rely on synchronization order as an ordering guide for v = 2 and vDst = v. See the chosen answer for further details.

Alexey
  • 9,197
  • 5
  • 64
  • 76
  • There is nothing to add to @manouti answer, but this question gives you another example if you need it: https://stackoverflow.com/questions/17108541/happens-before-relationships-with-volatile-fields-and-synchronized-blocks-in-jav – uraimo May 14 '15 at 20:04
  • Possible duplicate: http://stackoverflow.com/questions/11761552/detailed-semantics-of-volatile-regarding-timeliness-of-visibility – assylias May 15 '15 at 08:08

3 Answers3

20
  • i = 1 always happens-before v = 2

True. By JLS section 17.4.5,

If x and y are actions of the same thread and x comes before y in program order, then hb(x, y).

  • v = 2 happens-before vDst = v in JMM only if it's actually happens before in time
  • i = 1 happens-before iDst = i in JMM (and iDst will be predictably assigned 1) if v = 2 actually happens before vDst = v in time

False. The happens-before order does not make guarantees about things happening before each other in physical time. From the same section of the JLS,

It should be noted that the presence of a happens-before relationship between two actions does not necessarily imply that they have to take place in that order in an implementation. If the reordering produces results consistent with a legal execution, it is not illegal.

It is, however, guaranteed that v = 2 happens-before vDst = v and i = 1 happens-before iDst = i if v = 2 comes before vDst = v in the synchronization order, a total order over the synchronization actions of an execution that is often mistaken for the real-time order.

  • Otherwise order between i = 1 and iDst = i is undefined and resulting value of iDst is undefined as well

This is the case if vDst = v comes before v = 2 in the synchronization order, but actual time doesn't come into it.

user2357112
  • 260,549
  • 28
  • 431
  • 505
  • @user2357112, would it be more accurate to replace" v = 2 happens before vDst = v in the synchronization order" with "vDst = v is subsequent action for v = 2 in the synchronization order"? The spec does not have different flavors of "happens-before" (e.g. "generic" happens-before and happens-before in the synchronization order), so it might be confusing further. Otherwise, I find your answer giving most precise explanation where the inaccuracy in my answer is. – Alexey May 15 '15 at 09:39
  • @Alexey: Either phrasing would be accurate. – user2357112 May 15 '15 at 18:04
10

Yes all of them are correct according to this section about happens-before order:

  1. i = 1 always happens-before v = 2 since:

If x and y are actions of the same thread and x comes before y in program order, then hb(x, y).

  1. v = 2 happens-before vDst = v in JMM only if it's actually happens before in time, since v is volatile, and

A write to a volatile field (§8.3.1.4) happens-before every subsequent read of that field.

  1. i = 1 happens-before iDst = i in JMM (and iDst will be predictably assigned 1) if v = 2 actually happens before vDst = v in time. This is because in this case:
    • i = 1 happens-before v = 2
    • v = 2 happens-before vDst = v
    • vDst = v happens-before iDst = i

If hb(x, y) and hb(y, z), then hb(x, z).

EDIT:

As argued by @user2357112, it seems statements 2 and 3 are not accurately correct. The happens-before relationship does not necessarily impose a timing order between actions having this relationship, as mentioned in the same section of the JLS:

It should be noted that the presence of a happens-before relationship between two actions does not necessarily imply that they have to take place in that order in an implementation. If the reordering produces results consistent with a legal execution, it is not illegal.

Therefore, in terms of the rules mentioned in the JLS, we shouldn't make assumptions on the actual timing of the execution of the statements.

M A
  • 71,713
  • 13
  • 134
  • 174
  • 6
    "subsequent" is defined in terms of the synchronization order, not in terms of physical time, so I don't think 2 and 3 are entirely correct. Establishing guarantees in terms of true physical time is really hard. – user2357112 May 14 '15 at 20:05
  • 3
    @Blindy: "Happens-before" is a specifically defined term that has little to do with things physically happening before other things. Also, that "random document" is the language specification. – user2357112 May 14 '15 at 20:14
  • 1
    @Blindy http://gee.cs.oswego.edu/dl/jmm/cookbook.html shows that a volatile store as the second operation cannot be re-orderd with a normal store. You happen to be wrong when it comes to Java and volatile. – John Vint May 14 '15 at 20:15
  • @user2357112, so what "A write to a volatile field (§8.3.1.4) happens-before every subsequent read of that field." means? How to translate it from specificatish to plain English? – Alexey May 14 '15 at 20:20
  • 1
    @Alexey: If it's possible to find a chain of happens-before relations going from action A to action B, then B must see the effects of A and A can't see the effects of B. That doesn't quite capture the whole concept, but it's the best I can do under the constraints. – user2357112 May 14 '15 at 20:55
  • @Alexey the spec requires that a volatile read sees any volatile writes that have been "pushed" - but it does not require a volatile write to be "pushed" instantaneously. And it can't be due to hardware limitation (speed of light and all). So if it takes N nanoseconds for the write to be "pushed" - there is a window of N nanoseconds where the write has been "executed" but a read can see a stale value. (This is a bit simplistic but helps understand why you can't really reason in terms of wall clock time). See also: http://stackoverflow.com/questions/11761552 – assylias May 15 '15 at 08:07
6

All synchronization actions (volatile w/r, lock/unlock etc) form a total order. [1] That is a very strong statement; it makes analysis easier. For your volatile v, either read is before write, or write is before read, in this total order. The order depends on the actual execution of course.

From that total order, we can establish partial orders happens-before. [2] If all reads and writes on a variable (volatile or not) are on a partial order chain, it's easy to analyze - a read sees the immediate preceding write. That is the main point of JMM - establishing orders on read/writes so they can be reasoned like a sequential execution.

But what if the volatile read is before the volatile write? We need another crucial constraint here - the read must not see the write. [3]

Therefore, we can reason that,

  1. read of v sees either 0 (init value) or 2 (volatile write)
  2. if it sees 2, it must be the case that the read is after the write; and in that case, we have happens-before chain.

Last point - read of i must see one of the writes to i; in this example, 0 or 1. It will never see a magic value not from any writes.

quoting java8 spec:

[1] http://docs.oracle.com/javase/specs/jls/se8/html/jls-17.html#jls-17.4.4

[2] http://docs.oracle.com/javase/specs/jls/se8/html/jls-17.html#jls-17.4.5

[3] http://docs.oracle.com/javase/specs/jls/se8/html/jls-17.html#jls-17.4.7

random thoughts on the total order:

Because of this total order, we could say one sync action happens before another as if in time. That time may not correspond to wall clock, but it's not a bad mental model for our understanding. (In reality, one action in java corresponds to a storm of hardware activities, it is impossible to define a point in time for it)

And even physical time is not absolute. Remember that light travels 30cm in 1ns; on today's CPUs, temporal order is definitely relative. The total order actually requires that there is causality from one action to the next. That is a very strong requirement, and you bet that JVM tries hard to optimize it.

ZhongYu
  • 19,446
  • 5
  • 33
  • 61