haskell - 关于并发程序中IORef操作重新排序的原因

docs说:



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



所以...它不会破坏整个haskell；不是很有帮助。出现内存模型示例的discussion也让我提出了疑问(甚至Simon Simon都有些惊讶)。

从文档看我似乎很清楚的事情

在线程内的

中，atomicModifyIORef“从未观察到发生在任何较早的IORef操作之前或之后的IORef操作之后”，即，我们得到了部分排序:原子mod上方的东西->原子mod->之后的东西。虽然，这里的“从未观察到”一词暗示了我未曾预料到的怪异行为。

至少在没有数据依赖项

时，readIORef x可能会移到writeIORef y之前

逻辑上我看不到如何像readIORef x >>= writeIORef y这样重新排序

我不清楚

newIORef False >>= \v-> writeIORef v True >> readIORef v是否总是返回True吗？

在maybePrint情况下(来自IORef文档)，在readIORef myRef之前的seq(可能还有readIORef yourRef或其他东西)是否会强制重新排序的障碍？

我应该有什么简单明了的心理模型？是这样的吗？



...？如果没有，以上内容的更正版本是什么？

如果您的回答是“不要在并发代码中使用IORef；请使用TVar”，请说服我一些具体的事实，并举例说明您无法通过IORef进行推理的具体示例。

最佳答案

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

处理器可以按照自己喜欢的方式对指令进行重新排序:负载可能会超前于负载，负载可能会超前于商店，相关 Material 的负载可能会超前于其所依赖的 Material 负载(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证明了x = 1之后执行了y = 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实现了有序存储(atomicWriteIORef)，但是我没有看到有序加载(atomicReadIORef)，没有它，您就无法推理上面的IRIW问题。如果您的目标平台是x86，这不是问题，因为所有负载将在该平台上按程序顺序执行，并且存储永远不会超前负载(实际上，所有负载都是有序负载)。

在我看来，原子更新(atomicModifyIORef)似乎是所谓的CAS循环的一种实现(比较并设置循环，直到将值自动设置为b，如果其值为a，该循环才会停止)。您可以看到原子修改操作是有序加载和有序存储的融合，所有这些障碍都在其中，并且是原子执行的-不允许任何处理器在CAS的负载和存储之间插入修改指令。

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

通常，在推理算法时不使用x，y，z的具体值。取而代之的是，关于赋值的一些算法相关的不变式必须成立并得到证明-例如，在IRIW的情况下，如果线程3看到(0,1)=(r3,r4)，则您可以保证线程4永远不会看到(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

如果线程1 load z不是有序加载，则将允许它在有序存储(store x)之前进行。这意味着无论z加载到何处(寄存器，高速缓存行，堆栈等)，该值在x值可见之前就已经存在。查看该值是没有用的-您无法判断线程2的作用。出于同样的原因，您必须保证在执行load z之前刷新了写缓冲区-否则，它仍将作为线程2看到x值之前已存在的值的负载而出现。这很重要，下面将对此进行明确说明。

如果线程2 load x或load 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，则无需重试:如果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的线程”，因此，这不仅仅是从内存中加载内容的问题)

关于haskell - 关于并发程序中IORef操作重新排序的原因，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21506748/