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

thurstonn thurston at nomagicsoftware.com
Sat Oct 7 10:14:46 EDT 2017

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:                                                         
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)
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/

More information about the Concurrency-interest mailing list