什么形式上保证了非原子变量不能看到凭空出现的值,并像理论上原子一样创造数据竞赛?



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

该标准指出,std::memory_order_relaxed原子变量的规则允许出现"凭空"/"出乎意料"的值。

但是对于非原子变量,这个例子可以有UB吗? 在C++抽象机器中r1 == r2 == 42可能吗? 这两个变量最初都不会== 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;

上面的例子改编自标准,该标准明确表示原子对象的规范允许这种行为:

[注意:要求允许 r1 == r2 == 42 在以下情况下 例如,x 和 y 最初为零:

// 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);

但是,实现不应允许这种行为。

所谓的"记忆模型"的哪一部分保护非原子对象免受这些由读取看到凭空值引起的相互作用?


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

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

您的问题文本似乎缺少示例的重点和无气泡的值。 您的示例不包含数据争用 UB。 (如果xy在这些线程运行之前设置为42,则可能会发生这种情况,在这种情况下,所有投注都将关闭,并且引用数据竞争UB的其他答案适用。

没有针对真实数据竞赛的保护,只能防止凭空产生的值。

我认为你真的在问如何协调这个mo_relaxed的例子与非原子变量的理智和明确定义的行为。 这就是这个答案所涵盖的内容。


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

这种差距(我认为)不适用于非原子物体,仅适用于mo_relaxed.

他们说但是,实现不应该允许这种行为。显然,标准委员会找不到一种方法来正式确定该要求,因此目前它只是一个注释,但不是可选的。

很明显,即使这不是严格的规范,C++标准也打算不允许松弛原子的无气泡值(一般来说,我假设)。 后来的标准讨论,例如 2018 年的 p0668r5:修订C++内存模型(它不会"修复"这个问题,这是一个不相关的更改)包括多汁的侧节点,例如:

我们仍然没有一种可接受的方法来使我们的非正式(自 C++14 年以来)禁止凭空结果精确。其主要的实际效果是,使用松弛原子对C++程序进行形式验证仍然是不可行的。上面的论文提出了一种类似于 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3710.html 的解决方案。我们继续忽略这里的问题...

所以是的,标准的规范部分对于relaxed_atomic来说显然比对非原子的要弱。 这似乎是他们如何定义规则的不幸副作用。

AFAIK 在现实生活中,没有任何实现可以产生凭空产生的价值。


标准短语的更高版本更清楚地表明非正式建议,例如在目前的草案中: https://timsong-cpp.github.io/cppwp/atomics.order#8

  1. 实现应确保计算出的"无散"值通常依赖于自己的计算><。
    [
  1. 注意:建议 [of 8.] 同样不允许在以下示例中使用r1 == r2 == 42,x 和 y 最初为零:

    // 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);
    

    — 尾注 ]


(其余的答案是在我确定标准也打算禁止mo_relaxed这样做之前写的。

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

从形式上讲,ISO C++ 允许实现以任何方式实现函数/程序,从而产生与C++抽象机器相同的结果。 对于多线程代码,实现可以选择一种可能的抽象计算机排序,并确定这是始终发生的排序。 (例如,在编译到 ASM 以获得强序 ISA 时,重新排序宽松的原子存储时。 编写的标准甚至允许合并原子存储,但编译器选择不这样做)。但是程序的结果总是抽象机器可以产生的东西。 (只有 Atomics 一章介绍了一个线程在没有互斥锁的情况下观察另一个线程的操作的可能性。 否则,如果没有数据竞争 UB,这是不可能的)。

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

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

因此,我们不能做任何事情,让另一个线程暂时看到对象的不同值,或者单步写入。 发明对非原子对象的写入基本上总是编译器的错误;这是众所周知的,并且得到普遍同意,因为它可以破坏不包含 UB 的代码(并且在实践中已经为创建它的编译器错误的一些情况这样做了,例如 IA-64 GCC 我认为有这样的错误在某一时刻破坏了 Linux 内核)。 IIRC,Herb Sutter在他的演讲的第1或2部分中提到了这些错误,原子<>武器:C++内存模型和现代硬件",说它在C++11之前通常已经被认为是编译器错误,但C++11编纂了它,并使其更容易确定。

或者最近使用 x86 的 ICC 的另一个示例: 与 icc 崩溃:编译器能否在抽象机器中不存在的地方发明写入?


在C++抽象机器中,无论分支条件的负载的顺序或同时性如何,执行都无法达到y = r1;x = r2;xy都读作0,两个线程都不会写入它们。

不需要同步来避免UB,因为抽象机器操作的顺序不会导致数据争用。 ISO C++ 标准对推测执行或当错误推测到达代码时会发生什么没有任何可说的。 这是因为推测是实际实现的特征,而不是抽象机器的特征。 这取决于实现(硬件供应商和编译器编写者)来确保遵守"原样"规则。


C++编写像if (global_id == mine) shared_var = 123;这样的代码并让所有线程执行它是合法的,只要最多一个线程实际运行shared_var = 123;语句。 (只要存在同步以避免非原子int global_id上的数据竞争)。 如果这样的事情崩溃了,那将是混乱。 例如,您显然可以得出错误的结论,例如在C++中重新排序原子操作

观察到未发生非写入并不是数据竞争 UB。

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

我认为"出乎意料"的价值发明说明仅适用于松弛原子学,显然是原子学章节中对他们的特别警告。 (即便如此,AFAIK 它实际上不可能发生在任何真正的C++实现上,当然不是主流实现。 此时,实现不必采取任何特殊措施来确保非原子变量不会发生这种情况。

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

我没有看到任何理智的方法来争辩说C++抽象机器在执行此操作时在任何时候都会导致 UB,但看到r1 == r2 == 42意味着发生了不同步的读写,但那是数据竞争 UB。 如果可以发生这种情况,实现是否可以因为推测执行(或其他原因)而发明 UB? 答案必须是"否",C++标准才能完全可用。

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


可能导致此问题的假设 asm/硬件机制

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

要使42成为可能,线程 1 必须查看线程 2 的推理存储,线程 1 的存储必须由线程 2 的负载查看。 (确认分支推测是好的,允许这条执行路径成为实际采取的真实路径。

即跨线程的推测:如果它们在仅具有轻量级上下文切换的同一内核上运行,例如协程或绿色线程,则在当前硬件上可能。

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

因此,我们需要一种将两个逻辑内核之间的推测耦合在一起的设计。没有人这样做,因为这意味着如果检测到错误预测,需要回滚更多状态。 但假设这是可能的。 例如,一个 OoO SMT 内核,它允许在其逻辑内核之间存储转发,甚至在它们从无序内核中停用(即变得非推测)之前。

PowerPC 允许在已停用存储的逻辑内核之间进行存储转发,这意味着线程可以不同意存储的全局顺序。 但是等到他们"毕业"(即退休)并变得非投机意味着它不会将投机联系在一起,而不是将单独的逻辑核心上的投机联系在一起。 因此,当一个人从分支失误中恢复时,其他人可以让后端保持忙碌。 如果它们都不得不在任何逻辑内核上回滚错误预测,那将破坏 SMT 的很大一部分优势。

我想了一会儿,我找到了一个顺序,可以在真正的弱序 CPU 的单核上导致这种情况(线程之间的用户空间上下文切换),但最后一步存储无法转发到第一步加载,因为这是程序顺序,OoO exec 保留了这一点。

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

  • T2:分支预测预测r2 == 42为真。 (x = 42应该运行。

  • T2:运行x = 42。 (仍然是推测性的;r2 = yhasn't obtained a value yet so ther2 == 42' 比较/分支仍在等待确认该推测)。

  • 切换到线程 1 的上下文不会将 CPU 回滚到停用状态,也不会等待推测被确认为良好或被检测为错误推测。

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

  • T1:r1 = x;从投机x = 42商店获取价值

  • T1:发现r1 == 42为真。 (分支推测也发生在这里,实际上并没有等待存储转发完成。 但是沿着这条执行路径,在x = 42确实发生的地方,这个分支条件将执行并确认预测)。

  • T1:运行y = 42

  • 这一切都在同一个 CPU 内核上,所以这个y=42存储是在按程序顺序加载r2=y之后;它不能给该负载一个42,让r2==42推测得到确认。因此,这种可能的排序毕竟不能在行动中证明这一点。这就是为什么线程必须在具有线程间推测的单独内核上运行的原因,这样才能实现这样的效果。

请注意,x = 42不依赖于r2,因此不需要值预测来实现此目的。 无论如何,y=r1都在if(r1 == 42)内,因此编译器可以根据需要优化y=42,从而打破另一个线程中的数据依赖关系并使事情对称。

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


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

因为分支预测而不是价值预测而进行推测在这里具有相同的效果。 在这两种情况下,负载最终都需要看到42以确认推测是正确的。

价值预测甚至无助于使这种重新排序更合理。 我们仍然需要线程间推测内存重新排序,以便两个推测存储相互确认并引导自己存在。


ISO C++选择允许这种松弛的原子学,但AFAICT不允许这种非原子变量。 我不确定我是否确切地看到了标准中允许 ISO C++中的松弛原子情况,除了说明说它没有明确禁止。 如果还有其他代码对xy做了任何事情,那么也许,但我认为我的论点也适用于宽松的原子情况。 在C++抽象机器中,通过源代码的路径无法生成它。

正如我所说,实际上不可能在任何实际硬件(asm中)上使用AFAIK,或者在任何实际C++实现上C++AFAIK。 这更像是一个有趣的思想实验,研究非常弱的排序规则的疯狂后果,比如C++的松弛原子。 (这些排序规则并不禁止它,但我认为 as-if 规则和标准的其余部分是不允许的,除非有一些规定允许宽松的原子读取从未被任何线程实际写入的值

如果有这样的规则,那只适用于松弛的原子学,不适用于非原子变量。 数据竞赛UB几乎是关于非原子变量和内存排序的所有标准,但我们没有。

当可能存在争用条件时,什么保证了共享变量(正常,非原子)的读取看不到写入

没有这样的保证。

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

[介绍比赛]

如果出现以下情况,则两个操作可能并发

  • 它们由不同的线程执行,或者
  • 它们是未排序的,至少有一个由信号处理程序执行,并且它们不是由相同的信号处理程序调用执行的。

如果程序的执行包含两个潜在的并发冲突操作,其中至少一个不是原子的,并且两者都不会先于另一个发生,则程序的执行包含数据争用,但下面描述的信号处理程序的特殊情况除外。任何此类数据争用都会导致未定义的行为。...

特殊情况与问题不是很相关,但为了完整起见,我将包括它:

对同一类型volatile std::sig_­atomic_­t对象的两次访问不会导致数据争用,如果两者都发生在同一个线程中,即使一个或多个发生在信号处理程序中也是如此。

所谓的"内存模型"的哪一部分保护非原子对象免受这些由看到交互的读取引起的交互?

没有。 事实上,你会得到相反的结果,标准明确地将其称为未定义的行为。 在 [介绍种族]\21 中,我们有

如果程序的执行包含

两个潜在的并发冲突操作,其中至少一个不是原子的,并且两者都不会先于另一个发生,则程序的执行包含数据争用,但下面描述的信号处理程序的特殊情况除外。任何此类数据争用都会导致未定义的行为。

这涵盖了您的第二个示例。


规则是,如果在多个线程中具有共享数据,并且其中至少有一个线程写入该共享数据,则需要同步。 没有它,你就会有数据竞争和未定义的行为。 请注意,volatile不是有效的同步机制。 您需要原子学/互斥锁/条件变量来保护共享访问。

注意:我在这里给出的具体例子显然是不准确的。我假设优化器可能比它显然允许的更激进。评论中对此进行了一些很好的讨论。我将不得不进一步调查这个问题,但想在这里留下这个注释作为警告。

其他人已经给你答案,引用了标准的适当部分,这些部分直截了当地说明你认为存在的保证不存在。看起来你正在解释标准的一部分,即如果你使用原子对象memory_order_relaxed意味着非原子对象不允许这种行为,那么原子对象允许某种奇怪的行为。这是一个推理的飞跃,由标准的其他部分明确解决,这些部分声明了非原子对象的行为未定义。

实际上,下面是线程 1 中可能发生的事件顺序,这是完全合理的,但即使硬件保证所有内存访问在 CPU 之间完全序列化,也会导致您认为被禁止的行为。请记住,标准不仅要考虑硬件的行为,还要考虑优化器的行为,优化器通常会积极地重新排序和重写代码。

优化器可以重写线程 1

,如下所示:
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实际被告知要做的事情有任何相似之处。

原子变量对编译器重写代码的能力施加约束,并指示编译器发出特殊的 CPU 指令,这些指令对 CPU 重新排序内存访问的能力施加约束。涉及memory_order_relaxed的限制比通常允许的限制要强得多。编译器通常被允许完全删除对x的任何引用,如果它们不是原子的,则根本不y

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

这就是为什么数据竞争被标准标记为未定义行为的原因。可能发生的事情的空间可能比你的想象要疯狂得多,而且肯定比任何标准都能合理地包含的要宽

(Stackoverflow抱怨我上面放了太多评论,所以我通过一些修改将它们收集成一个答案。

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

[注意:要求允许 r1 == r2 == 42 在以下情况下 例如,x 和 y 最初为零:

// 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"发生。 这与内存模型无关。这是因果关系所必需的,因果关系是基本的逻辑方法,也是任何编程语言设计的基础。它是人与计算机之间的基本契约。任何内存模型都应该遵守它。否则就是一个错误。

这里的因果关系体现在线程内操作之间的线程内依赖关系上,例如数据依赖(例如,在同一位置写入后读取)和控制依赖(例如,分支中的操作)等。任何语言规范都不能违反它们。任何编译器/处理器设计都应尊重其提交结果(即外部可见结果或程序可见结果)的依赖性。

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

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

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

因果关系(或者更准确地说,这里的线程内依赖性)在 std C++中定义,但在早期草案中没有那么明确,因为依赖性更多地是微架构和编译器术语。在语言规范中,它通常被定义为操作语义。例如,由"if 语句"形成的控制依赖关系在您引用的同一版本的草稿中定义为"如果条件产生 true,则执行第一个子语句"。 这定义了顺序执行顺序。

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

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

[ 注意:在以下示例中,建议同样不允许r1 == r2 == 42,x 和 y 最初为零:

// 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);

最新更新