计组——cache替换算法及cache写策略

一、cache替换算法

1. 随机算法

若cache已满，则随机选择一个cache块进行替换
特点：实现简单，但完全没考虑局部性原理，命中率低，实际效果很不稳定

2.先进先出

若cache已满，则选择最先被调入的cache块进行替换
特点：实现简单，也没有考虑局部性原理，最先调入的cache块也可能是被频繁访问的，会产生抖动现象

3.近期最少使用

为每一个cache块设置一个计数器，用于记录该cache已经多久没有被访问。若cache已满，则选择计数器最大的cache块进行替换

• 命中时，所命中的行的计数器清零，比其低的计数器加1，其余不变；
• 未命中且还有空闲行时，新装入的行的计数器置0，其余非空闲行全加1；
• 未命中且无空闲行时，计数值最大的行的信息块被淘汰，新装行的块的计数器置0，其余全加1。

cache块的总数=$a^n$，则计数器需要n位。且cache装满后所有计数器的的值一定不重复

特点：基于局部性原理，近期被访问过的主存块，在不久的将来也很可能被再此访问，因此淘汰最久没被访问过的块是最合理的。LRU算法的实际运行效果优秀，cache命中率高。

若被频繁访问的主存块数量大于cache行的数量，则有可能发生抖动

4.最近不经常使用

为每一个cache块设置一个计数器（初始值为0），用于记录该cache已经被访问了几次（每访问一次，计数器加1）。若cache已满，则选择计数器最小的cache块进行替换
若有多个计数器最小的行，可按行号递增或者先进先出的策略进行替换
特点：曾经被经常访问的主存块在未来不一定会用到，没有很好地遵循局部性原理，因此实际效果不如近期最少使用

二、cache写策略

由于cache 中的数据块是主存块的副本，当对 Cache 中的内容进行变更时，就要考虑主存如何变更以及在什么时机变更的问题~

写操作也分为两种情况：
写命中（Write Hit）：要写的单元已经在 Cache 中
写不命中（Write Miss）：要写的单元不在 Cache 中

1. 写命中：

（1）全写法 Write Through

（又名写直达、直写法、写直通法）

同时修改 cache 和主存。需要频繁写主存，访存次数增加，但能保证数据的一致性，应用于数据准确率要求高，实时性高的场景。一般使用写缓冲（write buffer）(SRAM实现的FIFO队列)，在专门的控制电路控制下逐一写回。（若写操作很频繁，可能会因为写操作饱和而发生阻塞）

（2）写回法 Write Back

（又名写回、回写、一次性写）

先修改 cache 暂不修改主存，当cache块要被换出时（根据脏位判断是否需要写回）一次性写主存。应用于写操作频繁，写密集型的场景；但存在数据不一致的隐患。

2. 写不命中

（1）写分配法 Write Allocate

将主存块调入 cache 中，然后在Cache中修改，更新相应的地址单元。通常搭配写回法使用。这样可以利用空间局部特性，但是每次都要先读一个数据块到 cache 块，相对速度较慢

（2）非写分配法 Not Write Allocate

直接修改主存数据块里的地址单元，不把主存调入 cache 中

通常，非写分配法和全写法搭配使用；写分配法和写回法搭配使用。