c++ - 为什么 Boost 原子使用中的多生产者队列是无等待的

Question

Boost Atomic 示例中的无等待多生产者队列:

template<typename T>
class waitfree_queue {
public:
  struct node {
    T data;
    node * next;
  };
  void push(const T &data)
  {
    node * n = new node;
    n->data = data;
    node * stale_head = head_.load(boost::memory_order_relaxed);
    do {
      n->next = stale_head;
    } while (!head_.compare_exchange_weak(stale_head, n, boost::memory_order_release));
  }

  node * pop_all(void)
  {
    T * last = pop_all_reverse(), * first = 0;
    while(last) {
      T * tmp = last;
      last = last->next;
      tmp->next = first;
      first = tmp;
    }
    return first;
  }

  waitfree_queue() : head_(0) {}

  // alternative interface if ordering is of no importance
  node * pop_all_reverse(void)
  {
    return head_.exchange(0, boost::memory_order_consume);
  }
private:
  boost::atomic<node *> head_;
};

http://www.boost.org/doc/libs/1_63_0_b1/doc/html/atomic/usage_examples.html#boost_atomic.usage_examples.mp_queue

但是我发现push里面的代码是lock-free而不是wait-free的。假设多个生产者都在调用push，至少有一个生产者可以取得进展；其他生产者只是再次运行 while 循环，直到取得进展。存在一种调度方式，可以在不可预测的时间内使特定线程处于饥饿状态。

wait-free 的定义告诉我们，任何给定的线程提供了一个时间片将能够取得一些进展并最终完成，而 lock-free 告诉我们至少有一个线程可以取得进展。所以上面的代码似乎满足了无锁的定义。

我的理解有没有错误？

Answer 1

是的，您的分析看起来对抽象 C++ 模型是正确的。

推送是无锁的，但不是无等待的。 CAS 重试循环位于 head_ 上，其他线程可以在我们尝试时继续修改它，因此任何给定的线程都可以重试无限次。所以它不是免等待的。

而且，至少有一个线程会取得进展，一个线程无法休眠并阻塞所有其他线程，因此它 是无锁的。

---

pop_all_reverse(因此 pop_all)是无等待的。它们只进行无条件的原子交换(假设一些硬件公平...... .) 应该是免等待的。

如果在真实硬件上实现为 LL/SC 重试循环，它也只是技术上无锁，不能保证无等待。但我认为 HW 可以设计为通过有机会执行 LL 的核心来 boost 成功的 SC，以避免核心暂时获得处于独占状态的缓存行但在失去所有权之前无法完成其原子操作的可能性. IDK 是否典型。在最坏的情况下，我认为这甚至会在没有线程取得进展的情况下创建活锁。

---

更正常的是，exchange 总是在第一次执行时成功，但必须等待缓存行的所有权才能执行。

CAS 通常也是如此。即使在竞争激烈的情况下，我预计实际重试也很少见。第一次循环中的 CAS 已经被解码并等待执行，只是等待第一次加载作为输入。如果其他线程正在写入缓存行，则在它到达之前它将不可读，并且如果 CPU 注意到 CAS 等待并在发送常规读取请求后发送 RFO(Read For Ownership)，则可能到达独占状态。

或者也许有些 CPU 没有那么聪明；如果线路到达共享状态，那么 CAS 将不得不等待对 RFO 的响应，这将为另一个核心提供一个大窗口来获取线路并在第一次加载和第一次 CAS 之间修改它。

但是在第一个CAS之后，加载结果来自于之前的CAS，所以肯定会从核心独占的缓存行中读取数据，另一个CAS可以马上运行并成功。

所以在实践中，exchange 与 CAS 重试循环之间可能没有太大区别，即使在 x86 或其他 ISA 上，xchg 或 swp 具有真正的硬件支持，无需重试循环即可运行。 但结果可能更好地描述为无锁而不是无等待，因为即使有交换，也只有一个线程可以同时修改head_。可能的等待时间与其他线程的数量(以及原子操作的公平性)成比例。

因此，当您查看为真实硬件编译的代码时，定义开始感觉有点模糊。

不过，我仍然不会将此队列描述为免等待。当然是无锁的