3

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

其中一些编程语言：

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

  • 如果可能的话，那么我想看一个例子
  • 如果不可能，那么我想得到简单明了的解释为什么
什么是release+acquire和happens-before

Release/acquire建立happens-before不同线程之间的关系：换句话说，之前releasein的所有内容都Thread 1保证在Thread 2after中可见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还是严格的偏序。
这意味着它是：

  • 传递性：Thread 2保证不仅可以看到 的写入Thread 1，还可以Thread 1看到其他线程的所有写入
  • 不对称：ahappens-beforeb或bhappens-beforea都不允许
为什么我认为这release/acquire可能会破坏happens-before

正如我们从 IRIW 石蕊测试中知道的那样，release/acquire可能导致两个线程以不同的顺序查看来自不同线程的写入（对于 C++，另请参见此处的最后一个示例，以及来自 gcc wiki的这 两个示例）：

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

这里两个asserts 都可以通过，这意味着Thread 3和see 以不同的顺序Thread 4写入。xy

据我了解，如果它是普通变量，那么这将违反happens-before的不对称属性。但是因为 x 和 y 是原子的，所以没关系。（顺便说一句，我不确定）
Nate Eldredge在他的回答中证明这个 IRIW 示例是可以的。

但我仍然有一个偷偷摸摸的怀疑，可能存在类似于 IRIW 的东西，它会导致Thread 3并Thread 4看到常规写入以不同的顺序发生在发生之前——这会破坏发生在之前（它不再是传递的）。

注1

在cppreference中也有这样的引用：

该实现需要通过在必要时引入额外的同步来确保发生之前的关系是非循环的（只有在涉及消费操作时才需要，参见 Batty 等人）

引用暗示可能存在happens-before违反并需要额外同步的情况（“无环”意味着发生之前形成有向无环图，相当于说“严格偏序”）。

如果可能的话，我想知道这些情况是什么。

笔记2

由于 java 允许数据竞争，我也对happens-before仅在存在数据竞争时违反的情况感兴趣。

编辑 1（2021 年 11 月 3 日）

举个例子，这里解释了为什么顺序一致（SC）原子不能违反happens-before.
（对释放/获取原子的类似解释将是我问题的答案）。

“违反happens-before”我的意思是“违反 的公理happens-before，这是一个严格的偏序”。

严格的偏序直接对应于有向无环图 (DAG)。

这是来自 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
  • 在每个线程内，操作按程序顺序（sequenced-before order在 C++ 中也称为）发生：按照它们在代码中的顺序
  • 线程之间happens-before由 SC atomics 建立

请注意，图上的箭头始终向下
=> 图不能有环
=> 它始终是 DAG
=>happens-before不能违反公理

相同的证明不适用于release/acquire原子，因为（据我所知）它们不会以全局顺序发生=>之间的HB箭头Sw(a)并且Sr(a)可能向上=>可能存在循环。（对此我不确定）

4

4 回答 4

5

Happens-before 是 sequenced-before 和 synchronizes-with 的传递闭包。Sequenced-before 只是每个线程内的程序顺序，并且当获取负载从发布存储中获取其值时发生同步。所以在你的程序中，为了让两个断言都通过，以下关系必须成立：

  1. T3.x==1发生在T3.y==0（排序）之前
  2. T4.y==1发生在T4.x==0（同样）之前
  3. T1.x=1发生在之前T3.x==1（获取负载从发布存储中获取其值）
  4. T2.y=1发生在T4.y==1（同样）之前
  5. T1.x=1发生在T3.y==0（传递性）之前
  6. 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只是无序的。

由于存在与两个断言通过一致的有效发生前排序，因此当您运行程序时，两个断言都可能通过。

确实，如果在任一方向之间T3.y==0以及在和之间存在一些先发生的关系，那么每个组合都会导致违反规则：要么违反一致性，要么是偏序中的循环。但是同样，它们是无序的完全没问题，然后就不会发生违规。T2.y=1T4.x==0T1.x=1

如果加载和存储都放松了，或者即使x并且y根本不是原子的，那么上面的关系 3 和 4 将不会被任何规则暗示，因此发生前的排序将变得简单：

  1. T3.x==1发生在T3.y==0（排序）之前
  2. T4.y==1发生在T4.x==0（同样）之前

