4.10 替换算法
程序运行一段时间后，Cache存储空间被占满，当再有新数据要调入时,就需要通过某种机制决定替换的对象;
调出的数据块应该是以后再也用不到的数据块或者较长时间都不会再用到的数据块;
一、常见的几种替换算法
- 先进先出法-FIFO(First in First out)
- 最不经常使用法—LFU (Least Frequently Used )
- 近期最少使用法— LRU(Least recently used )
- 随机替换法
(1) FIFO 先进先出法
假设有一个数据块序列会被依次访问：$22, 11, 22, 19, 7, 16$，且cache中共有四行
| 数据块 | 22 | 11 | 22 | 19 | 7 | 16 |
|---|---|---|---|---|---|---|
| 行1 | 22 | 22 | 22 | 22 | 22 | 16 |
| 行2 | 11 | 11 | 11 | 11 | 11 | |
| 行3 | 19 | 19 | ||||
| 行4 | 7 | |||||
| 状态 | 载入 | 载入 | 命中 | 载入 | 载入 | 替换 |
FIFO根据进入cache的先后来淘汰数据块;
(2) LFU 最不经常使用法
现在数据块的序列变成了：$22, 11, 22, 19, 11, 16, 22, 4, 3$;
| 数据块 | 22 | 11 | 22 | 19 | 11 | 16 | 22 | 4 | 3 |
|---|---|---|---|---|---|---|---|---|---|
| 行1 | $22^1$ | $22^1$ | $22^2$ | $22^2$ | $22^2$ | $22^2$ | $22^3$ | $22^3$ | $22^3$ |
| 行2 | $11^1$ | $11^1$ | $11^1$ | $11^2$ | $11^2$ | $11^2$ | $11^2$ | $11^2$ | |
| 行3 | $19^1$ | $19^1$ | $19^1$ | $19^1$ | $4^1$ | $4^1$ | |||
| 行4 | $16^1$ | $16^1$ | $16^1$ | $3^1$ | |||||
| 状态 | 载入 | 载入 | 命中 | 载入 | 命中 | 载入 | 命中 | 替换 | 替换 |
图中数字的上标表示该数据块过去被调用的次数, 每一次淘汰使用次数最少的数据块;
如果有多个数据块被调用次数一样少，则可以随机淘汰;
（3）LRU 近期最少使用法
数据块的序列为：$22, 11, 22, 19, 7, 16, 4, 3$;
| 数据块 | 22 | 11 | 22 | 19 | 7 | 16 | 4 | 3 |
|---|---|---|---|---|---|---|---|---|
| 行1 | $22^0$ | $22^1$ | $22^0$ | $22^1$ | $22^2$ | $22^3$ | $4^0$ | $4^1$ |
| 行2 | $11^0$ | $11^1$ | $11^2$ | $11^3$ | $16^0$ | $16^1$ | $16^2$ | |
| 行3 | $19^0$ | $19^1$ | $19^2$ | $19^3$ | $3^0$ | |||
| 行4 | $7^0$ | $7^1$ | $7^2$ | $7^3$ | ||||
| 状态 | 载入 | 载入 | 命中 | 载入 | 载入 | 替换 | 替换 | 替换 |
图中数字的上标表示该数据块距离上一次调用经过的时间, 每一次淘汰时间最长的数据块;
任何一种淘汰算法不能仅从算法本身评价好坏，算法性能同很多因素有关系，如cache大小、程序块地址流等…
(4) 替换算法的抖动, 以FIFO为例
数据块的序列为：$22, 11, 19, 7, 16, 22, 11， 19$;
| 数据块 | 22 | 11 | 19 | 7 | 16 | 22 | 11 | 19 |
|---|---|---|---|---|---|---|---|---|
| 行1 | 22 | 22 | 22 | 22 | 16 | 16 | 16 | 16 |
| 行2 | 11 | 11 | 11 | 11 | 22 | 22 | 22 | |
| 行3 | 19 | 19 | 19 | 19 | 11 | 11 | ||
| 行4 | 7 | 7 | 7 | 7 | 19 | |||
| 状态 | 载入 | 载入 | 载入 | 载入 | 替换 | 替换 | 替换 | 替换 |
抖动就是将要访问的数据块就是刚刚淘汰的数据块, 发生抖动的情况将无法发挥cache告诉的特性；
如果cache的空间再多一行的话，该抖动就可以避免;（硬件特征）
如果要访问的数据块前移一格的话，抖动也可以避免;(程序行为)
计算机的高速的体现不仅和硬件有关，也和软件有关，软硬件协同才能保证高速特性的发挥；
peter学长加油！！！！！！！！收藏打卡了
谢谢学弟❤️