无锁编程：原子值有多新鲜？

Question

一个原子变量在多个并发的运行线程之间共享。据我所知，线程可以读取它执行宽松负载的陈旧值：

x.load(std::memory_order_relaxed)

如果我们使用release-acquire同步呢？据我从文档中得到的信息，执行获取的线程可以保证看到释放线程已写入变量的内容。

// Thread 1:
x.store(33, std::memory_order_release);

// Thread 2:
x.load(std::memory_order_acquire)

在这种情况下，线程 2 是否总是会看到新值？

现在，如果我们将执行松散存储的第三个线程添加到前面的示例中，线程 2 可能看不到该更新，因为同步仅在线程 1 和线程 2 之间建立。我说得对吗？

最后，据说读-修改-写操作总是对新值进行操作。这是否意味着它们强制线程 "see" 其他线程所做的更新，所以如果我们在读-修改-写操作之后加载，我们将看到至少与该操作一样新鲜的值？

// Thread 1:
x.fetch_add(1, std::memory_order_relaxed); // get the fresh value and add 1
if (x.load(std::memory_order_relaxed) == 3) // not older than fetch_add
    fire();

// Thread 2:
x.fetch_add(2, std::memory_order_relaxed); // will see thread 1 modification
if (x.load(std::memory_order_relaxed) == 3) // will see what fetch_add has put in x or newer
    fire();

对于 x 最初为零，我可以确定 fire 在这种情况下至少会被调用一次吗？我所有的测试都证明它可以工作，但也许这只是我的编译器或硬件的问题。

我也很好奇顺序。 x 修改和加载之间存在明显的依赖关系，因此我认为尽管指定了宽松的顺序，但这些指令不会重新排序。还是我错了？

Answer 1

关键是 memory_order_relaxed 意味着 fetch_add 不订购 loads/stores 到任何 other 位置。它会做任何需要成为原子的事情，仅此而已。但是，单个线程内的依赖顺序仍然适用。

要使 fetch_add 成为原子，它必须防止任何其他 fetch_add 尝试同时执行，以对它正在读取的相同输入值进行操作。几乎所有内容都使用 MESI cache-coherence protocol, so in practice an atomic fetch_add is done by keeping the cache line "locked" in M state from the read to the write. (Or with LL/SC, detecting that this didn't happen and retrying.) See also 的派生词来更详细地描述 x86。

C++ 没有指定任何关于如何它是如何实现的，但是了解 C++ 试图公开什么样的硬件操作是有用的。

For x initially zero, can I be sure that fire will be called at least once in this case?

是的，它会运行至少一次。它可以运行两次，因为两次加载都可能看到第二次 fetch_add.

的结果

负载总是看到 x 的值至少由 fetch_add 在其自己的线程中更新。 memory_order_relaxed 不允许线程观察其自身操作的乱序， 和 fetch_add 确实按某种顺序发生。所以至少 "goes second" 的线程会看到 x == 3.

无法预测顺序是什么。您可以通过查看 fetch_add 的 return 值来观察它，而不是使用单独的负载。（此代码不遵守 fetch_add 建立的顺序，因为多个线程可以获得相同的值。为此，您需要将值捕获为单个原子操作的一部分。）

I'm also curious about the ordering. There is a clear dependency between x modification and load, therefore I suppose these instructions not to be reordered in spite of the fact that relaxed order is specified.

运行时和编译时的内存重新排序，以及乱序执行，都保留了单个线程的行为。所有这些东西（包括编译器的 "as-if rule"）的黄金法则是 "don't break single-threaded code"。

但无法保证这些操作对其他线程全局可见的顺序。 x.fetch_add 的存储部分可以在 x.load 之后对其他个线程全局可见。它不会在 x86 上，因为 x86 不会重新排序来自同一地址的稍后加载的存储（但允许对其他地址进行 StoreLoad 重新排序，。）

第三个线程可能会看到 T1 和 T2 的操作发生的顺序与 T1 看到 T2 的操作的顺序不同。（即 不必是所有线程都同意的总顺序，除非您使用顺序一致性 。）

请注意，"observing" 加载变得全局可见只能是间接的：通过查看线程完成的其他存储，找出必须加载的值。但是负载是订购中真正重要的部分。

因此，如果 fire() 向内存中写入内容，第 3 个线程可以在它仍然看到 x==0 时看到它的发生。 只有当它看起来（对线程 3）就像 T1 的加载发生在任一线程中的 fetch_add 之前。即使线程 3 使用 x.fetch_add(mo_relaxed) 来观察 x 中的值，C++ 也允许这样做。但正如我所说，您不会在 x86 上看到它。

请注意，"dependency ordering" 是一个具有另一种含义的短语。即使在弱排序的 CPU 上，加载一个指针然后取消引用它也可以保证 LoadLoad 重新排序不会在两者之间发生。只有一种架构没有这样做：Alpha 需要一个屏障才能工作。这是 memory_order_consume 和 memory_order_relaxed 分开的原因之一。

您可以使用 memory_order_consume 而不是 memory_order_acquire 以更便宜地与 mo_release 生产者同步，如果它正在发布指针。（编译器通常只是加强 consume to acquire，因为它很难实现。）

依赖排序的mo_consume含义适用于两个不同的内存位置：指针和缓冲区。这与线程总是按顺序查看自己的操作完全不同。

当只有一个对象时，线程总是会看到至少与其最近存储一样新的数据。（新的是它观察操作的顺序，而不是绝对时间中的新！这只是意味着线程不能存储一个值，然后在下一次读取时发现该值从已经存储的存储中恢复为一个fetch_add之前见过。）

推理这些东西并不容易（例如，其他线程看到的全局顺序与涉及的线程之一看到的顺序）。列举所有可能或不可能的令人惊讶的重新排序也很棘手。

lock-free and stdatomic tag wikis. I'd especially recommend Jeff Preshing's blog 中有一些链接。他解释得很好，并且发表了很多好文章。

无锁编程：原子值有多新鲜？

Lock-free programming: how fresh is atomic value?

multithreading

c++11

concurrency

atomic

lock-free