原子操作的传播/可见性（原子加载 vs 原子RMW加载）

Question

背景

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

当前假设

我读到过，内存的变化会从其他线程中传播，以这样一种方式，使它们可能变得可见：

1. 以不同的顺序对不同的观察者可见，
2. 存在一定的延迟。

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

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

我相信所有的读-改-写（RMW）操作 总是读取任何线程写入的最新值，不管所使用的内存顺序如何。如果一个变量的所有其他修改也是顺序一致的，则同样适用于顺序一致的操作。据说两者都很慢，这对我的任务来说不好。如果不是所有原子读取都获得了最新值，则必须仅为读取原子变量的最新值使用RMW操作，或在while循环中使用原子读取，以我目前的理解。

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

（只有当上一个问题的答案是不是所有原子读操作总是读取最新值时，这个问题才有意义。请仔细阅读，我此处并非询问副作用的可见性和传播。我只关心原子变量本身的值。） 这将意味着根据所使用的操作来修改原子变量，可以保证任何随后的原子读取接收到变量的最新值。因此，我必须选择保证始终读取最新值的操作，或者与此特殊写操作一起使用松散的原子读取，这样就可以保证其他原子操作对修改的立即可见性。

- RmbRT

---

请不要在问题中放置答案。请发布您自己的答案并接受它。 - Raymond Chen

什么是非原子操作？ - curiousguy

@curiousguy 普通的读操作（例如整数）不能保证是原子性的，可能会读取到破碎的值，即使所有的写操作都是原子性的。 - RmbRT

Answer 1

原子操作是无锁的吗？

首先，让我们摆脱烦人的问题：在代码中使用atomic并不能保证实现是无锁的。 atomic只是实现无锁的一个工具。is_lock_free()会告诉你是否真正使用了无锁实现，这取决于你使用的C++实现和底层类型。

最新值是什么？

在多线程世界中，“最新”这个术语非常模糊。因为对于一个可能被操作系统挂起的线程来说，“最新”的值可能不再是另一个正在运行的线程所认为的“最新”。

std::atomic 仅保证对抗竞态条件，即确保在一个线程中对一个原子执行的 R、M 和 RMW 操作是原子性执行的，没有任何中断，并且所有其他线程只看到之前或之后的值，而不是中间的值。因此，atomic 通过在同一原子对象上的并发操作之间创建一个顺序来同步线程。

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

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

传播

传播不依赖于内存顺序或原子操作。 memory_order 是关于原子操作周围非原子变量的顺序约束，它们被视为栅栏。最好的解释是Herb Sutters presentation，如果你正在进行多线程优化，那么这个一个半小时的演示绝对值得一看。

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

但传播是否重要？

当设计无锁算法时，读取原子变量以获取最新状态是很诱人的。但是，虽然这种只读访问是原子性的，但紧随其后的操作却不是。因此，以下指令可能会假定一个已经过时的状态（例如，因为线程在原子读取后立即休眠）。

以if(my_atomic_variable<10)为例，假设您读取到了9。假设您处于最好的世界中，9将是所有并发线程设置的绝对最新值。与<10比较它的值不是原子性的，因此当比较成功和if分支时，my_atomic_variable可能已经具有新值10。这种问题可能会发生，而无论传播速度有多快，即使读取保证始终获得最新值。我甚至还没有提到ABA问题。

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

- Christophe

---

谢谢您的澄清。您能否更详细地阐述不同原子操作具有不同的可见性保证的部分（RMW 操作的文档表明实际上存在一个单一的“最新值”，这是 RMW 操作观察到的值）？ - RmbRT

假设你有3个线程。1想要在原子x上写入，2想要RMW x，3想要读取。如果操作的顺序是先1，那么2将根据1设置的值对x执行rmw。如果顺序是先2，则将执行rmw，但值将被1覆盖。在这两种情况下，您无法保证3读取的值。您可以完全让3读取由1设置的值，然后休眠，然后2更改x的值，但然后3醒来并继续处理具有过时值的非原子操作。 - Christophe

不同的处理器写入传播的速度是否有所不同？“看到最后一个值”的保证对于普通原子读取也有效吗？因此，在您的示例中，即使2在3之前，3是否可以读取1的值？该问题还扩展到多个读取器：如果存在读取2的值的读取器（并且为简单起见假设2在1之后），同时或稍后读取的读取器是否也读取相同的值，或者它们仍然可能看到1的值？ - RmbRT

@RmbRT 一个全知的观察者不就是另一个节点，会原子地读取原子吗？但归根结底：对我来说，rmw（compare&swap）似乎是正确的方法，因为当你只是原子地读取时，之后的指令就不再是原子的了，所以你不能确定它是你所操作的“最新”状态（例如，原子上的简单if语句可能会分支到过时的值）。因此，使用单独的读取和写入总是会有麻烦。我可以推荐安东尼·威廉姆斯（Antony Williams）的书《C++并发编程实战》，该书很好地分析了这些问题。 - Christophe

