C中的任何单用户单生产者无锁队列实现?

我正在编写一个带有消费者线程和生产者线程的程序,现在看来队列同步在程序中是一个很大的开销,我找了一些无锁队列实现,但只发现了Lamport的版本和PPoPP的改进版本’ 08:

enqueue_nonblock(data) { if (NULL != buffer[head]) { return EWOULDBLOCK; } buffer[head] = data; head = NEXT(head); return 0; } dequeue_nonblock(data) { data = buffer[tail]; if (NULL == data) { return EWOULDBLOCK; } buffer[tail] = NULL; tail = NEXT(tail); return 0; } 

两个版本都需要为数据预先分配的数组,我的问题是,是否存在使用malloc()动态分配空间的任何单用户单生产者无锁队列实现?

另一个相关问题是,如何测量队列同步中的确切开销? 比如pthread_mutex_lock()需要多长时间等。

如果你担心性能,将malloc()添加到混合中将无济于事。 如果您不担心性能,为什么不通过互斥锁简单地控制对队列的访问。 您是否真的测量过这种实现的性能? 听起来好像你正在走下熟悉的过早优化路线。

您展示的算法设法工作,因为虽然两个线程共享资源(即队列),但它们以非常特殊的方式共享它。 因为只有一个线程会改变队列的头索引(生产者),并且只有一个线程每个都改变尾索引(当然是消费者),所以你不能得到共享对象的不一致状态。 生产者更新头索引之前放入实际数据并且消费者更新尾索引之前读取它想要的数据也很重要。

它的工作原理与b / c一样,数组非常静态; 两个线程都可以依赖存储元素。 您可能无法完全替换数组,但您可以做的是更改数组的用途。

即,不是将数据保存在数组中,而是使用它来保持指向数据的指针。 然后你可以使用malloc()和free()数据项,同时通过数组在线程之间传递引用(指针)。

此外,posix确实支持读取纳秒时钟,尽管实际精度取决于系统。 你可以在之前和之后读取这个高分辨率时钟并且只是减去。

是。

存在许多无锁多读者多写器队列。

迈克尔和斯科特在1996年的论文中实施了一个。

我将(经过一些更多测试)发布一个包含此队列的小型无锁数据结构库(在C中)。

你应该看看FastFlow库

我记得几年前看到一个看起来很有趣的东西,虽然我现在似乎无法找到它。 :(提出的无锁实现确实需要使用CAS原语 ,尽管即使是锁定实现(如果你不想使用CAS原语)也有相当好的性能特征—锁只能防止多个读者或者多个生产者同时进入队列,生产者仍然没有与消费者竞争。

我确实记得队列背后的基本概念是创建一个链表,其中总是有一个额外的“空”节点。 这个额外的节点意味着当列表为空时,列表的头部和尾部指针只会引用相同的数据。 我希望我能找到这篇论文,我不是用我的解释做算法正义…

啊,哈!

我发现有人在没有文章的其余部分的情况下转录了算法 。 这可能是一个有用的起点。

我使用了一个相当简单的队列实现,符合大多数标准。 它使用了一个静态最大大小的字节池,然后我们在其中实现了消息。 有一个进程可以移动的头指针,以及另一个进程将移动的尾指针。

锁仍然是必需的,但我们使用了Peterson的2处理器算法 ,它非常轻巧,因为它不涉及系统调用。 只有非常小的,有界限的区域才需要锁定:最多几个CPU周期,所以你永远不会阻塞很长时间。

我认为分配器可能是性能问题。 您可以尝试使用自定义multithreading内存分配器,它使用链接列表来维护释放的块。 如果您的块不是(几乎)相同的大小,您可以实现“伙伴系统内存分配器”,这是非常快的。 您必须将队列(环形缓冲区)与互斥锁同步。

为避免过多同步,您可以尝试在每次访问时向队列中写入/读取多个值。

如果您仍想使用无锁算法,则必须使用预先分配的数据或使用无锁分配器。 有一篇关于无锁分配器“可扩展无锁动态内存分配”和实现Streamflow的论文

在开始使用无锁的东西之前,请看: 圆形无锁缓冲区

添加malloc会消除您可能获得的任何性能提升,基于锁定的结构也同样有效。 这是因为malloc需要对堆进行某种CAS锁定,因此某些forms的malloc有自己的锁定,因此您可能会锁定内存管理器。

要使用malloc,您需要预先分配所有节点并使用另一个队列管理它们…

请注意,您可以制作某种forms的可扩展数组,如果它已展开则需要锁定。

此外,虽然互锁在CPU上是无锁定的,但它们会在指令期间放置内存锁定和块内存,并且通常会使管道停滞。

这个实现使用C ++的new和delete,它可以使用malloc和free轻松移植到C标准库:

http://www.drdobbs.com/parallel/writing-lock-free-code-a-corrected-queue/210604448?pgno=2