[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.
Alex
> 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