中南大学 计算机操作系统实验报告

计算机操作系统 实验设计报告

学生姓名 学 号 专业班级 指导教师 胡小龙

学 院 信息科学与工程学院 完成时间 2014年5月

页面置换算法的模拟实现

一、设计目的

1、 增强学生对计算机操作系统基本原理、基本理论、基本算法的理解。 2、 提高和培养学生的动手能力。

二、设计内容

（一）概述

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。但应将那个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。置换算法的好坏，将直接影响到系统的性能。

一个好的页面置换算法，应具有较低的页面更换频率。从理论上将讲，应将那些以后不再访问的页面换出，或把那些较长时间内不再访问的页面调出。目前存在着不同的算法，他们都试图更接近与理论上的目标。

拥有页面交换机制的操作系统总是把当前进程中急需处理的部分页面换入到内存当中，而把更多暂时不需要处理的页面放置在外存当中。由于进程需要处理的页面顺序不同，因此必须要在内存与外存之间进行页面交换，页面置换算法也就应运而生。

（二）设计原理

1.先进先出（FIFO）算法

这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存停留时间最久的给予淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替代指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在incheng中，有些页面经常被访问，比如，含有全局变量，常用函数，例程等方面，FIFO

算法并不能保证这些页面不被淘汰。当需要选择一个页面淘汰时，总是选择最先进入内存空间的那一个页面。只要在系统中建立一个FIFO队列，以反映页面的活动情况。被选择的页面总是处于队首的页面，而最近调入的页面永远存放在队列的尾部。

2.最近最久未使用（LRU）算法

FIFO置换算法的性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后不能反映页面的使用情况。最近最久未使用（LRU）的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各个页面将来的使用情况，只能利用“最近的过去”，作为“最近的将来”的近似。该算法的基本思想是用最近的过去估计最近的将来。假定在内存中的某个页面，在最近一段时间内未被使用的时间最长，那么在最

1

近的将来也可能不再被使用。

3.理想页面置换（OPT）算法

最佳置换算法由Belady于1966年提出，这是一种理想情况下的页面置换算法，但实际上不可能实现。但人们目前把还无法预知一个进程在内的若干页面中，哪一个页面是未来最长时间内不再被访问，因而该算法无法实现。基本思想是内存中每个页都用该页面首次被访问前所要执行的指令数进行标记，标记最大的页应该被置换。

（三）详细设计及编码 1.模块设计

1． 进入系统模块。进入登陆界面，输入内存页面数和实际页数 2． 页面号打印模块。打印输入的页面号。

3． 菜单选择模块。选择相应的页面的置换方式，选择相应的字母，进入相应的功能。 4． 算法模块。选择相应的页面置换算法。 5． 显现输出模块。显示页面被置换的情况。

6． 缺页次数和缺页率模块。计算页面号输入的计算结果。 7． 退出系统模块。退出置换页面。

2.系统详细设计

（1）系统主界面设计（包含登陆模块设计）

首先贯穿全局的全局需要一系列的函数来实现本操作系统的各种功能。需要函数自带

的文件stdafx.h 和iostream.h 首先输入的页数自定义最大值为40程序用#define M 40实现。为了防止输入的页数太多，超出自定义40个数的范围，通过输入函数实现：int Input(int m,Pro p[M]) //输入函数。

（2）系统模块。

首先通过打印当前的页面

void print(Pro *page1) //打印当前的页面 {

Pro *page=new Pro[N]; page=page1;

for(int i=0;i

查找内存中是否存在要调入的页面 int Search(int e,Pro *page1 ) { Pro *page=new Pro[N]; page=page1; for(int i=0;i

找出离现在时间最长的页面 int Max(Pro *page1) { Pro *page=new Pro[N]; page=page1; int e=page[0].time,i=0;

2

while(i

for( i=0;i

找到最久不使用的页面

int Compfu(Pro *page1,int i,int t,Pro p[M]) { Pro *page=new Pro[N]; page=page1; int count=0; for(int j=i;j

（3） FIFO页面置换和缺页次数及缺页率模块实现如下：

if(c=='1')//FIFO页面置换 {n=1; cout<<\页面置换情况: \ while(i=0)i++;//找到相同的页面 else { if(t==N)t=0; else { n++; page[t].num=p[i].num; print(page); t++; } } } cout<<\缺页次数：\ 缺页率：\ }

（4）LRU页面置换和缺页次数及缺页率模块实现如下：

if(c=='2')//LRU页面置换 { n=1; cout<<\页面置换情况: \ while(i=0)

3