[concurrency-interest] Can ordered store be reordered with subsequent volatile load?

Vladimir Ozerov ppozerov at gmail.com
Wed Mar 30 15:37:35 EDT 2016


Aleksey,

> My personal rule of thumb is that acq/rel is okay in producer/consumer
> scenarios where you can get away with only partial ordering. But in
> locks, where you want to reason about multiple threads communicating in
> both directions, you nominally need full SC, and the correctness of any
> relaxation should be rigorously proved.

True. Though, it looks like relaxed store could still be a viable option
for unlock routine in some very specific cases.
Thanks for explanation.

Vladimir.

2016-03-27 13:42 GMT+03:00 Aleksey Shipilev <aleksey.shipilev at oracle.com>:

> On 03/27/2016 12:32 AM, Vladimir Ozerov wrote:
> > I am trying to wrap my head around the following problem. Consider we
> > have a kind of lightweight locking algorithm between two threads which
> > somewhat resembles classical Peterson's lock. One thread declares intent
> > to acquire a lock and then checks whether state of another thread allows
> it.
> >
> > The question is: provided very subtle "putOrdered" semantics and no data
> > dependency between "a" and "b", do I have any guarantees that store and
> > load will not be reordered in the code below?
>
> No, you don't have these guarantees. acquire/release-es (putOrdered is a
> release in disguise) are not sequentially consistent.
>
> In other words, you cannot freely change volatiles to acquire/releases
> and hope it does not break code. Famous example: replace volatiles with
> acq/rel in IRIW. I think Dekker/Peterson locks require the same
> guarantees that IRIW validates.
>
> > int a, b;
> >
> > boolean tryLock() {
> >     UNSAFE.putOrdered(a, 1); // Declare intent.
> >
> >     // No StoreLoad here as store is not volatile.
> >
> >     if (UNSAFE.getVolatile(b) == 1)) {
> >         // Reset intent and return false;
> >     }
> >
> >     return true;
> > }
>
> Even in the naive barrier interpretation that usually gives stronger
> answers, you have:
>
>  [LoadStore|StoreStore]
>  a = 1;
>
>  r1 = b;
>  [LoadLoad|LoadStore]
>
> Oops.
>
> > My hope is that ordering could be enforced by the fact that both
> > store and load in this example are synchronization actions
>
> Acq/rels are weird in the way they effectively induce synchronizes-with,
> but have limited ties in total synchronization order. (This is at odds
> with JMM spec as stated, and there is no easy way out: either you relax
> SW is-suborder-of SO, and allow acq/rel in SW; or you push acq/rel into
> SO and by extension into SW, effectively making them indistinguishable
> from volatiles).
>
> My personal rule of thumb is that acq/rel is okay in producer/consumer
> scenarios where you can get away with only partial ordering. But in
> locks, where you want to reason about multiple threads communicating in
> both directions, you nominally need full SC, and the correctness of any
> relaxation should be rigorously proved.
>
> Thanks,
> -Aleksey
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160330/0eacf30c/attachment.html>


More information about the Concurrency-interest mailing list