这也与两个断言的通过一致。（在非原子情况下，T1.x=1负载无序的事实x意味着存在数据竞争，因此行为在 C++ 中是未定义的。在 Java 等不同的语言中，我们可能已经定义了表示两个负载的行为成功并返回 0 或 1，但我们仍然可以让两个断言都通过。）如果您认为将程序更改为使用非原子加载和存储会阻止两个断言通过，那您就错了。

因此，获取和释放实际上加强了排序；有更多的关系必须保持，程序的行为变得更好定义。

于 2021-11-02T03:07:01.807 回答
2

已接受答案的以下片段有错误：

 Thread1   Thread2     Thread3 
 =======   =======     ======= 
    │         │           │    
    │     ┌ Wrel(a)──┐    │    
    │     │   │      │    │    
  Racq(a)<┘   │      │    │    
    │         ↓      │    │    
    │     ┌ Wrel(b) ┐│    │    
    ↓     │   │     ││    │    
  Racq(b)<┘   │     └─> Racq(b)
    │         │      │    ↓    
    │         │      └&gt; Racq(a)
    │         │           │    
    V         V           V

（顺便说一句，该图与SC:不同，Thread 1并且以不同的顺序Thread 3查看Wrel(a)和Wrel(b)。但边缘仍然指向下方）

Thread 1并且只有在来自不同线程时Thread 3才能看到不同Wrel(a)的顺序。Wrel(b)Wrel(a)Wrel(b)

这就是所谓的 IRIW（独立读取独立写入）测试。

所以片段应该改成这样：

Thread1   Thread2   Thread3   Thread4
=======   =======   =======   =======
   │         │         │         │   
   │    ┌ Wrel(a)┐     │         │   
Racq(a)<┘    │   │┌ Wrel(b)┐     │   
   ↓         │   ││    │   └&gt; Racq(b)
Racq(b)<─────│───│┘    │         ↓   
   │         │   └─────│────> Racq(a)
   │         │         │         │   
   V         V         V         V

（顺便说一句，该图与SC:不同，Thread 1并且以不同的顺序Thread 4查看Wrel(a)和Wrel(b)。但边缘仍然指向下方）

顺便说一句，我本可以将此作为已接受答案的建议编辑。

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

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

  • 对此特定主题感兴趣的人可能会看到修复
  • 人们可能会投票给这个答案（和修复）=> 如果有足够的选票，那么这将表明修复是正确的 => 修复将被版主或具有足够声誉的人纳入接受的答案
于 2021-11-15T13:23:03.157 回答
0

我想知道release+acquire是否会违反happens-before。

Happens-before 关系不能“违反”，因为它是一种保证。意思是，如果您以正确的方式建立它，它就会在那里，并具有所有含义（除非编译器中存在错误）。

但是，仅仅建立任何发生前的关系并不能保证您已经避免了所有可能的竞争条件。您需要在相关操作之间建立仔细选择的关系，这将消除可能发生数据竞争的所有情况。

让我们回顾一下这段代码：

// 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和x使用y内存memory_order_release排序。T3并T4使用memory_order_acquire.

现在，引用 cppreference：

Release-Acquire ordering 如果标记了线程A中的原子存储并且标记了来自同一变量的memory_order_release线程中的原子加载，则从线程的角度来看，在原子存储之前发生的所有内存写入（非原子和宽松原子），在线程中成为可见的副作用。也就是说，一旦原子加载完成，线程就可以保证看到线程写入内存的所有内容。Bmemory_order_acquireABBA

仅在释放和获取相同原子变量的线程之间建立同步。与同步线程中的一个或两个线程相比，其他线程可以看到不同的内存访问顺序。

它明确表示，仅建立store-load相应线程中的对之间的关​​系。对之间不形成任何关系load-load。回到我们的例子，happens-before 关系将形成下图：

如您所见，T1 和 T2 或 T3 和 T4 之间没有关系，也没有总顺序。T3 和 T4 可以任意顺序查看 T1 和 T2 的副作用。

上面的代码片段用于cppreference说明这种情况，当memory_order_acquire+memory_order_release可能太弱而无法避免数据竞争时（但这并不意味着这个例子违反了发生之前或内存模型，只是发生之前可能不会足以避免所有可能的数据竞争！）。

