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
