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.

Dummy node

The queue is never empty (head/tail are never checked for equality with 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.

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 dequeue checks whether the tail points to the last node, and tries to swing the tail to the last node if it lags behind.

Tagged pointers are used to deal with the ABA problem.

Back-off

Back-off strategies are used in both enqueue and dequeue operations to increase queue performance.

template<typename U> void enqueue(U&& value) {
    Backoff backoff;
    while ( true ) { 
    ... all the boring stuff ...
    ... CAS unsuccessful, the loop continues ...
    backoff(); 
    }
}

There are 2 strategies implemented as functors:

1. Yield back-off There is a set lower bound for the number of unsuccessful CAS instructions. This back-off will be executed only if the number of unsuccessful CAS's reaches that bound and will not be executed otherwise. The yield strategy is to perform std::this_thread::yield(), which switches the execution onto other threads that modify the container structure and are the reasons for the unsuccessful CAS operations in the current thread.

2. Exponential back-off After every unsuccessful CAS instruction, we perform a certain number of nop instructions, starting with a small initial value. With every unsuccessful CAS, that value increases exponentially on a given step until it reaches the upper bound.