C / C ++锁免费（或非阻塞）环形缓冲区的覆盖最早的数据？ [英] C /C++ Lock-free (or nonblocking) Ring Buffer that OVERWRITES oldest data?
问题描述
我试图找到一种方法，使一个锁定免费或非阻塞的方式，使一个环形缓冲区为单次消费/单个消费者，这种情况会写最早的数据诠释缓冲区。我读了很多的工作，当你返回false如果缓冲区已满无锁算法 - 即不添加;但我找不到甚至伪code，讨论有关如何，当你需要覆盖最早的数据做到这一点。
我使用GCC 4.1.2（在工作的限制，我无法升级版本......），我有Boost库，并在过去的我做我自己的原子和LT; T>是紧随pretty到upcomming规范变量类型（它不是完美的，但它是线程安全的，做什么，我需要）。
当我想过这个问题，我想用这些原子公司确实应该照顾的问题。有些粗糙psuedo- code，以我在想什么：
模板＆LT; typename的T，unsigned int类型尺寸和GT;
类RingBuffer {
私人的：
原子和LT; unsigned int类型＆GT; readIndex;
原子和LT; unsigned int类型＆GT; writeIndex;
枚举容量{大小=};
T * BUF;unsigned int类型getNextIndex（无符号整型我）
{
返回第（i + 1）％的大小;
}上市：
RingBuffer（）{//创建一个大小的阵列中，设置readIndex = writeIndex = 0}
〜RingBuffer（）{//删除数据}
无效的农产品（常量T＆amp; T公司）
{
如果（writeIndex == getNextIndex（readIndex））// 1
{
readIndex = getNextIndex（readIndex）; // 2
}
BUF [writeIndex] = T;
writeIndex = getNextIndex（writeIndex）; // 3
}布尔消耗（T＆amp; T公司）
{
如果（readIndex == writeIndex）// 4
返回false;
T = BUF [readIndex]
readIndex = getNexIndex（readIndex）; // 5
返回true;
}};
据我所知，这里没有死锁的情况，所以我们从安全的（如果我上面的执行是错误的，甚至在其伪code LEVE，建设性的批评总是AP preciated）。
但是，大竞争条件我能找到的是：
让我们假设缓冲区已满。也就是说，writeIndex + 1 = readIndex;
（1）出现时，就如同消耗被调用。并且是真实的
（4）为假，因此我们移动从缓冲器读
（5）发生时，并且readIndex是高级酮（因此，实际上是在空间中的缓冲
（2）发生，推进readIndex AGAIN，从而失去了价值。
基本上，其writter的一个经典问题，必须修改的读者，导致竞争条件。实际上不阻断整个列表每次我访问它，我不能想到的情况发生的方式prevent这一点。我在想什么？
- 先从一个生产者/消费者多队列取得适当进展的保障。
- 如果队列已满，推会失败，弹出一个值。那么就会有空间推新值。
I'm trying to find a way to make a Lock Free OR Non-blocking way to make a Ring Buffer for single consumer / single consumer that will over-write the oldest data int the buffer. I've read a lot of lock-free algorithms that work when you "return false" if the buffer is full--ie, don't add; but I can't find even pseudo-code that talks about how to do it when you need to overwrite the oldest data.
I am using GCC 4.1.2 (restriction at work, i can't upgrade the version...) and I have the Boost libraries, and in the past I made my own Atomic< T > variable type that follows pretty closely to the upcomming specification (its not perfect, but it is thread-safe and does what i need).
When I thought about it, I figured using these atomics should really take care of the problem. some rough psuedo-code as to what i was thinking:
template< typename T , unsigned int Size>
class RingBuffer {
private:
Atomic<unsigned int> readIndex;
Atomic<unsigned int> writeIndex;
enum Capacity { size = Size };
T* buf;
unsigned int getNextIndex(unsigned int i)
{
return (i + 1 ) % size;
}
public:
RingBuffer() { //create array of size, set readIndex = writeIndex = 0 }
~RingBuffer() { //delete data }
void produce(const T& t)
{
if(writeIndex == getNextIndex(readIndex)) //1
{
readIndex = getNextIndex(readIndex); //2
}
buf[writeIndex] = t;
writeIndex = getNextIndex(writeIndex); //3
}
bool consume(T& t)
{
if(readIndex == writeIndex) //4
return false;
t = buf[readIndex];
readIndex = getNexIndex(readIndex); //5
return true;
}
};
As far as I can tell, there is no deadlock situations here, so we're safe from that (If my implementation above is wrong even on its pseudo-code leve, constructive criticism is always appreciated). However,the BIG race condition I can find is:
lets assume the buffer is full. that is, writeIndex +1 = readIndex; (1) occurs, just as consume is being called. and is true (4) is false, so we move to read from the buffer (5) occurs, and the readIndex is advanced one (so there is, in fact, space in the buffer (2) occurs, advancing readIndex AGAIN, thus LOSING the value.
Basically, its a classic problem of the writter must modify the reader, causing a race condition. Without actually blocking the entire list everytime I access it, I can't think of a way to prevent this from happening. What am I missing??
- Start with a single producer/multiple consumer queue with appropriate progress guarantees.
- If the queue is full and the push would fail, pop one value. Then there will be space to push the new value.
这篇关于C / C ++锁免费（或非阻塞）环形缓冲区的覆盖最早的数据？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
