为什么n4507中提到的并行for_each可能会导致死锁，循环体中有一个自旋等待？

Question

请参阅来自 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4507.pdf，第 12 页的以下代码：

using namespace std::experimental::parallel;
std::atomic<int> x = 0;
int a[] = {1,2};
for_each(par, std::begin(a), std::end(a), [&](int n) {
  x.fetch_add(1, std::memory_order_relaxed);
  // spin wait for another iteration to change the value of x
  while (x.load(std::memory_order_relaxed) == 1) { }
});

本例附有注释：

上面的例子取决于迭代的执行顺序， 因此是未定义的（可能会死锁）。

但我不明白为什么它可能会导致僵局。据我了解，虽然内存顺序被指定为

std::memory_order_relaxed

，但这只是关于一个线程看到另一个线程所做的一些更改的时间，因此最终（在可能无限的时间之后）无论如何，更改都应该被阅读主题。

有人可以解释一下吗？谢谢！

Answer 1

示例代码可能死锁的原因与

memory_order_relaxed

的使用无关。

对原子变量的更改将变得对另一个核心可见，如果不可见（根据标准，它应该变得可见）， 它与内存排序无关，内存排序仅用于指定other内存操作相对于原子操作的排序方式。

链接引用的文档中给出的示例可能会死锁，因为显然不能保证执行真正并发。在后来的草案（N4640）中，对文本进行了修改：

...取决于迭代的执行顺序，如果两个迭代在同一执行线程上顺序执行，则不会终止。

这就是这一切的意义所在；如果两次迭代都按顺序执行，则第一次迭代将继续旋转一个永远不会改变的值。

Answer 2

线程在等待时正在读取新值，因此在某些时候它们应该看到它们所做的更改，正如我所理解的。

不，没有。

宽松的内存顺序并不意味着“来自其他线程的东西最终可能会在这次读取之前排序”。这意味着“在读取之前，其他线程中的内容不会被排序”。也就是说，任何其他写入都可能永远变得可见。

因此 UB。

现在在实际系统上，放宽的内存顺序（特别是无锁原子）完全有可能仍然使其他线程的修改可见。但就标准而言，这就是UB。过度热心的编译器确实可以将您的代码编译成硬代码，而不会费心从变量中读取，因为它知道它无法看到其他线程的更改。

Answer 3

使增量原子化但是

x.fetch_add

不是线程的同步点，因此任何两个线程可以同时拥有 1。因为读取-修改-写入在没有同步的情况下启动，因此无法获得所需的 x 值。