21

我正在编写一些无锁代码，并且想出了一个有趣的模式，但我不确定它在宽松的内存排序下是否会按预期运行。

解释它的最简单方法是使用示例：

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

c类似地，必须在评估条件后执行读取-修改-写入 (RMW) 操作（因为它以该条件为条件）。

我想知道的是，这段代码是否保证 的值c_local至少与a_localand的值一样最新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加载到b_local之前a会增加。我还认为，从返回的值fetch_add将至少与 中的任何观察值一样新b_local，assert因此应该成立。但我不确定，因为这与通常的内存排序示例大相径庭，而且我对 C++11 内存模型的理解并不完美（我无法确定地推理这些内存排序效果）。任何见解将不胜感激！

更新：正如 bames53 在评论中有用地指出的那样，给定一个足够智能的编译器，有可能if在适当的情况下完全优化an比fetch_add返回值更新（assert在我的第二个示例中可能会触发）。但是，如果插入(not ) 而不是ifan怎么办？不管做了什么优化，编译器肯定不能忽略这一点，但它是否确保代码的行为符合预期？在这种情况下，CPU 是否允许进行任何重新排序？atomic_signal_fenceatomic_thread_fence

然后第二个示例变为：

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?

另一个更新：在阅读了到目前为止的所有回复并自己梳理了标准之后，我认为仅使用标准不能证明代码是正确的。那么，任何人都可以提出一个符合标准并触发断言的理论系统的反例吗？

4

3 回答 3

4
于 2013-08-25T15:45:24.950 回答
3

这个例子得到了类似从稀薄空气中读取的行为的变体。规范中的相关讨论在第 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。

于 2013-09-02T05:18:02.527 回答
0

在阅读了到目前为止的所有回复并自己梳理了标准之后，我认为仅使用标准不能证明代码是正确的。

除非你承认非原子操作比原子操作更安全、更有序（这很愚蠢），并且没有原子操作（andtry_lock和shared_ptr::count）的 C++ 有一个语义，而对于那些不按顺序执行的特性，还有另一种语义，您还必须承认，根本没有任何程序可以被证明是正确的，因为非原子操作没有“顺序”，并且需要它们来构造和销毁变量。

或者，您不再将标准文本作为语言中唯一的词，而是使用一些常识，这总是被推荐的。

于 2019-11-26T23:18:47.793 回答