MyBlog


CPU cache 结构和缓存一致性(MESI 协议)

<p>[TOC]</p> <h1>一、cache</h1> <p>cpu cache 已经发展到了三级缓存结构,基本上现在买的个人电脑都是 L3 结构。</p> <h2>1. cache 的意义</h2> <p>为什么需要 CPU cache?因为 CPU 的频率太快了,快到主存跟不上,这样在处理器时钟周期内,CPU 常常需要等待主存,浪费资源。所以 cache 的出现,是为了缓解 CPU 和内存之间速度的不匹配问题(结构:cpu -&gt; cache -&gt; memory)。 CPU cache 有什么意义?cache 的容量远远小于主存,因此出现 cache miss 在所难免,既然 cache 不能包含 CPU 所需要的所有数据,那么 cache 的存在真的有意义吗?当然是有意义的——局部性原理。</p> <pre><code>A. 时间局部性:如果某个数据被访问,那么在不久的将来它很可能被再次访问; B. 空间局部性:如果某个数据被访问,那么与它相邻的数据很快也可能被访问;</code></pre> <h2>2. cache 和寄存器</h2> <p>存储器的三个性能指标——速度、容量和每位价格——导致了计算机组成中存储器的多级层次结构,其中主要是缓存和主存、主存和磁盘的结构。那么在主存之上,cache 和寄存器之间的关系是? <img src="https://www.showdoc.cc/server/api/common/visitfile/sign/203cb3d45cb33f27b6b1bd1db26fe003?showdoc=.jpg" alt="" /> 举个例子,当你在思考一个问题的时候,寄存器存放的是你当前正在思考的内容,cache 存放的是与该问题相关的记忆,主存则存放无论与该问题是否有关的所有记忆,所以,寄存器存放的是当前 CPU 执行的数据,而 cache 则缓存与该数据相关的部分数据,因此只要保证了 cache 的一致性,那么寄存器拿到的数据也必然具备一致性</p> <h1>二、CPU cache 结构</h1> <h2>1. 单核 CPU cache 结构</h2> <p><img src="https://www.showdoc.cc/server/api/common/visitfile/sign/91448a098564de5e7e8ec057f1873bea?showdoc=.jpg" alt="" /> 在单核 CPU 结构中,为了缓解 CPU 指令流水中 cycle 冲突,L1 分成了指令(L1P)和数据(L1D)两部分,而 L2 则是指令和数据共存。</p> <h2>2. 多核 CPU cache 结构</h2> <p><img src="https://www.showdoc.cc/server/api/common/visitfile/sign/a381036333ba0b11e7022c43677386c2?showdoc=.jpg" alt="" /> 多核 CPU 的结构与单核相似,但是多了所有 CPU 共享的 L3 三级缓存。在多核 CPU 的结构中,L1 和 L2 是 CPU 私有的,L3 则是所有 CPU 核心共享的。</p> <h1>三、MESI(缓存一致性)</h1> <p>缓存一致性:在多核 CPU 中,内存中的数据会在多个核心中存在数据副本,某一个核心发生修改操作,就产生了数据不一致的问题。而一致性协议正是用于保证多个 CPU cache 之间缓存共享数据的一致。 至于 MESI,则是缓存一致性协议中的一个,到底怎么实现,还是得看具体的处理器指令集。</p> <h2>1. cache 的写方式</h2> <p>cache 的写操作方式可以追溯到大学教程《计算机组成原理》一书。 A. write through(写通):每次 CPU 修改了 cache 中的内容,立即更新到内存,也就意味着每次 CPU 写共享数据,都会导致总线事务,因此这种方式常常会引起总线事务的竞争,高一致性,但是效率非常低; B. write back(写回):每次 CPU 修改了 cache 中的数据,不会立即更新到内存,而是等到 cache line 在某一个必须或合适的时机才会更新到内存中; 无论是写通还是写回,在多线程环境下都需要处理缓存 cache 一致性问题。为了保证缓存一致性,处理器又提供了写失效(write invalidate)和写更新(write update)两个操作来保证 cache 一致性。 写失效:当一个 CPU 修改了数据,如果其他 CPU 有该数据,则通知其为无效; 写更新:当一个 CPU 修改了数据,如果其他 CPU 有该数据,则通知其跟新数据; 写更新会导致大量的更新操作,因此在 MESI 协议中,采取的是写失效(即 MESI 中的 I:ivalid,如果采用的是写更新,那么就不是 MESI 协议了,而是 MESU 协议)。</p> <h2>2. cache line</h2> <p><img src="https://www.showdoc.cc/server/api/common/visitfile/sign/cf786c39a3476d710eabc431e3d3ed30?showdoc=.jpg" alt="" /> cache line 是 cache 与内存数据交换的最小单位,根据操作系统一般是 32byte 或 64byte。在 MESI 协议中,状态可以是 M、E、S、I,地址则是 cache line 中映射的内存地址,数据则是从内存中读取的数据。 工作方式:当 CPU 从 cache 中读取数据的时候,会比较地址是否相同,如果相同则检查 cache line 的状态,再决定该数据是否有效,无效则从主存中获取数据,或者根据一致性协议发生一次 cache-to--chache 的数据推送(参见 MESI 协议,文章最后的链接); 工作效率:当 CPU 能够从 cache 中拿到有效数据的时候,消耗几个 CPU cycle,如果发生 cache miss,则会消耗几十上百个 CPU cycle; cache 的工作原理以及在主板上的结构如下两图所示: <img src="https://www.showdoc.cc/server/api/common/visitfile/sign/989228057cdbf3fbc45ade355a42c2ea?showdoc=.jpg" alt="" /> <img src="https://www.showdoc.cc/server/api/common/visitfile/sign/09fadac76eb1350beba4a501dc7b1453?showdoc=.jpg" alt="" /></p> <h2>3. 状态介绍</h2> <p>MESI 协议将 cache line 的状态分成 modify、exclusive、shared、invalid,分别是修改、独占、共享和失效。</p> <ul> <li>modify:当前 CPU cache 拥有最新数据(最新的 cache line),其他 CPU 拥有失效数据(cache line 的状态是 invalid),虽然当前 CPU 中的数据和主存是不一致的,但是以当前 CPU 的数据为准;</li> <li>exclusive:只有当前 CPU 中有数据,其他 CPU 中没有改数据,当前 CPU 的数据和主存中的数据是一致的;</li> <li>shared:当前 CPU 和其他 CPU 中都有共同数据,并且和主存中的数据一致;</li> <li>invalid:当前 CPU 中的数据失效,数据应该从主存中获取,其他 CPU 中可能有数据也可能无数据,当前 CPU 中的数据和主存被认为是不一致的; 对于 invalid 而言,在 MESI 协议中采取的是写失效(write invalidate)。</li> </ul> <h2>4. cache 操作</h2> <p>MESI 协议中,每个 cache 的控制器不仅知道自己的操作(local read 和 local write),每个核心的缓存控制器通过监听也知道其他 CPU 中 cache 的操作(remote read 和 remote write),今儿再确定自己 cache 中共享数据的状态是否需要调整。 local read(LR):读本地 cache 中的数据; local write(LW):将数据写到本地 cache; remote read(RR):其他核心发生 read; remote write(RW):其他核心发生 write;</p> <h2>5. 状态转换和 cache 操作</h2> <p>如上文内容所述,MESI 协议中 cache line 数据状态有 4 种,引起数据状态转换的 CPU cache 操作也有 4 种,因此要理解 MESI 协议,就要将这 16 种状态转换的情况讨论清楚。 初始场景:在最初的时候,所有 CPU 中都没有数据,某一个 CPU 发生读操作,此时必然发生 cache miss,数据从主存中读取到当前 CPU 的 cache,状态为 E(独占,只有当前 CPU 有数据,且和主存一致),此时如果有其他 CPU 也读取数据,则状态修改为 S(共享,多个 CPU 之间拥有相同数据,并且和主存保持一致),如果其中某一个 CPU 发生数据修改,那么该 CPU 中数据状态修改为 M(拥有最新数据,和主存不一致,但是以当前 CPU 中的为准),其他拥有该数据的核心通过缓存控制器监听到 remote write 行文,然后将自己拥有的数据的 cache line 状态修改为 I(失效,和主存中的数据被认为不一致,数据不可用应该重新获取)</p> <h3>5.1 modify</h3> <p>场景:当前 CPU 中数据的状态是 modify,表示当前 CPU 中拥有最新数据,虽然主存中的数据和当前 CPU 中的数据不一致,但是以当前 CPU 中的数据为准; LR:此时如果发生 local read,即当前 CPU 读数据,直接从 cache 中获取数据,拥有最新数据,因此状态不变; LW:直接修改本地 cache 数据,修改后也是当前 CPU 拥有最新数据,因此状态不变; RR:因为本地内存中有最新数据,当本地 cache 控制器监听到总线上有 RR 发生的时,必然是其他 CPU 发生了读主存的操作,此时为了保证一致性,当前 CPU 应该将数据写回主存,而随后的 RR 将会使得其他 CPU 和当前 CPU 拥有共同的数据,因此状态修改为 S; RW:同 RR,当 cache 控制器监听到总线发生 RW,当前 CPU 会将数据写回主存,因为随后的 RW 将会导致主存的数据修改,因此状态修改成 I;</p> <h3>5.2 exclusive</h3> <p>场景:当前 CPU 中的数据状态是 exclusive,表示当前 CPU 独占数据(其他 CPU 没有数据),并且和主存的数据一致; LR:从本地 cache 中直接获取数据,状态不变; LW:修改本地 cache 中的数据,状态修改成 M(因为其他 CPU 中并没有该数据,因此不存在共享问题,不需要通知其他 CPU 修改 cache line 的状态为 I); RR:本地 cache 中有最新数据,当 cache 控制器监听到总线上发生 RR 的时候,必然是其他 CPU 发生了读取主存的操作,而 RR 操作不会导致数据修改,因此两个 CPU 中的数据和主存中的数据一致,此时 cache line 状态修改为 S; RW:同 RR,当 cache 控制器监听到总线发生 RW,发生其他 CPU 将最新数据写回到主存,此时为了保证缓存一致性,当前 CPU 的数据状态修改为 I;</p> <h3>5.3 shared</h3> <p>场景:当前 CPU 中的数据状态是 shared,表示当前 CPU 和其他 CPU 共享数据,且数据在多个 CPU 之间一致、多个 CPU 之间的数据和主存一致; LR:直接从 cache 中读取数据,状态不变; LW:发生本地写,并不会将数据立即写回主存,而是在稍后的一个时间再写回主存,因此为了保证缓存一致性,当前 CPU 的 cache line 状态修改为 M,并通知其他拥有该数据的 CPU 该数据失效,其他 CPU 将 cache line 状态修改为 I; RR:状态不变,因为多个 CPU 中的数据和主存一致; RW:当监听到总线发生了 RW,意味着其他 CPU 发生了写主存操作,此时本地 cache 中的数据既不是最新数据,和主存也不再一致,因此当前 CPU 的 cache line 状态修改为 I;</p> <h3>5.4 invalid</h3> <p>场景:当前 CPU 中的数据状态是 invalid,表示当前 CPU 中是脏数据,不可用,其他 CPU 可能有数据、也可能没有数据; LR:因为当前 CPU 的 cache line 数据不可用,因此会发生读内存,此时的情形如下。 A. 如果其他 CPU 中无数据则状态修改为 E; B. 如果其他 CPU 中有数据且状态为 S 或 E 则状态修改为 S; C. 如果其他 CPU 中有数据且状态为 M,那么其他 CPU 首先发生 RW 将 M 状态的数据写回主存并修改状态为 S,随后当前 CPU 读取主存数据,也将状态修改为 S; LW:因为当前 CPU 的 cache line 数据无效,因此发生 LW 会直接操作本地 cache,此时的情形如下。 A. 如果其他 CPU 中无数据,则将本地 cache line 的状态修改为 M; B. 如果其他 CPU 中有数据且状态为 S 或 E,则修改本地 cache,通知其他 CPU 将数据修改为 I,当前 CPU 中的 cache line 状态修改为 M; C. 如果其他 CPU 中有数据且状态为 M,则其他 CPU 首先将数据写回主存,并将状态修改为 I,当前 CPU 中的 cache line 转台修改为 M; RR:监听到总线发生 RR 操作,表示有其他 CPU 读取内存,和本地 cache 无关,状态不变; RW:监听到总线发生 RW 操作,表示有其他 CPU 写主存,和本地 cache 无关,状态不变;</p> <h2>5.5 总结</h2> <p>MESI 协议为了保证多个 CPU cache 中共享数据的一致性,定义了 cache line 的四种状态,而 CPU 对 cache 的 4 种操作可能会产生不一致状态,因此 cache 控制器监听到本地操作和远程操作的时候,需要对地址一致的 cache line 状态做出一定的修改,从而保证数据在多个 cache 之间流转的一致性。</p>

页面列表

ITEM_HTML