问题标签 [wait-free]

在 x86 上，像这样的原子 RMW 指令lock add dword [rdi], 1是使用现代 CPU 上的缓存锁定来实现的。因此，高速缓存行在指令期间被锁定。这是通过在读取值时获取行 EXCLUSIVE/MODIFIED 状态来完成的，并且 CPU 在指令完成之前不会响应来自其他 CPU 的 MESI 请求。

有两种并发进度条件，阻塞和非阻塞。原子 RMW 指令是非阻塞的。CPU 硬件在持有缓存锁时永远不会休眠或做其他事情（中断发生在原子 RMW 之前或之后，而不是期间），释放缓存行之前的步数有一个有限（且很小）的上限.

非阻塞算法在理论计算机科学中可以分为 3 种风格：

1. 等待免费：所有线程将在有限的步骤中取得进展。

2. 无锁：至少一个线程将在有限的步骤中取得进展

3. 无阻塞：如果没有争用，线程将在有限的步数内取得进展

x86 提供什么样的保证？

我想它至少是无锁的；如果存在争用，至少有一个 CPU 会取得进展。

但是 x86 是否可以免费等待原子指令？是否每个 CPU 都能保证在有限数量的步骤中取得进展，或者可能是一个或多个 CPU 处于饥饿状态并可能无限期延迟？

那么当多个内核在同一个缓存行上进行原子操作时会发生什么？

如果T是 C++ 基本类型，并且如果std::atomic<T>::is_lock_free()返回true，那么其中有什么std::atomic<T>是免等待的（不仅仅是无锁的）吗？比如，load，store，fetch_add，fetch_sub，compare_exchange_weak， 和compare_exchange_strong。

您是否还可以根据 C++ 标准中指定的内容以及在 Clang 和/或 GCC（您选择的版本）中实现的内容来回答。

我最喜欢的无锁和无等待定义取自C++ Concurrency in Action（免费提供）。如果满足以下第一个条件，则算法是无锁的，如果满足以下两个条件，则它是无等待的：

1. 如果访问数据结构的线程之一在其操作中途被调度程序挂起，则其他线程必须仍然能够完成它们的操作而无需等待挂起的线程。
2. 访问数据结构的每个线程都可以在有限的步数内完成其操作，而不管其他线程的行为。

我正在考虑具有两种方法的并发多生产者多消费者数据结构：success = try_put(elem)和success = try_get(&elem). 我假设这个数据结构有固定数量的预分配内存，如果它是满的或空的，success布尔标志包含false不能进行相应操作的意思。

数据结构不强制执行任何排序保证，因此它是堆栈、队列还是其他东西都没有关系。这个数据结构在文献中有名字吗？

是否有可能使这种数据结构的无等待实现？是否需要存在恒定时间的原子操作，如果是，它们应该如何使用？

给定以下我制作的简单无锁​​线性分配算法：

我想进一步改进它以在快速路径上无等待，完全丢弃 CAS 循环，最好使用fetch_add，但是我不确定如何处理分配失败的情况，因为请求的大小大于可用大小 - 当检测到这一点时，fetch_add已经增加了现在超过有效范围的位置，该有效范围可能由其他线程同时加载，这将进一步增加它并产生没有分配空间的错误错觉。这条路径仍然需要某种自旋等待循环，但是我想不出一个有效的解决方案。

任何想法？