c++ - std::atomic 中的任何内容都是免等待的？

Question

如 T是 C++ 基本类型，如果 std::atomic<T>::is_lock_free()返回 true ，那么 std::atomic<T> 中有什么吗？即 wait-free (不仅仅是无锁)？喜欢，load , store , fetch_add , fetch_sub , compare_exchange_weak , 和 compare_exchange_strong .

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

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

如果访问数据结构的线程之一在其操作中途被调度程序挂起，则其他线程必须仍然能够完成其操作而无需等待挂起的线程。

无论其他线程的行为如何，访问数据结构的每个线程都可以在有限步数内完成其操作。

Answer 1

存在普遍接受的无锁和无等待定义，您的问题中提供的定义与这些定义一致。我强烈认为 C++ 标准委员会肯定会坚持科学界普遍接受的定义。
一般来说，关于无锁/无等待算法的出版物假定 CPU 指令是无等待的。相反，关于进度保证的争论集中在软件算法上。
基于这个假设，我认为任何 std::atomic对于某些体系结构可以转换为单个原子指令的方法在该特定体系结构上是无等待的。这种翻译是否可能有时取决于该方法的使用方式。以fetch_or为例.在 x86 上，这可以转换为 lock or ，但前提是您不使用其返回值，因为该指令不提供原始值。如果使用返回值，那么编译器将创建一个 CAS 循环，该循环是无锁的，但不是无等待的。 (同样适用于 fetch_and/fetch_xor 。)
所以哪些方法实际上是无等待的，不仅取决于编译器，而且主要取决于目标架构。
假设单个指令实际上是无等待的在技术上是否正确，恕我直言，这是一个相当哲学的问题。诚然，可能无法保证指令在有限数量的“步骤”内完成执行(无论这样的步骤是什么)，但机器指令仍然是我们可以看到和控制的最低级别的最小单元。实际上，如果您不能假设单个指令是无等待的，那么严格来说，在该架构上运行任何实时代码是不可能的，因为实时也需要严格限制时间/步数。

这就是 C++17 标准在 [intro.progress] 中的规定:

Executions of atomic functions that are either defined to be lock-free (32.8) or indicated as lock-free (32.5) are lock-free executions.

• If there is only one thread that is not blocked (3.6) in a standard library function, a lock-free execution in that thread shall complete. [ Note: Concurrently executing threads may prevent progress of a lock-free execution. For example, this situation can occur with load-locked store-conditional implementations. This property is sometimes termed obstruction-free. — end note ]
• When one or more lock-free executions run concurrently, at least one should complete. [ Note: It is difficult for some implementations to provide absolute guarantees to this effect, since repeated and particularly inopportune interference from other threads may prevent forward progress, e.g., by repeatedly stealing a cache line for unrelated purposes between load-locked and store-conditional instructions. Implementations should ensure that such effects cannot indefinitely delay progress under expected operating conditions, and that such anomalies can therefore safely be ignored by programmers. Outside this document, this property is sometimes termed lock-free. — end note ]

另一个答案正确地指出我的原始答案有点不准确，因为存在两种更强的等待自由子类型。

免等待 - 如果一个方法保证每个调用在有限步数内完成它的执行，即不可能确定一个上限，但它仍然必须保证步数是有限的，则该方法是无等待的。

免等待有界 - 一个方法是无等待有界的，如果它保证每个调用在有界的步骤中完成它的执行，这个界限可能取决于线程的数量。

免等待人口遗忘 - 如果一个方法保证每个调用在有限的步数内完成它的执行，并且这个边界不依赖于线程的数量，那么它就是无等待填充。

所以严格来说，题中的定义和wait-free bounded的定义是一致的。
在实践中，大多数无等待算法实际上是无等待有界的，甚至是无等待群体无视的，即可以确定步数的上限。