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_;
};
但是我发现push中的代码是无锁的而不是等待的。假设多个生产者正在调用推送，至少有一个生产者可以取得进展;其他生产者只是再次运行while循环，直到取得进展。存在一种使特定线程在不可预测的时间内匮乏的调度方式。
无等待的定义告诉我们，任何提供时间片的给定线程都能够取得一些进展并最终完成，而无锁告诉我们至少有一个线程可以取得进展。所以上面的代码似乎满足了无锁的定义。
我的理解是否有错误？
是的，您的分析对于抽象C ++模型看起来是正确的。
Push是无锁的，但不是等待的。 CAS重试循环在head_上，其他线程可以在我们尝试时继续修改，因此任何给定的线程都可以重试无限次数。所以它不是等待的。
但是，至少有一个线程会取得进展，并且线程可以休眠并阻塞所有其他线程没有意义，所以它是无锁的。
pop_all_reverse（以及pop_all）是等待的。他们只进行无条件的原子交换（假设某些硬件公平性......）应该是等待的。
如果在真实硬件上实现为LL / SC重试循环，它也只是在技术上无锁定且无法保证等待。但是我认为HW可以被设计为通过一个有机会进行LL的核心来促进成功的SC，以避免核心暂时获得独占状态的缓存行但是在失去所有权之前无法完成其原子操作的可能性。 IDK，如果这是典型的或不是。在最糟糕的情况下，我认为甚至可以在没有线程进展的情况下创建活锁。
更常见的情况是，交换总是在第一次执行时成功，但必须等待缓存行的所有权才能执行。
CAS通常也是如此。我预计即使在高争用情况下，实际重试也很少见。通过循环的第一次行程中的CAS已经被解码并等待执行，只是等待第一次加载作为输入。如果其他线程正在写入高速缓存行，则在它到达之前它将是不可读的，并且如果CPU注意到CAS等待并且在发送常规读取请求之后发送RFO（读取所有权），则它可以到达独占状态。
或许某些CPU不那么聪明;如果线路到达共享状态，那么CAS将不得不等待对RFO的响应，这将为另一个核心提供一个大窗口来获取线路并在第一个负载和第一个CAS之间修改它。
但是在第一次CAS之后，加载结果来自之前的CAS，因此肯定会从核心拥有独占所有权的缓存行读取数据，而另一个CAS可以立即运行并成功。
因此在实践中，exchange与CAS重试循环之间可能没有太大差异，即使在x86或其他ISA上，其中xchg或swp具有真正的硬件支持，无需重试循环即可运行。但结果可能更好地描述为无锁而不是等待，因为即使使用交换，只有一个线程可以立即修改head_。可能的等待时间与其他线程的数量（以及原子操作的公平性）成比例。
因此，当您查看为真实硬件编译的代码时，定义会开始变得有点模糊。