11

文档说:

在并发程序中,IORef 操作对于另一个线程可能会出现乱序,具体取决于底层处理器架构的内存模型......需要实现以确保内存操作的重新排序不会导致类型正确的代码走错误的。特别是,在检查从 IORef 读取的值时,从当前线程的角度来看,创建该值的内存写入必须发生。

我什至不完全确定如何解析。爱德华杨

换句话说,“我们不保证重新排序,除非你不会有任何类型安全违规。” ...最后一句指出不允许 IORef 指向未初始化的内存

所以......它不会破坏整个haskell;不是很有帮助。引发内存模型示例的讨论也给我留下了一些问题(即使是 Simon Marlow 也似乎有点惊讶)。

从文档中我觉得很清楚的事情

  1. 在线程中,atomicModifyIORef“从未观察到在任何早期的 IORef 操作之前或在任何以后的 IORef 操作之后发生”,即我们得到以下部分排序:原子模式之上的东西 -> 原子模式 -> 之后的东西。虽然,这里的“从未观察到”一词暗示了我没有预料到的怪异行为。

  2. readIORef x之前可能会移动A writeIORef y,至少在没有数据依赖关系的情况下是这样。

  3. 从逻辑上讲,我看不出如何readIORef x >>= writeIORef y重新排序

我不清楚什么

  • newIORef False >>= \v-> writeIORef v True >> readIORef v一直回来True吗?

  • 在这种maybePrint情况下(来自 IORef 文档),a readIORef myRef(可能与 aseq或其他东西一起)之前readIORef yourRef是否会强制阻碍重新排序?

我应该有什么直截了当的心智模型?是不是像:

在单个线程内部和从单个线程的角度来看,IORef 操作的顺序将显得合理且连续;但编译器实际上可能会以打破并发系统中某些假设的方式重新排序操作;然而,当一个线程这样做时 atomicModifyIORef,没有线程会观察到 IORef出现在上面的操作atomicModifyIORef之后发生的操作,反之亦然。

...?如果不是,上面的更正版本是什么?

如果您的回答是“不要IORef在并发代码中使用;请使用TVar”,请用具体事实和具体示例来说服我,这些事情是您无法推理的IORef

4

3 回答 3

8

我不知道 Haskell 并发,但我对内存模型有所了解。

处理器可以按照他们喜欢的方式重新排序指令:加载可能先于加载,加载可能先于存储,依赖的东西的加载可能会先于它们依赖的东西的加载(a[i] 可能首先从数组加载值,然后对数组 a!) 的引用,存储可能会相互重新排序。您根本无法指望它说“这两件事肯定以特定的顺序出现,因为它们无法重新排序”。但是为了让并发算法运行,它们需要观察其他线程的状态。这是线程状态以特定顺序进行的重要之处。这是通过在指令之间放置障碍来实现的,这保证了指令的顺序对所有处理器来说都是相同的。

通常(最简单的模型之一),您需要两种类型的有序指令:不先于任何其他有序加载或存储的有序加载,以及根本不先于任何指令的有序存储,以及保证所有有序指令以相同的顺序出现在所有处理器中。这样你就可以推断出 IRIW 类型的问题:

Thread 1: x=1

Thread 2: y=1

Thread 3: r1=x;
          r2=y;

Thread 4: r4=y;
          r3=x;

如果所有这些操作都是有序加载和有序存储,那么您可以得出结论(1,0,0,1)=(r1,r2,r3,r4)是不可能的。实际上,线程 1 和 2 中的有序存储应该以某种顺序出现在所有线程中,并且 r1=1,r2=0 证明 y=1 在 x=1 之后执行。反过来,这意味着线程 4 在不观察 r3=1(在 r4=1 之后执行)的情况下永远无法观察到 r4=1(如果有序存储恰好以这种方式执行,则观察 y==1 意味着 x== 1)。

此外,如果加载和存储没有排序,通常允许处理器观察分配即使以不同的顺序出现:一个可能会看到 x=1 出现在 y=1 之前,另一个可能会看到 y=1 出现在 x 之前=1,因此允许值 r1、r2、r3、r4 的任意组合。

这已充分实现,如下所示:

有序负载:

load x
load-load  -- barriers stopping other loads to go ahead of preceding loads
load-store -- no one is allowed to go ahead of ordered load

订购商店:

load-store
store-store -- ordered store must appear after all stores
            -- preceding it in program order - serialize all stores
            -- (flush write buffers)
store x,v
store-load -- ordered loads must not go ahead of ordered store
           -- preceding them in program order

