7

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

2 回答 2

8

存在普遍接受的无锁和无等待定义，并且您的问题中提供的定义与这些定义一致。我强烈认为 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 population oblivious - 如果一个方法保证每个调用都在有限的步数内完成其执行，并且此界限不依赖于线程数，则该方法是无等待人口遗忘的。

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

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

于 2020-05-18T08:15:42.330 回答
4

由于wait-freedom 1的定义有很多种，而且人们会选择不同的定义，所以我认为准确的定义是最重要的，区分其专业化是必要且有用的。

这些是普遍接受的无等待定义及其专业化：

  • 无等待：所有线程将在有限的步骤中取得进展。

  • wait-free bounded：所有线程将在有限步数内取得进展，这可能取决于线程数。

  • wait-free population-oblivious 3：所有线程都将在固定数量的步骤中取得进展，这不取决于线程的数量。

总体而言，C++ 标准没有区分无锁和无等待（请参阅this other answer）。它总是提供不比无锁更强的保证。

当std::atomic<T>::is_lock_free()返回时，实现使用原子指令true而不是互斥锁，可能带有CAS循环或LL/SC循环。 原子指令无需等待。CAS 和 LL/SC 循环是无锁的。

方法的实现方式取决于许多因素，包括其用法、编译器、目标体系结构及其版本。例如：

  • 正如有人所说，在 x86 gcc 上，fetch_add()forstd::atomic<double> 使用CAS 循环 ( lock cmpxchg)，而 forstd::atomic<int> 使用 lock addor lock xadd。
  • 正如其他人所说，在具有 LL/SC 指令的架构上，fetch_add()如果没有更好的指令可用，则使用 LL/SC 循环。例如，在 ARM 版本 8.1 及更高版本上不是这种情况，其中ldaddal用于非松弛std::atomic<int>，ldadd如果松弛则使用。
  • 如另一个答案中所述，如果不使用返回值，则在 x86 上使用 gcc fetch_or() ， lock or否则使用CAS 循环（lock cmpxchg）。

正如我的这个答案中所解释的：

  • store()方法 和lock add, lock xadd,指令是无等待的lock or，无需等待，而它们的“算法”，即硬件为锁定高速缓存行所做的工作，是无等待有界的。
  • 该load()方法始终无需等待，无需人口。

1例如：

  • 所有线程都将在有限的步骤中取得进展（来源）

  • 所有线程都将在有限的步数内取得进展2

  • 他们都执行的每个“步骤”，所有线程都将在没有任何饥饿的情况下向前推进（来源）

2边界是否恒定尚不清楚，或者可能取决于线程数。

3一个奇怪的名字，不适合缩写，所以也许应该选择另一个。

于 2020-07-22T17:58:13.667 回答