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

Aleksey Shipilev shade at redhat.com
Sat Oct 7 10:27:02 EDT 2017


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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20171007/270df26d/attachment.sig>


More information about the Concurrency-interest mailing list