可以释放+获得中断发生之前吗?
Can release+acquire break happens-before?
今天的许多编程语言都有 happens-before
关系和 release+acquire
同步操作。
其中一些编程语言:
- C/C++11: happens-before, release+acquire
- Rust and Swift 完全采用了 C/C++ 内存模型——所以他们也有。
- Java: happens-before, release+acquire.
我想知道release+acquire
是否可以违反happens-before
:
- 如果可以的话,我想看一个例子
- 如果不可能,那么我想得到简单明了的解释为什么
什么是release+acquire
和happens-before
Release/acquire
在不同线程之间建立 happens-before
关系:换句话说,Thread 1
中 release
之前的所有内容都保证在 Thread 2
之后可见 acquire
:
\ Thread 1 /
\ -------- /
\ x = 1 / Everything
\ y = 2 / here...
\ write-release(ready = true) /
└───────────────────────────┘
|
└─────────────┐ (happens-before)
V
┌─────────────────────────┐
/ Thread 2 \
...is visible to / -------- \
everything / read-acquire(ready == true) \
here / assert(x == 1) \
/ assert(y == 2) \
不仅如此,happens-before
是一个strict partial order。
这意味着它是:
- 可传递:
Thread 2
保证不仅可以看到 Thread 1
的写入,还可以看到 Thread 1
看到的其他线程的所有写入
- 不对称:
a
发生在 b
之前,或者 b
发生在 a
之前,两者都是不允许的
为什么我认为 release/acquire
可能会破坏 happens-before
正如我们从 IRIW litmus 测试中了解到的那样,release/acquire
可能导致两个线程以不同的顺序查看来自不同线程的写入(对于 C++,另请参阅 gcc wiki 中的最后一个示例 here, and these two 示例):
// Thread 1
x.store(1, memory_order_release);
// Thread 2
y.store(1, memory_order_release);
// Thread 3
assert(x.load(memory_order_acquire) == 1 && y.load(memory_order_acquire) == 0)
// Thread 4
assert(y.load(memory_order_acquire) == 1 && x.load(memory_order_acquire) == 0)
这里assert
都可以通过,这意味着Thread 3
和Thread 4
看到写入x
和y
的顺序不同。
据我了解,如果是普通变量,那么这将违反happens-before的不对称性属性。
但是因为 x 和 y 是原子,所以没关系。
(顺便说一句,我不确定)
Nate Eldredge 这个 IRIW 示例是可以的。
但我仍然暗暗怀疑可能存在类似于 IRIW 的东西,这会导致 Thread 3
和 Thread 4
以不同的顺序看到常规写入 happen-before — 这会发生中断-之前(它不再具有传递性)。
注1
在cppreference中也有这句话:
The implementation is required to ensure that the happens-before relation is acyclic, by introducing additional synchronization if necessary (it can only be necessary if a consume operation is involved, see Batty et al)
引用暗示可能存在违反 happens-before
并且需要额外同步的情况(“非循环”意味着 happens-before 形成 directed acyclic graph,相当于说“严格偏序”).
如果可能的话我想知道这些案例是什么。
注2
由于 java 允许数据竞争,我也对 happens-before
仅在存在数据竞争的情况下被违反的情况感兴趣。
编辑 1(2021 年 11 月 3 日)
举个例子,这里解释为什么顺序一致 (SC) 原子不能违反 happens-before
。
(对 release/acquire 原子的类似解释将是我问题的答案)。
“违反 happens-before
”是指“违反 happens-before
的公理,即 strict partial order”。
严格偏序 correspond directly to directed acyclic graphs (DAGs).
这里是来自 wiki 的 DAG 示例(注意它没有循环):
让我们证明使用 SC 原子 happens-before
图保持非循环。
请记住,SC 原子以全局顺序发生(所有线程都相同),并且:
- 顺序与每个线程内的动作顺序一致
- 每个 SC 原子读取都会看到按此总顺序对同一变量的最新 SC 原子写入
看看这个 happens-before
图表:
Thread1 Thread2 Thread3
======= ======= =======
│ │ │
W(x) │ │
↓ │ │
Sw(a) ┐ │ W(y)
│ │ │ ↓
│ └> Sr(a) ┌ Sw(b)
│ ↓ │ │
│ Sr(b)<─┘ │
│ ↓ │
│ R(x) │
│ ↓ │
│ R(y) │
│ │ │
V V V
图表上:
- 时间往下流
W(x)
和 R(x)
是常规操作:写入和读取 x
Sw(a)
和 Sr(a)
是 SC 原子:a
的写入和读取
- 在每个线程中,操作按程序顺序发生(在 C++ 中又称为
sequenced-before order
):按照它们在代码中的顺序
- 线程间
happens-before
由SC原子建立
请注意图表上的箭头始终向下
=> 图形不能有循环
=> 它总是一个 DAG
=> happens-before
不能违反公理
相同的证明不适用于 release/acquire
原子,因为(据我所知)它们不会以全局顺序发生 => Sw(a)
和 [= 之间的 HB 箭头54=] 可能会向上 => 一个循环是可能的。 (我不确定)
I would like to know if release+acquire can violate happens-before.
Happens-before relationship 不能被“违反”,因为它是保证。意思是,如果您以正确的方式建立它,它就会存在,并带有所有含义(除非编译器中存在错误)。
但是,建立任何 发生前的关系并不能保证您已经避免了所有可能的race conditions。您需要在相关操作之间建立精心选择的关系,这将消除所有可能发生数据竞争的情况。
让我们回顾一下这段代码:
// Thread 1
x.store(1, std::memory_order_release);
// Thread 2
y.store(1, std::memory_order_release);
// Thread 3
while (x.load(std::memory_order_acquire) != 1);
if (y.load(std::memory_order_acquire) == 0) {
x_then_y = true;
}
// Thread 4
while (y.load(std::memory_order_acquire) != 1);
if (x.load(std::memory_order_acquire) == 0) {
y_then_x = true;
}
如您所见,T1
和 T2
使用 memory_order_release
内存排序更新 x
和 y
。 T3
和 T4
使用 memory_order_acquire
.
现在,引用 cppreference:
Release-Acquire ordering
If an atomic store in thread A
is tagged memory_order_release
and an atomic load in thread B
from the same variable is tagged memory_order_acquire
, all memory writes (non-atomic and relaxed atomic) that happened-before the atomic store from the point of view of thread A
, become visible side-effects in thread B
. That is, once the atomic load is completed, thread B
is guaranteed to see everything thread A
wrote to memory.
The synchronization is established only between the threads releasing and acquiring the same atomic variable. Other threads can see different order of memory accesses than either or both of the synchronized threads.
它明确表示,只有对应线程中的store-load
对之间建立关系。 load-load
对之间没有关系。 回到我们的例子,happens-before 关系将形成下图:
如您所见,T1和T2、T3和T4之间没有任何关系,也没有总序。 T3 和 T4 可以任意顺序查看 T1 和 T2 的副作用。
上面的代码片段在 cppreference
中用于说明情况,当 memory_order_acquire
+ memory_order_release
可能太弱而无法避免数据竞争(但这并不意味着这个例子违反了 happens-before 或内存模型,只是有 happens-before 可能不足以避免所有可能的数据竞争!)。
如果 memory_order_seq_cst
用于上述示例中的所有操作,则将在 T3 和 T4 中的 load
操作之间额外建立 happens-before。
意思是,当第一个 while(x.load) != 1
或 while(y.load) != 1
通过时,它 保证 在另一个 x.load
或 y.load
之后线程将得到 1
的结果,确保 x_then_y
和 y_then_x
不能同时为真。
请注意,在 java 中,为了简单起见,原子操作和 volatile
操作始终与 memory_order_seq_cst
类似(在某些情况下会牺牲性能)。
Happens-before 是 sequenced-before 和 synchronizes-with 的传递闭包。 Sequenced-before 只是每个线程内的程序顺序,而 synchronizes-with 发生在获取加载从发布存储获取其值时。所以在你的程序中,为了让两个断言都通过,必须满足以下关系:
T3.x==1
发生在 T3.y==0
(排序) 之前
T4.y==1
发生在 T4.x==0
之前(同样)
T1.x=1
发生在 T3.x==1
之前(获取负载从发布存储获取其值)
T2.y=1
发生在 T4.y==1
之前(同样)
T1.x=1
发生在 T3.y==0
之前(为了传递性)
T2.y=1
发生在 T4.x==0
之前(同样)
您可以检查这是否满足偏序的所有公理(反对称和传递)以及两个断言传递所隐含的所有 C++ 一致性规则。例如,T2.y=1
一定不会出现在 T3.y==0
之前,实际上我们的排序中不存在这种关系。但是 T3.y==0
发生在 T2.y=1
之前也是不正确的,这没有错;毕竟是部分订单。 T2.y=1
和 T3.y==0
只是无序的。
因为有一个有效的 happens-before 顺序与两个断言通过一致,所以当您 运行 程序时,两个断言都可以通过。
的确,如果 T3.y==0
和 T2.y=1
之间存在某种先行关系,并且 T4.x==0
和 T1.x=1
之间存在同样的关系,那么每个组合会导致一些违反规则的行为:要么是违反一致性,要么是部分顺序中的循环。但是同样,它们无序是完全可以的,这样就不会发生违规。
如果加载和存储都是松弛的,或者即使 x
和 y
根本不是原子的,那么上面的关系 3 和 4 不会被任何规则暗示,因此happens-before 排序将变得简单:
T3.x==1
发生在 T3.y==0
(排序) 之前
T4.y==1
发生在 T4.x==0
之前(同样)
这也与通过的两个断言一致。 (在非原子情况下,T1.x=1
与 x
的负载无序的事实将意味着存在数据竞争,因此该行为在 C++ 中未定义。在不同的语言中,如 Java,我们可能已经定义了表示两个加载都成功并且 return 为 0 或 1 的行为,但我们仍然可以让两个断言都通过。)如果您认为将程序更改为使用非原子加载并且stores 会阻止这两个断言通过,你错了。
所以获取和释放实际上加强了排序;必须保持 更多 关系,并且程序的行为变得 更好 定义。
回答:不,release/acquire不能中断happens-before。
证明由 Nate Eldredge 在 :
中给出
Oh, indeed. And actually, I might see how to prove it. The HB relation is transitive by its construction. The sequencing relation is acyclic, so if there is a cycle in HB, it must contain at least one synchronizes-with step, which is, roughly, an acquire load L that takes its value from a release store S. But because of the cycle, L happens before S. Therefore by p14, L must take its value from some store other than S, contradiction. Not quite a proof because I have oversimplified the definition of synchronizes-with from atomics.order p2, but it's a start.
我只是想把它放在一个单独的答案中,以便人们更容易注意到。
此外,这里有我的额外解释(也许这会让某些人更容易理解)。
首先,如果我们只使用 release/acquire
原子和非原子内存访问,那么 happens-before
是可传递的(和非循环的)构造。
类似于SC
图,在release/acquire
的情况下,边也总是指向下方:
Thread1 Thread2 Thread3
======= ======= =======
│ │ │
│ ┌ Wrel(a)──┐ │
│ │ │ │ │
Racq(a)<┘ │ │ │
│ ↓ │ │
│ ┌ Wrel(b) ┐│ │
↓ │ │ ││ │
Racq(b)<┘ │ └─> Racq(b)
│ │ │ ↓
│ │ └> Racq(a)
│ │ │
V V V
(顺便说一下,这张图不同于 SC
:Thread 1
和 Thread 3
请参阅 Wrel(a)
和 Wrel(b)
订单。但边缘仍然指向下方)
从 Wrel(x)
到 Racq(x)
的边总是指向下方,因为 Racq(x)
看到 Wrel(x)
和 之前的所有内容 Wrel(x)
已完成(请参阅答案末尾的注释)。
(在 C++ 规范中,这称为 synchronizes-with
,您可以了解更多信息 here。)
因此,与 SC
图形类似,所有边始终指向下方
=> 图形不能有循环
=> 它总是一个 DAG
=> happens-before
不能违反公理
实际上 happens-before
由 release/acquire
原子学产生 — 基本上是 Leslie Lamport 在 Time, Clocks and the Ordering of Events in a Distributed System.
中介绍的原始 happens-before
我真的建议所有对 HB
感兴趣的人阅读这篇论文 — Lamport 的解释简短明了,这个想法真的很酷。
我们也用图片来演示为什么循环是不可能的。
这是一个循环的样子:
Thread1 Thread2 Thread3
======= ======= =======
│ │ │
Racq(a)<─────│──────────│─────┐
↓ │ │ │
Wrel(b) ┐ │ │ │
│ │ │ │ │
│ └> Racq(b) │ │
│ ↓ │ │
│ Wrel(c) ┐ │ │
│ │ │ │ │
│ │ └> Racq(c) │
│ │ ↓ │
│ │ Wrel(a) ┘
│ │ │
V V V
在每个线程中 happens-before
是源代码中的操作顺序(在 C++ 中称为 sequenced-before
,在 Java 中称为 program order
)。
显然,这里不可能有 HB
个循环。
这意味着“返回”并关闭循环的边缘必须是 synchronizes-with
边缘,如上图中的 Wrel(a)->Racq(a)
边缘。
注意矛盾:
Wrel(a)
必须在Racq(a)
之前完成,因为Racq(a)
读取的是Wrel(a)
写入的值
Racq(a)
必须在 Wrel(a)
之前完成,因为有一个链 Racq(a)->Wrel(b)->Racq(b)->Wrel(c)->Racq(c)->Wrel(a)
,其中每个 Wrel(x)
(以及它之前的所有内容)在 Racq(x)
读取之前完成它。
这意味着 Wrel(a)->Racq(a)
边缘是不允许的 => 循环是不可能的。
就 C++ 内存模型而言,它违反了 coherence requirements:
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.
注释。
我声明:
Racq(x)
sees Wrel(x)
and everything before Wrel(x)
as completed
但在 C++ 标准中没有直接说明。
相反它有这个:
happens-before
定义了读取所看到的内容
Racq(x)
和 Wrel(x)
之间的关系称为 synchronizes-with
happens-before
是根据 synchronizes-with
和大量其他规则和命令构建的
可以从 C++ 标准中推导出我的陈述,尽管这可能并不容易。 (这就是为什么我建议改为阅读 this article)。
我使用该语句是因为它简洁地描述了内存屏障指令的作用,这就是 happens-before
可以(并且可能)很容易实现的方式。
通常,内存屏障指令就是我们实现 happens-before
及其所有数学属性所需要的全部。
对于不同 CPU 上的这些指令的概述,我会推荐 Paul E. McKenney 在 Memory Barriers: a Hardware View for Software Hackers 中的相关部分。
(例如,PowerPC 中的内存屏障与 C++ 中的 release/acquire
原子基本相同)
的以下片段有错误:
Thread1 Thread2 Thread3
======= ======= =======
│ │ │
│ ┌ Wrel(a)──┐ │
│ │ │ │ │
Racq(a)<┘ │ │ │
│ ↓ │ │
│ ┌ Wrel(b) ┐│ │
↓ │ │ ││ │
Racq(b)<┘ │ └─> Racq(b)
│ │ │ ↓
│ │ └> Racq(a)
│ │ │
V V V
(BTW notice that this graph is different from SC
: Thread 1
and Thread 3
see Wrel(a)
and Wrel(b)
in different orders. But edges point downwards nonetheless)
只有当Wrel(a)
和Wrel(b)
来自不同线程时,Thread 1
和Thread 3
才能看到Wrel(a)
和Wrel(b)
的顺序不同。
这就是所谓的 IRIW(独立写入的独立读取)测试。
所以片段应该改成这样:
Thread1 Thread2 Thread3 Thread4
======= ======= ======= =======
│ │ │ │
│ ┌ Wrel(a)┐ │ │
Racq(a)<┘ │ │┌ Wrel(b)┐ │
↓ │ ││ │ └> Racq(b)
Racq(b)<─────│───│┘ │ ↓
│ │ └─────│────> Racq(a)
│ │ │ │
V V V V
(BTW notice that this graph is different from SC
: Thread 1
and Thread 4
see Wrel(a)
and Wrel(b)
in different orders. But edges point downwards nonetheless)
顺便说一下,我本可以将其作为已接受答案的建议编辑。
我没有这样做是因为它是一个非常专业的主题,所以审稿人可能不知道所有的细微差别和细节,并拒绝编辑只是因为它确实修复了一个错误并不明显。
但我认为这是一个值得一提和修复的错误。
所以我把修复放在这个答案中,因为:
- 对此特定主题感兴趣的人可能会看到修复程序
- 人们可能会投票赞成这个答案(和修复)=> 如果有足够的票数,那么这将表明修复是正确的 => 修复将被版主或有问题的人纳入接受的答案足够的声望
今天的许多编程语言都有 happens-before
关系和 release+acquire
同步操作。
其中一些编程语言:
- C/C++11: happens-before, release+acquire
- Rust and Swift 完全采用了 C/C++ 内存模型——所以他们也有。
- Java: happens-before, release+acquire.
我想知道release+acquire
是否可以违反happens-before
:
- 如果可以的话,我想看一个例子
- 如果不可能,那么我想得到简单明了的解释为什么
什么是release+acquire
和happens-before
Release/acquire
在不同线程之间建立 happens-before
关系:换句话说,Thread 1
中 release
之前的所有内容都保证在 Thread 2
之后可见 acquire
:
\ Thread 1 /
\ -------- /
\ x = 1 / Everything
\ y = 2 / here...
\ write-release(ready = true) /
└───────────────────────────┘
|
└─────────────┐ (happens-before)
V
┌─────────────────────────┐
/ Thread 2 \
...is visible to / -------- \
everything / read-acquire(ready == true) \
here / assert(x == 1) \
/ assert(y == 2) \
不仅如此,happens-before
是一个strict partial order。
这意味着它是:
- 可传递:
Thread 2
保证不仅可以看到Thread 1
的写入,还可以看到Thread 1
看到的其他线程的所有写入 - 不对称:
a
发生在b
之前,或者b
发生在a
之前,两者都是不允许的
为什么我认为 release/acquire
可能会破坏 happens-before
正如我们从 IRIW litmus 测试中了解到的那样,release/acquire
可能导致两个线程以不同的顺序查看来自不同线程的写入(对于 C++,另请参阅 gcc wiki 中的最后一个示例 here, and these two 示例):
// Thread 1
x.store(1, memory_order_release);
// Thread 2
y.store(1, memory_order_release);
// Thread 3
assert(x.load(memory_order_acquire) == 1 && y.load(memory_order_acquire) == 0)
// Thread 4
assert(y.load(memory_order_acquire) == 1 && x.load(memory_order_acquire) == 0)
这里assert
都可以通过,这意味着Thread 3
和Thread 4
看到写入x
和y
的顺序不同。
据我了解,如果是普通变量,那么这将违反happens-before的不对称性属性。
但是因为 x 和 y 是原子,所以没关系。
(顺便说一句,我不确定)
Nate Eldredge
但我仍然暗暗怀疑可能存在类似于 IRIW 的东西,这会导致 Thread 3
和 Thread 4
以不同的顺序看到常规写入 happen-before — 这会发生中断-之前(它不再具有传递性)。
注1
在cppreference中也有这句话:
The implementation is required to ensure that the happens-before relation is acyclic, by introducing additional synchronization if necessary (it can only be necessary if a consume operation is involved, see Batty et al)
引用暗示可能存在违反 happens-before
并且需要额外同步的情况(“非循环”意味着 happens-before 形成 directed acyclic graph,相当于说“严格偏序”).
如果可能的话我想知道这些案例是什么。
注2
由于 java 允许数据竞争,我也对 happens-before
仅在存在数据竞争的情况下被违反的情况感兴趣。
编辑 1(2021 年 11 月 3 日)
举个例子,这里解释为什么顺序一致 (SC) 原子不能违反 happens-before
。
(对 release/acquire 原子的类似解释将是我问题的答案)。
“违反 happens-before
”是指“违反 happens-before
的公理,即 strict partial order”。
严格偏序 correspond directly to directed acyclic graphs (DAGs).
这里是来自 wiki 的 DAG 示例(注意它没有循环):
让我们证明使用 SC 原子 happens-before
图保持非循环。
请记住,SC 原子以全局顺序发生(所有线程都相同),并且:
- 顺序与每个线程内的动作顺序一致
- 每个 SC 原子读取都会看到按此总顺序对同一变量的最新 SC 原子写入
看看这个 happens-before
图表:
Thread1 Thread2 Thread3
======= ======= =======
│ │ │
W(x) │ │
↓ │ │
Sw(a) ┐ │ W(y)
│ │ │ ↓
│ └> Sr(a) ┌ Sw(b)
│ ↓ │ │
│ Sr(b)<─┘ │
│ ↓ │
│ R(x) │
│ ↓ │
│ R(y) │
│ │ │
V V V
图表上:
- 时间往下流
W(x)
和R(x)
是常规操作:写入和读取x
Sw(a)
和Sr(a)
是 SC 原子:a
的写入和读取
- 在每个线程中,操作按程序顺序发生(在 C++ 中又称为
sequenced-before order
):按照它们在代码中的顺序 - 线程间
happens-before
由SC原子建立
请注意图表上的箭头始终向下
=> 图形不能有循环
=> 它总是一个 DAG
=> happens-before
不能违反公理
相同的证明不适用于 release/acquire
原子,因为(据我所知)它们不会以全局顺序发生 => Sw(a)
和 [= 之间的 HB 箭头54=] 可能会向上 => 一个循环是可能的。 (我不确定)
I would like to know if release+acquire can violate happens-before.
Happens-before relationship 不能被“违反”,因为它是保证。意思是,如果您以正确的方式建立它,它就会存在,并带有所有含义(除非编译器中存在错误)。
但是,建立任何 发生前的关系并不能保证您已经避免了所有可能的race conditions。您需要在相关操作之间建立精心选择的关系,这将消除所有可能发生数据竞争的情况。
让我们回顾一下这段代码:
// Thread 1
x.store(1, std::memory_order_release);
// Thread 2
y.store(1, std::memory_order_release);
// Thread 3
while (x.load(std::memory_order_acquire) != 1);
if (y.load(std::memory_order_acquire) == 0) {
x_then_y = true;
}
// Thread 4
while (y.load(std::memory_order_acquire) != 1);
if (x.load(std::memory_order_acquire) == 0) {
y_then_x = true;
}
如您所见,T1
和 T2
使用 memory_order_release
内存排序更新 x
和 y
。 T3
和 T4
使用 memory_order_acquire
.
现在,引用 cppreference:
Release-Acquire ordering If an atomic store in thread
A
is taggedmemory_order_release
and an atomic load in threadB
from the same variable is taggedmemory_order_acquire
, all memory writes (non-atomic and relaxed atomic) that happened-before the atomic store from the point of view of threadA
, become visible side-effects in threadB
. That is, once the atomic load is completed, threadB
is guaranteed to see everything threadA
wrote to memory.The synchronization is established only between the threads releasing and acquiring the same atomic variable. Other threads can see different order of memory accesses than either or both of the synchronized threads.
它明确表示,只有对应线程中的store-load
对之间建立关系。 load-load
对之间没有关系。 回到我们的例子,happens-before 关系将形成下图:
如您所见,T1和T2、T3和T4之间没有任何关系,也没有总序。 T3 和 T4 可以任意顺序查看 T1 和 T2 的副作用。
上面的代码片段在 cppreference
中用于说明情况,当 memory_order_acquire
+ memory_order_release
可能太弱而无法避免数据竞争(但这并不意味着这个例子违反了 happens-before 或内存模型,只是有 happens-before 可能不足以避免所有可能的数据竞争!)。
如果 memory_order_seq_cst
用于上述示例中的所有操作,则将在 T3 和 T4 中的 load
操作之间额外建立 happens-before。
意思是,当第一个 while(x.load) != 1
或 while(y.load) != 1
通过时,它 保证 在另一个 x.load
或 y.load
之后线程将得到 1
的结果,确保 x_then_y
和 y_then_x
不能同时为真。
请注意,在 java 中,为了简单起见,原子操作和 volatile
操作始终与 memory_order_seq_cst
类似(在某些情况下会牺牲性能)。
Happens-before 是 sequenced-before 和 synchronizes-with 的传递闭包。 Sequenced-before 只是每个线程内的程序顺序,而 synchronizes-with 发生在获取加载从发布存储获取其值时。所以在你的程序中,为了让两个断言都通过,必须满足以下关系:
T3.x==1
发生在T3.y==0
(排序) 之前
T4.y==1
发生在T4.x==0
之前(同样)T1.x=1
发生在T3.x==1
之前(获取负载从发布存储获取其值)T2.y=1
发生在T4.y==1
之前(同样)T1.x=1
发生在T3.y==0
之前(为了传递性)T2.y=1
发生在T4.x==0
之前(同样)
您可以检查这是否满足偏序的所有公理(反对称和传递)以及两个断言传递所隐含的所有 C++ 一致性规则。例如,T2.y=1
一定不会出现在 T3.y==0
之前,实际上我们的排序中不存在这种关系。但是 T3.y==0
发生在 T2.y=1
之前也是不正确的,这没有错;毕竟是部分订单。 T2.y=1
和 T3.y==0
只是无序的。
因为有一个有效的 happens-before 顺序与两个断言通过一致,所以当您 运行 程序时,两个断言都可以通过。
的确,如果 T3.y==0
和 T2.y=1
之间存在某种先行关系,并且 T4.x==0
和 T1.x=1
之间存在同样的关系,那么每个组合会导致一些违反规则的行为:要么是违反一致性,要么是部分顺序中的循环。但是同样,它们无序是完全可以的,这样就不会发生违规。
如果加载和存储都是松弛的,或者即使 x
和 y
根本不是原子的,那么上面的关系 3 和 4 不会被任何规则暗示,因此happens-before 排序将变得简单:
T3.x==1
发生在T3.y==0
(排序) 之前
T4.y==1
发生在T4.x==0
之前(同样)
这也与通过的两个断言一致。 (在非原子情况下,T1.x=1
与 x
的负载无序的事实将意味着存在数据竞争,因此该行为在 C++ 中未定义。在不同的语言中,如 Java,我们可能已经定义了表示两个加载都成功并且 return 为 0 或 1 的行为,但我们仍然可以让两个断言都通过。)如果您认为将程序更改为使用非原子加载并且stores 会阻止这两个断言通过,你错了。
所以获取和释放实际上加强了排序;必须保持 更多 关系,并且程序的行为变得 更好 定义。
回答:不,release/acquire不能中断happens-before。
证明由 Nate Eldredge 在
Oh, indeed. And actually, I might see how to prove it. The HB relation is transitive by its construction. The sequencing relation is acyclic, so if there is a cycle in HB, it must contain at least one synchronizes-with step, which is, roughly, an acquire load L that takes its value from a release store S. But because of the cycle, L happens before S. Therefore by p14, L must take its value from some store other than S, contradiction. Not quite a proof because I have oversimplified the definition of synchronizes-with from atomics.order p2, but it's a start.
我只是想把它放在一个单独的答案中,以便人们更容易注意到。
此外,这里有我的额外解释(也许这会让某些人更容易理解)。
首先,如果我们只使用 release/acquire
原子和非原子内存访问,那么 happens-before
是可传递的(和非循环的)构造。
类似于SC
图,在release/acquire
的情况下,边也总是指向下方:
Thread1 Thread2 Thread3
======= ======= =======
│ │ │
│ ┌ Wrel(a)──┐ │
│ │ │ │ │
Racq(a)<┘ │ │ │
│ ↓ │ │
│ ┌ Wrel(b) ┐│ │
↓ │ │ ││ │
Racq(b)<┘ │ └─> Racq(b)
│ │ │ ↓
│ │ └> Racq(a)
│ │ │
V V V
(顺便说一下,这张图不同于 SC
:Thread 1
和 Thread 3
请参阅 Wrel(a)
和 Wrel(b)
订单。但边缘仍然指向下方)
从 Wrel(x)
到 Racq(x)
的边总是指向下方,因为 Racq(x)
看到 Wrel(x)
和 之前的所有内容 Wrel(x)
已完成(请参阅答案末尾的注释)。
(在 C++ 规范中,这称为 synchronizes-with
,您可以了解更多信息 here。)
因此,与 SC
图形类似,所有边始终指向下方
=> 图形不能有循环
=> 它总是一个 DAG
=> happens-before
不能违反公理
实际上 happens-before
由 release/acquire
原子学产生 — 基本上是 Leslie Lamport 在 Time, Clocks and the Ordering of Events in a Distributed System.
中介绍的原始 happens-before
我真的建议所有对 HB
感兴趣的人阅读这篇论文 — Lamport 的解释简短明了,这个想法真的很酷。
我们也用图片来演示为什么循环是不可能的。
这是一个循环的样子:
Thread1 Thread2 Thread3
======= ======= =======
│ │ │
Racq(a)<─────│──────────│─────┐
↓ │ │ │
Wrel(b) ┐ │ │ │
│ │ │ │ │
│ └> Racq(b) │ │
│ ↓ │ │
│ Wrel(c) ┐ │ │
│ │ │ │ │
│ │ └> Racq(c) │
│ │ ↓ │
│ │ Wrel(a) ┘
│ │ │
V V V
在每个线程中 happens-before
是源代码中的操作顺序(在 C++ 中称为 sequenced-before
,在 Java 中称为 program order
)。
显然,这里不可能有 HB
个循环。
这意味着“返回”并关闭循环的边缘必须是 synchronizes-with
边缘,如上图中的 Wrel(a)->Racq(a)
边缘。
注意矛盾:
Wrel(a)
必须在Racq(a)
之前完成,因为Racq(a)
读取的是Wrel(a)
写入的值
Racq(a)
必须在Wrel(a)
之前完成,因为有一个链Racq(a)->Wrel(b)->Racq(b)->Wrel(c)->Racq(c)->Wrel(a)
,其中每个Wrel(x)
(以及它之前的所有内容)在Racq(x)
读取之前完成它。
这意味着 Wrel(a)->Racq(a)
边缘是不允许的 => 循环是不可能的。
就 C++ 内存模型而言,它违反了 coherence requirements:
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.
注释。
我声明:
Racq(x)
seesWrel(x)
and everything beforeWrel(x)
as completed
但在 C++ 标准中没有直接说明。
相反它有这个:
happens-before
定义了读取所看到的内容Racq(x)
和Wrel(x)
之间的关系称为synchronizes-with
happens-before
是根据synchronizes-with
和大量其他规则和命令构建的
可以从 C++ 标准中推导出我的陈述,尽管这可能并不容易。 (这就是为什么我建议改为阅读 this article)。
我使用该语句是因为它简洁地描述了内存屏障指令的作用,这就是 happens-before
可以(并且可能)很容易实现的方式。
通常,内存屏障指令就是我们实现 happens-before
及其所有数学属性所需要的全部。
对于不同 CPU 上的这些指令的概述,我会推荐 Paul E. McKenney 在 Memory Barriers: a Hardware View for Software Hackers 中的相关部分。
(例如,PowerPC 中的内存屏障与 C++ 中的 release/acquire
原子基本相同)
只有当Thread1 Thread2 Thread3 ======= ======= ======= │ │ │ │ ┌ Wrel(a)──┐ │ │ │ │ │ │ Racq(a)<┘ │ │ │ │ ↓ │ │ │ ┌ Wrel(b) ┐│ │ ↓ │ │ ││ │ Racq(b)<┘ │ └─> Racq(b) │ │ │ ↓ │ │ └> Racq(a) │ │ │ V V V
(BTW notice that this graph is different from
SC
:Thread 1
andThread 3
seeWrel(a)
andWrel(b)
in different orders. But edges point downwards nonetheless)
Wrel(a)
和Wrel(b)
来自不同线程时,Thread 1
和Thread 3
才能看到Wrel(a)
和Wrel(b)
的顺序不同。
这就是所谓的 IRIW(独立写入的独立读取)测试。
所以片段应该改成这样:
Thread1 Thread2 Thread3 Thread4 ======= ======= ======= ======= │ │ │ │ │ ┌ Wrel(a)┐ │ │ Racq(a)<┘ │ │┌ Wrel(b)┐ │ ↓ │ ││ │ └> Racq(b) Racq(b)<─────│───│┘ │ ↓ │ │ └─────│────> Racq(a) │ │ │ │ V V V V
(BTW notice that this graph is different from
SC
:Thread 1
andThread 4
seeWrel(a)
andWrel(b)
in different orders. But edges point downwards nonetheless)
顺便说一下,我本可以将其作为已接受答案的建议编辑。
我没有这样做是因为它是一个非常专业的主题,所以审稿人可能不知道所有的细微差别和细节,并拒绝编辑只是因为它确实修复了一个错误并不明显。
但我认为这是一个值得一提和修复的错误。 所以我把修复放在这个答案中,因为:
- 对此特定主题感兴趣的人可能会看到修复程序
- 人们可能会投票赞成这个答案(和修复)=> 如果有足够的票数,那么这将表明修复是正确的 => 修复将被版主或有问题的人纳入接受的答案足够的声望