seq_cst顺序在IRIW文献测试中如何正式保证结果?

huangapple go评论71阅读模式
英文:

How does seq_cst order formally guarantee the result in an IRIW litmus test?

问题

考虑这个例子来自cppreference

#include <thread>
#include <atomic>
#include <cassert>
 
std::atomic<bool> x = {false};
std::atomic<bool> y = {false};
std::atomic<int> z = {0};
 
void write_x()
{
    x.store(true, std::memory_order_seq_cst);  // #1
}
 
void write_y()
{
    y.store(true, std::memory_order_seq_cst); // #2
}
 
void read_x_then_y()
{
    while (!x.load(std::memory_order_seq_cst))  // #3
        ;
    if (y.load(std::memory_order_seq_cst)) {  // #4
        ++z;
    }
}
 
void read_y_then_x()
{
    while (!y.load(std::memory_order_seq_cst))  // #5
        ;
    if (x.load(std::memory_order_seq_cst)) {  // #6
        ++z;
    }
}
 
int main()
{
    std::thread a(write_x);
    std::thread b(write_y);
    std::thread c(read_x_then_y);
    std::thread d(read_y_then_x);
    a.join(); b.join(); c.join(); d.join();
    assert(z.load() != 0);  // will never happen
}

为了证明assert永远不会发生,我们应该证明y-store发生在y-load-in-if之前,或者x-store发生在x-load-in-if之前,或者两者都发生。它们将确保z的值至少大于0,这使得assert永远不会发生,根据下面的规则。

由评估B确定的原子对象M的值,应该是由修改M的一些副作用A存储的值,其中B不会在A之前发生。

如果修改原子对象M的操作A在修改M的操作B之前发生,那么A应该在M的修改顺序中早于B。

如果原子对象M的值计算A在M的值计算B之前发生,并且A的值来自M上的副作用X,那么B计算的值应该是X上存储的值或者M上的副作用Y上存储的值,其中Y在M的修改顺序中跟随X。

如果原子对象M的值计算A在修改M的操作B之前发生,那么A应该从M上的副作用X取其值,其中X在M的修改顺序中在B之前。

如果原子对象M上的副作用X在M的值计算B之前发生,那么评估B应该从X上或者M的修改顺序中跟随X的副作用Y上取其值。

然而,我们只能得到这些条件

1. x-store同步x-load-in-while
2. y-store同步y-load-in-while
3. x-load-while在y-load-in-if之前被排序
4. y-load-while在x-load-in-if之前被排序

根据[intro.races] p10,第1点和第3点给出:

x-store线程间先于y-load-in-if发生

第2点和第4点给出:

y-store线程间先于x-load-in-if发生

然后,我无法找到任何可以证明y-store发生在y-load-in-if之前,或者x-store发生在x-load-in-if之前的关联。这种情况的特殊之处在于它们都是seq操作,因此还有一个额外的规则,称为单一总顺序S。即使有了这个规则,我只能得出以下结论:

1. x-store < x-load-in-while < y-load-in-if,在S中
2. y-store < y-load-in-while < x-load-in-if,在S中

符号<表示在S中先于。除了这些结论,我无法得到更多的信息来解释为什么断言永远不会发生。如何正确地使用当前的C++标准来解释这种情况?

英文:

Consider this example from cppreference

#include &lt;thread&gt;
#include &lt;atomic&gt;
#include &lt;cassert&gt;
 
std::atomic&lt;bool&gt; x = {false};
std::atomic&lt;bool&gt; y = {false};
std::atomic&lt;int&gt; z = {0};
 
void write_x()
{
    x.store(true, std::memory_order_seq_cst);  // #1
}
 
void write_y()
{
    y.store(true, std::memory_order_seq_cst); // #2
}
 
void read_x_then_y()
{
    while (!x.load(std::memory_order_seq_cst))  // #3
        ;
    if (y.load(std::memory_order_seq_cst)) {  // #4
        ++z;
    }
}
 
void read_y_then_x()
{
    while (!y.load(std::memory_order_seq_cst))  // #5
        ;
    if (x.load(std::memory_order_seq_cst)) {  // #6
        ++z;
    }
}
 
