5

语境 

我正在用 C++ 编写一个线程安全的原型线程/协程库，并且我正在使用原子来使任务切换无锁。我希望它尽可能高效。我对原子和无锁编程有一个大致的了解，但我没有足够的专业知识来优化我的代码。我做了很多研究，但很难找到我的具体问题的答案：不同内存顺序下不同原子操作的传播延迟/可见性是多少？

当前假设 

我读到对内存的更改是从其他线程传播的，它们可能会变得可见：

  1. 对不同的观察者以不同的顺序，
  2. 有一些延迟。

我不确定这种延迟的可见性和不一致的传播是否仅适用于非原子读取，或者也适用于原子读取，这可能取决于使用的内存顺序。当我在 x86 机器上开发时，我无法测试弱排序系统上的行为。

无论操作类型和使用的内存顺序如何，所有原子读取是否总是读取最新值？ 

我很确定所有读取-修改-写入（RMW）操作总是读取任何线程写入的最新值，而不管使用的内存顺序如何。对于顺序一致的操作似乎也是如此，但前提是对变量的所有其他修改也是顺序一致的。据说两者都很慢，这对我的任务不利。如果不是所有原子读取都获得最新值，那么我将不得不使用 RMW 操作来读取原子变量的最新值，或者在 while 循环中使用原子读取，据我目前的理解。

写入的传播（忽略副作用）是否取决于内存顺序和使用的原子操作？ 

（这个问题只有在前一个问题的答案是并非所有原子读取总是读取最新值时才有意义。请仔细阅读，我不在这里询问副作用的可见性和传播。我只关心原子变量本身的值。）这意味着根据用于修改原子变量的操作，可以保证任何后续原子读取都接收到变量的最新值。因此，我必须在保证始终读取最新值的操作之间进行选择，或者使用宽松的原子读取，同时使用这种特殊的写入操作来保证对其他原子操作的修改的即时可见性。

4

3 回答 3

8

原子锁是免费的吗？

首先，让我们摆脱房间里的大象：atomic在您的代码中使用并不能保证无锁实现。atomic只是无锁实现的推动者。 is_lock_free()将告诉您对于 C++ 实现和您正在使用的底层类型是否真的是无锁的。

最新值是多少？

“最新”一词在多线程世界中非常含糊。因为可能被操作系统休眠的一个线程的“最新”可能不再是另一个处于活动状态的线程的最新。

std::atomic唯一的保证是防止竞争条件，通过确保在一个线程中对一个原子执行的R、M 和 RMW以原子方式执行，没有任何中断，并且所有其他线程看到之前的值或之后的值，但永远不会看到什么之间。因此atomic，通过在同一原子对象上的并发操作之间创建顺序来同步线程。

您需要将每个线程视为具有自己时间的平行宇宙，并且不知道平行宇宙中的时间。就像在量子物理学中一样，你在一个线程中唯一能知道的关于另一个线程的事情就是你可以观察到的（即宇宙之间“发生在之前”的关系）。

这意味着您不应将多线程时间视为所有线程都存在绝对“最新”的时间。您需要将时间视为相对于其他线程。这就是为什么原子不会创建绝对最新的，而只是确保原子将具有的连续状态的顺序排序。

传播

传播不依赖于内存顺序，也不依赖于执行的原子操作。 memory_order是关于围绕原子操作的非原子变量的顺序约束，这些原子操作看起来像栅栏。对它如何工作的最好解释当然是Herb Sutters 演示文稿，如果您正在研究多线程优化，那绝对值得花一个半小时。

尽管特定的 C++ 实现可能会以影响传播的方式实现某些原子操作，但您不能依赖任何此类观察，因为无法保证传播在下一个版本中以相同的方式工作编译器或另一个 CPU 架构上的另一个编译器。

但是传播重要吗？

在设计无锁算法时，很容易读取原子变量以获取最新状态。但是，尽管这种只读访问是原子的，但紧随其后的操作却不是。所以下面的指令可能会假设一个已经过时的状态（例如，因为线程在原子读取之后立即发送到睡眠状态）。

假设if(my_atomic_variable<10)您阅读了 9。假设您处于最佳状态，并且 9 将是所有并发线程设置的绝对最新值。比较它的值<10不是原子的，所以当比较成功和if分支时，my_atomic_variable可能已经有了一个新的值 10。而且无论传播速度有多快，即使保证读取到，这种问题都可能发生总是得到最新的值。我什至还没有提到ABA问题。

