Cache 替换算法和写策略

前言：来吧，继续补 Cache 的知识。

替换算法

还记得组相联吗？就是主存中的一块可以放在 Cache 中的一组中的任意一行。但是 Cache 满了怎么办？就得覆盖掉一个，覆盖掉哪一个？这就是替换算法要解决的。

不去说什么先进先出、随机替换的算法。直接上最难的——最近最少用算法 LRU（least-recently used）

LRU

关键就是：总是把最近最少用的那一块淘汰掉

在具体到硬件的时候，Cache 每一行都有一个计数器。用来记录少用的次数。

具体看这个图：

现在有四个格子，但是有 5 个不一样的块要进来，我一步一步给你解释。

• 1 来，没有命中，1 进入缓存。计数器为 0
• 2 来，没有命中，2 进入缓存。2 计数器 0, 1计数器为 1（对应第三条）
• 3 来同上
• 4 来同上
• 1 又来，命中，1 的计数器变为 0。其余加 1。
• 2 又来，命中，2 的计数器变为 0。其余加 1。
• 5 来了，但是现在 Cache 满了。去掉哪一个呢？计数器最大的那个！
• 之后的就不说了

做题！

为了巩固上面的知识，我们来做题

MRU 的算法我们就不做了

假设主存以字为单位（16 位）先解决：「主存地址划分」

主存地址 = 主存标签 + 组号 + 块内地址

• 所以块内地址就是 6 位。因为块的大小是 64 字，有 64 个单元

• 由于是 4 路组相联。并且总大小是 4K 字。每一组的大小是 4 × 64 字。相除得到 4 。所以组号就是 4 位。

• 标志位：由于告诉你主存空间大小是 32K × 16 位。所以剩下的就是标志位

所以得到：

现在要循环访问 0~4351 10次

• 当访问 0 时，未命中，把 0~63 所有内容搬到缓存中，后来全命中

• 当访问 64 时，未命中，把 64~127 所有内容搬到缓存中，后来全命中

• ......（把 4352 分为每块 64 个，一共 68 块的块 ）

• 当访问 64~67 块（从 0 开始数）时，都不在缓存中，要替换。

第一次循环结束

第二次循环开始的时候，一共会有 20 个块要替换。

每次循环都是这样

所以：

命中率为：

再放个图感受一下。。。（我是不是没讲清楚。。。）

写策略

为什么要保持 Cache 和主存中数据的一致？

• 因为 Cache 中的内容是主存块副本，当对 Cache 中的内容进行更新时，就存在 Cache 和主存如何保持一致的问题。

• 当多个设备都允许访问主存时

  例如： I/O 设备可直接读写内存时，如果 Cache 中的内容被修改，则 I/O 设备读出的对应主存单元的内容无效；若 I/O 设备修改了主存单元的内容，则 Cache 中对应的内容无效。

• 当多个 CPU 都带有各自的 Cache 而共享主存时某个 CPU 修改了自身 Cache 中的内容，则对应的主存单元和其他 CPU 中对应的内容都变为无效。

写操作也有两种情况：

• 写命中（Write Hit）：要写的单元已经在 Cache 中
• 写不命中（Write Miss）：要写的单元不在 Cache 中

写策略

写命中：

• Write Through（通过式写、写直达、直写）

  同时写 Cache 和主存单元。但是经常要和主存操作，速度太慢。可以使用写缓冲，并行操作。

• Write Back（一次性写、写回、回写）

  只写 cache 不写主存，缺失（没找到）时一次写回。每行有个修改位（叫做 dirty 位），大大降低主存带宽需求，控制可能很复杂。

写不命中

• Write Allocate（写分配）

  将主存装入 Cache 中，然后更新相应单元。这样可以利用空间局部特性，但是每次都要读一个块。速度慢

• Not Write Allocate（非写分配）

  直接写主存单元，不把主存放入 Cache 中。

现代的计算机当然存在多级 Cache，我就不继续深挖了。。。