是什么正式保证非原子变量不能看到无中生有的值并创建像原子松弛理论上可以的数据竞争?

What formally guarantees that non-atomic variables can't see out-of-thin-air values and create a data race like atomic relaxed theoretically can?

这是一个关于 C++ 标准的正式保证的问题。

标准指出 std::memory_order_relaxed 原子变量的规则允许 "out of thin air" / "out of the blue" 值出现。

但是对于非原子变量,这个例子能有UB吗? r1 == r2 == 42 在 C++ 抽象机中可能吗?两个变量 == 42 最初都没有,所以你期望 if 主体都不应该执行,这意味着没有写入共享变量。

// Global state
int x = 0, y = 0;

// Thread 1:
r1 = x;
if (r1 == 42) y = r1;

// Thread 2:
r2 = y;
if (r2 == 42) x = 42;

以上示例改编自标准,explicitly says such behavior is allowed by the specification 用于原子对象:

[Note: The requirements do allow r1 == r2 == 42 in the following example, with x and y initially zero:

// Thread 1:
r1 = x.load(memory_order_relaxed);
if (r1 == 42) y.store(r1, memory_order_relaxed);
// Thread 2:
r2 = y.load(memory_order_relaxed);
if (r2 == 42) x.store(42, memory_order_relaxed);

However, implementations should not allow such behavior. – end note]

所谓的 "memory model" 的哪一部分保护非原子对象免受由读取看到凭空值 ?


当竞争条件 存在且 xy 具有 不同的 值时,是什么保证了读取共享变量(正常,非原子)看不到这样的值?

未执行的 if 机构能否创造导致数据竞争的自我实现条件?

When a race condition potentially exists, what guarantees that a read of a shared variable (normal, non atomic) cannot see a write

没有这样的保证。

存在竞争条件时,程序的行为未定义:

[intro.races]

Two actions are potentially concurrent if

  • they are performed by different threads, or
  • they are unsequenced, at least one is performed by a signal handler, and they are not both performed by the same signal handler invocation.

The execution of a program contains a data race if it contains two potentially concurrent conflicting actions, at least one of which is not atomic, and neither happens before the other, except for the special case for signal handlers described below. Any such data race results in undefined behavior. ...

特例与问题关系不大,但为了完整起见,我将其包括在内:

Two accesses to the same object of type volatile std::sig_­atomic_­t do not result in a data race if both occur in the same thread, even if one or more occurs in a signal handler. ...

What part of the so called "memory model" protects non atomic objects from these interactions caused by reads that see the interaction?

None。事实上,你会得到相反的结果,标准明确地将其称为未定义行为。在 [intro.races] 我们有

The execution of a program contains a data race if it contains two potentially concurrent conflicting actions, at least one of which is not atomic, and neither happens before the other, except for the special case for signal handlers described below. Any such data race results in undefined behavior.

其中涵盖了您的第二个示例。


规则是,如果您在多个线程中共享数据,并且这些线程中至少有一个写入该共享数据,那么您需要同步。否则,您将面临数据竞争和未定义的行为。请注意 volatile 不是有效的同步机制。您需要 atomics/mutexs/condition 个变量来保护共享访问。

注:我这里举的具体例子显然不准确。我假设优化器可能比它显然允许的更激进。有。我将不得不对此进行进一步调查,但想在此处留下此注释作为警告。

其他人已经给了你答案,引用了标准的适当部分,这些部分明确指出你认为存在的保证,实际上并不存在。看起来你正在解释标准的一部分,如果你使用 memory_order_relaxed 表示原子对象允许某种奇怪的行为,这意味着 non-atomic 对象不允许这种行为。这是一个推理的飞跃,由标准的其他部分明确解决,这些部分声明了 non-atomic 对象未定义的行为。

实际上,这是线程 1 中可能发生的事件的顺序,这完全合理,但即使硬件保证所有内存访问在 CPUs。请记住,该标准不仅要考虑硬件的行为,还要考虑优化器的行为,优化器通常会主动 re-order 和 re-write 代码。

线程 1 可能被优化器 re-written 看成这样:

old_y = y; // old_y is a hidden variable (perhaps a register) created by the optimizer
y = 42;
if (x != 42) y = old_y;