如果memory_order_seq_cst上面示例中的所有操作都使用了，那么load在 T3 和 T4 中的操作之间将另外建立发生之前。

意思是，当第一次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（在某些情况下会牺牲性能）。

于 2021-11-01T03:51:04.723 回答
0

回答：不，释放/获取不能中断发生在之前。

Nate Eldredge 在此评论中给出了证明：

哦，确实。实际上，我可能会看到如何证明这一点。HB 关系因其构造而具有传递性。排序关系是非循环的，所以如果在 HB 中有一个循环，那么它必须至少包含一个 synchronizes-with 步骤，大致就是一个从发布存储 S 中获取其值的获取负载 L。但是由于循环, L 发生在 S 之前。因此，通过 p14，L 必须从 S 之外的某个存储中获取其值，矛盾。不完全是一个证据，因为我从 atomics.order p2 中过度简化了 synchronizes-with 的定义，但这是一个开始。

我只是想把它放在一个单独的答案中，以便人们更容易注意到。

另外，这里是我的其他解释（也许它会让某些人更容易理解）。

首先，如果我们只使用release/acquire原子和非原子内存访问，那么happens-before通过构造是传递的（和非循环的）。

SC与图类似，在release/acquire边缘的情况下也总是指向下方：

 Thread1   Thread2     Thread3 
 =======   =======     ======= 
    │         │           │    
    │     ┌ Wrel(a)──┐    │    
    │     │   │      │    │    
  Racq(a)<┘   │      │    │    
    │         ↓      │    │    
    │     ┌ Wrel(b) ┐│    │    
    ↓     │   │     ││    │    
  Racq(b)<┘   │     └─> Racq(b)
    │         │      │    ↓    
    │         │      └&gt; 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，您可以在此处了解更多信息。）

结果，与SC图类似，所有边始终指向下方
=> 图不能有环
=> 它始终是 DAG
=>happens-before不能违反公理

实际上happens-before是由原子产生的release/acquire——基本上是happens-beforeLeslie Lamport 在分布式系统中的时间、时钟和事件排序中介绍的原版。
我真的建议所有感兴趣的人阅读这篇论文HB——Lamport 的解释简短而清晰，这个想法真的很酷。

让我们也用图片来演示为什么循环是不可能的。

这是一个循环的样子：

 Thread1    Thread2    Thread3   
 =======    =======    =======   
    │          │          │      
  Racq(a)<─────│──────────│─────┐
    ↓          │          │     │
  Wrel(b) ┐    │          │     │
    │     │    │          │     │
    │     └&gt; Racq(b)      │     │
    │          ↓          │     │
    │        Wrel(c) ┐    │     │
    │          │     │    │     │
    │          │     └&gt; Racq(c) │
    │          │          ↓     │
    │          │        Wrel(a) ┘
    │          │          │      
    V          V          V

在每个线程happens-before中是源代码中的操作顺序（它sequenced-before在 C++ 和program orderJava 中调用）。
显然，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++ 内存模型而言，它违反了一致性要求：

由评估 B 确定的原子对象 M 的值应是由修改 M 的某些副作用 A 存储的值，其中 B 不会发生在 A 之前。

笔记。

我说：

Racq(x)看到之前Wrel(x)的一切都已 Wrel(x)完成

但在 C++ 标准中没有直接说明。
相反，它有这个：

  • happens-before是什么定义了阅读所见
  • Racq(x)和之间的关系Wrel(x)称为synchronizes-with
  • happens-before由synchronizes-with大量其他规则和命令构建而成

可以从 C++ 标准中推断出我的陈述，尽管这可能并不容易。（这就是为什么我建议改为阅读这篇文章）。

我使用该语句是因为它简洁地描述了内存屏障指令的作用，这就是如何happens-before（并且可能是）轻松实现的。因此，通常我们只需要使用其所有数学属性
来实现内存屏障指令。 有关在不同 CPU 上的这些指令的概述，我会推荐Paul E. McKenney的Memory Barriers: a Hardware View for Software Hackers中的部分。 （例如，PowerPC 中的内存屏障与C++ 中的原子基本相同）happens-before

release/acquire

于 2021-11-11T16:47:10.920 回答