Acquire/release 具有 4 个线程的语义

Acquire/release semantics with 4 threads

我目前正在阅读 Anthony Williams 的《C++ 并发实战》。他的清单之一显示了这段代码,他声明 z != 0 可以触发的断言。

#include <atomic>
#include <thread>
#include <assert.h>

std::atomic<bool> x,y;
std::atomic<int> z;

void write_x()
{
    x.store(true,std::memory_order_release);
}

void write_y()
{
    y.store(true,std::memory_order_release);
}

void read_x_then_y()
{
    while(!x.load(std::memory_order_acquire));
    if(y.load(std::memory_order_acquire))
        ++z;
}

void read_y_then_x()
{
    while(!y.load(std::memory_order_acquire));
    if(x.load(std::memory_order_acquire))
        ++z;
}

int main()
{
    x=false;
    y=false;
    z=0;
    std::thread a(write_x);
    std::thread b(write_y);
    std::thread c(read_x_then_y);
    std::thread d(read_y_then_x);
    a.join();
    b.join();
    c.join();
    d.join();
    assert(z.load()!=0);
}

所以不同的执行路径,我能想到的是:

1)

Thread a (x is now true)
Thread c (fails to increment z)
Thread b (y is now true)
Thread d (increments z) assertion cannot fire

2)

Thread b (y is now true)
Thread d (fails to increment z)
Thread a (x is now true)
Thread c (increments z) assertion cannot fire

3)

Thread a (x is true)
Thread b (y is true)
Thread c (z is incremented) assertion cannot fire
Thread d (z is incremented)

有人可以向我解释一下这个断言是如何触发的吗?

他展示了这张小图:

y 的存储不应该也与 read_x_then_y 中的负载同步,x 的存储不应该与 read_y_then_x 中的负载同步吗?我很困惑。

编辑:

感谢您的回复,我了解原子的工作原理和使用方法 Acquire/Release。我只是不明白这个具体的例子。我试图弄清楚如果断言触发,那么每个线程做了什么?如果我们使用顺序一致性,为什么断言永远不会触发。

顺便说一句,我的推理是如果 thread a (write_x) 存储到 x 那么到目前为止它所做的所有工作都与任何其他线程同步读取 x 与获取排序。一旦 read_x_then_y 看到这个,它就会跳出循环并读取 y。现在,可能会发生两件事。在一个选项中,write_y 已写入 y,这意味着此版本将与 if 语句(加载)同步,这意味着 z 递增并且无法触发断言。另一个选项是如果 write_y 还没有 运行,这意味着 if 条件失败并且 z 不递增,在这种情况下,只有 x 为真并且 y仍然是错误的。一旦 write_y 运行s,read_y_then_x 跳出它的循环,但是 xy 都为真并且 z 递增并且断言不会触发。我想不出任何 'run' 或 z 永远不会增加的内存排序。有人可以解释我的推理哪里有缺陷吗?

另外,我知道循环读取总是在 if 语句读取之前,因为 acquire 阻止了这种重新排序。

释放-获取同步有(至少)这样的保证:在内存位置释放之前的副作用在获取内存位置后是可见的。

如果内存位置不同,则无法保证。更重要的是,没有总的(想想全球)订购保证。

看例子,线程A让线程C跳出循环,线程B让线程D跳出循环。

但是,在同一内存位置上,释放可能 "publish" 到获取的方式(或者获取可能 "observe" 释放的方式)不需要总排序。线程 C 观察 A 的释放,线程 D 观察 B 的释放是可能的,并且 C 观察 B 的释放和 D 观察 A 的释放只能在未来的某个地方。


该示例有 4 个线程,因为这是您可以强制执行此类非直观行为的最小示例。如果任何原子操作在同一个线程中完成,就会有一个你不能违反的顺序。

例如,如果 write_xwrite_y 发生在同一个线程上,则需要任何观察到 y 变化的线程都必须观察 x.

类似地,如果 read_x_then_yread_y_then_x 发生在同一个线程上,您会观察到 xy 至少在 read_y_then_x 中都发生了变化.

在同一个线程中使用 write_xread_x_then_y 对于练习来说毫无意义,因为很明显它没有正确同步,而使用 write_xread_y_then_x,它总是读取最新的 x


编辑:

The way, I am reasoning about this is that if thread a (write_x) stores to x then all the work it has done so far is synced with any other thread that reads x with acquire ordering.

(...) I can't think of any 'run' or memory ordering where z is never incremented. Can someone explain where my reasoning is flawed?

Also, I know The loop read will always be before the if statement read because the acquire prevents this reordering.

这是顺序一致的顺序,它强加了一个总顺序。也就是说,它强制 write_xwrite_y 都对所有线程依次可见; x 然后 yy 然后 x,但所有线程的顺序相同。

使用release-acquire,没有全序。释放的效果只保证对同一内存位置上的相应获取可见。使用 release-acquire,write_x 的效果保证对 通知 x 已更改的任何人可见。

注意到某些变化非常重要。如果您没有注意到更改,则说明您没有同步。因此,线程 C 未在 y 上同步,线程 D 未在 x.

上同步

从本质上讲,将发布-获取视为仅在正确同步时才有效的更改通知系统要容易得多。如果您不同步,您可能会或可能不会观察到副作用。

即使在 NUMA 中也具有高速缓存一致性的强内存模型硬件架构,或者 languages/frameworks 在总顺序方面同步,使得很难用这些术语来思考,因为实际上不可能观察到这种效果。

您考虑的是顺序一致性,最强(和默认)内存顺序。如果使用这个内存顺序,所有对原子变量的访问构成一个总顺序,断言确实无法触发。

但是,在这个程序中,使用了较弱的内存顺序(释放存储和获取加载)。这意味着,根据定义,您 不能 假设一个完整的操作顺序。特别是,您不能假设更改对同一顺序的其他线程可见。 (只有每个个体变量的总顺序才能保证任何原子内存顺序,包括memory_order_relaxed。)

xy 的存储发生在不同的线程上,它们之间没有同步。 xy 的负载发生在不同的线程上,它们之间没有同步。这意味着完全允许线程 c 看到 x && ! y 并且线程 d 看到 y && ! x。 (我只是在这里缩写acquire-loads,不要把这个语法理解为顺序一致的负载。)

底线:一旦你使用比顺序一致更弱的内存顺序,你就可以亲吻你的所有原子的全局状态的概念,即在所有线程之间保持一致,再见。这正是为什么这么多人建议坚持顺序一致性,除非您需要性能(顺便说一句,请记住测量它是否更快!)并且确定您在做什么。另外,征求第二意见。

现在,你是否会因此而被烧毁,这是一个不同的问题。该标准基于用于描述标准要求的抽象机,仅允许断言失败的场景。但是,您的编译器 and/or CPU 可能出于某种原因无法利用此容限。因此,对于给定的编译器和 CPU,您可能永远不会在实践中看到断言被触发。请记住,编译器或 CPU 可能总是使用比您要求的 更严格的 内存顺序,因为这永远不会导致违反标准的最低要求。它可能只会让您损失一些性能 – 但无论如何标准都没有涵盖这一点。

针对评论的更新:该标准没有定义一个线程看到另一个线程对原子的更改所花费的时间的硬性上限。向实施者提出的建议是,值最终应该 .

可见

排序保证,但与您的示例相关的保证不会阻止断言触发。基本的获取-释放保证是如果:

  • 线程 e 对原子变量执行释放存储 x
  • 线程 f 从同一原子变量执行获取加载
  • 那么如果f读取的值是e存储的值,e中的存储与f中的加载同步。这意味着 e 中 在此线程 中的任何(原子和非原子)存储在 x 的给定存储之前排序,对于 f 中的任何操作都是可见的也就是说,在此线程中,在给定负载之后排序。 [请注意,除这两个线程外,我们不提供任何保证!]

