在这个角落的情况下,C++ 11内存排序保证是什么？

Question

我正在编写一些无锁代码,我想出了一个有趣的模式,但我不确定它是否会在轻松的内存排序下表现得如预期.

解释它的最简单方法是使用一个例子:

std::atomic<int> a, b, c;

auto a_local = a.load(std::memory_order_relaxed);
auto b_local = b.load(std::memory_order_relaxed);
if (a_local < b_local) {
    auto c_local = c.fetch_add(1, std::memory_order_relaxed);
}

请注意,所有操作都使用std::memory_order_relaxed.

显然,在这上,负载为执行的线程a,并b在之前必须完成if情况进行评估.

类似地,读取 - 修改 - 写入(RMW)操作c必须在评估条件之后完成(因为它以条件为条件).

我想知道的是,这段代码保证的价值c_local至少高达最新的值a_local和b_local？如果是这样,如果放宽内存排序,这怎么可能？控制依赖是否与RWM操作一起充当某种获取范围？(请注意,在任何地方都没有相应的版本.)

如果上述情况属实,我相信这个例子也应该有效(假设没有溢出) - 我是对的吗？

std::atomic<int> a(0), b(0);

// Thread 1
while (true) {
    auto a_local = a.fetch_add(1, std::memory_order_relaxed);
    if (a_local >= 0) {    // Always true at runtime
        b.fetch_add(1, std::memory_order_relaxed);
    }
}

// Thread 2
auto b_local = b.load(std::memory_order_relaxed);
if (b_local < 777) {
    // Note that fetch_add returns the pre-incrementation value
    auto a_local = a.fetch_add(1, std::memory_order_relaxed);
    assert(b_local <= a_local);    // Is this guaranteed?
}

在线程1上,有一个控制依赖项,我怀疑它a总是在递增之前b递增(但它们每个都保持增加的颈部和颈部).在线程2上,还有另一个控制依赖项,我怀疑在加之前b加载的保证.我还认为从中返回的值至少与任何观察到的值一样近,因此应该保持.但我不确定,因为这与通常的内存排序示例有很大不同,而且我对C++ 11内存模型的理解并不完美(我无法在任何程度的确定性下推理这些内存排序效果).任何见解将不胜感激!b_localafetch_addb_localassert

---

更新:正如bames53在评论中有所指出,给定一个足够智能的编译器,可能if在适当的情况下可以完全优化,在这种情况下,松弛的负载可以重新排序在RMW之后发生,导致它们的值比fetch_add返回值更新(assert可能在我的第二个例子中触发).但是,如果不插入if,则插入atomic_signal_fence(未atomic_thread_fence)？无论做了什么优化,编译器当然都不能忽略它,但它确保代码的行为符合预期吗？在这种情况下,CPU是否允许进行任何重新排序？

然后第二个例子变为:

std::atomic<int> a(0), b(0);

// Thread 1
while (true) {
    auto a_local = a.fetch_add(1, std::memory_order_relaxed);
    std::atomic_signal_fence(std::memory_order_acq_rel);
    b.fetch_add(1, std::memory_order_relaxed);
}

// Thread 2
auto b_local = b.load(std::memory_order_relaxed);
std::atomic_signal_fence(std::memory_order_acq_rel);
// Note that fetch_add returns the pre-incrementation value
auto a_local = a.fetch_add(1, std::memory_order_relaxed);
assert(b_local <= a_local);    // Is this guaranteed?

---

另一个更新:在阅读了目前为止的所有回复并自己梳理标准之后,我认为只能使用标准来证明代码是正确的.那么,任何人都可以提出一个符合标准的理论体系的反例,并且还会触发断言吗？

Answer 1

这个例子展示了一种类似凭空读取的行为。规范中的相关讨论在第 29.3p9-11 节中。由于当前版本的 C11 标准不保证遵守依赖性，因此内存模型应该允许触发断言。最可能的情况是编译器优化掉了 a_local>=0 的检查。但即使你用信号栅栏替换该检查，CPU 也可以自由地重新排序这些指令。您可以使用开源 CDSChecker 工具在 C/C++11 内存模型下测试此类代码示例。您的示例中有趣的问题是，对于违反断言的执行，必须存在依赖循环。更具体地说：

由于 if 条件，线程一中的 b.fetch_add 取决于同一循环迭代中的 a.fetch_add 。线程2中的a.fetch_add依赖于b.load。对于断言违规，我们必须在比 T2 的 a.fetch_add 更晚的循环迭代中从 b.fetch_add 读取 T2 的 b.load。现在考虑 b.load 从中读取的 b.fetch_add 并将其命名为 # 以供将来参考。我们知道 b.load 依赖于 #，因为它从 # 获取值。

我们知道#必须依赖于T2的a.fetch_add，因为T2的a.fetch_add原子在与#相同的循环迭代中从T1读取并更新先前的a.fetch_add。所以我们知道 # 依赖于线程 2 中的 a.fetch_add。这给了我们一个依赖循环，这很奇怪，但 C/C++ 内存模型允许。实际产生该循环的最可能的方式是 (1) 编译器发现 a.local 始终大于 0，从而打破依赖性。然后它可以根据需要进行循环展开并重新排序 T1 的 fetch_add 。