Ordering Question

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Ordering Question

Michael Barker-4
Hi,

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?

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

Regards,
Michael Barker. 

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Ordering Question

Vitaly Davidovich
Yes to both of your questions.  As you suspect, you need a storeLoad between 1) and 2), and that's what a volatile write would give you.

On Tuesday, July 19, 2016, Michael Barker <[hidden email]> wrote:
Hi,

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?

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

Regards,
Michael Barker. 


--
Sent from my phone

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Ordering Question

Gil Tene-2
In reply to this post by Michael Barker-4
Not an authoritative answer Mike, but:

1. Since (to my understanding) the effective StoreStore-fence-like behavior of lazySet/putOrdered occurs *before* the store to X below, and not after it, it has no effect (different from a regular store) on ordering in the sequence.

2. The a volatile read does not prevent previous stores from being reordered past it.

As a result of these two observations, T1 can validly be reordered to:

T1:
1) B = Y (volatile read)
2) X = 1 (lazySet/putOrdered)

Which would then make the result you ask about quite possible:

T1 T2

                Y = 1
B = Y
                A = X
X = 1


[Note that even if the StoreStore-like-fence behavior was after the store (which I believe isn't the case), the reordering above would be valid, since it would still not prevent crossing the volatile read]

— Gil.

> On Jul 19, 2016, at 7:11 PM, Michael Barker <[hidden email]> wrote:
>
> Hi,
>
> 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?
>
> My current suspicion is that it is, due to 1) and 2) being reordered.  If so, can the final state of A=1, B=0 be prevented by strengthening 1) to be a volatile store?
>
> Regards,
> Michael Barker.
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

signature.asc (859 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Ordering Question

Vitaly Davidovich


On Tuesday, July 19, 2016, Gil Tene <[hidden email]> wrote:
Not an authoritative answer Mike, but:

1. Since (to my understanding) the effective StoreStore-fence-like behavior of lazySet/putOrdered occurs *before* the store to X below, and not after it, it has no effect (different from a regular store) on ordering in the sequence.
Yes, the storestore is before the store to X; if it was after, it would defeat its purpose.  But as you say below, the placement of the storestore doesn't matter in terms of preventing the volatile load from moving above it - you need a storeLoad in between 1) and 2).

2. The a volatile read does not prevent previous stores from being reordered past it.

As a result of these two observations, T1 can validly be reordered to:

T1:
1) B = Y (volatile read)
2) X = 1 (lazySet/putOrdered)

Which would then make the result you ask about quite possible:

T1              T2

                Y = 1
B = Y
                A = X
X = 1


[Note that even if the StoreStore-like-fence behavior was after the store (which I believe isn't the case), the reordering above would be valid, since it would still not prevent crossing the volatile read] 

— Gil.

> On Jul 19, 2016, at 7:11 PM, Michael Barker <<a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;mikeb01@gmail.com&#39;)">mikeb01@...> wrote:
>
> Hi,
>
> 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?
>
> My current suspicion is that it is, due to 1) and 2) being reordered.  If so, can the final state of A=1, B=0 be prevented by strengthening 1) to be a volatile store?
>
> Regards,
> Michael Barker.
> _______________________________________________
> Concurrency-interest mailing list
> <a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;Concurrency-interest@cs.oswego.edu&#39;)">Concurrency-interest@...
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest



--
Sent from my phone

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Ordering Question

Justin Sampson
In reply to this post by Michael Barker-4

Hi Michael,

 

I'm confused by the question. If T2 runs completely after T1, you get A=1 and B=0 without any reordering whatsoever. The only outcome that is impossible without reordering is A=0 and B=0. Is that the case you're asking about?

 

Cheers,

Justin

 

 

From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Michael Barker
Sent: Tuesday, July 19, 2016 7:11 PM
To: concurrency-interest
Subject: [concurrency-interest] Ordering Question

 

Hi,

 

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?

 

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

 

Regards,

Michael Barker. 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Ordering Question

Michael Barker-4
Hi Justin,

Good spot, I did mean A = 0, B= 0.

Mike.

On 20 July 2016 at 17:19, Justin Sampson <[hidden email]> wrote:

Hi Michael,

 

I'm confused by the question. If T2 runs completely after T1, you get A=1 and B=0 without any reordering whatsoever. The only outcome that is impossible without reordering is A=0 and B=0. Is that the case you're asking about?

 

Cheers,

Justin

 

 

From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Michael Barker
Sent: Tuesday, July 19, 2016 7:11 PM
To: concurrency-interest
Subject: [concurrency-interest] Ordering Question

 

Hi,

 

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?

 

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

 

Regards,

Michael Barker. 



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Ordering Question

Aleksey Shipilev-2
In reply to this post by Michael Barker-4
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
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Ordering Question

Alex Otenko
> 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 <[hidden email]> 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
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Ordering Question

Aleksey Shipilev-2
On 07/20/2016 12:48 PM, Alex Otenko wrote:

>> 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)
putOrdered/lazySet/release are not defined in JMM, so there is no
possibility for a rubber-stamped statement. I am using the closest
interpretation that is consistent with it's effect I can come by:
release-acquire brings happens-before, but not synchronization order.

See e.g. here:
  http://cs.oswego.edu/pipermail/concurrency-interest/2016-March/015037.html
  http://cs.oswego.edu/pipermail/concurrency-interest/2016-May/015104.html

Thanks,
-Aleksey


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Ordering Question

thurstonn
In reply to this post by Aleksey Shipilev-2
Is it necessary that the two int instance variables (a, b) are declared volatile in those tests that only access them through their respective VarHandles?

Maybe prevents stack allocation?
Reply | Threaded
Open this post in threaded view
|

Re: Ordering Question

Aleksey Shipilev-2
On 07/21/2016 09:32 AM, thurstonn wrote:
> Is it necessary that the two int instance variables (a, b) are declared
> volatile in those tests that only access them through their respective
> VarHandles?

No, it's not necessary.

-Aleksey



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Ordering Question

Justin Sampson
In reply to this post by Aleksey Shipilev-2
This is a recurring question -- there was a thread 2 years ago about it:

http://cs.oswego.edu/pipermail/concurrency-interest/2014-September/#12929

This was my contribution:

"My own _guess_ based on the docs is that a full-volatile write ensures a
happens-before relation with _all_ subsequent volatile reads of the same
field, whereas a lazy/ordered write ensures a happens-before relation
with any subsequent volatile read _that sees the value written_ by that
write.  Therefore lazy writes guarantee, for example, safe publication
of objects, without actually forcing everything immediately out to main
memory.  But all bets are off, of course, if the read itself is not a
volatile read."

Cheers,
Justin


-----Original Message-----
From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Aleksey Shipilev
Sent: Wednesday, July 20, 2016 2:56 AM
To: Alex Otenko
Cc: concurrency-interest
Subject: Re: [concurrency-interest] Ordering Question

On 07/20/2016 12:48 PM, Alex Otenko wrote:

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

putOrdered/lazySet/release are not defined in JMM, so there is no
possibility for a rubber-stamped statement. I am using the closest
interpretation that is consistent with it's effect I can come by:
release-acquire brings happens-before, but not synchronization order.

See e.g. here:
  http://cs.oswego.edu/pipermail/concurrency-interest/2016-March/015037.html
  http://cs.oswego.edu/pipermail/concurrency-interest/2016-May/015104.html

Thanks,
-Aleksey

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest