unpark/park memory visibility

classic Classic list List threaded Threaded
155 messages Options
1234 ... 8
Reply | Threaded
Open this post in threaded view
|

unpark/park memory visibility

thurstonn
Hello,

Does an unpark(...)/(return from) park() pair constitute an happens-before edge?

Looking at the javadoc there isn't the expected "has memory visibility effects of . . ." comment, but I guess I just always assumed it does.
Reply | Threaded
Open this post in threaded view
|

Re: unpark/park memory visibility

oleksandr otenko
No. You may consider them no-ops with no loss of generality.

In practice, though, unpark will have a full barrier, and both will
behave like full compiler barriers.

Alex

On 08/01/2015 18:59, thurstonn wrote:

> Hello,
>
> Does an unpark(...)/(return from) park() pair constitute an happens-before
> edge?
>
> Looking at the javadoc there isn't the expected "has memory visibility
> effects of . . ." comment, but I guess I just always assumed it does.
>
>
>
> --
> View this message in context: http://jsr166-concurrency.10961.n7.nabble.com/unpark-park-memory-visibility-tp11812.html
> Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
> _______________________________________________
> 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: unpark/park memory visibility

Chris Vest
In different terms, park() is allowed to return spuriously, that is, for no apparent reason. So you should always check that your expected condition for unparking was met. This check usually implies the ordering guarantees one needs, though the onus is on the programmer to ensure this.

Chris

> On 08/01/2015, at 20.31, Oleksandr Otenko <[hidden email]> wrote:
>
> No. You may consider them no-ops with no loss of generality.
>
> In practice, though, unpark will have a full barrier, and both will behave like full compiler barriers.
>
> Alex
>
>> On 08/01/2015 18:59, thurstonn wrote:
>> Hello,
>>
>> Does an unpark(...)/(return from) park() pair constitute an happens-before
>> edge?
>>
>> Looking at the javadoc there isn't the expected "has memory visibility
>> effects of . . ." comment, but I guess I just always assumed it does.
>>
>>
>>
>> --
>> View this message in context: http://jsr166-concurrency.10961.n7.nabble.com/unpark-park-memory-visibility-tp11812.html
>> Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
>> _______________________________________________
>> 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

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

Re: unpark/park memory visibility

oleksandr otenko
Yes. Let's also take this opportunity to remind ourselves that wait()
can also return spuriously, so park() is no different in this respect.

Alex

On 08/01/2015 21:31, Chris Vest wrote:

> In different terms, park() is allowed to return spuriously, that is, for no apparent reason. So you should always check that your expected condition for unparking was met. This check usually implies the ordering guarantees one needs, though the onus is on the programmer to ensure this.
>
> Chris
>
>> On 08/01/2015, at 20.31, Oleksandr Otenko <[hidden email]> wrote:
>>
>> No. You may consider them no-ops with no loss of generality.
>>
>> In practice, though, unpark will have a full barrier, and both will behave like full compiler barriers.
>>
>> Alex
>>
>>> On 08/01/2015 18:59, thurstonn wrote:
>>> Hello,
>>>
>>> Does an unpark(...)/(return from) park() pair constitute an happens-before
>>> edge?
>>>
>>> Looking at the javadoc there isn't the expected "has memory visibility
>>> effects of . . ." comment, but I guess I just always assumed it does.
>>>
>>>
>>>
>>> --
>>> View this message in context: http://jsr166-concurrency.10961.n7.nabble.com/unpark-park-memory-visibility-tp11812.html
>>> Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
>>> _______________________________________________
>>> 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

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

Re: unpark/park memory visibility

Yechiel Feffer
Reply | Threaded
Open this post in threaded view
|

Re: unpark/park memory visibility

David Holmes-6
Reply | Threaded
Open this post in threaded view
|

Re: unpark/park memory visibility

oleksandr otenko
In reply to this post by Yechiel Feffer
Reply | Threaded
Open this post in threaded view
|

Re: unpark/park memory visibility

thurstonn
In reply to this post by oleksandr otenko
smacks a bit like no means yes.

It does bring up an interesting question:  why is the "intrinsic" happens-before rule list as it is?
Other than monitors and volatiles, of course.
Is the logic something like: any known/possible/reasonable implementation is necessarily going to provide the memory model guarantees, or is it the semantics that drive it?

Take thread interruption - largely analogous to (un)park (except for the spurious de-parks), and I would guess largely similar implementations (?).  So why would interrupts provide hb, and not park?
I wonder if AQS, e.g., would have been implemented slightly differently if the hb guarantee was there
Reply | Threaded
Open this post in threaded view
|

Re: unpark/park memory visibility

David Holmes-6
In reply to this post by oleksandr otenko
Reply | Threaded
Open this post in threaded view
|

Re: unpark/park memory visibility

David Holmes-6
In reply to this post by thurstonn
Interruption is a top-level Thread API so it was decided not unreasonable to
have it behave as-if there were a "volatile boolean interrupted" field in
Thread. Hence the HB relation.

Park/unpark is the lowest-level of API and in 99.99% of cases will be used
in conjunction with volatile state variables, which provide the HB
relations. It would have been an excessive burden to require HB for the
unpark/park themselves.

David

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of
> thurstonn
> Sent: Saturday, 10 January 2015 4:06 AM
> To: [hidden email]
> Subject: Re: [concurrency-interest] unpark/park memory visibility
>
>
> smacks a bit like no means yes.
>
> It does bring up an interesting question:  why is the "intrinsic"
> happens-before rule list as it is?
> Other than monitors and volatiles, of course.
> Is the logic something like: any known/possible/reasonable
> implementation is
> necessarily going to provide the memory model guarantees, or is it the
> semantics that drive it?
>
> Take thread interruption - largely analogous to (un)park (except for the
> spurious de-parks), and I would guess largely similar
> implementations (?).
> So why would interrupts provide hb, and not park?
> I wonder if AQS, e.g., would have been implemented slightly differently if
> the hb guarantee was there
>
>
>
> --
> View this message in context:
http://jsr166-concurrency.10961.n7.nabble.com/unpark-park-memory-visibility-
tp11812p11819.html
Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
_______________________________________________
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: unpark/park memory visibility

Nathan Reynolds-2
In reply to this post by oleksandr otenko
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: unpark/park memory visibility

thurstonn
In reply to this post by David Holmes-6
David Holmes-6 wrote
Interruption is a top-level Thread API so it was decided not unreasonable to
have it behave as-if there were a "volatile boolean interrupted" field in
Thread. Hence the HB relation.

Park/unpark is the lowest-level of API and in 99.99% of cases will be used
in conjunction with volatile state variables
, which provide the HB
relations. It would have been an excessive burden to require HB for the
unpark/park themselves.

David
Thanks.
Just so I understand, you mean **user-level code** will pair unparks/parks with volatile variables, right?
Reply | Threaded
Open this post in threaded view
|

Re: unpark/park memory visibility

David Holmes-6
Not sure what you mean by "user-level" - it's all Java code. park/unpark are
low-level API's only normally used via higher-level concurrency abstractions
which also contain the volatile state variable(s) - eg
AbstractQueuedSynchronizer etc.

David

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of
> thurstonn
> Sent: Sunday, 11 January 2015 7:24 AM
> To: [hidden email]
> Subject: Re: [concurrency-interest] unpark/park memory visibility
>
>
> David Holmes-6 wrote
> > Interruption is a top-level Thread API so it was decided not
> unreasonable
> > to
> > have it behave as-if there were a "volatile boolean
> interrupted" field in
> > Thread. Hence the HB relation.
> >
> > Park/unpark is the lowest-level of API and in
> *
> > 99.99% of cases will be used
> > in conjunction with volatile state variables
> *
> > , which provide the HB
> > relations. It would have been an excessive burden to require HB for the
> > unpark/park themselves.
> >
> > David
>
> Thanks.
> Just so I understand, you mean **user-level code** will pair unparks/parks
> with volatile variables, right?
>
>
>
> --
> View this message in context:
http://jsr166-concurrency.10961.n7.nabble.com/unpark-park-memory-visibility-
tp11812p11842.html
Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
_______________________________________________
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: unpark/park memory visibility

thurstonn
So I think we're talking about the same thing.
I was using 'User-level' (AQS is userlevel) in contradistinction to the native implementation of Unsafe.(un)park ('JVM-level').

Here's an (very artificial) example that appears problematical:

Original source:
volatile boolean signal = false //global
T1:
for (int loops = 0; loops < 1 and ! signal; loops++)
{
        park();

}

T2:
signal = true;
unpark(T1);

now, without any guarantees of unpark/depark hb (or knowledge of its implementation), the following hypothetical history would be valid under the JMM:

T1: r1 = 0; //loops = 0
T1: r2 = signal (false)
T1: r1 < 1 && ! r2
T1: park() //blocks

T2: unpark(T1) // can be reordered before volatile write
T1: depark // return from park()
T1: r1 = r1 + 1 //++
T1: exit loop // r1 >= 1
T2: signal = true

The original source is in line with (un)park recommended use (paired with a volatile read/write), but it allows an unexpected/unreasonable history.

If unpark/depark were hb, such a history would be impossible and #signal need not even be volatile (piggybacking on the hb) - although I'm not sure that would have any efficiency benefit




Reply | Threaded
Open this post in threaded view
|

Re: unpark/park memory visibility

David Holmes-6
Happens-before establishes inter-thread orderings, what you are concerned
about here is the intra-thread ordering: can a volatile write followed by
unpark() be reordered? Intra-thread semantics are governed by program order:
everything is supposed to execute in program order as per the semantics of
the instructions being executed - unless the compiler can determine that a
reordering can be done without affecting any semantics. When it comes to
function calls compilers generally don't know if they can reorder so they
don't. But in general if you had a very smart compiler there would have to
be something about the call to unpark that told it that it could not be
reordered with the volatile write (or put another way there will always be a
limit on what the compiler can determine about the semantics of the call).

David


> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of
> thurstonn
> Sent: Sunday, 11 January 2015 9:29 AM
> To: [hidden email]
> Subject: Re: [concurrency-interest] unpark/park memory visibility
>
>
> So I think we're talking about the same thing.
> I was using 'User-level' (AQS is userlevel) in contradistinction to the
> native implementation of Unsafe.(un)park ('JVM-level').
>
> Here's an (very artificial) example that appears problematical:
>
> Original source:
> volatile boolean signal = false //global
> T1:
> for (int loops = 0; loops < 1 and ! signal; loops++)
> {
>         park();
>
> }
>
> T2:
> signal = true;
> unpark(T1);
>
> now, without any guarantees of unpark/depark hb (or knowledge of its
> implementation), the following hypothetical history would be
> valid under the
> JMM:
>
> T1: r1 = 0; //loops = 0
> T1: r2 = signal (false)
> T1: r1 < 1 && ! r2
> T1: park() //blocks
>
> T2: unpark(T1) // can be reordered before volatile write
> T1: depark // return from park()
> T1: r1 = r1 + 1 //++
> T1: exit loop // r1 >= 1
> T2: signal = true
>
> The original source is in line with (un)park recommended use
> (paired with a
> volatile read/write), but it allows an unexpected/unreasonable history.
>
> If unpark/depark were hb, such a history would be impossible and #signal
> need not even be volatile (piggybacking on the hb) - although I'm not sure
> that would have any efficiency benefit
>
>
>
>
>
>
>
>
> --
> View this message in context:
http://jsr166-concurrency.10961.n7.nabble.com/unpark-park-memory-visibility-
tp11812p11844.html
Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
_______________________________________________
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: unpark/park memory visibility

Justin Sampson
In reply to this post by thurstonn
Thurston wrote:

> Here's an (very artificial) example that appears problematical:
>
> Original source:
> volatile boolean signal = false //global
> T1:
> for (int loops = 0; loops < 1 and ! signal; loops++)
> {
>         park();
>
> }
>
> T2:
> signal = true;
> unpark(T1);

I don't understand the significance of the for-loop here. Isn't that
equivalent to this?

T1: if (!signal) park();
T2: signal = true; unpark(T1);

Remember that park() can return spuriously. If the compiler reorders
the unpark(T1) before the signal = true, that will just appear to be
a spurious wakeup, which is in fact legal. So this example isn't
really much help in resolving the broader question.

Due to spurious wakeups, we really have to make the example more
realistic by making the loop continue indefinitely. That gives us:

T1: while (!signal) park();
T2: signal = true; unpark(T1);

(In real code we always have to check the interrupt status after
returning from park(), but let's agree to ignore that for this
analysis.)

Now it's more interesting... If nothing is reordered, T1 is
guaranteed to terminate. But if T2 is reordered, T1 could park
once, get unparked by T2, go right back around the loop to park
again, and then never be unparked.

So it really does seem like there has to be some kind of ordering
guarantee going on here for the typical park/unpark idiom to work
reliably. The javadoc for unpark() says, in part, "If the thread was
blocked on park then it will unblock. Otherwise, its next call to
park is guaranteed not to block." The very notion that there is an
identifiable "next call" seems to imply that there's some kind of
inherent ordering. Let's call it "parking order". :) So the question
is, what constraints does parking order impose on reordering of
reads and writes?

Let's say, for the sake of argument, that parking order is as strong
as happens-before order, as if unpark() were writing a volatile
field that park() is reading. Well, it turns out practically that we
can't piggyback on that happens-before edge anyway! Sticking with
the example code above, if the first time through the loop, T1 reads
the true value that T2 has written to the signal variable, T1 never
calls park() at all. If there's no park(), there's no happens-before
edge from unpark() to park(). So T1 goes on its merry way based on
having seen signal == true, but if we've declared signal to be
non-volatile, then none of T2's prior writes are guaranteed to be
visible to T1.

Therefore parking order does need to give us some guarantees about
reordering, but can actually be weaker than happens-before order
since we do always use it in conjunction with volatile state
variables. If I'm on the right track, is there a spec-worthy way to
describe those guarantees in such terms?

Cheers,
Justin

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

Re: unpark/park memory visibility

David Holmes-6
Justin writes below:
> The javadoc for unpark() says, in part, "If the thread was
> blocked on park then it will unblock. Otherwise, its next call to
> park is guaranteed not to block." The very notion that there is an
> identifiable "next call" seems to imply that there's some kind of
> inherent ordering.

It is simply referring to the fact that unpark is "sticky" - it sets the
token and unparks the thread. If the thread was not parked the token remains
sets and so next time park() is called it claims the token and returns
immediately.

