cache和主存的映射方式
全相联映射
主存块可以放在cache的任意位置
假设某个计算机的主存地址空间大小为256MB,按字节编址。
其数据cache有8个cache行,行长64B
由此可知,我们想要求出主存被分为多少块,就用256MB/64B =228/26=2^22
由于主存有28位,那么它就有22位用来表示主存块号,还有剩下6位用来表示块内地址
cache命中判定:
要访问1011010110.....001110
1.主存地址前22位,对比cache中所有块的标记
2.若标记匹配,且有效位=1,则cache命中,访问块内地址位=001110的单元
3.若没有命中,或者有效位=0,那么正常访问主存即可
直接映射
每个主存块只能放到一个特定的位置,cache块号=主存块号%cache总块数
%是取余操作,比如说cache块有8块,他映射主存的10号块的位置,那么10%8=2
假设某个计算机的主存地址空间大小为256MB,按字节编址。
其数据cache有8个cache行,行长64B
此时cache有8个块,当主存块号(二进制)对2^3进行取余 ,那么这个运算结果就相当于我们保留了末尾3位
此时如果主存地址可以映射到cache的0号位置,那么它的末尾三位一定是0
这时候相比全相联映射我们可以把表示主存块号的22位分割成19位标记+3位行号
块内地址依然是6位
此时如果想要访问101.....110001110
1.先根据主存块好找到后3位确定cache行
2.在看如果主存块号的前19位与cache标记匹配且有效位=1,那么cache命中,访问地址为001110的单元
3.若没有命中,或者有效位=0,那么正常访问主存即可
组相联映射
把cache块分组,cache块分为若干块,每个主存块可放到特定分组中任意一个位置,组号=主存块号%分组数
比如说,我们分了4组(0~3),我们要把主存15位置的数据映射到cache,那么就15%4=3,就放到第3组
假设某个计算机的主存地址空间大小为256MB,按字节编址。
其数据cache有8个cache行,行长64B
cache2路组相联映射,2块为1组,分4组
组的数量为22个,那么当主存块号(二进制)对22进行取余,相当于保留了后2位
此时也可以和直接映射一样把主存块号分为22位的标记,和2位的组号
此时如果想要访问101.....10001110
1.根据主存块号后2位,找到cache中的01组
2.如果前20位与分组哪某个标识匹配,且有效位=1,则cache命中,访问地址为001110的单元
3.若没有命中,或者有效位=0,那么正常访问主存即可
标记
为了区分主存块在cache上映射的地址,每个cache块都需要有一个标记,对应它所映射的主存块的位置
标记位如果没有指向,就让它指向0,这时候问题就来了,如果没有另外一个标识,那他们就会默认指向内存块0的位置,这样是不妥的
那么光是有标记还不够,还需要有一个有效位,来辨别这个标记是否有效。
好处和坏处
1.直接映射命中率最低,全相联映射命中率最高
2.直接映射的判断开销最小,所需时间最短,全相联映射的判断开销最大,所需时间最长
3.直接映射标记所占的额外空间开销最少,全相联映射所占空间开销最大
替换算法
全相联映射
cache满了才需要替换,在全局选择替换哪一块
直接映射(无需考虑替换算法)
如果对应位置非空,则毫无选择的直接替换
组相联映射
只有分组满了才需要替换,在分组内选择替换哪一块
随机算法(RAND)
如果cache已满,则随机选择一块替换
随机算法的实现很简单,但是没有考虑到局部性原理,因此命中率很低,实际效果不稳定
如图:随机算法在释放的时候都是随机的

先进先出算法(FIFO)
若cache已满,替换最先被掉入cache的块。
实现简单,最开始按#0#1#2放入cache,之后轮流替换#0#1#2
FIFO依然没有考虑到局部性原理,原先被掉入cache的块也可能是被频繁访问的

近期最少使用(LRU)
为每一个cache块设置一个计数器,用于记录每个cache块已经多久么有被访问了,当cache满后,替换计数器最大的
如果cache块的总数为2^n ,那么就需要n位的计数器
1.命中时,所命中的计数器清零,比其低的计数器+1,其余不变
2.未命中且还有空闲行时,新装入的行的计数器置0,其余非空闲行全加1
3.未命中且无空闲行时,计数器最大的行信息块被淘汰,新装行的块计数器置0,其余全+1
基于局部性原理,近期被访问过的主存块,在不久的将来可能会被再次访问,因此淘汰醉酒没有被访问过的块是合理的,lru算法的实际运行效果优秀,cache命中率高,但是如果被频繁访问的主存块的数量大于cache行的数量,则有可能发生抖动
最近不经常使用(LFU)
为每个cache块设置一个计数器,用于记录每个cache块被访问了几次,cache满后,替换计数器最小的
新掉入的块计数器为=0 之后每次被访问都会让那个计数器+1,需要替换是,选择计数器最小的那一行
如果需要替换的时候遇到两个计数器值相等的,那么就根据fifo策略,替换掉最先进入的行
曾经被警察访问的主存块不一定在未来被用到,并没有很好的尊循局部性原理,因此运行效率不如LRU