Re: [boost] [lockfree] review

Subject: Re: [boost] [lockfree] review
From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2011-09-01 07:04:16

Hans Boehm wrote:

[... RMW/store-load barrier free (on fast path) release for lock with a
queue  ...]

> Interestingly, there is a 2011 POPL paper by Attiya et al that proves, IIRC,
> that store-load ordering or atomic RMW operations are unavoidable in some
> cases.  I haven't looked into this enough to understand how to reconcile that
> with the above result.  The kind of scheduler hack needed in step 6 above is
> probably outside their model.

http://infoscience.epfl.ch/record/161286/files/popl168gf-attiya.pdf
(Laws of Order: Expensive Synchronization in Concurrent Algorithms
Cannot be Eliminated)

Nice title. ;-)

I think they are talking about impossibility of RMW/store-load barrier
free lock acquisition.

RMW/store-load barrier free (on fast path) release for queued lock is
out of scope of their paper, AFAICS.

regards,
alexander.