在这两个中,我可以看到 IORef 实现了一个有序存储atomicWriteIORefatomicReadIORef如果您的目标平台是 x86,这不是问题,因为所有加载都将在该平台上按程序顺序执行,并且存储永远不会先于加载(实际上,所有加载都是有序加载)。

atomicModifyIORef在我看来,原子更新(您可以将原子修改操作视为有序加载和有序存储的融合,所有这些障碍都在那里,并以原子方式执行 - 不允许处理器在 CAS 的加载和存储之间插入修改指令。


此外,writeIORef 比 atomicWriteIORef 便宜,因此您希望在线程间通信协议允许的范围内尽可能多地使用 writeIORef。虽然writeIORef x vx >> writeIORef y vy >> atomicWriteIORef z vz >> readIORef t不保证 writeIORefs 相对于其他线程出现的顺序,但可以保证它们都将出现在之前atomicWriteIORef- 所以,看到 z==vz,你可以在这一刻得出结论 x==vx 和 y ==vy,你可以断定IORef t是在存储到x、y、z之后加载的,其他线程可以观察到。后一点要求 readIORef 是一个有序负载,据我所知没有提供,但它会像 x86 上的有序负载一样工作。

通常,在推理算法时,您不会使用 x、y、z 的具体值。相反,一些与分配值有关的算法相关的不变量必须保持,并且可以被证明——例如,在 IRIW 的情况下,您可以保证线程 4 永远不会看到(0,1)=(r3,r4),如果线程 3 看到(1,0)=(r1,r2),并且线程 3 可以利用这一点:这意味着某些东西在没有获得任何互斥锁或锁的情况下被相互排除。


一个示例(不在 Haskell 中),如果加载未排序,或者有序存储不刷新写入缓冲区(要求在有序加载执行之前使写入值可见),则该示例将不起作用。

假设,z 将显示 x,直到 y 被计算,或者 y,如果 x 也被计算。不要问为什么,在上下文之外不是很容易看到 - 它是一种队列 - 只是享受什么样的推理是可能的。

Thread 1: x=1;
          if (z==0) compareAndSet(z, 0, y == 0? x: y);

Thread 2: y=2;
          if (x != 0) while ((tmp=z) != y && !compareAndSet(z, tmp, y));

因此,两个线程设置 x 和 y,然后将 z 设置为 x 或 y,这取决于是否也计算了 y 或 x。假设最初都是 0。转换为加载和存储:

Thread 1: store x,1
          load z
          if ==0 then
            load y
            if == 0 then load x -- if loaded y is still 0, load x into tmp
            else load y -- otherwise, load y into tmp
            CAS z, 0, tmp -- CAS whatever was loaded in the previous if-statement
                          -- the CAS may fail, but see explanation

Thread 2: store y,2
          load x
          if !=0 then
          loop: load z -- into tmp
                load y
                if !=tmp then -- compare loaded y to tmp
                  CAS z, tmp, y  -- attempt to CAS z: if it is still tmp, set to y
                  if ! then goto loop -- if CAS did not succeed, go to loop

如果线程 1load z不是有序加载,那么它将被允许先于有序存储 ( store x)。这意味着无论 z 被加载到何处(寄存器、缓存行、堆栈……),该值在 x 的值可见之前就已经存在。查看该值是没有用的 - 您无法判断线程 2 的进度。出于同样的原因,您必须保证写入缓冲区在load z执行之前被刷新 - 否则它仍然会显示为在线程 2 可以看到 x 的值之前存在的值的负载。这一点很重要,下面会很清楚。

如果线程 2load xload z不是有序加载,它们可能会先于store y,并将观察在 y 对其他线程可见之前写入的值。

但是,请注意,如果加载和存储是有序的,那么线程可以协商谁来设置 z 的值,而无需竞争 z。例如,如果线程 2 观察到 x==0,则可以保证线程 1 稍后肯定会执行 x=1,并且之后会看到 z==0 - 因此线程 2 可以离开而无需尝试设置 z。

如果线程 1 观察到 z==0,那么它应该尝试将 z 设置为 x 或 y。因此,首先它会检查 y 是否已经设置。如果没有设置,以后会设置,所以尝试设置为x - CAS可能会失败,但前提是线程2同时将z设置为y,所以不需要重试。同样,如果线程 1 观察到的 y 已设置,则无需重试:如果 CAS 失败,则线程 2 已将其设置为 y。由此我们可以看到线程1根据要求将z设置为x或y,并没有过多地争用z。

另一方面,线程 2 可以检查是否已经计算了 x。如果不是,那么设置 z 将是线程 1 的工作。如果线程 1 计算了 x,则需要将 z 设置为 y。这里我们确实需要一个 CAS 循环,因为如果线程 1 尝试同时将 z 设置为 x 或 y,则单个 CAS 可能会失败。

这里重要的一点是,如果“不相关”的加载和存储没有序列化(包括刷新写入缓冲区),则不可能进行这样的推理。但是,一旦对加载和存储进行了排序,两个线程都可以找出它们各自的路径_will_take_in_the_future,这样就可以在一半的情况下消除争用。大多数时候 x 和 y 将在显着不同的时间计算,所以如果 y 在 x 之前计算,线程 2 很可能根本不会触及 z。(通常,“触摸 z”也可能意味着“唤醒等待 cond_var z 的线程”,因此这不仅仅是从内存中加载某些内容的问题)

于 2014-02-02T12:14:07.200 回答
4
  1. 在线程内,atomicModifyIORef“从未观察到发生在任何早期的 IORef 操作之前,或在任何后续的 IORef 操作之后”,即我们得到部分排序:原子模式之上的东西 -> 原子模式 -> 之后的东西。虽然,这里的“从未观察到”一词暗示了我没有预料到的怪异行为。

在讨论内存重新排序问题时,“从未观察到”是标准语言。例如,CPU 可能会比必要更早地发出对内存位置的推测性读取,只要该值在执行读取(早期)和应该执行读取(按程序顺序)之间没有变化。不过,这完全取决于 CPU 和缓存,它永远不会暴露给程序员(因此像“从未观察到”这样的语言)。

  1. readIORef x 可能在 writeIORef y 之前移动,至少在没有数据依赖关系的情况下

真的

  1. 从逻辑上讲,我看不到如何重新排序 readIORef x >>= writeIORef y 之类的东西

正确,因为该序列具有数据依赖性。要写入的值取决于第一次读取返回的值。

对于其他问题:newIORef False >>= \v-> writeIORef v True >> readIORef v将始终返回True(其他线程没有机会访问此处的 ref)。

myprint示例中,面对添加到未来 GHC 和各种 CPU 架构的新优化,您几乎无法确保其可靠地工作。如果你写:

writeIORef myRef True
x <- readIORef myRef
yourVal <- x `seq` readIORef yourRef

尽管 GHC 7.6.3 产生了正确的 cmm(可能是 asm,尽管我没有检查),但没有什么可以阻止具有宽松内存模型的 CPU 将readIORef yourRefto 移到所有myref/seq东西之前。唯一 100% 可靠的防止它的方法是使用 GHC 不提供的内存栅栏。(Edward 的博客文章确实介绍了您现在可以做的其他一些事情,以及您可能不想依赖它们的原因)。

我认为您的心智模型是正确的,但是重要的是要知道并发操作引入的可能的明显重新排序可能非常不直观。

编辑:在 cmm 级别,上面的代码片段看起来像这样(简化的伪代码):

[StackPtr+offset] := True
x := [StackPtr+offset]
if (notEvaluated x) (evaluate x)
yourVal := [StackPtr+offset2]

所以有几件事可能发生。目前的 GHC 不太可能提前移动最后一行,但我认为如果这样做看起来更优化,它可以。我更担心的是,如果您通过 LLVM 进行编译,LLVM 优化器可能会用刚刚写入的值替换第二行,然后第三行可能会被常量折叠不存在,这更有可能读取可以更早地移动。不管 GHC 做什么,大多数 CPU 内存模型都允许 CPU 本身在没有内存屏障的情况下提前移动读取。

于 2014-02-02T07:21:02.423 回答
1

http://en.wikipedia.org/wiki/Memory_ordering用于非原子并发读写。(基本上当您不使用原子时,只需查看目标 CPU 的内存排序模型)

目前可以认为 ghc不会为非原子(和命令式)加载和存储重新排序您的读取和写入。但是,GHC Haskell 目前没有指定任何类型的并发内存模型,因此这些非原子操作将具有底层 CPU 模型的排序语义,正如我在上面链接的那样。

换句话说,目前 GHC没有正式的并发内存模型,并且由于任何优化算法都倾向于使用某种等价模型,因此目前没有重新排序。

也就是说:您现在唯一可以拥有的语义模型是“其实现方式”

给我发电子邮件!我正在为 7.10 修补一些原子,让我们尝试制作一些语义!

编辑:一些比我更了解这个问题的人在这里加入了 ghc-users 线程http://www.haskell.org/pipermail/glasgow-haskell-users/2013-December/024473.html。假设我在这条评论和我在 ghc-users 线程中所说的任何内容都错了:)

于 2014-02-02T07:05:35.487 回答