Why is happens-before order a partial order?

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Why is happens-before order a partial order?

thurstonn
I'm hoping for some clarification on the distinction between synchronization
order (described as a total order over all synchronization actions) and
happens-before order (described as a partial order).  I believe it is just a
semantical distinction without a difference, but I want to make sure there
isn't a subtle difference that I'm missing)
Note:  I am *not* asking about the difference between synchronization order
and happens-before order, just the characterization as one as "total" and
the other as "partial".

A simple program to illustrate (letters are just labels, and all
instructions are plain memory accesses unless specified; order is source
program order in the usual way). For simplicity, assume that the program
just executes the 3 threads one time each (concurrently) and then exits.
<pre>
volatile int x;

Thread 1:                                    Thread 2:                                            
Thread 3:
A:                                              D:  r1 = x // volatile read
"sees" 10              G:
B:                                              E:                                                        
H:  
C: x = 10 //volatile write                F:
</pre>

Ok, so the synchronization order is (C < D), i.e. over {C, D}
Given the rules of  JLS 17.4.5. Happens-before Order,
we have:
hb(A, B), hb(B, C) and due to transitivity hb(A, C)
hb(C, D) all synchronizes-with relations are also hb
hb(D, E), hb(E, F) and due to transitivity hb(D, F)
and
hb(G, H)

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

Or is there a subtle difference, between the ordering/visibility guarantees
of SO C < D, than the {A-F} happens before order?





--
Sent from: http://jsr166-concurrency.10961.n7.nabble.com/
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why is happens-before order a partial order?

thurstonn
Drat. I can't seem to format the example "program" appropriately, (I use nabble to post) - it looked fine in the preview.
volatile int x;

Thread 1:                                    Thread 2:                                              Thread 3:
A:                                              D:  r1 = x // volatile read "sees" 10              G:
B:                                              E:                                                          H:
C: x = 10 //volatile write                F:


Sent from the JSR166 Concurrency mailing list archive at Nabble.com.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why is happens-before order a partial order?

Aleksey Shipilev-3
In reply to this post by thurstonn
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


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Why is happens-before order a partial order?

thurstonn
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/
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why is happens-before order a partial order?

Alex Otenko
In reply to this post by thurstonn
A total order is also a partial order.

So (not using your example)

A -> B -> C -> D -> E
       /        \
F -> G           H

could be a representation of happens-before for two threads:

A < B < D < E is a total order (program order)

F < G < C < H is a total order (program order)

B < C < D < H is a total order (synchronization order)


Now, if B is a write, and C, D, H are reads, then all of them synchronize-with B.

Alex

On 7 Oct 2017, at 15:14, thurstonn <[hidden email]> wrote:

I'm hoping for some clarification on the distinction between synchronization
order (described as a total order over all synchronization actions) and
happens-before order (described as a partial order).  I believe it is just a
semantical distinction without a difference, but I want to make sure there
isn't a subtle difference that I'm missing)
Note:  I am *not* asking about the difference between synchronization order
and happens-before order, just the characterization as one as "total" and
the other as "partial".

A simple program to illustrate (letters are just labels, and all
instructions are plain memory accesses unless specified; order is source
program order in the usual way). For simplicity, assume that the program
just executes the 3 threads one time each (concurrently) and then exits.
<pre>
volatile int x;

Thread 1:                                    Thread 2:                                             
Thread 3:
A:                                              D:  r1 = x // volatile read
"sees" 10              G:
B:                                              E:                                                         
H:  
C: x = 10 //volatile write                F:
</pre>

Ok, so the synchronization order is (C < D), i.e. over {C, D}
Given the rules of  JLS 17.4.5. Happens-before Order,
we have:
hb(A, B), hb(B, C) and due to transitivity hb(A, C)
hb(C, D) all synchronizes-with relations are also hb
hb(D, E), hb(E, F) and due to transitivity hb(D, F)
and
hb(G, H)

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

Or is there a subtle difference, between the ordering/visibility guarantees
of SO C < D, than the {A-F} happens before order?





--
Sent from: http://jsr166-concurrency.10961.n7.nabble.com/
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why is happens-before order a partial order?

Aleksey Shipilev-3
In reply to this post by thurstonn
On 10/07/2017 04:36 PM, thurstonn wrote:
> 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?

By definition in 17.4.6, execution is the tuple that contains exactly one synchronization order, and
exactly one happens-before order, among other things. I.e. these are the orders over the set of
actions present in that execution.

But this does not say how many executions can relate to a particular program.

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

Yes, assuming no other actions are synchronization actions, except for C and D. The missing
relations to G and H forbid us from calling that partial order total.

-Aleksey




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Why is happens-before order a partial order?

Alex Otenko
In reply to this post by thurstonn
Now, about your example specifically:

On 7 Oct 2017, at 15:14, thurstonn <[hidden email]> wrote:

...A simple program to illustrate (letters are just labels, and all
instructions are plain memory accesses unless specified; order is source
program order in the usual way). For simplicity, assume that the program
just executes the 3 threads one time each (concurrently) and then exits.
<pre>
volatile int x;

Thread 1:                                    Thread 2:                                             
Thread 3:
A:                                              D:  r1 = x // volatile read
"sees" 10              G:
B:                                              E:                                                         
H:  
C: x = 10 //volatile write                F:
</pre>

Ok, so the synchronization order is (C < D), i.e. over {C, D}
Given the rules of  JLS 17.4.5. Happens-before Order,
we have:
hb(A, B), hb(B, C) and due to transitivity hb(A, C)
hb(C, D) all synchronizes-with relations are also hb
hb(D, E), hb(E, F) and due to transitivity hb(D, F)
and
hb(G, H)

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. It just happens to be a total order this time. (Every total order is also a partial order)


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, not every partial order is total. So synchronization order is required to always be total. (vs happens-before being total order in this particular execution - it won’t be in a different execution, eg D: r1 = x // volatile read “does not see” 10 is allowed. The synchronization order then is D <= C - still total; but happens-before then is no longer total, it will be partial.


Or is there a subtle difference, between the ordering/visibility guarantees
of SO C < D, than the {A-F} happens before order?

Well… the subtle difference is in the name: one has to be a total order, the other does not have to be. That is, all synchronization actions are lined up in a sequence (so the order between all reads and writes in this sequence exists - synchronizes-with can be established). All other reads and writes are not necessarily lined up in a sequence - the outcome is that you cannot tell which one is before which. This is only a model. This is a representation of the fact that the normal writes may be observed by different CPU cores in different order. (The spec is even weaker than that, and accounts for other things, too, but just to give a concrete example of what effect this model relates to)


Alex

--
Sent from: http://jsr166-concurrency.10961.n7.nabble.com/
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why is happens-before order a partial order?

thurstonn
In reply to this post by Aleksey Shipilev-3
Ok, thanks.

For those following along, it's probably covered by:

17.4.7. Well-Formed Executions
"The happens-before order is given by the transitive closure of
synchronizes-with edges and program order"







--
Sent from: http://jsr166-concurrency.10961.n7.nabble.com/
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest