计算机组成原理-Cache替换算法
文章目录
- 总览
- 随机算法（RAND）
- 先进先出算法（FIFO）
- 近期最少使用算法（LRU）
- 最不经常使用算法（LFU）
- 总结
总览
随机算法（RAND）
没有选择性地考虑替换哪一块Cache，或者说没有考虑局部性原理（要用的可能Cache块），使得可能下一次要访问的Cache块被替换了，进而导致替换次数频繁
先进先出算法（FIFO）
先进入的Cache的先被替换
近期最少使用算法（LRU）
人为判断替换哪个Cache块：从当前要访问的主存块往前看，将其与Cache块对比，直到只剩下一个Cache块没有对应的主存块则替换它
Cache块的总数为2的n次方时，计数器只需要n位。
若装满后此时只有替换和命中，替换时会替换计数器值最大的，命中时会由于未命中的比其低的计数器加1，所以最大的计数器的位数依然不会超过n位
且Cache装满后所有计数器的值一定不重复。
抖动现象依然可能存在
最不经常使用算法（LFU）
若有多个计数器最小的行（多个计数器的行同时最小），可以按照行号递增或者FIFO（先进先出）策略来选择替换的
新调入的块计数器赋值为0，之后每访问一次计算器+1.需要替换时，选择计数器最小的一行
计数器比特位较长，因为此时计数器的值的大小没有限制
总结
