[concurrency-interest] Why is happens-before order a partial order?

thurstonn thurston at nomagicsoftware.com
Sat Oct 7 10:36:17 EDT 2017

Aleksey Shipilev-3 wrote
> Reformatting the example:
> Thread 1:
>  A:
>  B:
>  C: x = 10 //volatile write
> Thread 2:
>  D: r1 = x // volatile read "sees" 10
>  E:
>  F:
> Thread 3:
>  G:
>  H:
> On 10/07/2017 04:14 PM, thurstonn wrote:
>> so summarizing, we have *over* {A-F}, A <= B <= C <= D <= E <= F. Now,
>> isn't that enumeration
>> above a "happens-before" order?  And if so, how is it not a total order
>> (over {A-F})?
> It is, but the partiality comes it when you consider any pair of actions.
> In spec language, "two
> actions can be ordered by a happens-before relationship". Notice "can",
> not "should".
> In your example, G or H  are not hb-ordered with any other action (except
> for G and H), and this is
> where partiality gets you. In fact, if synchronizes-with was not present
> between C and D, no
> inter-thread HB edges would be present at all. Of course, you can select
> the subset of actions, and
> claim totality there, but this is not the order JMM talks about.
>> Sure, it would be appropriate to say it is a partial order over the set
>> of *all* memory actions
>> {A-H}, but wouldn't we say the same about the synchronization order, i.e.
>> it's a partial order
>> over {A-H} (only relating C and D)?
> No. By definition, "A synchronization order is a total order over *all of
> the synchronization
> actions* of an execution". Notice "all synchronization actions". In your
> example only C and D are
> synchronization actions, and SO is total over them.
> -Aleksey
> _______________________________________________

Well, yes that's my understanding (as is clear from the OP).
So, just for clearing up the semantics, would it be correct to say that the
JMM is saying there is exactly *one* happens-before order (for a given
execution), just as there is only one synchronization order?

And if so, the single happens-before order of the above execution would be:
A <= B <= C <= D <= E <= F, G <= H

Sent from: http://jsr166-concurrency.10961.n7.nabble.com/

More information about the Concurrency-interest mailing list