Skip to content

M&S Queue

Jump to bottom
Mykhailo Sobko edited this page Sep 1, 2022 · 23 revisions

Implementation here

Overview

  • A Michael-Scott lock-free queue with support for blocking pops.
  • Usable with any number of producers and consumers.
  • The queue is implemented as a singly linked list with pointers to the head and tail.
  • Uses tagged pointers to avoid the ABA problem.

Dummy node

The queue is never empty (head and tail are never checked for being nullptr). To provide physical (but not logical) nonemptiness, a dummy node is added in the constructor of the queue, which is both head and tail. Consequently, during dequeue, the returned element becomes the new dummy node (new head), and the preceding dummy node (old head) gets deleted. This technique manages both head and tail without performing double CAS.

image

Helping

Another technique that is often used in lock-free programming is helping. After enqueue, we only try once to update the tail in CAS, which may fail. If this is the case, the tail is actually updated in another method that can be called from another thread. The next enqueue checks whether the tail points to the last node, and tries to swing the tail to the last node if it lags behind. The same holds for next dequeue: before doing its task, it checks tail for consistency and tries to move it to the next node if this is needed. In this way, the algorithm of a single operation is spread across all container's operations. In other words, one operation depends on others to finish its job (possibly, in another thread).

Related sources:

Other implementations:

Clone this wiki locally