[cpp-threads] Examples of cross-thread ordering

[Herb Sutter]

I would like to understand better some parts of the Java and draft C++
memory models, in particular what they say about three examples below
that are adapted from a recent paper by Arvind and Maessen. I could try
to interpret the models myself, but for accuracy it would be very
helpful for me if you the authors of those models could say how the
rules of those models can be used to derive precise answers to the
examples. I understand that the answers may be different in the two
models.

In all example, all variables are volatile (Java) or atomic<> (C++
draft), except that variables whose names start with r are locals.


Example 1:

  // thread T1
  x = 1;	// a
  y = 2;	// b
  r1 = y;	// c

  // thread T2
  y = 3;	// d
  x = 4;	// e
  r2 = x;	// f

It is possible to have r1 == 3 and r2 == 1? How is the answer derived
from applying the rules in the Java and draft C++ memory models?


Example 2:

  // thread T1
  x = 1;	// a
  r1 = y;	// b
  r2 = y;	// c

  // thread T2
  y = 2;	// d
  z = 6;

  // thread T3
  y = 4;	// e
  r3 = z;
  x = 8;	// f
  r4 = x;	// g

If r1 == 2 and r2 == 4 (and r3 == 6), is it possible to have r4 == 1?

(I think that variable z, and therefore r3, seem to be unnecessary and
I'll write Arvind separately about that, but I include it as it appears
in the original example.)


Example 3:

  // thread T1
  x = 1;	// a
  y = 3;	// b
  r1 = y;	// c

  // thread T2
  y = 4;	// d
  r2 = x;	// e

  // thread T3
  x = 2;	// f

If r1 == 4 and r2 == 2, what if anything can we say about a
happens-before relationship between lines a and f?


Thanks,

Herb