时间戳

首页 > 解决方案 > 无锁单生产者/单消费者循环缓冲区 - CPU 推测能否打破内存屏障逻辑？

c++ - 无锁单生产者/单消费者循环缓冲区 - CPU 推测能否打破内存屏障逻辑？

问题描述

当我考虑推测执行及其对简单代码的影响时，我一直在研究无锁的单一生产者/单一消费者循环缓冲区。

有了这个实现，只有一个可以调用函数的push()唯一线程和另一个可以调用函数的唯一线程pop()。

这是Producer代码：

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
}

这是Consumer代码：

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

问题

如果push()由于推测执行而将其编译为以下函数怎么办：

bool push(const Element& item)
{       
  const auto current_tail = _tail.load(std::memory_order_relaxed);  // 1
  const auto next_tail = increment(current_tail);

  //The load is performed before the test, it is valid
  const auto head = _head.load(std::memory_order_acquire);         

  //Here is the speculation, the CPU speculate that the test will succeed
  //store due to speculative execution AND it respects the memory order due to read-acquire
  _array[current_tail] = item;                             
  _tail.store(next_tail, std::memory_order_release); 

  //Note that in this case the test checks if you it has to restore the memory back
  if(next_tail == head)//the code was next_tail != _head.load(std::memory_order_acquire)    
  { 
   //We restore the memory back but the pop may have been called before and see an invalid memory
    _array[current_tail - 1] = item;                                 
    _tail.store(next_tail - 1, std::memory_order_release);             
    return true;
  }
  return false; // full queue
}

对我来说，要完全有效，推送功能应该确保在条件成功后发出屏障：

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_relaxed))            // 2               
  { 
    //Here we are sure that nothing can be reordered before the condition
    std::atomic_thread_fence(std::memory_order_acquire);            //2.1
    _array[current_tail] = item;                                    // 3
    _tail.store(next_tail, std::memory_order_release);              // 4
    return true;
  }
  return false; // full queue
}

标签： c++multithreadingc++11atomiclock-free

解决方案

回复：您建议的重新排序：不，编译器不能发明对原子变量的写入。

运行时推测也不能发明实际上对其他线程可见的写入。它可以将任何它想要的东西放在它自己的私有存储缓冲区中，但是在存储对其他线程可见之前，必须检查早期分支的正确性。

通常这是通过按顺序退休来工作的：只有在所有先前的指令都退休/非推测性之后，一条指令才能退休（成为非推测性的）。在存储指令退出之前，存储不能从存储缓冲区提交到 L1d 高速缓存。

回复：标题：不，推测执行仍然必须尊重内存模型。如果 CPU 想要推测性地加载超过不完整的获取加载，它可以，但前提是它检查以确保这些加载结果在“正式”允许发生时仍然有效。

x86 CPU在实践中会这样做，因为强大的 x86 内存模型意味着所有加载都是获取加载，因此任何无序加载都必须是推测性的，如果无效则回滚。（这就是为什么您可以获得内存顺序错误推测管道核弹的原因。）

所以 asm 按照 ISA 规则所说的方式工作，而 C++ 编译器知道这一点。编译器使用它在目标 ISA 之上实现 C++ 内存模型。

如果您在 C++ 中执行获取加载，它确实可以作为获取加载。

您可以根据所写的 C++ 重新排序规则对您的逻辑进行心理建模，以实现可能的编译时 + 运行时重新排序。请参阅http://preshing.com/20120913/acquire-and-release-semantics/。

推荐阅读