读取的唯一好处是避免数据竞争和 UB。但是，如果您想跨线程同步决策/操作，则需要使用 RMW，例如比较和交换（例如atomic_compare_exchange_strong），以便原子操作的排序产生可预测的结果。

于 2019-03-09T17:59:38.773 回答
1

经过一番讨论，以下是我的发现： 首先，让我们定义原子变量的最新值的含义：在挂钟时间，从外部观察者的角度来看，对原子变量的最新写入。如果有多个同时的最后写入（即，在同一周期内的多个内核上），那么选择其中一个并不重要。

  1. 任何内存顺序的原子加载都不能保证读取到最新值。这意味着必须先传播写入，然后才能访问它们。这种传播可能相对于它们的执行顺序是无序的，并且相对于不同的观察者来说顺序不同。

    std::atomic_int counter = 0;

void thread()
{
    // Imagine no race between read and write.
    int value = counter.load(std::memory_order_relaxed);
    counter.store(value+1, std::memory_order_relaxed);
}

for(int i = 0; i < 1000; i++)
    std::async(thread);

    在这个例子中，根据我对规范的理解，即使没有读写执行干扰，仍然可能有多次执行thread读取相同的值，因此最终counter不会是 1000。这是因为使用普通读取时，虽然线程保证以正确的顺序读取对同一变量的修改（它们不会读取新值，而在下一个值读取旧值），但不能保证读取全局最新写入的值到一个变量。

    这就产生了相对论效应（就像在爱因斯坦的物理学中一样），即每个线程都有自己的“真相”，这正是我们需要使用顺序一致性（或获取/释放）来恢复因果关系的原因：如果我们简单地使用松弛负载，那么我们甚至可以破坏因果关系和明显的时间循环，这可能是由于指令重新排序与无序传播相结合而发生的。内存排序将确保由不同线程感知的那些独立现实至少是因果一致的。

  2. 原子读取-修改-写入 (RMW) 操作（例如 exchange、compare_exchange、fetch_add 等）保证对上面定义的最新值进行操作。这意味着写入的传播是强制的，并导致对内存的一个通用视图（如果您所做的所有读取都是使用 RMW 操作从原子变量中读取的），与线程无关。因此，如果您使用atomic.compare_exchange_strong(value,value, std::memory_order_relaxed)or atomic.fetch_or(0, std::memory_order_relaxed)，那么您可以保证感知到一个包含所有原子变量的全局修改顺序。请注意，这并不能保证您对非 RMW 读取有任何排序或因果关系。

    std::atomic_int counter = 0;

void thread()
{
    // Imagine no race between read and write.
    int value = counter.fetch_or(0, std::memory_order_relaxed);
    counter.store(value+1, std::memory_order_relaxed);
}

for(int i = 0; i < 1000; i++)
    std::async(thread);

    在这个例子中（同样，假设没有任何thread()执行相互干扰），在我看来，规范禁止value包含除全球最新书面值之外的任何内容。所以，counter最终总是1000。

现在，什么时候使用哪种读法？ 

如果您只需要每个线程内的因果关系（对于按什么顺序发生的事情可能仍有不同的看法，但至少每个读者对世界都有一个因果一致的看法），那么原子加载和获取/释放或顺序一致性就足够了。

但是，如果您还需要新的读取（因此您绝不能读取除全局（跨所有线程）最新值之外的值），那么您应该使用 RMW 操作进行读取。仅这些并不会为非原子和非 RMW 读取创建因果关系，但所有线程中的所有 RMW 读取共享完全相同的世界视图，始终是最新的。

因此，总结一下：如果允许不同的世界观，请使用原子加载，但如果您需要客观现实，请使用 RMW 加载。

于 2019-03-10T19:40:23.497 回答
0

多线程是令人惊讶的领域。首先，原子读取不是在写入之后排序的。我读一个值并不意味着它是以前写的。有时，这样的读取可能会看到（间接，由其他线程）由同一线程进行的一些后续原子写入的结果。

顺序一致性显然与可见性和传播有关。当一个线程写入一个原子“顺序一致”时，它会使其所有先前的写入对其他线程可见（传播）。在这种情况下，（顺序一致的）读取相对于写入进行排序。

通常，性能最高的操作是“宽松的”原子操作，但它们提供了最低限度的排序保证。原则上存在一些因果悖论...... :-)

于 2019-03-09T20:54:44.810 回答