关于IORef操作在并发程序中重新排序的推理

我不知道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证明在x = 1之后执行y = 1.反过来,这意味着线程4永远不会观察到r4 = 1而没有观察到r3 = 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实现了一个有序的store(atomicWriteIORef),但我没有看到有序的load(atomicReadIORef),没有它,你就无法解释上面的IRIW问题.如果您的目标平台是x86,这不是问题,因为所有负载将在该平台上按程序顺序执行,并且存储永远不会超过负载(实际上,所有负载都是有序负载).

原子更新(atomicModifyIORef)在我看来是一个所谓的CAS循环的实现(比较和设置循环,它不会停止,直到一个值原子设置为b,如果它的值是a).您可以将原子修改操作视为有序加载和有序存储的融合,具有所有这些障碍,并以原子方式执行 - 不允许处理器在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

如果线程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观察到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的线程",因此它不仅仅是从内存中加载某些内容的问题)