在C\C++中实现多生产者/消费者无锁队列

Question

我已经在无锁队列上的单个生产者/消费者上完成了我的基本实现,并且运行良好.但是,当我尝试将其扩展到多个生产者/消费者时,我开始遇到冲突.我通过SO发现了一个与此问题相关的类似帖子(对于多个读取或写入线程,是否存在无锁队列？)我发现一篇文章在原始实现上更进一步.我也对这篇希望得到一些指导的文章感到困惑.

第一个是这个实现在使用多个生产者/消费者时是否真的有用,或者在原始的Michael-Scott实现中缺少某些与多个生产者/消费者设置一起工作的东西.

第二个是文章" 无锁FIFO队列的乐观方法", Dequeue部分显示了虚拟值的使用.如何确定要使用的适当值？如果我使用整数,那么我会确定我为虚拟值选择的整数不是我决定排队的实际值吗？

任何建议或总体方向都会很棒.如果有人想知道我在Visual Studio中创建它以更好地理解非阻塞算法.我想尽可能地使它成为通用的,以便我可以排队所需的任何内容(队列中的数据是模板化的,因此用户可以指定要排队的内容).

Answer 1

小心邪恶:ABA问题.

你可以开始阅读这个,这个和这个.

Answer 2

您可以创建一个廉价的包装类型，以便您可以跟踪项目的有效性，并且用户可以透明地传递值而不必担心。这会产生一些小的内存开销，但如果您想允许空值入队和出队（而不是将它们视为“虚拟”哨兵），那么实际上没有更好的方法。

例子：

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