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

Alex Otenko oleksandr.otenko at gmail.com
Sat Oct 7 10:39:48 EDT 2017

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.


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

More information about the Concurrency-interest mailing list