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

Question

如果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. 无论其他线程的行为如何，访问数据结构的每个线程都可以在有限步数内完成其操作。

Answer 1

存在普遍接受的无锁和无等待定义，您的问题中提供的定义与这些定义一致。我强烈认为 C++ 标准委员会肯定会坚持科学界普遍接受的定义。

一般来说，关于无锁/无等待算法的出版物假定 CPU 指令是无等待的。相反，关于进度保证的争论集中在软件算法上。

基于这个假设，我认为任何std::atomic可以转换为某个体系结构的单个原子指令的方法在该特定体系结构上都是无等待的。这种翻译是否可能有时取决于该方法的使用方式。举个例子fetch_or。在 x86 上，这可以转换为lock or，但前提是您不使用其返回值，因为此指令不提供原始值。如果使用返回值，那么编译器将创建一个 CAS 循环，该循环是无锁的，但不是无等待的。（同样适用于fetch_and/ fetch_xor。）

所以哪些方法实际上是无等待的，不仅取决于编译器，而且主要取决于目标架构。

假设单个指令实际上是无等待的在技术上是否正确，恕我直言，这是一个相当哲学的问题。确实，可能无法保证指令在有限数量的“步骤”内完成执行（无论这样的步骤是什么），但机器指令仍然是我们可以看到和控制的最低级别的最小单元。实际上，如果您不能假设单个指令是无等待的，那么严格来说，不可能在该架构上运行任何实时代码，因为实时也需要严格限制时间/步数。

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

定义为无锁 (32.8) 或指示为无锁 (32.5) 的原子函数的执行是无锁执行。

• 如果标准库函数中只有一个线程未被阻塞 (3.6)，则该线程中的无锁执行将完成。[ 注意：并发执行线程可能会阻止无锁执行的进度。例如，这种情况可能发生在加载锁定存储条件实现中。这种特性有时被称为无障碍。— 尾注 ]
• 当一个或多个无锁执行同时运行时，至少应该完成一个。[注意：某些实现很难为这种效果提供绝对保证，因为来自其他线程的重复和特别不合时宜的干扰可能会阻止前进，例如，通过在加载锁定和条件存储之间重复窃取缓存行以实现无关目的指示。实现应确保此类影响不会在预期的操作条件下无限延迟进度，因此程序员可以安全地忽略此类异常。在本文档之外，此属性有时称为无锁。— 尾注 ]

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

• wait-free - 如果一个方法保证每个调用在有限数量的步骤中完成它的执行，即不可能确定上限，但仍然必须保证步骤数量是有限的。
• 无等待有界- 如果一个方法保证每个调用在有界的步骤中完成其执行，则该方法是无等待有界的，其中此界限可能取决于线程的数量。
• 无等待填充不经意——如果一个方法保证每个调用在有限步数内完成其执行，并且该边界不依赖于线程数，则该方法是无等待填充无知的。

所以严格来说，题中的定义和wait-free bounded的定义是一致的。

在实践中，大多数无等待算法实际上是无等待有界的，甚至无等待群体无视，即，可以确定步数的上限。