一种基于局部性原则的时钟置换改进算法

王珍玲，丁 春

(天津职业技术师范大学信息技术工程学院，天津 300222)

0 引言

操作系统虚拟存储器管理技术的优点具有很强的吸引力，现代操作系统从理论到实践证明了这种技术是行之有效的，且已成为大多数操作系统的一个基本组成部分。虚拟存储器的理论依据——局部性原理，是指程序在执行过程中的一个较短时间内，程序所执行的指令地址和操作数的地址分别局限于一定的区域内，它具体表现为时间局部性和空间局部性两个方面［1］。

实现虚拟存储器管理技术采用的页面置换算法直接影响着计算机系统的性能。如果选用的算法不合适，可能会出现“抖动”现象。也就是说，刚被置换出主存的页面，不久又要被访问，这样又要把它调入主存，同时，又要将某一页置换出主存。如果频繁地进行页面从主存到辅存的置换，致使系统的大部分时间浪费在页面的调度上，从而影响整个系统的性能［2］。

由于数据结构简单，时钟算法是操作系统常用的页面置换算法，但是该算法在实现上淘汰页面所进行的I/O操作会产生较大的开销。本文针对时钟算法的这一缺陷，提出一种改进的时钟算法，可减少淘汰页面时需要的I/O操作，以提高系统性能。

1 虚拟存储器管理的相关技术

1.1 数据结构

数据结构即分区分配中所用的数据组织形式。常用的数据结构有两种形式:空闲分区表或空闲分区链。当空闲分区表或空闲分区链为空时，如果有进程的页面要执行，而该页又属于缺页现象，则需要采用页面置换算法从主存淘汰一个页面。

1.2 页表［3］

页表是一个数组，每个表目对应着进程的一个虚页，记录着物理页架号、修改位和访问位等有关进程的信息。

(1)物理页架号:为进程的一个页面存放的物理页架号。

(2)修改位:有2个状态。为“1”时，表示对应的进程页面调入主存后内容被修改过，置换出主存时，需修改交换区和相应的文件;为“0”时，表示对应的进程页面调入主存后内容没有修改过，置换出主存时，什么也不需要做。

(3)访问位:有2个状态。为“1”时，表示对应的进程页面调入主存后被访问过;为“0”时，表示对应的进程页面调入主存后没有被访问过。

当需要将进程的某一页装入内存时，如果空闲分区表或空闲分区链为空，则需要参照进程的页表，按照一定的页面置换算法，从主存淘汰一个页面。

2 时钟算法

把调入主存的进程的各个页面，按调入主存的时间顺序用链指针进行链接，选择淘汰页时，从链头开始查找。按照局部性原理，刚刚被访问的页很快还要被访问的可能性很大［4］。在寻找淘汰页的时候，为了避免刚刚访问的页被淘汰，以避免“抖动”现象的出现，页面链表头的访问位为1的页面，不断被移动到链尾［5］，这样将增大系统的开销。

时钟算法［6］是将进程需要访问的所有页构成像时钟一样的环形链表，用一个指针指向调入主存最早的页。当产生缺页中断时，先检测指针指向的页。如果它的访问位为0，则淘汰该页。新装入的页插入到这个位置，然后指针向前移动一个位置;如果它的访问位为1，则清除为0，同时将指针向前移动一个位置，继续检查访问位，直到找到第一个访问位为0的页面。时钟算法如图1所示。

图1 时钟算法

按照时钟置换算法，当选择出淘汰页后，由于该页调入主存有可能被修改过，这样，置换出主存时要相应地修改交换区和相应的文件［7-8］。

3 改进的时钟算法

为了尽量避免按照时钟置换算法将调入主存后被修改过的页置换出去，从而增加系统修改交换区和相应的文件带来的开销，在选择淘汰页时，可同时参考页表的访问位和修改位的状态。在遵循局部性原则的基础上，在出现缺页现象时，优先淘汰访问位和修改位都为0的页面。

当运行一个进程时，由操作系统设置进程所有页的访问位和修改位初值为0。每次调入主存时，该页的访问位置为1;如果调入主存又被修改，该页的修改位置为1。访问位被定期(如间隔某个时间)清0。

进程的所有页面，按照访问位和修改位的值可分为 4 类［6，9］。

(1)a类:最近未访问过，未修改。值为00。

(2)b类:最近未访问过，已修改。值为01。

(3)c类:最近访问过，未修改。值为10。

(4)d类:最近访问过，已修改。值为11。

改进的时钟算法同样将进程需要访问的所有页构成像时钟一样的环形链表，用一个指针指向调入主存最早的页。当产生缺页中断时，扫描环形链表，首先检查指针指向的最早页属于哪一类，来确定淘汰页。具体执行过程如下。

(1)从指针指向的链头开始，循环扫描环形链表，寻找第一个a类页，即访问位为0，修改位为0，则该页为选定的淘汰页，而在第一轮扫描期间不改变该页的访问位。

(2)如果第(1)步失败，即没有找到a类页，则重新开始第二轮扫描。在第二轮扫描期间，寻找第一个b类页，即访问位为0，修改位为1，遇到的第一个b类页为选定的淘汰页。在第二轮扫描期间，将所经过的每一页的访问位都置为0。

(3)如果第(2)步也失败，即没有找到b类页，则将指针返回初始位置，且将环型链表中所有页面的访问位清0;然后，返回第(1)步，继续执行。此时，一定能够找到被淘汰的页。

改进的时钟算法在执行过程中，循环扫描环型链表中所有页，优先淘汰的页是最近没有被访问过且没有被修改过的页。它的优点在于，在满足局部性原则的基础上，选择出的淘汰页不必对交换区和相应的文件进行修改。如果第一轮没有找到淘汰页，进入第二轮寻找。在第二轮寻找的过程中，按照局部性原则，选择出的淘汰页属于最近没有被访问的页。如果第二轮也没有找到淘汰页，就把环型链表中的所有页的访问位都清0，然后，返回第(1)步，循环上述过程，肯定能够找到要淘汰的页［10］。

改进的时钟算法在算法的实现性能上比时钟置换算法有较好的改进。为了实现虚拟存储器管理技术，当进程访问的页不在主存时，系统需要将辅存的页面调入主存，从而需要启动I/O操作，而在这一活动中将要消耗近10%的CPU工作时间。置换算法的基本目的是力求减少I/O操作的次数和减少一次I/O操作的开销［11-12］。改进的时钟算法在出现缺页现象时，通过参考页表中访问位和修改位，减少了缺页时需要的I/O操作，从而减少了CPU机时的消耗，提高了CPU的工作效率。

驻留主存中页面所构成的环型链表及页面的所属类如图2所示［13］。按照改进的时钟算法，淘汰页的顺序依次为:1页、9页、4页、2页、3页、5页、6页、7页、8页、10页、0页。

图2 环型页面链表

4 时钟改进算法性能分析与测试

4.1 算法性能分析

当发生缺页中断时，首先要从辅存读入该页，然后再进行内存存取。有效的页面存取时间［6］可以表示为:

有效的页面存取时间=(1-p)×m+p×缺页处理时间

其中:p代表缺页中断概率;m代表内存存取时间。

在任何情况下，缺页中断处理所花费的时间基本上由3部分组成:

(1)处理缺页中断的时间;

(2)从辅存调入该页的时间;

(3)重新启动该进程的时间。

操作系统可以通过代码的设计使第(1)、(3)项的执行时间控制在1～100 μs，而在第(2)项花费的时间将近25 ms。从辅存调入该页的时间，即启动一次I/O操作的时间直接影响着缺页处理时间，并与有效的页面存取时间成正比关系。

