52高速缓冲存储器( Cache) 口四 Cache置换策略 Cache的容量总是比主存储器小得多,因此,必 然会出现cPU需要访问的数据不在 Cache中的 情况。这时,就要从主存中调入新的数据块如 果这时可以装人新块的几个 Cache块都已经装满 时,就必须淘汰其中某块中的数据以装入新数据, 选择 被淘 Cache e置换 算法)。 在直接映象方式下,不存在块替换的算法,因为 每块的位置映象是固定的,需要哪一块数据就 可直接确定地将该块数据调入上层确定位置。而 其他两种映象就存在替换策略的问题,就是要选 择簪换到哪一个 Cache块。 ■置换策略直接影响 Cache主存体系的命中率
5.2 高速缓冲存储器（Cache） 四. Cache置换策略 ◼ Cache的容量总是比主存储器小得多，因此，必 然会出现CPU需要访问的数据不在Cache中的 情况。这时，就要从主存中调入新的数据块。如 果这时可以装入新块的几个Cache块都已经装满 时，就必须淘汰其中某块中的数据以装入新数据， 选择被淘汰块的方法称为Cache置换策略（替换 算法）。 ◼ 在直接映象方式下，不存在块替换的算法，因为 每一块的位置映象是固定的，需要哪一块数据就 可直接确定地将该块数据调入上层确定位置。而 其他两种映象就存在替换策略的问题，就是要选 择替换到哪一个Cache块。 ◼ 置换策略直接影响Cache—主存体系的命中率
52高速缓冲存储器( Cache) 1.随机法 随机数产生器产生一个随机数,以此确定要被 替换的块。 2.先进先出法(FFO) 这种算法的思想是这样的,不管已调入块的使 用频率如何,选择最早调入的块作为替换的对 象 3.最近最少使用法(LRU 这种算法又称为最久未使用法。选择近期最久 没有被访问的块作为被替换的块
5.2 高速缓冲存储器（Cache） 1．随机法 随机数产生器产生一个随机数，以此确定要被 替换的块。 2．先进先出法（FIFO） 这种算法的思想是这样的，不管已调入块的使 用频率如何，选择最早调入的块作为替换的对 象。 3．最近最少使用法（LRU） 这种算法又称为最久未使用法。选择近期最久 没有被访问的块作为被替换的块
5,2高速缓冲存储器( Cache) ■LRU算法的实现方法: 1)寄存器栈法: 设置一个与 Cache中数据块数相等的寄存器 堆栈,存放每个块的块号。最近使用过的块号 始终保持在栈的顶部,最久未使用过的块号放 在栈的底部 块访问时,从栈顶向栈底顺序查找该块的块 号,如果找到,将该块号抽出来放在栈顶,如 果没有找到,栈顶压入该块块号,栈底的块号 出栈
5.2 高速缓冲存储器（Cache） ◼ LRU算法的实现方法： 1）寄存器栈法： 设置一个与Cache中数据块数相等的寄存器 堆栈，存放每个块的块号。最近使用过的块号 始终保持在栈的顶部，最久未使用过的块号放 在栈的底部。 块访问时，从栈顶向栈底顺序查找该块的块 号，如果找到，将该块号抽出来放在栈顶，如 果没有找到，栈顶压入该块块号，栈底的块号 出栈
5,2高速缓冲存储器( Cache) 寄存器栈法示意图 11,6访问时: 2 11 11 297 找到 9 7 2 6 6 11 没找到 9 7 9
5.2 高速缓冲存储器（Cache） 寄存器栈法示意图 11，6 访问时： 2 11 9 7 11 11 2 9 7 找到 2 11 9 7 6 6 2 11 9 没找到
5,2高速缓冲存储器( Cache) 2)计数法: ■为 Cache中每个块设置一个计数器,按一定的 周期自动计数。当某一块数据被访问时,其对 应的计数器清零。 ■计数值表示上一次访问后经过的时间,替换选 择计数值最大的块替换出去。 块地址流|主存块1主存块2主存块3主存块4主存块5主存块4 块号|计数器块号计数器块号计数器块号计数器块号计数器块号计数器 Cache块01001011101n1500501 Cache块1 012002|0121021 Cache块2 10300301310310 Cache块3 10 l1400401400 操作类型装入装入装入装入替换命中
5.2 高速缓冲存储器（Cache） 2）计数法： ◼ 为Cache中每个块设置一个计数器，按一定的 周期自动计数。当某一块数据被访问时，其对 应的计数器清零。 ◼ 计数值表示上一次访问后经过的时间，替换选 择计数值最大的块替换出去。 块地址流 主存块 1 主存块 2 主存块 3 主存块 4 主存块 5 主存块 4 块号 计数器 块号 计数器 块号 计数器 块号 计数器 块号 计数器 块号 计数器 Cache 块 0 1 00 1 01 1 10 1 11 5 00 5 01 Cache 块 1 01 2 00 2 01 2 10 2 11 2 11 Cache 块 2 01 10 3 00 3 01 3 10 3 10 Cache 块 3 01 10 11 4 00 4 01 4 00 操作类型 装入 装入 装入 装入 替换 命中