int main()
{
    std::thread a(write_x);
    std::thread b(write_y);
    std::thread c(read_x_then_y);
    std::thread d(read_y_then_x);
    a.join(); b.join(); c.join(); d.join();
    assert(z.load() != 0);  // will never happen
}

In order to prove the assert will never happen, we should prove either y-store happens before y-load-in-if, or x-store happens before x-load-in-if, or both. They will guarantee the value of z should be at least greater than 0, which makes the assert never happen, as per the below rules.

> The value of an atomic object M, as determined by evaluation B, shall be the value stored by some side effect A that modifies M, where B does not happen before A.

> If an operation A that modifies an atomic object M happens before an operation B that modifies M, then A shall be earlier than B in the modification order of M.

> If a value computation A of an atomic object M happens before a value computation B of M, and A takes its value from a side effect X on M, then the value computed by B shall either be the value stored by X or the value stored by a side effect Y on M, where Y follows X in the modification order of M.

> If a value computation A of an atomic object M happens before an operation B that modifies M, then A shall take its value from a side effect X on M, where X precedes B in the modification order of M.

> If a side effect X on an atomic object M happens before a value computation B of M, then the evaluation B shall take its value from X or from a side effect Y that follows X in the modification order of M.

However, we can only have these conditions

1. x-store synchronizes x-load-in-while
2. y-store synchronizes y-load-in-while
3. x-load-while is sequenced before y-load-in-if
4. y-load-while is sequenced before x-load-in-if 

According to [intro.races] p10, bullet 1 and 3 give:
> x-store inter-thread happens before y-load-in-if

bullet 2 and 4 give:
> y-store inter-thread happens before x-load-in-if

Then, I cannot find any association that can prove y-store happens before y-load-in-if, or x-store happens before x-load-in-if. The special for this case is they are all seq operations, so there is also an extra rule, called single total order S. Even with that rule, I can only conclude the following things:

1. x-store &lt; x-load-in-while &lt; y-load-in-if, in S
2. y-store &lt; y-load-in-while &lt; x-load-in-if, in S

The symbol &lt; means precedes. Apart from these conclusions, I cannot get more information that can interpret why the assertion will never happen. How to correctly use the current C++ standard to interpret this case?

答案1

得分: 5

