前言：来吧，继续补 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，我就不继续深挖了。。。