改进的时钟算法在实现页面置换的过程中，优先淘汰的页面是主存中访问位和修改位为0的页面，选择这样的页面优先淘汰既遵循了局部性原则，又避免了对辅存相应的页面进行修改，所以可以避免启动I/O操作;其次选择的淘汰页面为访问位为0、修改位为1的页面，这样的页面选择遵循了局部性原则，从而避免了刚刚淘汰的页又要被访问，需要启动I/O操作，减少了进程在运行过程中消耗在缺页处理的时间。这样缩短了有效的页面存取时间，提高了系统的性能。

4.2 算法的性能测试

驻留主存页面及页面访问属性如图2所示。假设出现5次缺页中断，需要进行5次淘汰页面的情况下:

(1)采用时钟算法。选择出的淘汰页面依次为:1页、2页、3页、4页和5页。由于2页、3页和5页的访问位均为1，属于最近刚刚访问的页面，根据局部性原则，短时间还要访问的可能性很大，这样又需要从辅存调入主存，则需要启动3次I/O操作。

(2)采用改进的时钟算法。选择出的淘汰页面依次为:1页、9页、4页、2页和3页。与时钟算法相比，不需要淘汰第5页，增加了第9页，而第9页属于a类页，既满足了局部性原则，又不需要对辅存相应的页面进行修改，这样相对于时钟算法，减少了1次I/O操作，同时辅存相应的页面不需要修改，也避免了1次I/O操作。

由以上分析可以说明，在淘汰页面的时候，改进的时钟算法相对于时钟算法，在产生的I/O操作次数和对辅存相应的页面进行修改的次数均有所减少，从而减少了系统在页面置换上的消耗，提高了系统的性能。

5 结束语

改进的时钟算法，延续了时钟算法的数据结构，充分利用了页表表项访问位和修改位，具有数据组织结构简单、明了，使用便利等优点;同时在优先考虑先来先服务的原则及遵循局部性原则的基础上，利用访问位和修改位的状态值，在主存空间出现缺页现象时，优先选择出淘汰页面，既避免了“抖动”现象，又可最大限度地减少系统淘汰页面带来的开销，从而提高了实现虚拟存储管理的性能。

［1］黄水松，黄干平，曾平，等.计算机操作系统［M］.武汉:武汉大学出版社，2003:156-158.

［2］曹先彬，陈香兰.操作系统原理与设计［M］.北京:机械工业出版社，2009:180-187.

［3］汤小丹，梁红兵，哲凤屏，等.计算机操作系统(第3版)［M］.西安:西安电子科技大学出版社，2007:153-154.

［4］徐宗元.操作系统(第2版)［M］.北京:高等教育出版社，2005:120.

［5］［美］Lubomir F Bic，Alan C Shaw.操作系统原理［M］.梁洪亮，等译.北京:清华大学出版社，2005:214-215.

［6］孟庆昌.操作系统［M］.北京:电子工业出版社，2004:186-187.

［7］谌卫军，王浩娟.操作系统［M］.北京:清华大学出版社，2012:115-117.

［8］许日滨，孙英华，程亮.操作系统［M］.北京:北京邮电大学出版社，2005:154-158.

［9］刘振鹏，王煜，张明.操作系统(第3版)［M］.北京:中国铁道出版社，2007:174-175.

［10］［美］William Stallings.操作系统:精髓与设计原理［M］.陈向群，陈渝译.北京:机械工业出版社，2010:248-249.

［11］李占胜，毕会娟，李艳平，等.一种对LRFU置换策略的自适应改进［J］.计算机工程与应用，2008，44(17):153-157.

［12］魏文国，赵慧民，庄林凯，等.一种基于时钟自适应的改进缓存替换算法［J］.中山大学学报:自然科学版，2012，51(6):54-57，62.

［13］［荷］Andrew S Tanenbaum.现代操作系统(第3版)［M］.陈向群，马洪兵译.北京:机械工业出版，2009:120-121.

［14］刘智臣，孟益民，余俊杰.一种时钟改进算法的分析与实现［J］.计算机工程，2006，32(14):63-65.