[cpp-threads] Examples of cross-thread ordering

[Jeremy Manson]

Herb Sutter wrote:
> Thanks, Jeremy. I'm adding Shaz Qadeer who is interested in this and has
> some questions about JMM as well as C++MM.
> 
> Jeremy Manson wrote:
>> 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
>>>
> 
> Can you explain a little more where this total order comes from, and how
> to analyze an example like this rigorously? One of the things that
> puzzles me about the JMM specification is that it partly relies on a
> happens-before relationship and partly doesn't.

I don't know what you mean by partly doesn't.  I suspect that what is 
confusing you is that the happens-before order is partly determined by 
the total order I described, which is called the synchronization order. 
  Let's tackle happens-before and forget for the moment about the more 
confusing causality rules.

So, if you have the example above, where x and y are volatile, legal 
synchronization orders could include:

a,b,c,d,e,f
a,b,d,e,f,c
a,d,e,f,b,c
d,e,f,a,b,c

and so on and so forth.

Each volatile read must see the last volatile write in the 
synchronization order.  So if we have a,d,e,f,b,c, then f must see the 4 
written by e, and c must see the 2 written at b.

Synchronization order must reflect program order, as well.  Therefore, 
if you have b, d, c in the synchronization order, that means that you 
must also have a -> b -> d -> c.  e -> f must come after d in the 
synchronization order, so you can have:

a, b, d, e, f, c
a, b, d, e, c, f
a, b, d, c, e, f

In all of these, the read at f returns 4.

>>> 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.
> 
> Sure, that's the intuitive result, but again can I reason about that
> rigorously using happens-before? For example, can I mechanically apply
> the JMM rules to say that if r1==2 and r2==4 then d->b->e->c, and so
> because b->e therefore a->f?

Sounds right to me.  I'm sorry if I wasn't a little clearer on that point.

>>>
>>> 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.
> 
> Why is there a distinction between these two orders, and does there need
> to be? Is there a unified order one can systematically apply?
> 

Given the synchronization order, you can determine what we call the 
"synchronizes-with order".  Each volatile write "synchronizes-with" all 
subsequent volatile reads of the same variable in the synchronization 
order.  So, if we have a,d,e,f,b,c, then you have a -sw-> f, e -sw-> f, 
b -sw-> c.

The synchronizes-with order composes with program order to produce the 
happens-before order.  Note that the happens-before order is a partial 
order.  A normal (i.e., non-volatile, non-final) read can return the 
value written by any write as long as:

a) there was no intervening write to that variable in the happens-before 
order, and

b) the read does not happen-before the write.

So, let's say we have normal variable z, and volatile x:

Thread 1:
1: z = 0;
2: z = 1;
3: x = 1;

Thread 2:
4: r1 = x;
5: if (r1 == 1) {
6:   r2 = z;
7:   z = 2;
8: }

Thread 3:
9: z = 3;

Let's assume the read of z in line 6 occurs.  That means that the read 
of x in line 4 returned 1.  That means line 3 occurred before line 4 in 
the synchronization order.  We can draw a synchronizes-with arrow from 
line 3 to line 4.  So, now we know the happens-before relationships in 
this program.  Basically, all of Thread 1 happens-before all of Thread 2.

Which writes can the read at line 6 see?  All of those that meet point 
a) and b) above.  That includes the writes at lines 2 and 9.  It does 
not include the write at line 7, because that violates point b).  It 
does not include the write at line 1, because that violates point a).

This result should be reasonably intuitive, but perhaps the 
formalization of it takes a while to grasp.  I think of it in terms of a 
partial order over actions in an execution, which I think ends up being 
the most intuitive way of thinking about it once you understand it.

To answer your actual question, then, the synchronization order 
determines which values are read and written by volatile variables, 
while the happens-before order, which is determined partially by the 
synchronization order, determines the values read and written by normal 
variables.

This is all ignoring the issue of causality, but it is important to 
understand how happens-before works in the model before understanding 
causality.

Hope that helps.  It is probably as clear as mud.  I would be happy to 
clear up other questions you have.

					Jeremy