循环无锁缓冲区 [英] Circular lock-free buffer

问题描述

我正在设计一个连接到一个或多个数据源流的系统，并对数据进行一些分析，而不是根据结果触发事件。在典型的多线程生产者/消费者设置中，我将有多个生产者线程将数据放入队列中，并且多个消费者线程读取数据，并且消费者仅对最新数据点加n个点感兴趣。如果慢消费者不能跟上，生产者线程将必须阻塞，当然没有未处理的更新消费者线程当然会阻塞。使用具有读取器/写入器锁定的典型并发队列将工作得很好，但是数据进来的速度可能是巨大的，所以我想减少我的锁定开销，特别是生产者的写锁。我认为一个循环的无锁缓冲区是我需要的。

I'm in the process of designing a system which connects to one or more stream of data feeds and do some analysis on the data than trigger events based on the result. In a typical multi-threaded producer/consumer setup, I will have multiple producer threads putting data into a queue, and multiple consumer threads reading the data, and the consumers are only interested in the latest data point plus n number of points. The producer threads will have to block if slow consumer can not keep up, and of course consumer threads will block when there are no unprocessed updates. Using a typical concurrent queue with reader/writer lock will work nicely but the rate of data coming in could be huge, so i wanted to reduce my locking overhead especially writer locks for the producers. I think a circular lock-free buffer is what I needed.

现在有两个问题：

1. 是否是循环无锁缓冲区的答案？

1. Is circular lock-free buffer the answer?

如果是这样，在滚动我自己之前，你知道任何公共实现， / p>

If so, before i roll my own, do you know any public implementation that will fit my need?

始终欢迎任何实现循环无锁缓冲区的指针。

Any pointers in implementing a circular lock-free buffer are always welcome.

BTW，在Linux上的C ++中执行此操作。

BTW, doing this in C++ on Linux.

一些其他信息：

响应时间对我的系统至关重要。理想情况下，消费者线程将希望尽快看到任何更新，因为额外的1毫秒的延迟可能会使系统毫无价值，或者价值更低。

The response time is critical for my system. Ideally the consumer threads will want to see any updates coming in as soon as possible because an extra 1 millisecond delay could make the system worthless, or worth a lot less.

设计理念我倾向于一个半无锁循环缓冲区，其中生产者线程将数据放入缓冲区尽可能快，让我们调用缓冲区A的头部，而不阻塞，除非缓冲区已满，当A满足缓冲器Z的结束。消费者线程将各自保持两个指向循环缓冲器的指针，P和P ，其中P是线程的本地缓冲器头，P 是P之后的第n个项。每个消费者线程一旦完成处理当前P就将提前它的P和P ，并且缓冲器指针Z的结束以最慢的P 。当P赶上A，这意味着没有更多的新更新要处理，消费者旋转和忙等待A再次前进。如果消费者线程旋转太长时间，它可以进入休眠状态并等待一个条件变量，但我可以与消费者占用CPU周期等待更新，因为这不会增加我的延迟（我会有更多的CPU核心比线程）。想象一下，你有一个圆形轨道，生产者在一群消费者面前运行，关键是调整系统，使生产者通常运行在消费者之前几步，这些操作大部分可以使用无锁技术。我理解获得执行权的细节不容易...好吧，非常努力，这就是为什么我想学习他人的错误，然后再做一些自己的。

The design idea I'm leaning toward is a semi-lock-free circular buffer where the producer thread put data in the buffer as fast as it can, let's call the head of the buffer A, without blocking unless the buffer is full, when A meets the end of buffer Z. Consumer threads will each hold two pointers to the circular buffer, P and P_n, where P is the thread's local buffer head, and P_n is nth item after P. Each consumer thread will advance its P and P_n once it finish processing current P and the end of buffer pointer Z is advanced with the slowest P_n. When P catch up to A, which means no more new update to process, the consumer spins and do busy wait for A to advance again. If consumer thread spin for too long, it can be put to sleep and wait for a condition variable, but i'm okay with consumer taking up CPU cycle waiting for update because that does not increase my latency (I'll have more CPU cores than threads). Imagine you have a circular track, and the producer is running in front of a bunch of consumers, the key is to tune the system so that the producer is usually runing just a few step ahead of the consumers, and most of these operation can be done using lock-free techniques. I understand getting the details of the implementation right is not easy...okay, very hard, that's why I want to learn from others' mistakes before making a few of my own.

推荐答案

您想要的艺术术语是无锁队列。有一个一套出色的笔记，其中包含了Ross Bencina的代码和论文链接。我最信任的工作的人是 Maurice Herlihy （对于美国人，他发音他的名字像Morris）。

The term of art for what you want is a lock-free queue. There's an excellent set of notes with links to code and papers by Ross Bencina. The guy whose work I trust the most is Maurice Herlihy (for Americans, he pronounces his first name like "Morris").

这篇关于循环无锁缓冲区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！