一个原子RMW确实保证其加载端在修改顺序或原子对象中看到“最新值”。这意味着它与写入和其他RMW进行了串行化，这对于使1000个fetch_add(1)执行的总修改为+= 1000是必要的。另请参见C++顺序一致性是否保证读取内存中存储的最新值？和原子读取是否保证读取最新值？。 - Peter Cordes

Answer 2

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

1. Atomic loads of any memory order have no guarantee that the latest value is read. This means that writes have to propagate before you can access them. This propagation may be out of order with respect to the order in which they were executed, as well as differing in order with respect to different observers.

   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);
   

   In this example, according to my understanding of the specs, even if no read-write executions were to interfere, there could still be multiple executions of thread that read the same values, so that in the end, counter would not be 1000. This is because when using normal reads, although threads are guaranteed to read modifications to the same variable in the correct order (they will not read a new value and on the next value read an older value), they are not guaranteed to read the globally latest written value to a variable.

   This creates the relativity effect (as in Einstein's physics) that every thread has its own "truth", and this is exactly why we need to use sequential consistency (or acquire/release) to restore causality: If we simply use relaxed loads, then we can even have broken causality and apparent time loops, which can happen because of instruction reordering in combination with out-of-order propagation. Memory ordering will ensure that those separate realities perceived by separate threads are at least causally consistent.

2. Atomic read-modify-write (RMW) operations (such as exchange, compare_exchange, fetch_add,…) are guaranteed to operate on the latest value as defined above. This means that propagation of writes is forced, and results in one universal view on the memory (if all reads you make are from atomic variables using RMW operations), independent of threads. So, if you use atomic.compare_exchange_strong(value,value, std::memory_order_relaxed) or atomic.fetch_or(0, std::memory_order_relaxed), then you are guaranteed to perceive one global order of modification that encompasses all atomic variables. Note that this does not guarantee you any ordering or causality of non-RMW reads.

   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);
   

   In this example (again, under the assumption that none of the thread() executions interfere with each other), it seems to me that the spec forbids value to contain anything but the globally latest written value. So, counter would always be 1000 in the end.

现在，何时使用哪种读取方式？ 

如果您仅需要在每个线程内部的因果关系（可能仍然存在对发生的顺序有不同看法的情况，但至少每个单独的读取器对世界的因果一致性视图是一致的），那么原子加载和获取/释放或顺序一致性就足够了。

但是，如果您还需要新鲜的读取（以便您永远不会读取除全局（跨所有线程）最新值之外的其他值），则应该使用RMW操作进行读取。这些操作本身不会为非原子和非RMW读取创建因果关系，但是所有线程上的所有RMW读取共享完全相同的世界视图，始终保持最新状态。

因此，总结一下： 如果允许不同的世界观，则使用原子加载，但如果需要客观事实，请使用RMWs进行加载。

- RmbRT

---

简而言之，由于RMW or 0高度可能是原子加载，因此它可能以相同的方式执行 :-) - guest

我不这么认为。就我所知，RMW操作与读取操作的行为完全不同。 - RmbRT

相对论中，如果某个事件X是A的过去，并且A向B发送信号，当B接收到信号时，此时X在B的过去。但这在机器翻译编程中可能不成立。 - curiousguy

RMW 操作根据规范被强制表现出这种行为（如果我理解正确的话）。 - RmbRT

@curiousguy 在我的例子中，线程1可以加载counter = 0，然后写入counter=1，在线程2中，即使它发生在1被写入之后，你仍然可能会加载counter = 0，然后将其写入1。这是因为没有保证原子加载读取变量的最新值。对于fetch_or，你不能读取早于最新写入的值，因此在1被写入后，你不能加载0。使用RMW来加载一个值会强制将最新的写入传播到执行RMW操作的CPU。 - RmbRT

Answer 3

多线程编程是一个令人惊讶的领域。 首先，原子读取在写入后不是有序的。也就是说，读取一个值并不意味着它在写入之前被写入。有时这样的读取甚至可能看到（间接地，由其他线程）同一线程的某些后续原子写入的结果。

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

通常，最高效的操作是“松散”的原子操作，但它们提供最少的排序保证。原则上，总会存在一些因果关系悖论... :-)

- guest

---

你能解释一下那些悖论是如何发生的吗？ - RmbRT

Alpha AXP 因其非常弱的内存模型而声名狼藉。例如，假设最初 x=y=0。处理器 1 执行 x = x+1; y = x。尽管只有处理器 1 修改了 x 和 y，y 是由 x 计算出来的，并且处理器 1 从未将 y 设置大于 x，但处理器 2 可以计算 y>x 为真（它读取 y 并得到 1，然后读取 x 并得到 0）。 - Raymond Chen

C++的MT语义纯属胡扯。如果值来自未来，那么UB也可能来自未来，因此任何程序语义都无法定义。请不要提及未来。 - curiousguy

@RaymondChen 但是没有CPU会读取“未来”。它们只会重新排序不可避免的副作用，即很快就会发生的事情可以更早地发生。这与《飞出个未来》不同。 - curiousguy

UB does come from the future! “UB确实来自未来” - Raymond Chen