书接上回，组成原理之旅——Cache与内存的映射 – 掘金 (juejin.cn)，Cache除了存储数据之外，有一个有效位（Valid）。不止于此，还可能需要替换控制位来实现Cache行的替换策略，以及修改位来控制写Cache时数据的一致性。

Cache中主存块的替换策略

采用组相联映射或者全相联映射时，会存在需要将内存块调入Cache但Cache已满的情况。此时就需要从已有Cache行中选择一行与新调入的行进行替换。

不同的替换策略，需要记录不同的信息，我们把存储这些替换信息的位称为替换控制位。

随机替换算法

随机替换算法从已有Cache中随机选择一块进行替换。这种方法实现简单。但依据程序局部性原理程序的局部性原理，会导致命中率较低。

这种算法不需要任何的替换位。

先进先出算法（FIFO）

FIFO算法会选择最早被调入Cache中的内存块进行替换。它容易实现，但未能遵循局部性原理，最先被调入的块可能频繁被使用。

如下图中，1被频繁使用，被调出后又被调入，显然在访问4号块的时候调出1号块是不合理的。

这种算法在实现时，在每次内存块被调入内存后，旧Cache行的替换算法位的数字自增1(i++)，当Cache满时，淘汰替换算法位最大的。因此我们需要$log_2(Cache行数)$位替换算法位

贝拉迪异常（Belady’s Anomaly）

贝拉迪异常指的是，Cache容量增加但Cache命中率降低的异常现象。只有FIFO算法存在贝拉迪异常。

近期最少使用算法（LRU）

LRU算法很好地遵循了程序局部性原理。
LRU会替换最久没有被使用过的行。

实际在实现该算法时，LRU算法会将调入的新内存块的替换控制位设置为0。

当缓存命中时，假设命中的行的Cache控制位的值是$m$，其它的Cache行的替换控制位的值若大于$m$则对应的替换控制位自增1（++i)，命中行的替换控制位直接设为0。

当需要替换出Cache时，选择替换控制位值最大的Cache行。
需要的替换控制位的位数也是$log_2(Cache行数)$

Cache写策略

全写法（写直通法，Write through）

CPU的写命中Cache时，数据会同时写入Cache和主存的写缓冲区。

设立主存写缓冲区的目的是为了提高IO效率，只有写缓冲区写满或者主存的访问空闲时写缓冲区的数据才会真正被写入到主存中。

这样在替换时新调入的块直接放入Cache，无需对旧行的数据做任何处理。因此也无需对Cache行记录任何信息

回写法（写回法，write-back）

当CPU命中Cache时，读和写的操作仅会作用于Cache，不会立即作用于内存。仅有当Cache行换出时才会异步地写回内存。

回写法中每个Cache行需要1位来记录该行数据是否发生过修改。当命中Cache并写入数据时，Cache中的修改位（有时也称为脏位）会设置为1

某个时刻，需要换出Cache时，若修改位是1，Cache行的数据会被更新到内存中，再进行替换。否则直接用调入的新块覆盖当前行

写分配法和非写分配法

这两种策略都是在Cache未命中时的策略

“分配”的指的是，在Cache未命中后，分配Cache的一行来将访存地址所在的块调入内存。

写分配法会在Cache未命中时，会先把内存块调入Cache，再写Cache。
这种策略能更好地利用程序局部性原理，但每次不命中都要调入Cache

非写分配法则会直接由CPU写入主存，不做其它操作。

写直通法会与非写分配法搭配使用

写回法会与写分配法搭配使用

练习

假设主存地址为32位，按字节编址，主存和Cache之间采用全相联映射的方式和随机替换策略，主存块大小为1个字，每字32位，采用写回法（Write back)方式和随机替换策略，则存放32K字数据的Cache总容量应有多少位？

首先我们计算主存块的大小

$主存块大小 = 1 * 32bit = 32bit = 4Byte$
因为是全相联映射，所以Tag的位数为$总地址位数 – 块内地址位数$

每个Cache行都有个必须的1位有效位来指明Cache行是否有效。

之后再考虑替换控制位。因为是随机替换算法，所以无需考虑替换控制位。替换控制为为0

接着再考虑写控制位。采用的是写回法，在换出时需要根据Cache块是否被修改来决定是否将Cache数据写回主存。需要1个控制位

因此，一行Cache需要比特位是

接着，求Cache的行数，主存块大小为1个字 存放32K字数据，通过这两句话，我们可以知道Cache一共有32k行。

总结