6、并发保证.md

### 并发保证

* 综合前面所有说的 cache 、多处理机来综合讲解。



#### 缓存一致性

常见的缓存一致性协议

* 有MSI（已讲解）、MESI、MOSI、Firefly、Synapse及DragonProtocol等。
* 其中最出名的就是MESI（MESI属于窥探协议），该协议中最重要的内容有两部分：缓存行的状态以及消息通知机制。



MESI 窥探协议的基本思想（同 MSI )

* 所有cache与内存，cache与cache（cache之间也会有数据传输）之间的数据传输都发生在一条共享的总线上，并且所有的cpu都能看到这条总线，如果某个 cache要读写内存，都需要经过仲裁（arbitrate）。
* 窥探协议的思想是，cache不但与内存通信时和总线打交道，而且它会不停地窥探总线上发生的数据交换，跟踪其他cache在做什么。所以当一个cache代表它所属的cpu去读写内存时，其它cpu都会得到通知，其 cache 控制器会结合 cache 的状态与消息所指向的地址来判断是否要修改自己的 cache。



MESI 缓存行的状态

* 缓存行有四种状态 Modified、Exclusive、Shared、Invalid，而MESI 命名正是以这4中状态的首字母来命名的。

* 该协议要求在每个缓存行上维护两个状态位，使得每个数据单位可能处于M、E、S和I这四种状态之一,各种状态含义如下：

  * 和 MSI 协议基本没什么区别，只是多了个 E（也是读的状态，但是只有当前一个 cache 在读） ，在转换位 M 前要是 E。

  | 状态                       | 描述                                                         | 监听任务                                                     |
  | -------------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |
  | I(Invalid)：失效           | 表明该缓存行已失效，它要么已经不在缓存中，要么它的内容已经过时。处于该状态下的缓存行等同于它从来没被加载到缓存中 | 无                                                           |
  | S(Shared)：共享            | 表明该缓存行是主内存中某一段数据的拷贝，处于该状态下的缓存行只能被cpu读取，不能写入，因为此时还没有独占。不同cpu的缓存行都可以拥有这段内存数据的拷贝 | 该缓存行必须时刻监听使该缓存行`无效`或者`独享`该缓存行的请求，如果监听到，则必须把其缓存行状态设置为`I。` |
  | E(Exclusive)：独占（互斥） | 和 Shared 状态一样，表明该缓存行是内存中某一段数据的拷贝。区别在于，该缓存行独占该主内存地址，其他处理器的缓存行不能同时持有它，如果其他处理器原本也持有同一缓存行，那么它会马上变成“Invalid”状态 | 该缓存行必须时刻监听其他试图`读取`该缓存行对应的主存地址的操作，如果监听到，则必须把其缓存行状态设置为S。 |
  | M(Modified)：修改          | 表明该缓存行已经被修改，缓存行只有处于Exclusive状态才能被修改。此外，已修改cache line如果被丢弃或标记为Invalid，那么先要把它的内容回写到内存中 | 该缓存行必须时刻监听所有`试图读取`该缓存行对应的主存地址的操作，如果监听到，则必须在此操作执行前把其缓存行中的`数据写回主内存，并更改状态为S。` |



MESI 缓存的一致性消息通知机制

* 根据”窥探协议“的规范，每个动作都需要广播通知到其他CPU，于是有以下的消息通信机制
* 六种消息（就是比上面介绍的 MSI 多了三个 ack）
  * Read（读取数据），cpu发起读取数据请求，请求中包含需要读取的数据地址；
  * Read Response，作为Read消息的响应，该消息可能是内存响应的，也可能是某cpu响应的(比如该地址在某cpu cache Line中为Modified状态，则该cpu必须返回该地址的最新数据)；
  * Invalidate（独占），cpu发起独占一个cache line，其他cpu请失效对应的cache line的消息，消息中包含了内存地址，所有的其它cpu需要将对应cache line置为Invalid状态；
  * Invalidate ACK，收到Invalidate消息的cpu在将对应cache line置为Invalid后，返回Invalid ACK；
  * Read Invalidate（读取并独占数据），相当于Read消息+Invalidate消息，即取得数据并且独占它，将收到一个Read Response和所有其它cpu的Invalidate ACK；
  * Write back（修改并回写数据），写回消息，即将状态为Modified的cache line写回到内存，通常在该行将被替换时使用。现代cpu cache基本都采用”写回(Write Back)”而非”直写(Write Through)”的方式。



