锁、内存屏障与缓存一致性

在应用层，关于锁的使用大家应该都很熟悉了，作用就是为了保护共享变量不被同时操作而导致无法预测的情况。然而深入到具体实现，锁仅仅只是锁定临界区吗？

锁的实现其实还必须实现一个语义，也就是内存屏障。内存屏障主要用于防止指令重排而导致的无法预测的情况。代码经过编译器生成的指令并不一定都是按着我们原先的想法来生成的，可能经过优化等情况进行了指令的重排，然而这些重排在执行后的结果应当是一致的。其实及时编译器不重排指令，在现代的cpu中，也常常会将指令乱序执行，所以内存屏障可以保证屏障指令前后的指令顺序。

内存屏障也分为读屏障(rmb)与写屏障(wmb)。这些读写屏障主要用于在多核cpu的情形下可以强制同步cpu中缓存不一致的情况。

这些又牵扯到了多cpu中缓存一致性的问题。假设只有一个cpu，那么cpu只会从自己的缓存中读数据，假如发生了缓存miss，则会从主存中读取数据到缓存中，所以cpu无论在何时看到的最终内存数据都是一致的。

但是在多核情况下，就不是这么简单的了。每个cpu都有自己的缓存，每个cpu最终看到的数据，就是不在缓存中的主存+已在缓存中的数据。所以假设多cpu的情况下，某个cpu更新了某个cache line中的值又没有回写到内存中，那么其它cpu中的数据其实已经是旧的已作废的数据，这是不可接受的。

为了解决这种情况，引入了缓存一致性协议，其中用的比较多的称为MESI，分别是cache line可能存在的四种状态：

• Modified。数据已读入cache line，并且已经被修改过了。该cpu拥有最新的数据，可以直接修改数据。当其它核心需要读取相应数据的时候，此数据必须刷入主存。
• Exclusive。数据已读入cache line，并且只有该cpu拥有它。该cpu可以直接修改数据，但是该数据与主存中数据是一致的。
• Shared。多个cpu共享某内存的数据，可能由Exclusive状态改变而来，当某个cpu需要修改数据的时候，必须提交RFO请求来获取数据的独占权，然后才能进行修改。
• Invalid。无效的cache line，和没有载入一样。当某个cpu的cache line处于Shared状态，别的cpu申请写的时候，接收了RFO请求后会变为此种状态。

这四种状态可以不断的改变，有了这套协议，不同的cpu之间的缓存就可以保证数据的一致性了。但是依赖这套协议，会大大的降低性能，比如一个核心上某个Shared的cache line打算写，则必须先RFO来获取独占权，当其它核心确认了之后才能转为Exclusive状态来进行修改，假设其余的核心正在处理别的事情而导致一段时间后才回应，则会当申请RFO的核心处于无事可做的状态，这是不可接受的。

于是在每个cpu中，又加入了两个类似于缓存的东西，分别称为Store buffer与Invalidate queue。

Store buffer用于缓存写指令，当cpu需要写cache line的时候，并不会执行上述的流程，而是将写指令丢入Store buffer，当收到其它核心的RFO回应后，该指令才会真正执行。

Invalidate queue用于缓存Shared->Invalid状态的指令，当cpu收到其它核心的RFO指令后，会将自身对应的cache line无效化，但是当核心比较忙的时候，无法立刻处理，所以引入Invalidate queue，当收到RFO指令后，立刻回应，将无效化的指令投入Invalidate queue。

这套机制大大提升了性能，但是很多操作其实也就异步化了，某个cpu写入了东西，则该写入可能只对当前CPU可见（读缓存机制会先读Store buffer，再读缓存），而其余的cpu可能无法感知到内存发生了改变，即使Invalidate queue中已有该无效化指令。

为了解决这个问题，引入了读写屏障。写屏障主要保证在写屏障之前的在Store buffer中的指令都真正的写入了缓存，读屏障主要保证了在读屏障之前所有Invalidate queue中所有的无效化指令都执行。有了读写屏障的配合，那么在不同的核心上，缓存可以得到强同步。

所以在锁的实现上，一般lock都会加入读屏障，保证后续代码可以读到别的cpu核心上的未回写的缓存数据，而unlock都会加入写屏障，将所有的未回写的缓存进行回写。