因此,无法保证 f 读取 e 存储的值,而不是 e.g. x 的一些旧值。如果它读取更新的值,那么负载也会与存储同步,并且没有任何顺序保证上面提到的相关操作。

我把记忆顺序比顺序一致的原子比作相对论,其中有 no global notion of simultaneousness

PS:也就是说,原子加载不能只读取任意旧值。例如,如果一个线程对初始化为 0 的 atomic<unsigned> 变量执行周期性增量(例如,使用释放顺序),而另一个线程定期从该变量加载(例如,使用获取顺序),那么,除了最终包装,后一个线程看到的值必须是单调递增的。但这遵循给定的排序规则:一旦后一个线程读取 5,在从 4 增加到 5 之前发生的任何事情都在读取 5 之后发生的任何事情的相对过去。事实上,减少而不是回绕memory_order_relaxed甚至不允许此内存顺序不对访问其他变量的相对顺序(如果有的话)做出任何承诺。

让我们看一下并行代码:

void write_x()
{
    x.store(true,std::memory_order_release);
}

void write_y()
{
    y.store(true,std::memory_order_release);
}

这些指令之前没有任何内容(它们处于并行性的开始,之前发生的一切也发生在其他线程之前)所以它们没有有意义的释放:它们是有效的放松操作。

我们再看一遍并行代码,之前这两个操作不是有效的release:

void read_x_then_y()
{
    while(!x.load(std::memory_order_acquire)); // acquire what state?
    if(y.load(std::memory_order_acquire))
        ++z;
}

void read_y_then_x()
{
    while(!y.load(std::memory_order_acquire));
    if(x.load(std::memory_order_acquire))
        ++z;
}

请注意,所有加载都指的是变量,其中没有任何内容被有效释放,因此这里没有任何内容被有效获取:我们重新获取之前在 main 中已经可见的操作的可见性。

因此您看到所有操作都有效地 放松:它们不提供可见性(在已经可见的部分之上)。这就像在获取围栏之后再进行获取围栏一样,这是多余的。没有暗示没有暗示的新内容。

所以现在一切都放松了,一切都结束了。

另一种查看方式是注意原子加载不是保持值不变的 RMW 操作,因为 RMW 可以被释放和负载不能.

就像所有原子存储都是原子变量修改顺序的一部分,即使变量是有效常量(即值始终相同的非 const 变量),原子 RMW 操作在某处在原子变量的修改顺序中,即使没有值的变化(并且不可能有值的变化,因为代码总是比较和复制完全相同的位模式)。

在修改顺序中可以有释放语义(即使没有修改)。

如果您使用互斥量保护变量,您将获得释放语义(即使您只是读取变量)。

如果您使用以下方式进行所有加载(至少在执行多次操作的函数中):

  • 保护原子对象的互斥锁(然后删除原子,因为它现在是多余的!)
  • 或带有 acq_rel 订单的 RMW,

先前证明所有操作都已有效放宽的证明不再有效,并且 read_A_then_B 函数中至少一个中的某些原子操作必须在另一个函数中的某些操作之前排序,因为它们在运行在相同的对象上。如果它们在变量的修改顺序中并且您使用 acq_rel、,那么您在其中一个 之间有一个发生之前的关系(很明显哪个发生在哪个不是确定性)。

无论哪种方式执行现在都是顺序的,因为所有操作都是有效的获取和释放,即有效的获取和释放(即使是那些有效放松的操作!)。

如果我们把两个if语句改成while语句,这样代码就正确了,z就可以保证等于2。

void read_x_then_y()
{
    while(!x.load(std::memory_order_acquire));
    while(!y.load(std::memory_order_acquire));
    ++z;
}

void read_y_then_x()
{
    while(!y.load(std::memory_order_acquire));
    while(!x.load(std::memory_order_acquire));
    ++z;
}