Re: [boost] [lockfree] review

Subject: Re: [boost] [lockfree] review
From: Hans Boehm (Hans.Boehm_at_[hidden])
Date: 2011-08-30 18:58:26

Alexander Terekhov <terekhov <at> web.de> writes:

> 
> 
> Hans Boehm wrote:
> [...]
> > > > plus a number of real lock-free algorithms (which do matter) don't
> > > > work.
> 
> I'm really interested to know the exact number/names of algorithms.
I asked Doug Lea this question 3 or 4 years ago when this was still being 
actively discussed.  He's more of an expert on practical concurrent 
algorithms.  I got back a bunch of answers.  One simple and common example is 
the algorithm for releasing a queued lock.  I need to set the lock state to 
unlocked and then check the queue for waiters.  If those are reordered, I get 
lost wakeup problems.  His assessment was that such cases are surprisingly 
common, though there are clearly also a bunch of scenarios, like lazy 
initialization via double-checked locking, for which acquire-release atomics 
suffice.

> 
> [... "based on Dekker's example" ...]
> 
> Yes, acquire/release is free from implicit store-load barrier (same as
> with TSO and even IBM 370).
> 
> Note that computer hardware vendors never provided and still do not
> provide implicit store-load barrier for hardware.
Note that we're not actually requiring a full store-load barrier in the 
implementation.  We only need a barrier that orders atomic stores and atomic 
loads, which could perhaps be appreciably cheaper, though on current 
architectures it isn't.
> 
> In this respect I really like "Figure 8":
> 
> http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf
> (Figure 8: Simple categorization of relaxed models. ...)
The situation is really quite different when you're talking about 1995 
hardware ISAs as opposed to programming languages like C++.  At the 1995 
hardware level, you can no longer distinguish data and synchronization 
accesses, so you would also add the overhead to data accesses.  And whatever 
you promise is unlikely to be visible to the programmer anyway, since compiler 
reordering is likely to invalidate whatever properties you tried to guarantee 
at the hardware level.  Providing full sequential consistency at the hardware 
level without compiler changes is likely to buy you essentially nothing, and 
do so at significant expense either in hardware complexity and/or performance.

For what it's worth, Sarita Adve is both an author of the report you cite and 
the original and perhaps strongest advocate for the "sequential consistency 
for data-race-free programs" programming model.

> 
> Why the heck is C++'s default mode for atomics so special in this
> respect? 
At the programming language level, this isn't at all unique.  I believe Ada 83 
atomic accesses were sequentially consistent.  Certainly Java volatiles are.

> 
> regards,
> alexander.
>