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

Alex Otenko oleksandr.otenko at gmail.com
Sat Oct 7 10:52:00 EDT 2017

Now, about your example specifically:

> On 7 Oct 2017, at 15:14, thurstonn <thurston at nomagicsoftware.com> 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)


> --
> Sent from: http://jsr166-concurrency.10961.n7.nabble.com/
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20171007/b0f1fba8/attachment.html>

More information about the Concurrency-interest mailing list