24

所以我正在阅读有关即将推出的 C++0x 标准的一部分的内存模型。但是,我对允许编译器执行的某些限制感到有些困惑,特别是关于推测加载和存储的限制。

首先,一些相关的东西:

Hans Boehm 关于线程和 C++0x 中的内存模型的页面

Boehm,“线程不能作为库实现”

Boehm 和 Adve,“C++ 并发内存模型的基础”

Sutter,“棱镜:微软本机代码平台的基于原则的顺序内存模型”,N2197

Boehm,“并发内存模型编译器后果”,N2338

现在,基本思想本质上是“无数据争用程序的顺序一致性”,这似乎是在易于编程和允许编译器和硬件机会优化之间的一个不错的折衷。如果不同线程对同一内存位置的两次访问没有排序,则定义为发生数据竞争,其中至少一次存储到内存位置,并且至少一次不是同步操作。这意味着对共享数据的所有读/写访问都必须通过某种同步机制,例如互斥锁或对原子变量的操作(好吧,可以仅对专家以宽松的内存顺序对原子变量进行操作,但默认提供为了顺序一致性)。

鉴于此,我对普通共享变量上的虚假或推测加载/存储的限制感到困惑。例如,在 N2338 中,我们有示例

switch (y) {
    case 0: x = 17; w = 1; break;
    case 1: x = 17; w = 3; break;
    case 2: w = 9; break;
    case 3: x = 17; w = 1; break;
    case 4: x = 17; w = 3; break;
    case 5: x = 17; w = 9; break;
    default: x = 17; w = 42; break;
}

不允许编译器转换成

tmp = x; x = 17;
switch (y) {
    case 0: w = 1; break;
    case 1: w = 3; break;
    case 2: x = tmp; w = 9; break;
    case 3: w = 1; break;
    case 4: w = 3; break;
    case 5: w = 9; break;
    default: w = 42; break;
}

因为如果 y == 2 存在对 x 的虚假写入,如果另一个线程同时更新 x,这可能是一个问题。但是,为什么这是一个问题?这是一场数据竞赛,无论如何都是被禁止的;在这种情况下,编译器通过两次写入 x 只会使情况变得更糟,但即使是一次写入也足以进行数据竞争,不是吗?即一个合适的 C++0x 程序需要同步对 x 的访问,在这种情况下将不再存在数据竞争,并且虚假存储也不会成为问题?

I'm similarly confused about Example 3.1.3 in N2197 and some of the other examples as well, but maybe an explanation for the above issue would explain that too.

EDIT: The Answer:

The reason why speculative stores are a problem is that in the switch statement example above, the programmer might have elected to conditionally acquire the lock protecting x only if y != 2. Hence the speculative store might introduce a data race that was not there in the original code, and the transformation is thus forbidden. The same argument applies to Example 3.1.3 in N2197 as well.

4

2 回答 2

8

我不熟悉您所指的所有内容,但请注意,在 y==2 的情况下,在代码的第一位,x 根本没有被写入(或读取,就此而言)。在第二段代码中,它被写入了两次。这比只写一次和写两次(至少在现有的线程模型中,例如 pthreads 中)有更大的区别。此外,存储一个根本不会存储的值比仅存储一次与存储两次的区别更大。出于这两个原因,您不希望编译器只是用tmp = x; x = 17; x = tmp;.

假设线程 A 想假设没有其他线程修改 x。希望它被允许期望如果 y 为 2,并且它向 x 写入一个值,然后将其读回,它将取回它已写入的值,这是合理的。但是,如果线程 B 正在同时执行您的第二段代码,那么线程 A 可以写入 x 并稍后读取它,并取回原始值,因为线程 B 在写入“之前”保存并在“之后”恢复它。或者它可以取回 17,因为线程 B 在写入“之后”存储了 17,并且在线程 A 读取之后再次存储了 tmp。线程 A 可以进行它喜欢的任何同步,但这无济于事,因为线程 B 没有同步。它不同步的原因(在 y==2 的情况下)是它没有使用 x。

简而言之,如果允许您提出的转换,引入虚假写入,那么将永远不可能分析一些代码并得出结论它不会修改 x (或任何其他内存位置)。有许多方便的习惯用法因此是不可能的,例如在没有同步的情况下在线程之间共享不可变数据。

因此,虽然我不熟悉 C++0x 对“数据竞争”的定义,但我假设它包含一些条件,允许程序员假设未写入对象,并且这种转换会违反这些条件。我推测如果 y==2,那么您的原始代码以及并发代码:x = 42; x = 1; z = x在另一个线程中,未定义为数据竞争。或者至少如果它是一场数据竞争,它不会允许 z 以 17 或 42 结束。

考虑到在这个程序中,y 中的值 2 可能用于表示,“还有其他线程在运行:不要修改 x,因为我们在这里没有同步,所以会引入数据竞争”。也许根本没有同步的原因是,在 y 的所有其他情况下,没有其他线程在运行可以访问 x。在我看来,C++0x 想要支持这样的代码是合理的:

if (single_threaded) {
    x = 17;
} else {
    sendMessageThatSafelySetsXTo(17);
}

显然,您不希望将其转换为:

tmp = x;
x = 17;
if (!single_threaded) {
    x = tmp;
    sendMessageThatSafelySetsXTo(17);
}

这与您的示例中的转换基本相同,但只有 2 种情况,而不是足以使它看起来像一个很好的代码大小优化。

于 2010-01-04T20:31:04.203 回答
5

如果y==2, 并且另一个线程修改或读取x, 原始样本中如何存在竞争条件?该线程从不接触x,因此其他线程可以自由地这样做。

但是在重新排序的版本中,我们的线程会修改x,即使只是暂时的,所以如果另一个线程也操作它,我们现在有一个之前不存在的竞争条件。

于 2010-01-04T20:43:28.610 回答