优化器执行此操作可能有完全合理的理由。例如,它可能决定将 42 写入 y 的可能性要大得多,并且出于依赖性原因,如果将存储写入 y,管道可能会工作得更好宜早不宜迟。

规则是明显的结果必须看起来好像您编写的代码就是执行的代码。但并不要求您编写的代码与 CPU 实际被告知要执行的操作有任何相似之处。

原子变量对编译器 re-write 代码的能力施加了约束,并指示编译器发出特殊的 CPU 指令,这些指令对 CPU 到 re-order 内存访问。涉及 memory_order_relaxed 的约束比通常允许的约束要强得多。如果 xy 不是原子的,通常允许编译器完全删除任何引用。

此外,如果它们是原子的,编译器必须确保其他 CPUs 将整个变量视为具有新值或旧值。例如,如果变量是一个跨越高速缓存行边界的 32 位实体,并且修改涉及更改高速缓存行边界两侧的位,则 CPU 可能会看到从未写入的变量值因为它只看到缓存行边界一侧的位更新。但是用 memory_order_relaxed.

修饰的原子变量是不允许的

这就是标准将数据竞争标记为未定义行为的原因。 space 可能发生的事情可能比你想象的要多得多,而且肯定比任何标准都能合理涵盖的范围更广。

您的问题文本似乎缺少示例的要点和 out-of-thin-air 值。您的示例不包含 data-race UB。 (如果 xy 在这些线程 运行 之前被设置为 42,在这种情况下,所有的赌注都被关闭,其他答案引用 data-race UB申请。)

没有针对真实数据竞争的保护,只能针对 out-of-thin-air 值。

我认为您实际上是在问如何协调 mo_relaxed 示例与 non-atomic 变量的理智和 well-defined 行为。这就是这个答案所涵盖的内容。


该注释指出了原子 mo_relaxed 形式主义中的一个漏洞,不是 警告您可能对某些实现产生真正的影响。

这个差距不适用于(我认为)non-atomic 对象,mo_relaxed

他们说但是,实现不应该允许这样的行为。 – 尾注]。显然,标准委员会无法找到一种方法来正式确定该要求,所以现在它只是一个注释,而不是可选的。

很明显,尽管这不是严格规范的,但 C++ 标准 打算 禁止宽松原子的 out-of-thin-air 值(通常我假设)。后来的标准讨论,例如2018's p0668r5: Revising the C++ memory model(它没有“修复”这个,这是一个不相关的变化)包括多汁的 side-nodes 比如:

We still do not have an acceptable way to make our informal (since C++14) prohibition of out-of-thin-air results precise. The primary practical effect of that is that formal verification of C++ programs using relaxed atomics remains unfeasible. The above paper suggests a solution similar to http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3710.html . We continue to ignore the problem here ...

所以是的,relaxed_atomic 标准的规范部分显然比 non-atomic 弱。这似乎是他们如何定义规则的一个不幸的副作用。

据我所知,在现实生活中没有实现可以产生 out-of-thin-air 值。


以后版本的标准短语非正式推荐更清楚,例如在当前草案中:https://timsong-cpp.github.io/cppwp/atomics.order#8

  1. Implementations should ensure that no “out-of-thin-air” values are computed that circularly depend on their own computation.
    ...
  1. [ Note: The recommendation [of 8.] similarly disallows r1 == r2 == 42 in the following example, with x and y again initially zero:

       // Thread 1:
       r1 = x.load(memory_order::relaxed);
       if (r1 == 42) y.store(42, memory_order::relaxed);
       // Thread 2:
       r2 = y.load(memory_order::relaxed);
       if (r2 == 42) x.store(42, memory_order::relaxed);
    

    — end note ]


(答案的其余部分是在我确定标准 打算 也不允许 mo_relaxed 这样做之前写的。)

我很确定 C++ 抽象机允许r1 == r2 == 42.
C++ 抽象机操作中每个可能的操作顺序都会导致 r1=r2=0 没有 UB,即使没有同步。因此该程序没有 UB,任何 non-zero 结果将违反“as-if”规则

