Re: [boost] boost lockfree queue.hpp - alternate implementation w/o compare_exchange

Subject: Re: [boost] boost lockfree queue.hpp - alternate implementation w/o compare_exchange
From: boost_at_[hidden]
Date: 2015-10-23 14:41:01

On 2015-10-22 03:18, Giovanni Piero Deretta wrote:
> On 22 Oct 2015 9:04 a.m., "Gavin Lambert" <gavinl_at_[hidden]> 
> wrote:
>> 
>> On 22/10/2015 20:57, Giovanni Piero Deretta wrote:
>>> 
>>> It seems to me then it is not really lock free then, right?
>> 
>> 
>> There's a difference between "lock free" and "wait free" (though I
> haven't examined the code to see which most correctly applies here).
>> 
>> Wait-free is better than lock-free, of course, but it's also 
>> incredibly
> hard to achieve in an MPMC problem.
>> 
>> 
> 
> Lock free still requires at least one thread to make progress in any
> situation. If this were the case  yield wouldn't be necessary. As I t 
> is I
> do not think it qualifies even as obstruction-free.

Assuming all threads are currently schedule, then multiple reader and 
writer threads make progress on average, and at least one reader thread 
and one writer thread will make progress.  Assuming all threads are 
scheduled, it is absolutely obstruction free, and lock free.  It is 
'mostly' wait free...  the waiting is the time it takes to increment the 
trailing edge of either back (for writers) or front (for readers).