综上

* 如果只有 cache，那么在多个线程共享变量的情况下，缓存一致性协议已经能够保障一个线程对共享变量的更新对其它处理器上运行的线程来说是可见的。
* 但是需要说明的是缓存一致性协议只能保证数据的可见性，却不能保证数据的有序性和原子性。



缓存一致性问题：延长该指令的 CPI ,使下条指令无法执行

* 缓存的一致性消息传递是一个同步操作，是需要时间的，这就导致缓存行进行状态切换时产生延迟。从一个缓存行切换状态时发送请求指令，到其他缓存收到消息完成各自的切换并且发出回应消息，这么一长串的时间内CPU一直出于阻塞状态，直到所有缓存响应完成，才会执行下一条指令。

* 假如某数据存在于其他cpu的cache中，那自己每次需要修改数据时，都需要发送Read Invalidate消息，除了等待最新数据的返回，还需要等待其他cpu的Invalidate ACK才能继续执行其他指令。这个等待确认的过程会阻塞处理器，这会降低处理器的性能。因为这个等待远远比一个指令的执行时间长的多。



#### Store Buffer

<img src="https://img-blog.csdnimg.cn/20201225164723388.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="40%"/>

介绍

* 为了解决CPU切换状态时的阻塞问题，避免这种CPU运算能力的浪费，引入了存储缓存（store buffer）。处理器把它想要写入到主存的值写到存储缓存（store buffer），然后继续去处理其他事情。
* 当所有失效确认（Invalidate Acknowledge）都接收到时，数据才会最终被提交（写入cache）。
* 但是 Store Buffer 会带来如下三个问题



问题一：读到 Cache 中过期的值（即新值在 store buffer 中）

* 示例

  ```
  a = 1;
  b = a + 1;
  ```

  * 例如 CPU0 执行上述代码，此时 CPU0 把 a=1 放到存储缓存，然后发起 read invalid 广播，在收到响应之前，CPU0 已经执行到 b=a+1;
  * 此时 CPU0 其实想使用的是 store buffer 中的 a=1 的值，但是 store buffer 没有提交到 cache，所以 CPU0 无法使用这个值。

* 解决方案：

  * store forwarding 技术：cpu可以直接从 store buffer 中加载数据，即支持将 cpu 存入 store buffer 的数据传递 (forwarding) 给后续的加载操作，而不经由 cache。





问题二：顺序执行，但是写入 cache 的先后顺序不同（例如因为 E -> M 和 S -> M 速度不同，但只有到了 M 才可以写 Cache）

* 示例

  ```
  a = 3；
  void A(){
    a = 10;
    b= 3;
  }
  
  void B(){
    if(b==3){
      assert a == 10;
    }
  }
  ```

  * CPU0 执行 A，CPU1 执行 B。
  * 假如 CPU0 执行后 b 比 a 先在 cache 中生效，从而导致CPU1 读到 b=3 时，a 还在 CPU0 的 store buffer 中。所以导致 B 中的断言失败。给人的感觉就是A被重排序了。
  * 所以导致”指令重排“的其中一个原因：cpu 为了优化指令的执行效率，引入了store buffer（forwarding），而又因此导致了指令执行顺序的变化。

* 解决方案：

  * 要保证这种顺序一致性，靠硬件是优化不了了，需要在软件层面支持，所以 cpu 提供了**写屏障（write memory barrier）指令**

  * Linux操作系统将写屏障指令封装成了 smp_wmb() 函数。

    * cpu 执行 smp_mb() 的思路是，会先把当前 store buffer 中的数据刷到 cache 之后，再执行屏障后的“写入操作”

  * 该思路有两种实现方式：

    * 一是简单地刷 store buffer，但如果此时远程 cache line没有返回，则需要等待。
    * 二是将当前 store buffer 中的条目打标，然后将屏障后的“写入操作”也写到 store buffer 中，cpu 继续干其他的事，当被打标的条目全部刷到 cache line，之后再刷后面的条目

  * 以第二种实现逻辑为例，看以下代码执行过程：

    ```
    a = 3；
    
    void A(){
      a = 10;
      smp_wmb()
      b= 3;
    }
    
    void B(){
      if(b==3){
        assert a == 10;
      }
    }
    ```

    * CPU0 执行A，CPU1执行B。
    * 假如 b 存在于 CPU0 的缓存中，当 CPU0 执行 a=10 的时侯，因为 CPU0 的 cache 中不存在 a，所以将 a 写入到 store buffer 中，然后继续执行smp_wmb() 内存屏障，此时 CPU0 会将 store buffer 中的所有条目进行标记；然后继续执行 b=3
    * 虽然 CPU0 的 cache 中存在 b，但是因为 store buffer 中存在打标的数据，所以 b 不能被赋值，只能也被写入 store buffer中，CPU0 继续干其他的事，当被打标的条目全部刷到 cache line，之后再刷后面的条目，这样一来就保证 A 顺序执行，不会被重排序。



