圆形无锁缓冲 [英] 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?

如果是这样，我才推出自己的，你知道任何公开的实施，将适合我的需要？

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.

顺便说一句，在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满足缓冲Z.消费者线程月底将各持有两个指针的循环缓冲器，P和P <子> N ，其中P是线程的本地缓冲区头，P <子>ñ 是P.后的第n项每个消费者线程将推进其P和P <子> N 一旦处理完目前的P和缓冲区指针的Z到底是先进与最慢的P <子>ñ 。当P赶上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.

推荐答案

艺术为你想要的是一个无锁队列术语。这里有一个一套优秀的链接到code和论文由Ross Bencina 的笔记。这家伙的工作，我最信任的是莫里斯·赫利希（对美国人来说，他宣告他的名字，如莫里斯）。

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屋！