# Why is happens-before order a partial order? Classic List Threaded 8 messages Open this post in threaded view
|

## Why is happens-before order a partial order?

 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.
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:
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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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           Hcould 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.AlexOn 7 Oct 2017, at 15:14, thurstonn <[hidden email]> wrote:I'm hoping for some clarification on the distinction between synchronizationorder (described as a total order over all synchronization actions) andhappens-before order (described as a partial order).  I believe it is just asemantical distinction without a difference, but I want to make sure thereisn't a subtle difference that I'm missing)Note:  I am *not* asking about the difference between synchronization orderand happens-before order, just the characterization as one as "total" andthe other as "partial".A simple program to illustrate (letters are just labels, and allinstructions are plain memory accesses unless specified; order is sourceprogram order in the usual way). For simplicity, assume that the programjust executes the 3 threads one time each (concurrently) and then exits.
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:
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 hbhb(D, E), hb(E, F) and due to transitivity hb(D, F)andhb(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, howis 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}, butwouldn't we say the same about the synchronization order, i.e. it's apartial order over {A-H} (only relating C and D)?Or is there a subtle difference, between the ordering/visibility guaranteesof 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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 allinstructions are plain memory accesses unless specified; order is sourceprogram order in the usual way). For simplicity, assume that the programjust executes the 3 threads one time each (concurrently) and then exits.
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:
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 hbhb(D, E), hb(E, F) and due to transitivity hb(D, F)andhb(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, howis 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}, butwouldn't we say the same about the synchronization order, i.e. it's apartial 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 guaranteesof 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