2、LRU算法及其实现 在块表内为每一块设置一个计数器 计数器的长度与 Cache地址中的组内块号字段的长度相同。 计数器的使用及管理规则: 新装入或替换的块,其计数器清0,同组中其它块的计数器都加1。 命中的块,其计数器清0,同组的其它计数器中,凡是计数器的值小于命中 块所属计数器原来值的,都加1,其余计数器不变。 需要替换时,在同组的所有计数器中选择计数值最大的计数器,它所对应的 块就是要被替换的块 ·例子:IBM370165机的 Cache采用组相联映象方式。每组有4块,为了实 现LRU替换算法,在块表中为每一块设置一个2位的计数器。在访问 Cache的 过程中,块的装入、替换及命中时,计数器的工作情况如表 块地址流|主存块1主存块2「主存块3主存块4主存块5主存块4 块号计数器块号计数器块号计数器块号计数器块号计数器块号计数器 Cache块0 10 11500|501 Cache块101|200201210[211 cahe2閡0國103|003|o1|310310 Cache块3bd011014004014 00 装入装入装入装入替换命中 ●LRU算法的优点:命中率比较高 能够比较正确地利用程序的局部性特点, 充分地利用历史上块地址流的分布情况。 是一种堆栈型算法,随着组内块数增加,命中率单调上升, ●LRU算法的缺点 控制逻辑复杂,增加了判断和处理命中的情况。 3、比较对法 以三个块为例,三个块分别称为块A、B、C 表示方法 用TAB=1表示B块比A块更久没有被访问过, 如果要表示块C最久没有被访问过 从最近到最远分别是:A、B、C或B、A、C 即CLRU=TAB·TBC·TAC+TAB·TBC·TAC=TAB·TBC ARU=TAB·TAC BLRU=TAB·TBC ●每次访问之后要改变触发器的状态 在访问块A之后:TAB=1,TAC=1 在访问块B之后:TAB=0,TBC=1 在访问块C之后:TAC=0,TBC=03—9 2、LRU 算法及其实现 • 在块表内为每一块设置一个计数器， 计数器的长度与 Cache 地址中的组内块号字段的长度相同。 • 计数器的使用及管理规则： 新装入或替换的块，其计数器清 0，同组中其它块的计数器都加 1。 命中的块，其计数器清 0，同组的其它计数器中，凡是计数器的值小于命中 块所属计数器原来值的，都加 1，其余计数器不变。 需要替换时，在同组的所有计数器中选择计数值最大的计数器，它所对应的 块就是要被替换的块。 • 例子：IBM 370/165 机的 Cache 采用组相联映象方式。每组有 4 块，为了实 现 LRU 替换算法，在块表中为每一块设置一个 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 装入 装入 装入 装入 替换 命中 • LRU 算法的优点：命中率比较高 能够比较正确地利用程序的局部性特点， 充分地利用历史上块地址流的分布情况。 是一种堆栈型算法，随着组内块数增加，命中率单调上升。 • LRU 算法的缺点： 控制逻辑复杂，增加了判断和处理命中的情况。 3、比较对法 以三个块为例，三个块分别称为块 A、B、C • 表示方法： 用 TAB = 1 表示 B 块比 A 块更久没有被访问过， 如果要表示块 C 最久没有被访问过： 从最近到最远分别是：A、B、C 或 B、A、C 即 CLRU = TAB TBC TAC +TAB TBC TAC = TAB TBC LRU AB BC LRU AB AC B T T A T T =  =  • 每次访问之后要改变触发器的状态。 在访问块 A 之后：TAB＝1，TAC＝1 在访问块 B 之后：TAB＝0，TBC＝1 在访问块 C 之后：TAC＝0，TBC＝0