[concurrency-interest] Ordering Question

Alex Otenko oleksandr.otenko at gmail.com
Wed Jul 20 05:48:24 EDT 2016


> 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.



Since hb for putOrdered/laziSet aren’t specified in JMM, can you show which happens-before is brought by release-acquire here? (Or in general which ones are introduced? I have an idea what that might relate to, but need a rubber-stamped statement)


Alex


> On 20 Jul 2016, at 10:14, Aleksey Shipilev <aleksey.shipilev at oracle.com> wrote:
> 
> 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
> 
> 
> _______________________________________________
> 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