Wait-free MPSC and MPMC implement in D

[David Nadlinger]

On Wednesday, 9 May 2018 at 04:17:17 UTC, Shachar Shemesh wrote:
> On 09/05/18 01:09, David Nadlinger wrote:
>> The algorithm isn't wait-free (haven't thought too carefully 
>> about this, though)
>
> This mirrors a discussion I had with Maor (who originally wrote 
> it). Let's see if I bring you around the way I was brought 
> around.

Ah, and I've been taking Liran to be the originator of this fine 
piece of work up to now… ;)

> At the API level, there are two areas where the algorithm 
> *cannot* be wait free. If a consumer tries to consume from an 
> empty queue, or a producer tries to produce to a full one.

True, but some applications might favour APIs which can provide 
these guarantees by blocking instead of aggressively 
early-returning. For example, one could use a helping scheme to 
implement a MPSC queue that doesn't starve any producers even if 
the queue is close to full, or a SPMC queue that doesn't starve 
any consumers even if the queue is close to empty.

> Those two aside […] the algorithm actually is wait free.

Is it, though?

If we assume the usual definition of wait-freedom (bounded number 
of steps for each thread to make progress), then MCSPQueue.pop() 
is problematic, as any one thread could get persistently unlucky 
with the cas(). This could also be the case in the steady state 
with a non-empty queue; for example, if the producer pushes 
elements at a rate matching that at which (n - 1) of n consumer 
threads pop them.

I'd need to think more carefully about the 
non-sequentially-consistent isFull() before making any statements 
about SCMPQueue.

  — David