M&S Queue
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. The dummy node technique manages both of them without double CAS.
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 element that is returned becomes the new dummy node (new head), and the preceding dummy node (old head) gets deleted.
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 is dependent on others to finish its job (possibly, in another thread).
Tagged pointers are used to deal with the ABA problem.
- https://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf
- https://habr.com/en/post/202190/
- https://habr.com/en/post/219201/
-
Libcdc:
- Source code: https://github.com/khizmax/libcds
- Doc: http://libcds.sourceforge.net/doc/cds-api/index.html
- Entry guide: https://habr.com/ru/post/196834/
- Boost: