[cpp-threads] Examples of cross-thread ordering

[Jeremy Manson]

Hi Herb,

Herb Sutter wrote:

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

Java doesn't allow this result for volatiles.  All accesses to volatiles 
need to be in a single, total order, where each read returns the last 
write to that variable (i.e., sequentially consistent).  This is not 
such a result.


> 
> 
> 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 don't see how; it doesn't look as if there is a total order that would 
reflect that.

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


Not a lot.  If -> is the happens-before relationship, we can say a -> b 
-> c, d -> e, f -> e and d -> c.  If there is no other code creating 
happens-before relationships, then we can say that there isn't a 
happens-before relationship between the two.

This is because there are two factors at work here in Java -- a total 
order over accesses to volatiles, and the happens-before order, which is 
determined based on program order and on which volatile read sees which 
volatile write.  In the total order, line a has to occur before line f, 
because otherwise, line e wouldn't see the value 2.  This implies 
nothing for the happens-before order, though, because a and f are both 
writes.

I didn't know Arvind and Maessen were still working on this area -- the 
last I heard from them about it was 5 or 6 years ago.  Where is this 
paper located / published?

					Jeremy