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

11
votes

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).

3
c++multithreadingqueuenonblocking
Maybe this article is of interest. – Kerrek SB
I've always felt that a lockless ringbuffer best suited to back an LL-FIFO (still not sure how safe they are, busy testing some of my ideas atm). – Necrolis
@KerrekSB: I was looking for that article. Thank you – Seb
@KerrekSB: After reading that article I had a few questions maybe you could clear up. This mentions the use of critical sections and spin locks so in general this still uses a type of lock. In this case do we have to have a lock? Is there, at the moment no safe lock less multi producer/consumer algorithm? – Seb
@Seb: The "lock" in question is only a local one that protects one very short operation, namely the update of two pointers. Spinning is not a problem in this case, as you won't be spinning for very long, and a busy wait may well be faster than any other sort of lock that would trigger a context switch. You cannot do without some sort of synchronization, and since there isn't in general an atomic hardware primitive for what the critical section does, the spinlock is an appropriate solution... – Kerrek SB

3 Answers

5
votes

Beware of the evil : ABA problem.

You can start reading this, this, and this.

0
votes

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;
    };
};
0
votes

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.