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

黄凤艳

（赤峰学院计算机科学与技术系，内蒙古赤峰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 先进先出置换算法

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

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