samedi 2 octobre 2021

Is lock-free, wait-free, single poducer single consumer ring buffer overwriting least recent data on overflow possible?

I have been investigating lock-free, wait-free, C++ SPSC ring buffer implementations for a while. For particularly enqueue operation when buffer is full, I have encountered several different methodologies to handle the situation. For example, this guy's implementation for push and pop operations are as follows:

bool push(const Element& item)
{       
  const auto current_tail = _tail.load(std::memory_order_relaxed);  // 1
  const auto next_tail = increment(current_tail);                   
  if(next_tail != _head.load(std::memory_order_acquire))            // 2               
  {     
    _array[current_tail] = item;                                    // 3
    _tail.store(next_tail, std::memory_order_release);              // 4
    return true;
  }
  return false; // full queue
}

bool pop(Element& item)
{
  const auto current_head = _head.load(std::memory_order_relaxed);    // 1
  if(current_head == _tail.load(std::memory_order_acquire))           // 2
    return false; // empty queue

  item = _array[current_head];                                       // 3
  _head.store(increment(current_head), std::memory_order_release);   // 4
  return true;
}

His approach is simply rejecting enqueuing new element when buffer is full and this is just fine. After that, I have been looking for a way to transform this implementation to overwriting on least recent data when buffer is exhausted style. To do this, according to this guy, when queue is full, _head index must also be advanced by push operation. But now, two threads are able to write to the same variable which must be synchronized. Since I am not a C++ expert, I can't simply figure out if this can be simply done by adding some atomic load or store operations but my gut feelings tell me that such a thing is not possible because even if _head and _tail synchronizations are well adjusted, it is then possible that a pop() may get an element that is partially set (or filled) by the push, ie. line labeled as "3" in both functions would not be atomic and filthy race conditions are possible. Also, I could not find such an implementation on GitHub and Google searches.

So, is such a SPSC ring buffer is possible to realize preserving lock-free and wait-free features? If possible, I kindly ask you to provide concise instructions or code. Also, can you pass your opinions on my approach to transform above push and pop functions?

Aucun commentaire:

Enregistrer un commentaire