几种页面置换算法的基本原理及实现方法

黄凤艳

（赤峰学院计算机科学与技术系，内蒙古赤峰024000）

几种页面置换算法的基本原理及实现方法

黄凤艳

（赤峰学院计算机科学与技术系，内蒙古赤峰024000）

本文介绍了计算机专业研究生考试中操作系统考研大纲要求的四种全局页面置换算法的基本原理及实现方法.

页面；置换算法；基本原理；实现方法

在多道程序的正常运行过程中，属于不同进程的页面被分散存放在主存页框中，当正在运行的进程所访问的页面不在内存时，系统会发生缺页中断，在缺页中断服务程序中会将所缺的页面调入内存，如内存已无空闲页框，缺页中断服务程序就会调用页面置换算法，页面置换算法的目的就是选出一个被淘汰的页面.把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中.因此，置换算法应该置换那些被访问概率最低的页，将它们移出内存.

1 最佳置换算法

基本原理：淘汰以后不再需要的或最远的将来才会用到的页面.这是1966年Belady提出的理想算法，但无法实现，主要用于评价其他置换算法.

例：分配给某进程的内存页面数是3页，页面地址流如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，其内存动态分配过程如下：

70120304230321201 77722222222222222 0000004440000000 111333333331111

2 先进先出置换算法

基本原理：总是选择在内存驻留时间最长的一页面将其淘汰.

实现方法：建立一个队列，队列长度为系统分配给该进程的内存页面数.如果所访问的页面不在内存中：当内存有空闲时，将访问的页面号；当内存没有空闲时，淘汰队首页面，将访问的页面号插入队尾.如果所访问的页面在内存中则队列无变化.

例：分配给某进程的内存页面数是3页，页面地址流如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1.

队列变化如下所示：

3 最近最少使用置换算法

基本原理：淘汰的页面是在最近一段时间内最久未被访问的那一页，它是基于程序局部性原理来考虑的，认为那些刚被使用过的页面可能还要立即被使用，而那些在较长时间内未被使用的页面可能不会立即被使用.

实现方法：建立一个堆栈，堆栈的容量为系统分配给该进程的内存页面数.当正在运行的进程访问某页面时，如该页面不在内存时，则判断内存是否已无空闲页框：①尚有空闲页框，则将访问的页面入栈.②无空闲页框，则淘汰栈底的页面，然后将访问的页面入栈；如访问的页面在内存中，则直接将它提到栈顶.

例：分配给某进程的内存页面数是3页，页面地址流如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1.

堆栈变化如下所示：

4 时钟页面置换算法

基本原理：把进程已调入内存的页面链接成循环队列，形成类似于钟表面的环形表，用指针指向循环队列中下一个将被替换的页面.

实现方法：

①一个页面首次装入内存时，其“引用位”置0；

②内存中的任何一个页面被访问时，其“引用位”置1；

③淘汰页面时，存储管理从指针当前指向的页面开始扫描循环队列，把所遇到的“引用位”是1的页面的“引用位”清0，并跳过这个页面；把所遇到的“引用位”是0的页面淘汰，指针推进一步；

④扫描循环队列时，如果遇到所有页面的“引用位”均为1，指针就会环绕整个循环队列一圈，把碰到的所有页面的“引用位”清0；指针停在起始位置，并淘汰这一页，然后指针推进一步.

例：分配给某进程的内存页面数是3页，页面地址流如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1.

注：有星号的页面表示其引用位为1，否则为0，“→”表示指针的当前位置.

内存动态分配过程如下：

70120304230321201 77722224444333300 0000000222221111 111333330000222

〔1〕孙钟秀.操作系统教程(第4版)[M].高等教育出版社, 2008.

〔2〕张尧学,史美林,张高.计算机操作系统教程(第3版)[M].清华大学出版社，2006.

TP316.7

A

1673-260X（2010）11-0018-02