Categories
程式開發

缓存一致性协议的工作方式


现代计算机都是多核cpu,cpu需要和内存交互,但内存相对cpu的速度实在太慢,于是cpu和内存之间还有cache层,每个cpu都有属于自己的cache,cache由cache line组成,每个cache line 64位(根据不同架构,也可能是32位或128位),每个cache line知道自己对应什么范围的物理内存地址,当cpu需要读取某一个内存地址的值时,它会把内存地址传递给一级cache,一级cache会检查它是否有这个内存地址对应的cache line。如果没有,它会以cache line为单位从内存加载数据,是的,一次加载整个cache line,这是基于这样一个假设:内存访问倾向于本地化(localized),如果我们当前需要某个地址的数据,那么很可能我们马上要访问它的邻近地址。

缓存一致性协议的工作方式 1

窥探协议的基本思想

所有cache与内存,cache与cache(是的,cache之间也会有数据传输)之间的传输都发生在一条共享的总线上,而所有的cpu都能看到这条总线,同一个指令周期中,只有一个cache可以读写内存,所有的内存访问都要经过仲裁(arbitrate)。

窥探协议的思想是,cahce不但与内存通信时和总线打交道,而且它会不停地窥探总线上发生的数据交换,跟踪其他cache在做什么。所以当一个cache代表它所属的cpu去读写内存时,其它cpu都会得到通知,它们以此来使自己的cache保持同步。

MESI协议的工作方式

”MESI“该名称来自4个状态的首字母的缩写,协议中最重要的内容有两部分:cache line的状态以及消息通知机制。

cache line的状态有4个:

Invalid,表明该cache line已失效,它要么已经不在cache中,要么它的内容已经过时。处于该状态下的cache line等同于它从来没被加载到cache中。Shared,表明该cache line是内存中某一段数据的拷贝,处于该状态下的cache line只能被cpu读取,不能写入,因为此时还没有独占。不同cpu的cache line都可以拥有这段内存数据的拷贝。Exclusive,和 Shared 状态一样,表明该cache line是内存中某一段数据的拷贝。区别在于,该cache line独占该内存地址,其他处理器的cache line不能同时持有它,如果其他处理器原本也持有同一cache line,那么它会马上变成“Invalid”状态。Modified,表明该cache line已经被修改,cache line只有处于Exclusive状态才能被修改。此外,已修改cache line如果被丢弃或标记为Invalid,那么先要把它的内容回写到内存中。

我们发现,cpu有读取数据的动作,有独占的动作,有独占后更新数据的动作,有更新数据之后回写内存的动作,根据”窥探协议“的规范,每个动作都需要通知到其他cpu,于是有以下的消息机制:

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 line状态以及消息机制,我们来看看cpu之间是如何协作的。为了简化,假设我们有个四核cpu系统,每个cpu只有一个cache line,每个cache line大小为1个字节,内存地址空间一共两个字节的数据,地址分别为0x0和0x8,有如下操作序列:

缓存一致性协议的工作方式 2

初始状态,4个cpu的cache line都为Invalid状态(黑色表示Invalid)。cpu0发送Read消息,加载0x0的数据,数据从内存返回,cache line状态变为Shared。cpu3发送Read消息,加载0x0的数据,数据从内存返回,cache line状态变为Shared。cpu0发送Read消息,加载0x8的数据,导致cache line被替换,由于之前状态为Shared,即与内存中数据一致,可直接覆盖,而无需回写。cpu2发送Read Invalidate消息,从内存返回最新数据,cpu3返回Invalidate ACK,并将状态变为Invalid,cpu2获得独占权,状态变为Exclusive。cpu2修改cache line中的数据,cache line状态为Modified,同时内存中0x0的数据过期。cpu1 对地址0x0的数据执行原子(atomic)递增操作,发出Read Invalidate消息,cpu2将返回Read Response(而不是内存),包含最新数据,并返回Invalidate ACK,同时cache line状态变为Invalid。最后cpu1获得独占权,cache line状态变为Modified,数据为递增后的数据,而内存中的数据仍然为过期状态。cpu1 加载0x8的数据,此时cache line将被替换,由于之前状态为Modified,因此需要先执行写回操作,此时内存中0x0的数据得以更新。

总结

这就是缓存一致性协议,一个状态机,仅此而已。因为该协议的存在,每个cpu就可以放心操作属于自己的cache,而不需要担心本地cache中的数据会不会已经被其他cpu修改了之类的烦心事。

但到目前为止,cpu并不满足,觉得在缓存一致性协议的框架下工作性能不够高,但这并不是协议的问题,协议本身逻辑很严谨,没毛病(同类协议之间的优劣那是另外一回事)。性能差在哪里?假如某数据存在于其他cpu的cache中,那自己每次需要修改数据时,都需要发送Read Invalidate消息,除了等待最新数据的返回,还需要等待其他cpu的Invalidate ACK才能继续执行其他指令,这是一种同步行为,cpu可忍不了,我们看看cpu如何优化自己?

Memory Barriers: a Hardware View for Software Hackers​www.puppetmastertrading.com

缓存一致性(Cache Coherency)入门-InfoQ​www.infoq.cn”

题图:珠穆朗玛峰