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

Aleksey Shipilev aleksey.shipilev at oracle.com
Sun Mar 27 06:42:39 EDT 2016


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 --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: OpenPGP digital signature
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160327/390d8a8a/attachment.bin>


More information about the Concurrency-interest mailing list