不翻译代码部分。只返回翻译好的内容:

  • ++z (位于 #4#6) 都发生在 main 中的 z.load() 之前(thread.thread.member/4intro.races/910.2),如果它们确实发生。

  • 这些副作用必然对加载操作可见(intro.races/18),所以唯一让 assert 触发的方式是 #4#6 都读取 false

  • read_x_then_y 中,#3 读取 #1 写入的 true,这意味着 #1#3 之前的一致性排序(atomics.order/3.1),并且 #3#4 处加载 y 之前强烈发生(intro.races/12.1)。

  • #4 读取 false 会使它在 #1 写入 true 之前一致性排序(atomics.order/3.3,其中 Xfalse 的初始写入)。

  • 进行一些澄清:

    • atomics.order/3.3 中的第一部分只是说明 AB 必须是不同的原子操作,它不仅限于读-修改-写操作。P0668 纸张引入了这个措辞,总结如下:

    第三个要点对应于通常所说的 "读发生在写之前":A 读取了先于 B 的写入。

    • 对象的初始化从技术上来说不算是副作用,这是 CWG2587 的讨论主题,不仅限于原子操作。我认为这里的意图很清楚,规则包括初始化时谈到副作用。

    • y 的(常量)初始化是否发生在 #2 之前是标准(按我的理解)未明确规定的另一点,但我们可以再次应用常识:如果它不在 #2 之前发生,那么这个程序会有未定义行为,因为它访问了一个生命周期之外的对象(res.on.objects/2),任何进一步的分析都没有意义。这当然是荒谬的,所以我们假设 #2 确实在 y 初始化之后发生,并且它遵循 y 的修改顺序中的初始化(intro.races/15)。

  • 这个分析给出了总操作顺序 Sseq_cst 操作的顺序 #1 < #3 < #4 < #2,其中 #4read_x_then_y 中读取 false

  • 对于 read_y_then_x,重复相同的过程(再次假设 #6 得到 false)得出 #2 < #5 < #6 < #1

  • 在第一种情况下,#1S 中排在 #2 前面,在第二种情况下,#2S 中排在 #1 前面。显然,没有可能的 S 能同时与这两者保持一致,这意味着 #4#6 不能在这个程序的任何可能执行中都读取 false。引用 P0668:

如果这些约束无法满足任何总顺序 S,那么产生一致性顺序的候选执行是无效的。

英文:

Both ++z (at #4 and #6) happen before z.load() in main ([thread.thread.member]/4, [intro.races]/9, /10.2), if they happen at all.

These side effects are necessarily visible to the load ([intro.races]/18), so the only way for the assert to fire is for both #4 and #6 to read false.

In read_x_then_y, #3 reads true written by #1, meaning #1 is coherence-ordered before #3 ([atomics.order]/3.1), and #3 strongly happens before the load of y at #4 ([intro.races]/12.1).

#4 reading false would make it coherence-ordered before the write of true at #1 ([atomics.order]/3.3, where X is the initial 'write' of false).


Few points of clarification here:

  • The first part of [atomics.order]/3.3 simply states that A and B must be different atomic operations, it does not limit the scope of this bullet to just read-modify-write ones. P0668, the paper that introduced the wording, summarizes:
    > The third bullet corresponds to what's often called "reads before": A reads a write earlier than B.

  • Initialization of an object not technically being a side effect is the subject of CWG2587, and is not unique to atomics. I think it is clear enough that the intent here is that these rules include initialization when talking about side effects.

  • (Constant) initialization of y happening before #2 is another point that the standard (by my reading, at least) fails to explicitly specify, but we can once again apply common sense: if it doesn't happen before #2, this program has undefined behavior because it accesses an out-of-lifetime object ([res.on.objects]/2), and any further analysis is meaningless. That would of course be absurd, so we'll assume that #2 does in fact happen after y is initialized, and as such it follows the initialization in the modification order of y ([intro.races]/15).


This analysis gives us the ordering #1 &lt; #3 &lt; #4 &lt; #2 in the total order S of seq_cst operations ([atomics.order]/4) on an execution where #4 in read_x_then_y reads false.

Repeating the same for read_y_then_x (once again assuming #6 gets false) yields #2 &lt; #5 &lt; #6 &lt; #1.

In the first case, #1 precedes #2 in S, in the second case, #2 precedes #1. Clearly, there's no possible S that is consistent with both of these, meaning #4 and #6 can't both read false on any possible execution of this program. Quoting P0668 again:
> If these constraints are not satisfiable by any total order S, then the candidate execution which gave rise to the coherence order is not valid.

答案2

得分: 1

考虑 S 中的两种可能性之一,即 x-store < y-storey-store < x-store。这两者之一必须为真,因为这两个存储都是所有 SC 操作的总序的一部分。

对于每种情况,read 函数中的一个明显会由于 S 中的加载顺序而增加 z 的值。(而另一个函数也可能在两个存储都变得可见后增加;第二个加载可以在两个存储都变得可见之后发生。)

同步与无关,write_xwrite_y 中没有我们可以看到的先前操作。


非正式地说,所有原子操作的单一总序的存在(即使在不同对象上)是保证所有线程都同意两个独立存储的顺序的基础;这是 IRIW(独立读取者,独立写入者)的检验。

一个 C++ 程序,它没有数据竞争并对所有原子操作使用 seq_cst,其行为可以解释为源代码顺序的某种交错执行。即无数据竞争的程序的顺序一致执行,SC-DRF。

有趣的是,在 CPU 内存模型中,只有最弱的模型实际允许 IRIW 的“重新排序”,而实际执行它的真正硬件(不管纸面上允许什么)实际上更加罕见。例如,ARMv8 不允许它,但在其他方面相当弱;ARMv7 允许它,但没有 ARM 硬件实际执行它。只要存储数据只通过一致缓存对其他核心可见,所有核心就会同意存储顺序,这远不及顺序一致性强,并且如果你使用了 seq_cst 之外的内容,z == 0 将是允许的。

英文:

Consider each of the two possibilities, x-store &lt; y-store in S, or y-store &lt; x-store in S. One or the other of those must be true, because both stores are part of the total order of all SC operations.

For each case, one of the read functions will provably increment z due to the order of the loads in S. (And the other function might also happen to increment; the second load could happen after both stores have become visible.)

Syncs-with is irrelevant, there are no earlier operations in write_x or write_y for us to see.


Informally, the existence of a single total order of all atomic operations (even on different objects) is what guarantees that all threads agree on the order of two independent stores; this is an IRIW litmus test. (Independent Readers, Independent Writers).

A C++ program that's data-race free and uses seq_cst for all its atomic operations behaves in a way that's explainable as some interleaving of source order. i.e. sequentially consistent execution of data-race free programs, SC-DRF.

Fun fact: in CPU memory models, only the weakest models actually allow IRIW "reordering" and real hardware that actually does it (regardless of what's allowed on paper) is even rarer. e.g. ARMv8 disallows it but otherwise is quite weak; ARMv7 allowed it but no ARM hardware ever did it. Having all cores agree on a store order is vastly weaker than sequential consistency, and happens automatically if store data only becomes visible to other cores via coherent cache.

But in C++, only seq_cst forbids it; if you'd used acq_rel (or release for the stores and acquire for the loads), z == 0 would be allowed.

答案3

得分: 1

  1. 根据此内容:

<sup>3</sup> 对某个原子对象 M 上的原子操作 A 如果_在一致性顺序之前_另一个原子操作 B,则
<sup>(3.1)</sup> — A 是一个修改操作,且 B 读取 A 存储的值,或
<sup>(3.2)</sup> — AM 的修改顺序中位于 B 之前,或
<sup>(3.3)</sup> — AB 不是相同的原子读取-修改-写操作,并存在 M 的原子修改 X,使得 A 读取 X 存储的值,且 XM 的修改顺序中位于 B 之前,或
<sup>(3.4)</sup> — 存在 M 的原子修改 X,使得 AX 之前_在一致性顺序之前_,且 XB 之前_在一致性顺序之前_。

如果我们希望 x-load-in-ify-load-in-if 返回 false,我们需要以下的_在一致性顺序之前_关系:

  • 对于 xx-load-in-if -&gt; x-store -&gt; x-load-in-while
  • 对于 yy-load-in-if -&gt; y-store -&gt; y-load-in-while
  1. 根据此内容:

<sup>12</sup> 如果一个评估 A 强发生在 评估 D 之前,那么要么
<sup>(12.1)</sup> — AD 之前有序,或
<sup>(12.2)</sup> — AD 同步,并且 AD 都是顺序一致的原子操作 ([atomics.order]),或
<sup>(12.3)</sup> — 存在评估 BC,使得 AB 之前有序,BC 之前简单发生,且 CD 之前有序,或
<sup>(12.4)</sup> — 存在评估 B,使得 A 强发生在 B 之前,且 B 强发生在 D 之前。
[注 11: 简单来说,如果 A 强发生在 B 之前,那么在所有上下文中 A 看起来在 B 之前被评估。 强发生在之前不包括消费操作。 — 结尾注]

这是我们示例的_强发生在_关系:

  • x-store -&gt; x-load-in-while -&gt; y-load-in-if
  • y-store -&gt; y-load-in-while -&gt; x-load-in-if
  1. 根据此内容:

<sup>4</sup> 存在一个对所有 memory_&#173;order​::​seq_&#173;cst 操作的单一总序列 S,包括屏障,满足以下约束。首先,如果 AB 都是 memory_&#173;order​::​seq_&#173;cst 操作,且 A 强发生在 B 之前,那么 AS 中位于 B 之前。其次,对于对象 M 上的每一对原子操作 AB,其中 A 在_一致性顺序之前_ B,需要满足以下四个条件:
<sup>(4.1)</sup> — 如果 AB 都是 memory_&#173;order​::​seq_&#173;cst 操作,那么 AS 中位于 B 之前;和
...

我们需要将所有操作放入一个单一总序列 S,同时保留以下两点:

  • _一致性顺序之前_关系:
    • x-load-in-if -&gt; x-store -&gt; x-load-in-while
    • y-load-in-if -&gt; y-store -&gt; y-load-in-while
  • 和_强发生在_关系:
    • x-store -&gt; x-load-in-while -&gt; y-load-in-if
    • y-store -&gt; y-load-in-while -&gt; x-load-in-if

首先让我们看看_强发生在_关系:

  • 无论您如何将操作放入单一总序列 Sy-load-in-ifx-load-in-if 将是最后一个操作
  • 如果 x-load-in-if 是最后一个操作,那么 x-store -&gt; x-load-in-ifS 中,但根据_一致性顺序之前_,它应该是 x-load-in-if -&gt; x-storeS 中 => 矛盾。
  • y-load-in-ifS 中的最后一个操作时,相同的逻辑也适用。

因此,C++ 不允许同时返回 false(且

英文:
  1. According to this:
    > <sup>3</sup> An atomic operation A on some atomic object M is coherence-ordered before another atomic operation B on M if
    > <sup>(3.1)</sup> — A is a modification, and B reads the value stored by A, or
    > <sup>(3.2)</sup> — A precedes B in the modification order of M, or
    > <sup>(3.3)</sup> — A and B are not the same atomic read-modify-write operation, and there exists an atomic modification X of M such that A reads the value stored by X and X precedes B in the modification order of M, or
    > <sup>(3.4)</sup> — there exists an atomic modification X of M such that A is coherence-ordered before X and X is coherence-ordered before B.

we need the following coherence-ordered before relations if we want x-load-in-if and y-load-in-if to return false:

  • for x: x-load-in-if -&gt; x-store -&gt; x-load-in-while
  • for y: y-load-in-if -&gt; y-store -&gt; y-load-in-while
  1. According to this:
    > <sup>12</sup> An evaluation A strongly happens before an evaluation D if, either
    > <sup>(12.1)</sup> — A is sequenced before D, or
    > <sup>(12.2)</sup> — A synchronizes with D, and both A and D are sequentially consistent atomic operations ([atomics.order]), or
    > <sup>(12.3)</sup> — there are evaluations B and C such that A is sequenced before B, B simply happens before C, and C is sequenced before D, or
    > <sup>(12.4)</sup> — there is an evaluation B such that A strongly happens before B, and B strongly happens before D.
    > [Note 11: Informally, if A strongly happens before B, then A appears to be evaluated before B in all contexts. Strongly happens before excludes consume operations. — end note]

these are the strongly happens before relations for our example:

  • x-store -&gt; x-load-in-while -&gt; y-load-in-if
  • y-store -&gt; y-load-in-while -&gt; x-load-in-if
  1. According to this:
    > <sup>4</sup> There is a single total order S on all memory_&#173;order​::​seq_&#173;cst operations, including fences, that satisfies the following constraints. First, if A and B are memory_&#173;order​::​seq_&#173;cst operations and A strongly happens before B, then A precedes B in S. Second, for every pair of atomic operations A and B on an object M, where A is coherence-ordered before B, the following four conditions are required to be satisfied by S:
    > <sup>(4.1)</sup> — if A and B are both memory_&#173;order​::​seq_&#173;cst operations, then A precedes B in S; and
    > ...

we need to put all the operations in a single total order S, while preserving both:

  • coherence-ordered before relations:
    • x-load-in-if -&gt; x-store -&gt; x-load-in-while
    • y-load-in-if -&gt; y-store -&gt; y-load-in-while
  • and strongly happens before relations:
    • x-store -&gt; x-load-in-while -&gt; y-load-in-if
    • y-store -&gt; y-load-in-while -&gt; x-load-in-if

Let's first look at strongly happens before relations:

  • no matter how exactly you put the operations in a single total order S, either y-load-in-if or x-load-in-if will be the last operation
  • if x-load-in-if will be the last operation, then x-store -&gt; x-load-in-if in S, but according to coherence-ordered before it should be x-load-in-if -&gt; x-store in S => contradiction.
    The same logic works when y-load-in-if is the last operation in S.

As a result, executions where both x-load-in-if and y-load-in-if return false (and z=0) aren't allowed in C++.

huangapple
  • 本文由 发表于 2023年3月3日 17:51:14
  • 转载请务必保留本文链接:https://go.coder-hub.com/75625523.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定