操作系统实验指导书2013(梁宝华)

实验三 页面置换算法

一、实验目的

通过该题目的设计过程，熟悉页面置换算法及其实现，掌握常用页面置换算法的原理、软件开发方法并提高解决实际问题的能力。页面置换算法是虚拟存储管理实现的关键，通过本次设计理解内存页面调度的机制，在模拟实现FIFO、LRU和OPT几种经典页面置换算法的虚拟基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。

二、实验内容与要求

编写程序实现对3个页面置换算法的模拟，要求至少采用两种不同的置换算法分别进行模拟。

三、实验平台

操作系统：Windows XP 编译器： VC6.0

四、实验方法原理及设计方案 原理：

在请求分页存储管理中，如果被访问的页不在内存中，则产生缺页中断，操作系统进行中断处理，在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送到磁盘的对换区中。但应将那个页面调出，所以需要根据一定的算法来确定。使用三种算法计算访问命中率。 (1).FIFO（先进先出）

设计原理：该算法总是淘汰最先进入内存的页面，即选择在内存中停留时间最长的一页予以淘汰。流程图如图3-1。 (2).LRU（最近最久未使用）

设计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问，或者反过来说如果某页很长时间未被访问，则它在最近一段时间也不会被访问。该算法赋予每个页面一个访问字段，用来记录该页面上一次被访问以来所经历的时间t，当必须淘汰一个页面时，LRU算法选择现有页面中t值最大的那个页面。流程图如图3-2。 (3).OPT（最佳淘汰算法）

设计原理：需要进行页面置换，其选择的被淘汰页面将是以后永不使用，或者是最长（未来）时间内不再被访问的页面。采用最佳淘汰算法，通常可以保证获得最低的缺页率。流程图如图3-3。

16

图3-1 FIFO置换算法流程图

17

图3-2 LRU页面置换算法流程图

18

图3-3 OPT页面置换算法流程图

总体设计方案

1.总体设计流程图：

19