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

Alexander Terekhov TEREKHOV at de.ibm.com
Tue Mar 24 16:12:14 EDT 2015


"Put another way, a system may pass this test and still fail IRIW"

I don't think so, do you have a real world example?

Marko Topolnik <marko at hazelcast.com>@cs.oswego.edu on 24.03.2015 20:30:41

Sent by:	concurrency-interest-bounces at cs.oswego.edu


To:	Alexander Terekhov/Germany/IBM at IBMDE
cc:	concurrency-interest <Concurrency-interest at cs.oswego.edu>
Subject:	Re: [concurrency-interest] Enforcing total sync order on modern
       hardware


On Tue, Mar 24, 2015 at 7:15 PM, Alexander Terekhov <TEREKHOV at de.ibm.com>
wrote:
      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.

But this dispenses with the essential feature of IRIW, which is the
independency of two writes so that any other thread can receive them in
arbitrary order without breaching causality. In your example you have
second write dependent on the first, introducing a clear happens-before
edge between X = 1 and Y = 1. Put another way, a system may pass this test
and still fail IRIW. Therefore they cannot be considered equivalent.

---
Marko

      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
             hardware


      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.

      ---
      Marko


_______________________________________________
Concurrency-interest mailing list
Concurrency-interest at cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest





More information about the Concurrency-interest mailing list