64

C++11 标准定义了一个内存模型（1.7、1.10），其中包含内存排序，大致为“顺序一致”、“获取”、“使用”、“释放”和“松弛”。同样粗略地说，一个程序只有在它是无竞争的情况下才是正确的，如果所有动作都可以按照一个动作发生的顺序排列——在另一个动作发生之前，就会发生这种情况。动作 X 在动作Y之前发生的方式是X在Y之前排序（在一个线程内），或者X 线程间发生在 Y 之前。除其他外，当

  • X与Y同步，或
  • X在Y之前是依赖排序的。

当X是在某个原子变量上具有“释放”顺序的原子存储，并且Y是在同一变量上具有“获取”顺序的原子负载时，会发生同步。在Y加载“消费”排序（以及合适的内存访问）的类似情况下，会发生依赖排序之前的情况。synchronizes-with的概念将happens-before关系传递地扩展到在线程中被排序在另一个之前的动作，但是依赖排序之前仅通过被调用的sequenced-before的严格子集传递地扩展携带依赖，它遵循一组较大的规则，特别是可以被std::kill_dependency.

那么，“依赖排序”概念的目的是什么？与更简单的先排序/同步排序相比，它有什么优势？由于它的规则更严格，我认为可以更有效地实施。

您能否举一个程序示例，其中从发布/获取切换到发布/使用既正确又提供了重要的优势？什么时候会std::kill_dependency提供改进？高级别的论点会很好，但对于特定于硬件的差异会加分。

4

4 回答 4

13

N2492引入了数据依赖排序 ，其基本原理如下：

有两个重要的用例，其中当前的工作草案 (N2461) 不支持在某些现有硬件上可能实现的可扩展性。

  • 对很少写入的并发数据结构的读取访问

很少编写的并发数据结构在操作系统内核和服务器风格的应用程序中都很常见。示例包括表示外部状态的数据结构（如路由表）、软件配置（当前加载的模块）、硬件配置（当前使用的存储设备）和安全策略（访问控制权限、防火墙规则）。超过 10 亿比 1 的读写比率相当普遍。

  • 指针介导发布的发布-订阅语义

线程之间的许多通信都是以指针为中介的，其中生产者发布一个指针，消费者可以通过该指针访问信息。无需完全获取语义即可访问该数据。

在这种情况下，线程间数据依赖排序的使用导致了数量级的加速，并在支持线程间数据依赖排序的机器上实现了类似的可扩展性改进。这样的加速是可能的，因为这样的机器可以避免昂贵的锁获取、原子指令或内存栅栏，否则这些都是需要的。

强调我的

那里提出的激励用例rcu_dereference()来自 Linux 内核

于 2013-10-31T18:29:25.370 回答
12

Load-consume 与 load-acquire 非常相似，不同之处在于它只对依赖于 load-consume 的数据的表达式评估诱导发生之前的关系。用结果包装表达式kill_dependency会产生一个不再携带来自负载消耗的依赖关系的值。

关键用例是编写器按顺序构造数据结构，然后将共享指针摆动到新结构（使用 arelease或acq_relatomic）。reader 使用 load-consume 读取指针，并取消引用它以获取数据结构。取消引用创建了数据依赖关系，因此可以保证读者看到初始化的数据。

std::atomic<int *> foo {nullptr};
std::atomic<int> bar;

void thread1()
{
    bar = 7;
    int * x = new int {51};
    foo.store(x, std::memory_order_release);
}

void thread2()
{
    int *y = foo.load(std::memory_order_consume)
    if (y)
    {
        assert(*y == 51); //succeeds
        // assert(bar == 7); //undefined behavior - could race with the store to bar 
        // assert(kill_dependency(*y) + bar == 58) // undefined behavior (same reason)
        assert(*y + bar == 58); // succeeds - evaluation of bar pulled into the dependency 
    }
}

提供负载消耗有两个原因。主要原因是 ARM 和 Power 负载保证会消耗，但需要额外的防护才能将它们转化为获取。（在 x86 上，所有加载都是获取的，因此在简单编译下消耗不会提供直接的性能优势。）第二个原因是编译器可以将后面的操作移动到消耗之前而不依赖于数据，而对于获取则无法做到这一点. （启用此类优化是将所有这些内存排序构建到语言中的重要原因。）

包装一个值kill_dependency允许计算一个表达式，该表达式取决于在加载消耗之前要移动到的值。这很有用，例如，当值是先前读取的数组的索引时。

