A Wait-Free MPMC Queue

[饶萌]

I've just created a real wait-free MPMC queue in 100+ lines of C++11 code: WFMPMC.

Appreciate it if you can help check.

Thank,

Meng

[Anthony Williams]

On 18/10/2018 09:23, 饶萌 wrote:
> I've just created a real wait-free MPMC queue in 100+ lines of C++11

> code: WFMPMC <https://github.com/MengRao/WFMPMC>.

>
> Appreciate it if you can help check.

This is not wait free. If you have two writers, and both take an index.
The writer with the lower index then gets suspended, but the writer with
the higher index completes.

Now, the next reader has to wait, because the slot it is trying to read
from isn't complete yet, even though there is ready data in another slot.

Cheers,

Anthony

[饶萌]

Thank you for the quick response.

Yes, it is an issue, and there's a solution to mitigate this risk by checking empty()/full() before getting an index.

But anyway it's not strict wait-free, I see.

Thanks,

Meng

Anthony Williams <antho...@gmail.com> 于2018年10月18日周四 下午5:02写道：

[Dmitry Vyukov]

Hi Anthony,

This sounds more like non-linerizable rather then non-wait-free.
I guess wait-free property only makes sense for _try_ push/pop
operations. TryPop won't block, but it can [falsely] return false
because a future pop appears to happen before a preceding push.
Non-linerizability may or may not be a problem depending on particular
use case.

[Anthony Williams]

On 19/10/2018 17:15, Dmitry Vyukov wrote:
> On Thu, Oct 18, 2018 at 10:02 AM Anthony Williams <antho...@gmail.com> wrote:
>>
>> On 18/10/2018 09:23, 饶萌 wrote:
>>> I've just created a real wait-free MPMC queue in 100+ lines of C++11
>>> code: WFMPMC <https://github.com/MengRao/WFMPMC>.
>>>
>>> Appreciate it if you can help check.
>>
>> This is not wait free. If you have two writers, and both take an index.
>> The writer with the lower index then gets suspended, but the writer with
>> the higher index completes.
>>
>> Now, the next reader has to wait, because the slot it is trying to read
>> from isn't complete yet, even though there is ready data in another slot.
>
> Hi Anthony,
>
> This sounds more like non-linerizable rather then non-wait-free.

For something to be wait-free, you can suspend any subset of threads
indefinitely and all other threads will proceed OK.

In this case, if a thread is suspended mid-insert then other threads
will be unable to proceed, even when there is meaningful work to be done.

Cheers,

Anthony

[Dmitry Vyukov]

You are right!
But non-linearazible too.