问题三：Store Buffer 大小有限

* 问题描述

  * store buffer 的大小是有限的，特别是出现写屏障时，后续的所有写入操作 (不管是否cache missing) 都会挤压在 store buffer 中 （直到 store buffer中屏障前的条目处理完），因此store buffer很容易会满
  * 当 store buffer 满了之后，cpu 还是会卡在等待对应的 Invalidate ACK 以处理 store buffer 中的条目。

* 解决方案：

  <img src="https://img-blog.csdnimg.cn/20201225164700157.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="40%"/>

  * 化同步为异步，引入失效队列（Invalid Queue）
  * 接收到 Invalidate 消息的 cpu 不必处理了自己的 cache line 之后才响应 Invalidate ACK ，而是可以先将 Invalid 消息放到某个请求队列 Invalid Queue，然后直接响应 Invalidate ACK，具体约定如下：
    * 对于所有收到的 Invalidate 请求，Invalidate Acknowlege 消息必须立刻发送；
    * Invalidate 并不真正执行，而是被放在失效队列中，在方便的时候才会去执行（其实具体什么时候执行CPU也没法确认）；
    * 处理器不会发送任何消息给所处理的缓存条目，直到它处理 Invalidate 请求。

  * 失效队列处理问题（**读屏障指令**）
    * 因为就算引入失效队列，CPU 也不知道什么时候才应该去处理 Invalidate 请求，也就是说通过硬件已经不能继续进行优化了，所以提供了读屏障指令。

    * 处理器如果遇到读屏障指令，那么必须先处理所有已经在失效队列中的失效操作的指令。这个其实很好相通，因为其他处理器的改动，对于当前出来器来说只是读取。

  * Linux操作系统将写屏障指令封装成了 smp_rmb() 函数。和 smp_wmb() 类似，cpu 执行 smp_rmb() 的时侯，会先把当前invalidate queue中的数据处理掉之后，再执行屏障后的“读取操作”。



经过这一系列软件和硬件方面的优化，终于对缓存一致性优化完成。

 

#### 内存屏障

说明

* 内存屏障（Memory Barrier）是一类同步屏障指令，用于解决**多处理器下**的内存可见性问题和重排序问题，如果只有单处理器并没有这些问题
* 可见性问题，也就是一致性问题，这个很常见，比如多个线程同时加一个数，最后结果并不是正确的。
* 重排序问题
  * 对于单处理器来说，乱序优化节省了大量等待时间（指令流水和指令并行那里已经解释过，减少指令间冲突带来的损失，包括结构冲突，数据冲突，控制冲突，减少了浪费的时钟周期，而且实现方式有软件和硬件两种手段），提高了处理器的性能。
  * 在多核时代，因为重排序会导致工作线程似乎表现出了随机行为。





屏障分类

* 写屏障 Store Memory Barrier (SMB, smp_wmb)：
  * 是对于当前执行修改操作的处理器来说的
  * 会告诉处理器在执行该指令之后的指令之前，先处理提交所有已经保存在存储缓存（store buffer）中的数据的指令。
  * 理解为该指令是开始将 store buffer 中的所有数据刷新到 Cache 的信号，处理完之后再继续下面的操作。
* 读屏障 Load Memory Barrier (RMB, smp_rmb)：
  * 是对于从 Cache 总线接收到失效消息的处理器来说的
  * 会告诉处理器在执行任何的加载前，先处理所有已经在失效队列中的失效操作的指令。
  * 理解为该条指令是开始处理invalid queue中所有无效指令的信号，处理完无效队列中的操作后再继续下面的操作
* 全屏障 Memory Barrier (MB, smp_mb)：同时具有读屏障和写屏障功能的指令。





#### 原子性

CPU 能保证的原子操作是 CPU 指令级别的，而不是高级语言的操作符。

* 比如上面介绍的 MIPS 指令集的 LL/SC