请注意，使用消耗会导致不再传递的发生之前的关系（尽管它仍然保证是非循环的）。例如，存储 tobar发生在存储到 foo 之前，它发生在取消引用之前y，发生在读取之前bar（在注释掉的断言中），但存储到bar不会发生在读取之前bar。这导致了更复杂的happens-before定义，但您可以想象它是如何工作的（从sequenced-before开始，然后通过任意数量的release-consume-dataDependency或release-acquire-sequencedBefore链接传播）

于 2013-11-05T10:58:20.287 回答
8

Jeff Preshing 有一篇很棒的博文回答了这个问题。我自己无法添加任何内容，但认为任何想了解消费与获取的人都应该阅读他的帖子：

http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/

他展示了一个特定的 C++ 示例以及跨三种不同架构的相应基准汇编代码。与 相比memory_order_acquire，memory_order_consume在 PowerPC 上可能提供 3 倍的加速，在 ARM 上提供 1.6 倍的加速，而在 x86 上的加速可以忽略不计，无论如何都具有很强的一致性。问题是，在他写这篇文章的时候，只有 GCC 实际对待消费语义与获取语义有任何不同，并且可能是因为一个错误。尽管如此，它表明如果编译器编写者能够弄清楚如何利用它，则可以使用加速。

于 2015-10-11T04:36:32.327 回答
5

我想记录一个部分发现，即使这不是一个真正的答案，也不意味着正确的答案不会有很大的赏金。

在盯着 1.10 看了一会儿之后，特别是第 11 段中非常有用的注释，我认为这实际上并不难。synchronizes-with (henceforth: s/w) 和dependency-ordered-before (dob)之间的最大区别在于， happens-before关系可以通过任意连接sequenced-before (s/b) 和 s/w 来建立，但是dob不是这样。请注意线程间的定义之一发生在之前：

A同步X并X在之前排序B

但是类似的语句 for Ais dependency-ordered beforeX丢失了！

因此，通过发布/获取（即 s/w），我们可以订购任意事件：

A1    s/b    B1                                            Thread 1
                   s/w
                          C1    s/b    D1                  Thread 2

但现在考虑这样的任意事件序列：

A2    s/b    B2                                            Thread 1
                   dob
                          C2    s/b    D2                  Thread 2

A2 在这个序列中， happens-before 仍然是正确的C2（因为A2是 s/bB2和B2 线程间发生在 C2dob 之前；但我们可以争辩说你永远无法真正分辨！）。但是，happens -before是不正确的。事件和不是相对于彼此排序的，除非它实际上持有对的依赖。这是一个更严格的要求，如果没有这个要求，-to-不能“跨”发布/使用对进行排序。A2 D2A2D2C2 D2A2D2

换句话说，发布/消费对只传播动作的顺序，这些动作携带从一个到下一个的依赖关系。不依赖的所有内容都不会在发布/消费对中排序。

此外，请注意，如果我们附加一个最终的、更强大的发布/获取对，则顺序会恢复：

A2    s/b    B2                                                         Th 1
                   dob
                          C2    s/b    D2                               Th 2
                                             s/w
                                                    E2    s/b    F2     Th 3

现在，根据引用的规则，D2 线程间发生 before F2，因此C2andB2也是如此，因此A2 发生之前 F2。但请注意， and之间仍然没有排序——排序只是介于和之后的A2事件之间。D2A2

总之，依赖携带是一般排序的严格子集，并且发布/使用对仅在携带依赖的动作之间提供排序。只要不需要更强的排序（例如通过释放/获取对），理论上就有可能进行额外的优化，因为不在依赖链中的所有内容都可以自由重新排序。

也许这是一个有意义的例子？

std::atomic<int> foo(0);

int x = 0;

void thread1()
{
    x = 51;
    foo.store(10, std::memory_order_release);
}

void thread2()
{
    if (foo.load(std::memory_order_acquire) == 10)
    {
        assert(x == 51);
    }
}

如所写，代码是无竞争的，并且断言将保持，因为释放/获取对x = 51在断言中的加载之前对存储进行排序。但是，通过将“acquire”更改为“consume”，这将不再是真的，并且程序将在 上发生数据竞争x，因为x = 51存储到foo. 优化点是这个 store 可以自由地重新排序，而不用关心在foo做什么，因为没有依赖关系。

于 2013-10-27T23:18:46.343 回答