形式上,ISO C++ 允许实现以任何方式实现函数/程序,从而提供与 C++ 抽象机相同的结果。对于 multi-threaded 代码,实现可以选择一种可能的 abstract-machine 排序并确定该排序总是发生。 (例如,在为 strongly-ordered ISA 编译为 asm 时重新排序松散的原子存储时。编写的标准甚至允许合并原子存储,但 )。 但是程序的结果总是必须是抽象机器可以产生的东西。 (只有 Atomics 章节介绍了在没有互斥锁的情况下一个线程观察另一个线程的行为的可能性。否则,如果没有 data-race UB,这是不可能的)。

我认为其他答案对此不够仔细。 (第一次发布时我也没有)。 不执行的代码不会导致 UB(包括 data-race UB),并且不允许编译器发明写入到对象。 (除了已经 无条件地 写入它们的代码路径,例如 y = (x==42) ? 42 : y; 显然会创建 data-race UB。)

对于任何 non-atomic 对象,如果不 实际上 写入它,那么其他线程也可能正在读取它,而不管 not-executed 中的代码 if 块。该标准允许这样做,并且不允许在抽象机器尚未写入变量时突然将其读取为不同的值。 (对于我们甚至不读取的对象,例如相邻的数组元素,另一个线程甚至可能正在写入它们。)

因此,我们不能做任何让另一个线程暂时看到对象的不同值,或阻止其写入的事情。发明写入 non-atomic 对象基本上总是一个编译器错误;这是众所周知的,并且得到普遍认可,因为它可以破坏不包含 UB 的代码(并且在实践中已经这样做了一些创建它的编译器错误,例如 IA-64 GCC 我认为有一个这样的错误破坏 Linux 内核的点)。 IIRC,Herb Sutter 在他的演讲的第 1 部分或第 2 部分提到了此类错误,atomic<> Weapons: The C++ Memory Model and Modern Hardware",说在 C++11 之前它通常被认为是编译器错误,但 C++11 将其编纂并使其更容易确定。

或另一个最近的 x86 ICC 示例:


在 C++ 抽象机 中,执​​行无法达到 y = r1;x = r2;,无论加载的顺序或同时性如何b运行ch 条件。 xy 都读作 0 并且两个线程都没有写测试它们。

不需要同步来避免 UB,因为 abstract-machine 操作的顺序不会导致 data-race。 ISO C++ 标准对推测执行或 mis-speculation 到达代码时发生的情况没有任何说明。那是因为推测是真实实现的一个特征,不是抽象机的特征。确保遵守“as-if”规则取决于实现(硬件供应商和编译器编写者)。


在 C++ 中编写 if (global_id == mine) shared_var = 123; 这样的代码并让所有线程执行它是合法的,只要最多一个线程实际 运行 shared_var = 123; 语句。 (并且只要存在同步就可以避免 non-atomic int global_id 上的数据竞争)。如果像this这样的东西坏了,那就乱了。例如,您显然可以得出错误的结论,例如

观察到 non-write 没有发生并不是 data-race UB。

它也不是 运行 if(i<SIZE) return arr[i]; 的 UB,因为数组访问仅在 i 在边界内时发生。

我认为“出乎意料”value-invention 注释 显然适用于 relaxed-atomics,作为原子章节中对他们的特别警告。 (即便如此,据我所知,它实际上不会发生在任何真正的 C++ 实现上,当然不是主流实现。在这一点上,实现不必采取任何特殊措施来确保它不会发生 non-atomic变量。)

除了标准的原子章节之外,我不知道有任何类似的语言允许实现允许值像这样突然出现。

我没有看到任何理智的方式来论证 C++ 抽象机在执行此操作时会在任何时候导致 UB,但是看到 r1 == r2 == 42 将暗示发生了不同步的读写,但那是 data-raceUB。如果这可能发生,一个实现是否可以因为推测执行(或其他一些原因)而发明 UB?答案必须是“否”才能使 C++ 标准完全可用。

对于宽松的原子学,凭空发明 42 并不意味着 UB 已经发生;也许这就是标准说规则允许的原因?据我所知,标准的原子章节之外没有任何东西允许它。


可能导致这种情况的假设的 asm/硬件机制

(没有人想要这个,希望每个人都同意构建这样的硬件是一个坏主意。似乎不太可能在逻辑核心之间耦合推测永远值得在一个时回滚所有核心的缺点检测到错误预测或其他 mis-speculation.)

要使 42 成为可能,线程 1 必须查看线程 2 的推测存储,线程 2 的加载必须查看线程 1 的存储。 (确认b运行ch推测是正确的,让这条执行路径成为实际走的真实路径。)

