可以释放+获得中断发生之前吗?

Can release+acquire break happens-before?

今天的许多编程语言都有 happens-before 关系和 release+acquire 同步操作。

其中一些编程语言:

我想知道release+acquire是否可以违反happens-before:


什么是release+acquirehappens-before

Release/acquire 在不同线程之间建立 happens-before 关系:换句话说,Thread 1release 之前的所有内容都保证在 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
这意味着它是:


为什么我认为 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 3Thread 4看到写入xy的顺序不同。

据我了解,如果是普通变量,那么这将违反happens-before的不对称性属性。 但是因为 x 和 y 是原子,所以没关系。 (顺便说一句,我不确定)
Nate Eldredge 这个 IRIW 示例是可以的。

但我仍然暗暗怀疑可能存在类似于 IRIW 的东西,这会导致 Thread 3Thread 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 原子以全局顺序发生(所有线程都相同),并且:

看看这个 happens-before 图表:

 Thread1  Thread2  Thread3 
 =======  =======  ======= 
    │        │        │    
   W(x)      │        │    
    ↓        │        │    
   Sw(a) ┐   │       W(y)  
    │    │   │        ↓    
    │    └> Sr(a)  ┌ Sw(b) 
    │        ↓     │  │    
    │       Sr(b)<─┘  │    
    │        ↓        │    
    │       R(x)      │    
    │        ↓        │    
    │       R(y)      │    
    │        │        │    
    V        V        V    

图表上:

请注意图表上的箭头始终向下
=> 图形不能有循环
=> 它总是一个 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;
}

如您所见,T1T2 使用 memory_order_release 内存排序更新 xyT3T4 使用 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) != 1while(y.load) != 1 通过时,它 保证 在另一个 x.loady.load 之后线程将得到 1 的结果,确保 x_then_yy_then_x 不能同时为真。


请注意,在 java 中,为了简单起见,原子操作和 volatile 操作始终与 memory_order_seq_cst 类似(在某些情况下会牺牲性能)。

Happens-before 是 sequenced-before 和 synchronizes-with 的传递闭包。 Sequenced-before 只是每个线程内的程序顺序,而 synchronizes-with 发生在获取加载从发布存储获取其值时。所以在你的程序中,为了让两个断言都通过,必须满足以下关系:

  1. T3.x==1 发生在 T3.y==0(排序)
  2. 之前
  3. T4.y==1 发生在 T4.x==0 之前(同样)
  4. T1.x=1 发生在 T3.x==1 之前(获取负载从发布存储获取其值)
  5. T2.y=1 发生在 T4.y==1 之前(同样)
  6. T1.x=1 发生在 T3.y==0 之前(为了传递性)
  7. T2.y=1 发生在 T4.x==0 之前(同样)

您可以检查这是否满足偏序的所有公理(反对称和传递)以及两个断言传递所隐含的所有 C++ 一致性规则。例如,T2.y=1 一定不会出现在 T3.y==0 之前,实际上我们的排序中不存在这种关系。但是 T3.y==0 发生在 T2.y=1 之前也是不正确的,这没有错;毕竟是部分订单。 T2.y=1T3.y==0 只是无序的。

因为有一个有效的 happens-before 顺序与两个断言通过一致,所以当您 运行 程序时,两个断言都可以通过。

的确,如果 T3.y==0T2.y=1 之间存在某种先行关系,并且 T4.x==0T1.x=1 之间存在同样的关系,那么每个组合会导致一些违反规则的行为:要么是违反一致性,要么是部分顺序中的循环。但是同样,它们无序是完全可以的,这样就不会发生违规。

如果加载和存储都是松弛的,或者即使 xy 根本不是原子的,那么上面的关系 3 和 4 不会被任何规则暗示,因此happens-before 排序将变得简单:

  1. T3.x==1 发生在 T3.y==0(排序)
  2. 之前
  3. T4.y==1 发生在 T4.x==0 之前(同样)

与通过的两个断言一致。 (在非原子情况下,T1.x=1x 的负载无序的事实将意味着存在数据竞争,因此该行为在 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    

(顺便说一下,这张图不同于 SCThread 1Thread 3 请参阅 Wrel(a)Wrel(b)订单。但边缘仍然指向下方)

Wrel(x)Racq(x) 的边总是指向下方,因为 Racq(x) 看到 Wrel(x) 之前的所有内容 Wrel(x) 已完成(请参阅答案末尾的注释)。
(在 C++ 规范中,这称为 synchronizes-with,您可以了解更多信息 here。)

因此,与 SC 图形类似,所有边始终指向下方
=> 图形不能有循环
=> 它总是一个 DAG
=> happens-before 不能违反公理

实际上 happens-beforerelease/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 1Thread 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)


顺便说一下,我本可以将其作为已接受答案的建议编辑。

我没有这样做是因为它是一个非常专业的主题,所以审稿人可能不知道所有的细微差别和细节,并拒绝编辑只是因为它确实修复了一个错误并不明显。

但我认为这是一个值得一提和修复的错误。 所以我把修复放在这个答案中,因为:

  • 对此特定主题感兴趣的人可能会看到修复程序
  • 人们可能会投票赞成这个答案(和修复)=> 如果有足够的票数,那么这将表明修复是正确的 => 修复将被版主或有问题的人纳入接受的答案足够的声望