[concurrency-interest] Enforcing total sync order on modern hardware

Alexander Terekhov TEREKHOV at de.ibm.com
Tue Mar 24 14:15:28 EDT 2015

again, IRIW is about write atomicity... minimal scenario for that needs
only three threads:

T1: X = 1;
T2: if (X) Y = 1;
T3: A = Y; B = X;

A == 1 && B == 0 is possible without write atomicity.

Marko Topolnik <marko at hazelcast.com> on 24.03.2015 18:44:16

To:	Oleksandr Otenko <oleksandr.otenko at oracle.com>
cc:	Alexander Terekhov/Germany/IBM at IBMDE, concurrency-interest
       <Concurrency-interest at cs.oswego.edu>
Subject:	Re: [concurrency-interest] Enforcing total sync order on modern

On Tue, Mar 24, 2015 at 3:32 PM, Oleksandr Otenko <
oleksandr.otenko at oracle.com> wrote:
      The outcome r1==0, r3==0 is disallowed through the same reasoning in
      Dekker's idiom as in IRIW: since r1==0, y=1 must not happen before
      r1=y; then r3=x, being after y=1 in program order, must also not
      precede r1=y, and transitively cannot precede x=1. You need this step
      that from "Y must not precede X" follows that "X happens-before Y" -
      but that's what makes the order total.

      In IRIW you have the same chain of reasoning. Even if you get rid of
      synchronization order, but keep synchronizes-with and transitive
      closure, then from observing r0==1 and r2==1 you still have the same
      edges. The key here still is the conclusion that since r1==0, y=1
      must not happen before r1=y, which is the only part that requires
      total ordering - cannot be partially ordered. But it is exactly the
      same bit that cannot be partially ordered in Dekker's idiom: r1=y
      happens-before y=1 because otherwise r1=y should observe 1. If you
      don't have mutual exclusion in ordering r1=y and y=1 in Dekker's
      idiom, why would the outcome r1==0, r3==0 be forbidden?

This the IRIW (1,0,1,0) result in a happens-before diagram:

T4: x=0 --> y=0 ----> r2=y --> r3=x
T3: x=0 --> y=0 --/-----> r0=x --> r1=y
                 /    /---^
T2: y=1 --------/    /
T1: x=1 -----------/

(note that I made the setting of initial values in T3 and T4 explicit)

As you can witness, there are no violations of the union of
synchronizes-with and program order ("transitive closure", even though that
term actually applies to something else). Therefore IRIW only violates
sequential consistency and does not violate what I assume under the term
"happens-before consistency".

BTW as for your earlier observation that IRIW is not minimal because Dekker
is smaller, note that the "issue of interest" for IRIW is the sequentially
inconsistent observation of mutually independent stores, as observed by
mutually independent loads. Here "mutually independent" means "done by
separate, independent threads". Clearly, IRIW is exactly the minimal
scenario for that.


More information about the Concurrency-interest mailing list