即跨线程的推测:如果它们 运行 在同一个核心上并且只有一个轻量级的上下文切换,那么在当前的硬件上是可能的,例如协程或 green threads.

但是在当前的硬件上,在这种情况下线程之间的内存重新排序是不可能的。 Out-of-order 在同一个内核上执行代码给人一种一切都按程序顺序发生的错觉。要在线程之间进行内存重新排序,它们需要 运行 在不同的内核上运行。

所以我们需要一种将两个逻辑核心之间的推测耦合在一起的设计。没有人这样做,因为这意味着如果预测错误,则需要回滚更多状态检测到。但这在假设上是可能的。例如,一个 OoO SMT 核心允许 store-forwarding 在其逻辑核心之间甚至在它们从 out-of-order 核心退出之前(即成为 non-speculative)。

PowerPC 允许 store-forwarding 用于 retired 存储的逻辑内核,这意味着线程可以不同意存储的全局顺序。但是等到他们“毕业”(即退休)并成为 non-speculative 意味着它不会将对单独逻辑核心的推测联系在一起。因此,当一个人从 b运行ch 未命中中恢复时,其他人可以让 back-end 保持忙碌。如果他们都必须回滚任何逻辑核心的错误预测,那将破坏 SMT 的很大一部分优势。

我想了一会儿,我发现了一个在真正的 weakly-ordered CPUs 的单核上导致这个的顺序(线程之间有 user-space 上下文切换) ,但最后一步存储无法转发到第一步加载,因为这是程序顺序,OoO exec 保留了它。

  • T2:r2 = y; 停顿(例如高速缓存未命中)

  • T2:b运行ch预测预测r2 == 42为真。 ( x = 42 应该 运行.

  • T2:x = 42运行秒。 (仍然是推测;r2 = yhasn't obtained a value yet so ther2 == 42` compare/branch 仍在等待确认推测)

  • 到线程 1 的上下文切换发生 没有 将 CPU 回滚到退休状态或以其他方式等待推测被确认为好或检测为 mis-speculation.

    这部分不会发生在真正的 C++ 实现上,除非它们使用 M:N 线程模型,而不是更常见的 1:1 C++ 线程到 OS 线程。真正的 CPUs 不会重命名特权级别:它们不会中断或以其他方式进入内核,其中可能需要回滚并重做从不同架构状态进入内核模式的推测指令。

  • T1:r1 = x; 从投机 x = 42 存储中获取其值

  • T1:发现r1 == 42为真。 (B运行ch 推测也发生在这里,实际上并没有等待 store-forwarding 完成。但是沿着这条执行路径,x = 42 确实发生了,这个 b运行 ch 条件将执行并确认预测)。

  • T1: y = 42 运行s.

  • 这一切都在同一个 CPU 核心上,所以这个 y=42 存储在 r2=y 加载到 program-order 之后;它不能给负载一个 42 来确认 r2==42 推测。 所以这种可能的顺序毕竟并没有证明这一点。这就是为什么线程必须 运行 在单独的内核上使用 inter-thread 推测效果的原因这是可能的。

请注意 x = 42r2 没有数据依赖性,因此不需要 value-prediction 来实现这一点。 y=r1 无论如何都在 if(r1 == 42) 中,因此编译器可以根据需要优化到 y=42,从而打破另一个线程中的数据依赖性并使事情对称。

请注意,关于绿色线程或其他单核上下文切换的论点实际上并不相关:我们需要单独的内核来进行内存重新排序。


我之前评论说我认为这可能涉及value-prediction。 ISO C++ 标准的内存模型当然弱到足以允许使用 value-prediction 可以创建的疯狂“重新排序”,但这种重新排序不是必需的。 y=r1 可以优化为 y=42,并且原始代码无论如何都包含 x=42,因此该存储对 r2=y 负载没有数据依赖性。 42 的推测存储很容易在没有价值预测的情况下实现。 (问题是让其他线程看到它们!)

推测是因为b运行ch预测而不是值预测这里效果一样。在这两种情况下,负载最终都需要看到 42 以确认推测是正确的。

Value-prediction 甚至没有帮助使这种重新排序更合理。我们仍然需要 inter-thread 推测 内存重新排序,以使两个推测存储相互确认并 bootstrap 自身存在。


ISO C++ 选择允许这种宽松的原子,但 AFAICT 不允许这种 non-atomic 变量。我不确定我在标准 does 中到底看到了什么允许 ISO C++ 中的 relaxed-atomic 案例,除了说明它没有被明确禁止的注释之外。如果有任何其他代码对 xy 做了任何事情,那么也许,但我认为我的论点 does 也适用于宽松的原子情况。在 C++ 抽象机中没有通过源的路径可以产生它。

正如我所说,在任何真正的硬件(在 asm 中)或在任何真正的 C++ 实现上的 C++ 中实践 AFAIK 是不可能的。它更像是一个有趣的 thought-experiment 到非常弱的排序规则的疯狂后果,比如 C++ 的 relaxed-atomic。 (那些 排序规则不会禁止它,但我认为 as-if 规则和标准的其余部分会禁止,除非有一些规定允许宽松的原子读取值这是从未实际由任何线程编写的。)

如果有这样的规则,它只适用于宽松的原子,而不适用于 non-atomic 变量。 Data-race UB 几乎是标准需要说明的关于 non-atomic 变量和内存排序的全部内容,但我们没有。

(Whosebug 抱怨我在上面提出的评论太多,所以我将它们收集到一个答案中并进行了一些修改。)

您从 C++ 标准工作草案 N3337 中引用的截取是错误的。

[Note: The requirements do allow r1 == r2 == 42 in the following example, with x and y initially zero:

// Thread 1: r1 = x.load(memory_order_relaxed); if (r1 == 42) y.store(r1, memory_order_relaxed); // Thread 2: r2 = y.load(memory_order_relaxed); if (r2 == 42) x.store(42, memory_order_relaxed);

编程语言不应该允许这种“r1 == r2 == 42”发生。 这与内存模型无关。这是因果关系所要求的,这是基本的逻辑方法论,也是任何编程语言设计的基础。它是人与计算机之间的基本契约。任何内存模型都应该遵守它。否则就是一个错误。

这里的因果关系体现在线程内各操作之间的线程内依赖,如数据依赖(如同处读后写)、控制依赖(如分支操作)等。任何语言规范都不能违反它们。任何 compiler/processor 设计都应该尊重其提交结果的依赖性(即外部可见结果或程序可见结果)。

内存模型主要是关于多处理器之间的内存操作顺序,它不应该违反线程内依赖性,尽管弱模型可能允许在一个处理器中发生的因果关系在另一个处理器中被违反(或看不见) .

在您的代码片段中,两个线程都具有(线程内)数据依赖性(加载-> 检查)和控制依赖性(检查-> 存储),以确保它们各自的执行(在线程内)是有序的。这意味着,我们可以检查后面的操作的输出以确定前面的操作是否已经执行。

那么我们可以用简单的逻辑推导出来,如果r1r2都是42,那么一定存在依赖循环,这是不可能的,除非去掉一个条件检查,从本质上打破了依赖循环。这与内存模型无关,而是线程内数据依赖。

因果关系(或更准确地说,这里是线程内依赖)在 C++ std 中定义,但在早期草案中没有明确定义,因为依赖更多是微体系结构和编译器术语。在语言规范中,它通常被定义为操作语义。比如"if statement"形成的控制依赖,在你引用的同一个版本的draft中定义为"If the condition yields true the first substatement is executed. ",它定义了顺序执行顺序。

也就是说,编译器和处理器可以安排 if 分支的一个或多个操作在 if 条件解决之前执行。但是无论编译器和处理器如何安排操作,在 if 条件解决之前,if 分支的结果都不能提交(即,对程序可见)。应该区分语义要求和实现细节。一个是语言规范,另一个是编译器和处理器如何实现语言规范。

实际上,当前的 C++ 标准草案已在 https://timsong-cpp.github.io/cppwp/atomics.order#9 中稍作修改并修正了此错误。

[ Note: The recommendation similarly disallows r1 == r2 == 42 in the following example, with x and y again initially zero:

// Thread 1: r1 = x.load(memory_order_relaxed); if (r1 == 42) y.store(42, memory_order_relaxed); // Thread 2: r2 = y.load(memory_order_relaxed); if (r2 == 42) x.store(42, memory_order_relaxed);