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

Beware of the evil : ABA problem.

You can start reading this, this, and this.

You can make a cheap wrapper type so that you can keep track of validity of the items and the user can transparently pass in values without worrying about it. This incurs some small memory overhead but there's not really a better way if you want to allow enqueue and dequeue of null values (rather than treating them as "dummy" sentinels).

Example:

template<typename T>class MyQueue{    /* . . . */public:    void Enqueue(T * value)    {        MyQueueItem item;        item.value = value;        item.isValid = true;        /* enqueue it now           . . . */    }    T * Dequeue()    {        MyQueueItem validItem;        /* Get the first element where isValid == true           . . . */        return validItem.value;    }private:    struct MyQueueItem    {        T * value;        bool isValid;    };};

There's no explicit support for the atomic cpu instructions needed to implement non-blocking queues in C++ (yet, it's in the newer specs).

It's possible to access the instructions on your machine, but you'll have to either inline some assembly or find a library (TBB or maybe boost) that does it for you.