C/C++无锁(或非阻塞)环形缓冲区,它覆盖了最旧的数据？

Question

我正在尝试找到一种方法来实现无锁或无阻塞方式,为单个消费者/单个消费者创建一个环形缓冲区,它将覆盖缓冲区中最旧的数据.我已经阅读了很多无锁算法,如果缓冲区已满,当你"返回false"时可以工作 - 即不添加; 但是,当你需要覆盖最旧的数据时,我甚至找不到谈论如何做的伪代码.

我正在使用GCC 4.1.2(工作中的限制,我无法升级版本......)并且我有Boost库,并且在过去我制作了自己的Atomic <T>变量类型,它紧跟着upcomming规范(它不完美,但它是线程安全的,并做我需要的).

当我想到它时,我认为使用这些原子应该真正解决问题.关于我在想什么的一些粗糙的伪代码:

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

};

据我所知,这里没有死锁情况,所以我们对此是安全的(如果我的上述实现在错误的代码级别上是错误的,那么建设性的批评总是受到赞赏).但是,我能找到的BIG竞争条件是:

让我们假设缓冲区已满.也就是说,writeIndex +1 = readIndex; (1)发生,正如消耗被调用.并且是真的(4)是假的,所以我们从缓冲区(5)移动读取,并且readIndex是高级的(因此实际上,缓冲区(2)中的空间发生,推进readIndex AGAIN,因此失去价值.

基本上,它的一个经典的写作问题必须修改读者,造成竞争条件.每次访问时都没有实际阻止整个列表,我想不出有办法防止这种情况发生.我错过了什么？

Answer 1

1. 从具有适当进度保证的单个生产者/多个消费者队列开始.
2. 如果队列已满并且推送失败,则弹出一个值.然后会有空间推动新价值.