M&S Queue
Implementation here
- 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.
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.
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).
- Concurrent Queue Algorithms: https://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf
- Lock-free queues: https://habr.com/en/post/219201/
- Libcdc:
- Boost: