1、轮换法及其实现
轮换法通常用于组相联映象及地址变换方式中，常见的有两种实现方法。
方法一：每块一个计数器
在上面介绍组相联地址变换方式中，块表内用来表示每一块映象关系的一个存储字由三字段组成，包括主存地址的区号E和块号B、Cache的块号b及一个有效位e。为了实现轮换法，还要再增加设置一个替换计数器字段。计数器字段的长度与Cache地址中的组内块号字段的长度相同。
替换方法及计数器的管理规则是：被装入或被替换的块，它所属的计数器清为"0"，同组的其它块所属的计数器都加"1"。需要替换时，在同组中选择计数器的值最大的块作为被替换的块。
下面举一个例子来说明轮换法是如何实现的。
Solar-16/65机的Cache采用组相联映象方式。Cache每组的块数为4，因此，每块用一个2位的计数器。刚开始时，同组的4个计数器均为00。装入及替换的过程见表3.4。实际上，是装入还是替换是由有效位决定的，而替换计数器用来指示装入或替换的块号。
表3.4 一种轮换法的装入及替换过程
|
序列
|
初始值
|
装入块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"，用计数器的值直接作为被替换块的块号。
轮换法的优点是实现比较简单。与随机法相比，它能够利用历史上的块地址流情况，把最先装入的块作为被替换的块。但是，与随机法相同，它也没有能够利用程序的局部性特点。因为最先装入cache个块，很可能也是经常要使用的块。因此，它的效果虽然比随机法好，但仍然不理想。