David
-----

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of Justin
> Sampson
> Sent: Sunday, 11 January 2015 9:11 PM
> To: thurstonn; [hidden email]
> Subject: Re: [concurrency-interest] unpark/park memory visibility
>
>
> Thurston wrote:
>
> > Here's an (very artificial) example that appears problematical:
> >
> > Original source:
> > volatile boolean signal = false //global
> > T1:
> > for (int loops = 0; loops < 1 and ! signal; loops++)
> > {
> >         park();
> >
> > }
> >
> > T2:
> > signal = true;
> > unpark(T1);
>
> I don't understand the significance of the for-loop here. Isn't that
> equivalent to this?
>
> T1: if (!signal) park();
> T2: signal = true; unpark(T1);
>
> Remember that park() can return spuriously. If the compiler reorders
> the unpark(T1) before the signal = true, that will just appear to be
> a spurious wakeup, which is in fact legal. So this example isn't
> really much help in resolving the broader question.
>
> Due to spurious wakeups, we really have to make the example more
> realistic by making the loop continue indefinitely. That gives us:
>
> T1: while (!signal) park();
> T2: signal = true; unpark(T1);
>
> (In real code we always have to check the interrupt status after
> returning from park(), but let's agree to ignore that for this
> analysis.)
>
> Now it's more interesting... If nothing is reordered, T1 is
> guaranteed to terminate. But if T2 is reordered, T1 could park
> once, get unparked by T2, go right back around the loop to park
> again, and then never be unparked.
>
> So it really does seem like there has to be some kind of ordering
> guarantee going on here for the typical park/unpark idiom to work
> reliably. The javadoc for unpark() says, in part, "If the thread was
> blocked on park then it will unblock. Otherwise, its next call to
> park is guaranteed not to block." The very notion that there is an
> identifiable "next call" seems to imply that there's some kind of
> inherent ordering. Let's call it "parking order". :) So the question
> is, what constraints does parking order impose on reordering of
> reads and writes?
>
> Let's say, for the sake of argument, that parking order is as strong
> as happens-before order, as if unpark() were writing a volatile
> field that park() is reading. Well, it turns out practically that we
> can't piggyback on that happens-before edge anyway! Sticking with
> the example code above, if the first time through the loop, T1 reads
> the true value that T2 has written to the signal variable, T1 never
> calls park() at all. If there's no park(), there's no happens-before
> edge from unpark() to park(). So T1 goes on its merry way based on
> having seen signal == true, but if we've declared signal to be
> non-volatile, then none of T2's prior writes are guaranteed to be
> visible to T1.
>
> Therefore parking order does need to give us some guarantees about
> reordering, but can actually be weaker than happens-before order
> since we do always use it in conjunction with volatile state
> variables. If I'm on the right track, is there a spec-worthy way to
> describe those guarantees in such terms?
>
> Cheers,
> Justin
>
> _______________________________________________
> 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: unpark/park memory visibility

thurstonn
In reply to this post by David Holmes-6
Multi-thread histories are all about inter-thread semantics.
In the example history (which is valid according to the JMM), T1 can "see" the unpark() before it sees the update to signal.

Reply | Threaded
Open this post in threaded view
|

Re: unpark/park memory visibility

David Holmes-6
thurstonn writes:
>
> Multi-thread histories are all about inter-thread semantics.
> In the example history (which is valid according to the JMM), T1 can "see"
> the unpark() before it sees the update to signal.

It is only valid according to the JMM if the intra-thread reordering of the
volatile write and unpark is allowed. You can't just treat the unpark as a
simple memory access.

David

>
> --
> View this message in context:
> http://jsr166-concurrency.10961.n7.nabble.com/unpark-park-memory-v
> isibility-tp11812p11849.html
> Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
> _______________________________________________
> 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: unpark/park memory visibility

thurstonn
David Holmes-6 wrote
thurstonn writes:
>
> Multi-thread histories are all about inter-thread semantics.
> In the example history (which is valid according to the JMM), T1 can "see"
> the unpark() before it sees the update to signal.

It is only valid according to the JMM if the intra-thread reordering of the
volatile write and unpark is allowed. You can't just treat the unpark as a
simple memory access.

David

>
> --
> View this message in context:
> http://jsr166-concurrency.10961.n7.nabble.com/unpark-park-memory-v
> isibility-tp11812p11849.html
> Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
> _______________________________________________
> 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
Exactly my point; without a requirement that there is a hb(unpark, depark), a JVM implementation **theoretically** could implement (un)park in such a way, that it entails nothing but a simple memory write/read (or even no shared memory mutation at all). didn't alex describe (un) park as "semantically a no-op"?  No-ops can be reordered with anything.

I'm not saying that is practical (in fact I can't imagine how that could be done, but I don't know how real JVM's implement it now).  But the first rule of Java concurrency, is don't rely on that kind of thinking - unless there are explicit synchronization actions - intuition, etc. are *not reliable*

And so I'm just stating that the hb should be made explicit (I had assumed it implicitly all along);
If you think it through, it's very hard to imagine how developers could write bullet-proof correct concurrent code that relies on park/unpark without there being a hb(unpark, depark), which of course would invalidate the kind of histories above.

There's already an explicit "interrupt hb rule" (and a thread death rule, etc) - park fits the same pattern.

1234 ... 8