8

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

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

但是对于非原子变量,这个例子能不能有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;

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

[注意:在以下示例中,要求确实允许 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创造导致数据竞争的自我实现条件?

4

5 回答 5

8

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

没有这样的保证。

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

[介绍.races]

两个动作可能是并发的,如果

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

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

特殊情况与问题不太相关,但为了完整起见,我将其包括在内:

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

于 2019-06-19T18:52:12.060 回答
6

您的问题文本似乎缺少示例的重点和无中生有的价值。您的示例不包含数据竞争 UB。(它可能会在这些线程运行之前设置为xy设置为42,在这种情况下,所有赌注都已关闭,并且引用 data-race 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的解决方案。我们继续忽略这里的问题......

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

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++ 抽象机器操作中的每一种可能的操作顺序都会导致r1=r2=0没有 UB,即使没有同步也是如此。因此,该程序没有 UB,任何非零结果都将违反“as-if”规则

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

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

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

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

或者最近使用 ICC for x86 的另一个例子: icc 崩溃:编译器可以发明抽象机器中不存在的写入吗?


在 C++ 抽象机中,无论​​分支条件的负载的顺序或同时性如何, 执行都无法达到y = r1;or 。并且都读取为并且没有线程写入它们。x = r2;xy0

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


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

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

它也不是 UB 运行if(i<SIZE) return arr[i];,因为数组访问只有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 = y hasn't obtained a value yet so ther2 == 42` 比较/分支仍在等待确认该推测)。

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

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

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

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

  • T1:y = 42运行。

  • 这都在同一个 CPU 内核上,所以这个y=42存储r2=y在程序顺序加载之后;它不能给这个负载 a42r2==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++ 中的宽松原子案例,除了说明它没有明确禁止的说明之外。如果有任何其他代码可以做任何事情,x那么y可能,但我认为我的论点适用于宽松的原子情况。在 C++ 抽象机中没有通过源代码的路径可以生成它。

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

如果有这样的规则,它只适用于宽松的原子,而不适用于非原子变量。Data-race UB 几乎是所有关于非原子变量和内存排序的标准,但我们没有。

于 2019-09-22T12:06:12.783 回答
5

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

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

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

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


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

于 2019-06-19T18:54:19.773 回答
2

注意:我在这里给出的具体例子显然不准确。我假设优化器可能比它明显允许的更具侵略性。评论中有一些关于此的精彩讨论。我将不得不对此进行进一步调查,但想将此注释留在这里作为警告。

其他人已经给出了答案,并引用了标准的适当部分,这些部分明确表明您认为存在的保证并不存在。看来您正在解释标准的一部分,如果您使用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比通常允许的要强得多。如果它们不是原子的,则通常允许编译器完全摆脱对任何引用的引用xy

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

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

于 2019-06-19T19:27:58.890 回答
1

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

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

[注意:在以下示例中,要求确实允许 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”发生。这与内存模型无关。这是因果关系所要求的,因果关系是基本的逻辑方法论,也是任何编程语言设计的基础。它是人与计算机之间的基本契约。任何内存模型都应该遵守它。否则它是一个错误。

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

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

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

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

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

也就是说,编译器和处理器可以安排 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);

于 2019-11-23T20:38:44.857 回答