multithreading - 寻找无锁的RT安全单读取器单写入器结构

Question

我正在寻找符合以下要求的无锁设计:

一个单一作者写入一个结构，一个单一读者从此结构中读取(此结构已经存在，并且可以安全地同时读取/写入)

，但有时需要由作者更改结构，然后初始化，切换并写入新结构(相同类型但具有新内容)

，并且在下一次读取器读取时，将切换到此新结构(如果编写器将开关多次切换到新的无锁结构，则读取器将丢弃这些结构，而忽略其数据)。

必须重用这些结构，即在写入/读取/切换操作期间不允许堆内存分配/释放，以实现 RT的目的。

我目前已经实现了一个包含这些结构的多个实例的环形缓冲区。但是这种实现方式遭受这样的事实，即当编写者使用了环形缓冲区中存在的所有结构时，没有更多地方可以更改结构...但是环形缓冲区的其余部分包含一些不必读取的数据读者可以使用，但作者不能重复使用。结果，环形缓冲区不适合该目的。

关于无锁设计的(名称或伪实现)有什么想法吗？ 感谢您考虑了此问题。

Answer 1

这是一个关键是有三个缓冲区，读取器保留要从中读取的缓冲区。编写器写入其他两个缓冲区之一。碰撞的风险很小。另外，这会扩展。只要使您的成员数组比读取器的数量加上写入器的数量长一个元素即可。

class RingBuffer
{
  RingBuffer():lastFullWrite(0)
  { 
    //Initialize the elements of dataBeingRead to false
    for(unsigned int i=0; i<DATA_COUNT; i++)
    {
      dataBeingRead[i] = false;
    } 
  }

  Data read()
  {
    // You may want to check to make sure write has been called once here
    // to prevent read from grabbing junk data. Else, initialize the elements
    // of dataArray to something valid.
    unsigned int indexToRead = lastFullWriteIndex;
    Data dataCopy;
    dataBeingRead[indexToRead] = true;
    dataCopy = dataArray[indexToRead];
    dataBeingRead[indexToRead] = false;
    return dataCopy;
  }

  void write( const Data& dataArg )
  {
    unsigned int writeIndex(0);

    //Search for an unused piece of data.
    // It's O(n), but plenty fast enough for small arrays.
    while( true == dataBeingRead[writeIndex] && writeIndex < DATA_COUNT )
    {
      writeIndex++;
    }  

    dataArray[writeIndex] = dataArg;

    lastFullWrite = &dataArray[writeIndex];
  }

private:
  static const unsigned int DATA_COUNT;
  unsigned int lastFullWrite;
  Data dataArray[DATA_COUNT];
  bool dataBeingRead[DATA_COUNT];
};

注意:这里写的方式有两个副本，可以读取您的数据。如果通过引用参数将数据从读取函数中传递出去，则可以将其缩减为一个副本。