Sword 内存屏障-缓存一致性协议

缓存一致性协议介绍

    现代计算机都是多核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),如果我们当前需要某个地址的数据,那么很可能我们马上要访问它的邻近地址)。

由于每个cpu独立工作,那就会有一个显著的问题:多个cache与内存之间的数据同步该怎么做?

缓存一致性协议就是要解决这个问题,协议有多种,可以分为两类:“窥探(snooping)”协议和“基于目录的(directory-based)”协议,

本文所讲述的MESI协议属于一种“窥探协议“。

 

窥探协议的基本思想
     所有cache与内存,cache与cache(是的,cache之间也会有数据传输)之间的传输都发生在一条共享的总线上,而所有的cpu都能看到这条总线,

同一个指令周期中,只有一个cache可以读写内存,所有的内存访问都要经过仲裁(arbitrate)。cahce不但与内存通信时和总线打交道,

而且它会不停地窥探总线上发生的数据交换,跟踪其他cache在做什么。所以当一个cache代表它所属的cpu去读写内存时,

其它cpu都会得到通知,它们以此来使自己的cache保持同步。

 

MESI协议的工作方式
协议中最重要的内容有两部分: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,于是有以下的消息机制:

Readcpu发起读取数据请求,请求中包含需要读取的数据地址。

Read Response作为Read消息的响应,该消息可能是内存响应的,也可能是某cpu响应的(比如该地址在某cpu cache Line中为Modified状态,则该cpu必须返回该地址的最新数据)。

Invalidatecpu发起”我要独占一个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)”的方式。

Sword 内存屏障-缓存一致性协议

初始状态,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的数据得以更新。

 

Sword 内存屏障-缓存一致性协议

上一篇:精确的浮点数运算


下一篇:虚拟头结点