3.3.3 Cache替换算法及其实现 Cache替换算法使用时间: 发生段失效,且可以装入新调入块的几个 Cache块都已经被装满时 直接映象方式实际上不需要替换算法。 全相联映象方式的替换算法最复杂。 Cache替换算法要解决的问题: 1、记录每次访问 Cache的块号。 2、管理好所记录的 Cache块号,为找出被替换的块号提供方便。 3、根据记录和管理的结果,找出被替换的块号。 Cache替换算法的主要特点:全部用硬件实现 1、轮换法及其实现 用于组相联映象方式中,有两种实现方法。 方法一:每块一个计数器 在块表内增加一个替换计数器字段, 计数器的长度与 Cache地址中的组内块号字段的长度相同。 替换方法及计数器的管理规则: 新装入或替换的块,它的计数器清0;同组其它块的计数器都加 在同组中选择计数器的值最大的块作为被替换的块 ·例子: Solar-1665小型机的 Cache采用位选择组相联映象方式。 Cache每组的块数为4,因此,每块用一个2位的计数器 种轮换法的装入及替换过程 序列初始值装入块0装入块01装入块10装入块1替换块00 块00 10 块01 11 块10 10 块11 00 01 方法二:每组一个计数器 替换规则和计数器的管理: 本组有替换时,计数器加“1 计数器的值就是要被替换出去的块号。 例如:NOVA3机的 Cache采用组相联映象方式s Cache每组的块数为8,每组设置一个3位计数器。 在需要替换时,计数器的值加“1” 用计数器的值直接作为被替换块的块号 轮换法的优点:实现比较简单。 能够利用历史上的块地址流情况, 轮换法的缺点:没有利用程序的局部性特点3—8 3.3.3 Cache 替换算法及其实现 • Cache 替换算法使用时间： 发生段失效，且可以装入新调入块的几个 Cache 块都已经被装满时。 直接映象方式实际上不需要替换算法。 全相联映象方式的替换算法最复杂。 • Cache 替换算法要解决的问题： 1、记录每次访问 Cache 的块号。 2、管理好所记录的 Cache 块号，为找出被替换的块号提供方便。 3、根据记录和管理的结果，找出被替换的块号。 • Cache 替换算法的主要特点：全部用硬件实现 1、轮换法及其实现 用于组相联映象方式中，有两种实现方法。 方法一：每块一个计数器 • 在块表内增加一个替换计数器字段， 计数器的长度与 Cache 地址中的组内块号字段的长度相同。 • 替换方法及计数器的管理规则： 新装入或替换的块，它的计数器清 0；同组其它块的计数器都加“1”。 在同组中选择计数器的值最大的块作为被替换的块。 • 例子：Solar-16/65 小型机的 Cache 采用位选择组相联映象方式。 Cache 每组的块数为 4，因此，每块用一个 2 位的计数器。 一种轮换法的装入及替换过程 序列 初始值 装入块00 装入块01 装入块10 装入块11 替换块00 块 00 00 00 01 10 11 00 块 01 00 01 00 01 10 11 块 10 00 01 10 00 01 10 块 11 00 01 10 11 00 01 方法二：每组一个计数器 • 替换规则和计数器的管理： 本组有替换时，计数器加“1”， 计数器的值就是要被替换出去的块号。 • 例如：NOVA3 机的 Cache 采用组相联映象方式。 Cache 每组的块数为 8，每组设置一个 3 位计数器。 在需要替换时，计数器的值加“1”， 用计数器的值直接作为被替换块的块号。 • 轮换法的优点：实现比较简单。 能够利用历史上的块地址流情况， • 轮换法的缺点：没有利用程序的局部性特点