[concurrency-interest] Ordering Question

Aleksey Shipilev aleksey.shipilev at oracle.com
Wed Jul 20 05:14:43 EDT 2016


On 07/20/2016 05:11 AM, Michael Barker wrote:
> I have a question around ordering of events.
> 
> Given, threads (T1, T2), and variables (A, B, X, Y) where X and Y are
> shared on the heap and visible to T1 and T2.
> 
> Initially:
> 
> X = 0
> Y = 0;
> 
> T1:
> 1) X = 1 (lazySet/putOrdered)
> 2) B = Y (volatile read)
> 
> T2
> 3) Y = 1 (compare and set)
> 4) A = X (volatile read)
> 
> Is it possible to get a final state of A = 1 and B = 0?

(Later emails say the state in question is A = 0, B = 0)

> My current suspicion is that it is, due to 1) and 2) being reordered. 
> If so, can the final state of A=0, B=0 be prevented by strengthening 1)
> to be a volatile store?

Let's work backwards, and make all ops over X/Y volatile. This gives us
a nice property that all volatile ops are totally ordered by
synchronization order, and therefore either (B = Y) or (A = X) should
come last in the total order. Which automatically precludes (0, 0),
because the last read in the order has to read 1.

If X = 1 is a putOrdered/lazySet/release store, then total
synchronization order is out of the picture. It is actually hard to
reason about the acq/rel outcomes in the realm of plain JMM, but here is
a try. release-acquire brings a happens-before. Let's see if we can
construct a plausible execution that reads (0, 0) and is consistent with
JMM.

We have at least this plausible execution, which is happens-before
consistent:

 (X = 1) --hb--> (B = Y):0  // from program order
 (Y = 1) --hb--> (A = X):0  // from program order
 (X = 1)   ...   (A = X):0  // does not observe the write
 (Y = 1)   ...   (B = Y):0  // does not observe the write

Looking closer at this example, this looks like a Dekker idiom. It is
known to work with sequential consistency (volatiles):
 http://hg.openjdk.java.net/code-tools/jcstress/file/6faec60f9c90/tests-custom/src/main/java/org/openjdk/jcstress/tests/volatiles/DekkerTest.java

http://hg.openjdk.java.net/code-tools/jcstress/file/6faec60f9c90/tests-custom/src/main/java/org/openjdk/jcstress/tests/varhandles/DekkerTest.java

And breaks without sequential consistency (acq/rels):

http://hg.openjdk.java.net/code-tools/jcstress/file/6faec60f9c90/tests-custom/src/main/java/org/openjdk/jcstress/tests/varhandles/DekkerRelaxation1Test.java

http://hg.openjdk.java.net/code-tools/jcstress/file/6faec60f9c90/tests-custom/src/main/java/org/openjdk/jcstress/tests/varhandles/DekkerRelaxation2Test.java

DekkerRelaxation1Test tests produces interesting result on x86, and
DekkerRelaxation2Test produces interesting result on POWER:

      [OK] o.o.j.t.varhandles.DekkerRelaxation1Test
    (fork: #1, iteration #1, JVM args: [-server])
  Observed state   Occurrences              Expectation
            0, 0       410,875   ACCEPTABLE_INTERESTING
            0, 1    76,450,930               ACCEPTABLE
            1, 0     1,628,809               ACCEPTABLE
            1, 1       116,146               ACCEPTABLE

     [OK] o.o.j.t.varhandles.DekkerRelaxation2Test
    (fork: #1, iteration #1, JVM args: [-server])
  Observed state   Occurrences              Expectation
            0, 0        98,773   ACCEPTABLE_INTERESTING
            0, 1    19,801,809               ACCEPTABLE
            1, 0     2,593,447               ACCEPTABLE
            1, 1        47,501               ACCEPTABLE

Bottom line: (usual rant about using special non-sequentially-consistent
access modes like there is no tomorrow)

Thanks,
-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/20160720/c932cc99/attachment-0001.sig>


More information about the Concurrency-interest mailing list