计算机组成原理_Cache的替换算法
计算机组成原理总目录
Cache的替换算法
(1)全相联映射下,若Cache已满,则在所有Cache块中选取一个Cache块进行替换
(2)直接映射下,若Cache已满,则从Cache对应要调入的主存块位置进行替换
(3)组相联映射下,当Cache内的分组满后,才需要进行替换
1. 随机算法(RAND)
随机算法(Random)顾名思义就是随机地选择Cache块进行替换
如下图:
- 橙色:代表Cache有空块可直接使用,则调入主存块到空闲Cache块中
- 红色:代表该主存块在Cache中未命中,则替换该Cache块
- 绿色:代表该主存块在Cache中命中,直接访问该Cache块即可
分析:没有考虑到局部性原理,运气不好的话刚调入的Cache块有会被马上替换出来
2. 先进先出(FIFO)
先进先出算法(First In First Out)顾名思义就是替换最先被使用的Cache块
如下图:
- 橙色:代表Cache有空块可直接使用,则调入主存块到空闲Cache块中
- 红色:代表该主存块在Cache中未命中,【则替换最先被使用的Cache块】
- 绿色:代表该主存块在Cache中命中,直接访问该Cache块即可
分析:同样没有考虑到局部性原理,如果最先被使用的先被调出,而后又频繁使用1234块,就会发生【抖动现象】
抖动:频繁调入调出Cache块,造成性能的下降==
如下图的极端情况,在下图中的访问主存块顺序下,可能一下都没命中
(有没有觉得很像你在电脑word写了半天论文,却因为切到QQ回了一条消息而导致word卡死,论文没了)
3. 近期最少使用(LRU)
近期最少使用算法(Least Recently Used):
每个Cache都设置一个【计数器】,代表每个Cache块有多久没被访问,当Cache满的时候替换【计数器】最大的Cache块
如下图:
- 橙色:代表Cache有空块可直接使用,【则调入主存块到空闲Cache块中并设置计数器为0,其余非空闲块计数器+1】
- 红色:代表该主存块在Cache中未命中,【则替换计数器最大的Cache块,并清零该计数器,其他非空闲块计数器+1】
- 绿色:代表该主存块在Cache中命中,【则比该Cache块计数器低的均+1,并清零该Cache块计数器】
分析:该算法比较好的利用了局部性原理(近期被访问的主存块可能在不就还会被访问到),因此该算法很不错
但是如果频繁被访问的主存块数 > Cache的块数,则可能还会发生抖动现象
4. 最近不经常使用(LFU)
最近不经常使用算法(Least Frequently Used):
每个Cache都设置一个【计数器】,用于记录每个Cache块被访问的次数,当Cache满的时候替换【计数器】最小的Cache块如下图:
- 橙色:代表Cache有空块可直接使用,【则调入主存块到空闲Cache块中并设置计数器为0】
- 红色:代表该主存块在Cache中未命中,【则选择计数器最小的Cache块替换,若计数器同样小,则可以采用其他策略(RAND、FIFO、按顺序)进行替换,并重置计数器为0】
- 绿色:代表该主存块在Cache中命中,【则命中的Cache块计数器+1】
分析:没有很好的利用局部性原理,因为已知经常用到的主存块在未来不一定要用到,其命中率相比LRU较低,且CPU访问主存的次数极高,代表计数器将会占用较多的空间
LRU和LFU比较:LRU会替换最近最少访问的Cache块,而LFU会替换访问次数最小的Cache块
虽然算法不一样,但从说明上这么一看似乎LRU也可以理解成LFU,最近最少访问不就等于访问次数最小吗?
但是假设我们先频繁访问了某程序的主存数据A【主存块号为1、2、3、4】,将其全部装入Cache,如果未来需要频繁访问程序的主存数据B【97、98、99】
(1)对LFU算法而言,就会出现频繁调入调出计数器最小的【Cache块(1)】,即抖动现象
(2)但对于LRU算法的影响较小,LRU算法能更快的把数据A的Cache块全部替换成数据B的主存块