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: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2015-10-23 16:53:20

On Fri, Oct 23, 2015 at 7:41 PM,  <boost_at_[hidden]> wrote:
> 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).
>

According to your previous description, it seems to me that a writer
could be blocked forever waiting for a preempted, dead thread or
blocked thread. Similarly for a reader.