Implementing a multiple producer/consumer lockless queue in C\C++

Question

I have finished my basic implementation on a single producer/consumer on a lockless queue and it runs nicely. However, when I try to expand it to a multiple producer/consumer I start to get conflicts. I found through SO a similar post related to this issue (Is there such a thing as a lockless queue for multiple read or write threads?) and I found an article that went a bit further on the original implementation. I am also confused on this article that would hope for some guidance.

The first is does this implementation really work when using multiple producers/consumers or is there something that I am missing in the original Michael-Scott implementation that works with the multiple producer/consumer setup.

The second is in the article An Optimistic Approach to Lock-Free FIFO Queues the Dequeue section shows the use of a dummy value. How can I determine what is an appropriate value to use? If I use integers what will make me certain that the integer I pick for the dummy value isn't an actual value that I decided to queue up?

Any advice or a general direction would be great. And if anyone wishes to know I am creating this in Visual Studio to get a better understanding on non-blocking algorithms. I would like to make this as universal as possible so that I can queue up anything desired (The data in the queue is templated so the user can specify what to queue).

Answer 1

Beware of the evil : ABA problem.

You can start reading this, this, and this.