OS页面置换算法模拟实现

计算机操作系统

课程设计报告

院 系： 计算机与电子信息学院 专 业： 班 级：

设计题目： 页面置换算法的模拟 姓 名： 指导教师：

2011年 6月 16 日

页面置换算法的模拟实现

一、设计目的

本课程设计是学习完“操作系统原理”课程后进行的一次全面的综合训练， 通过请求页式管理方式中页面置换算法的模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理中的页面置换算法。

二、设计内容

（1）概述

在进程运行过程中，若其所要访问的页面不在内存所需把他们调入内存，但内存已无空闲时，为了保证进程能够正常运行，系统必须从内存中调入一页程序或数据送磁盘的对换区中。但应将那个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。置换算法的好坏，将直接影响到系统的性能。

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

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

1.先进先出（FIFO）算法

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

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

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

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

面，在最近一段时间内未被使用的时间最长，那么在最近的将来也可能不再被使用。

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

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

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

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

3．菜单选择模块。选择相应的页面的置换方式，选择相应的字母，进入相应的功能。

4．算法模块。选择相应的页面置换算法。 5．显现输出模块。显示页面被置换的情况。

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

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; while(i{if(efor( 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{if(page[t].num==p[j].num )break; else count++; }

return count; }

3. FIFO页面置换和缺页次数及缺页率模块实现如下： if(c=='1')//FIFO页面置换 {n=1; cout<<\"页面置换情况: \"<=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<<\"页面置换情况: \"<{ int k; k=t=Search(p[i].num,page); if(t>=0) page[t].time=0; else { n++; t=Max(page); page[t].num=p[i].num; page[t].time=0; } if(t==0){page[t+1].time++;page[t+2].time++;} if(t==1){page[2].time++;page[0].time++;} if(t==2){page[1].time++;page[0].time++;} if(k==-1) print(page); i++; } cout<<\"缺页次数：\"<5．OPT页面置换和缺页次数及缺页率模块实现如下（本代码在页面置换中： if(c=='3')//OPT页面置换 { n=1; while(i=0)i++; else { int temp=0,cn; for(t=0;t（4）结果及分析 4.1 测试方案

1. 测试方案(一)

输入可用页面为3，实际页数是20，各个页面号7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1（课本例题）选择实验要求FIFO页面置换，然后选择LRU算法。最后选择OPT（对比）。 2. 测试方案（二)

输入可用页面为3，实际页数是20，各个页面号1 0 7 1 0 2 1 2 2 3 0 3 4 0 3 0 2 1 0 7选择实验要求FIFO页面置换，然后选择LRU算法。最后选择OPT（对比1） 3.测试方案（三)

输入可用页面为4，实际页数是20，各个页面号7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1（课本例题）选择实验要求FIFO页面置换，然后选择LRU算法。最后选择OPT（对比）

4.2 测试结果

1. 测试方案（一)结果。

输入可用页面为3，实际页数是20，各个页面号7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 测试成功。见图（图4-1输入页面登陆与输入）选择FIFO页面置换时显示页面置换情况、缺页次数和缺页率（见图4-2 FIFO页面置换界面）。

图4-1输入页面登陆与输入

图4-2 FIFO页面置换界面

选择LRU页面置换时显示页面置换情况、缺页次数和缺页率（见图4-3 LRU页面置换界面）

图4-3 LRU页面置换界面

选择OPT页面置换时（对比）显示页面置换情况、缺页次数和缺页率（见图4-4OPT页面置换界面）

图4-4 3OPT页面置换界面

2. 测试方案（二)结果。输入可用页面为3，实际页数是20，各个页面号1 0 7 1 0 2 1 2 2 3 0 3 4 0 3 0 2 1 0 7 测试成功。见图（图4-5输入页面登陆与输入）选择FIFO页面置换时显示页面置换情况、缺页次数和缺页率（见图4-5 FIFO页面置换界面）

图4-5输入页面登陆与输入

选择LRU页面置换时显示页面置换情况、缺页次数和缺页率（见图4-6 LRU页面置换界面）

选择OPT页面置换时（对比）显示页面置换情况、缺页次数和缺页率（见图4-7OPT页面置换界面）

图4-6 LRU页面置换界面 图4-7OPT页面置换界面 3. 测试方案（三)结果。

输入可用页面为3，实际页数是20，各个页面号7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 测试成功。见图（图4-1输入页面登陆与输入）选择FIFO页面置换时显示页面置换情况、缺页次数和缺页率（见图4-8 FIFO页面置换界面）

图4-8 FIFO页面置换界面

选择LRU页面置换时显示页面置换情况、缺页次数和缺页率（见图4-9LRU页面置换界面）

选择OPT页面置换时（对比）显示页面置换情况、缺页次数和缺页率（见图4-10OPT页面置换界面）

图4-9LRU页面置换界面 图4-9LRU页面置换界面 4.3测试结果分析

从上述结果可知,在内存页面为3个页面时, 由于用户进程的所有指令基本上都没装入内存，只装入一小部分,从而算法之间的差别比较大。三种算法的访内命中率大致在45％至75％之间变化。但是,FIFO算法与OPT算法之间的差别一般在25个百分点左右。

比较上述三种算法,以OPT算法的命中率最高, LRU算法次之,其次是FIFO算法。

（5）设计小结

一开始选题的时候我并没有考虑太多，原以为题目难度都差不多，于是就选了个冷门的。但是没想到本题的难度和完成的代码量远远超出了我的预期。原以为本题看起来很简单，也就不过是一个随机数函数和三种算法实现而已，但是事实证明我彻彻底底的错了。

首先是随机数生成，来回看了好几遍都没弄懂生成方法，最后经同学指点一下才终于明白，然后就是页式管理的原理和页面置换算法等等，很多都忘记了，不得不再次打开课本。由于个人水平有限，光是理解原理及理清程序结构就已经花费了我很多宝贵的时间，加上本来时间就不充裕，于是我果断选择敏捷软件开发模型用于完成此课程设计。

依照软件工程原则，分析需求，画出程序结构图，将程序模块化，进行概要设计和详细设计，撰写实验报告同时编写程序代码，对编写完模块进行构件化处理，完善好接口，进行功能测试，不断发布可执行程序，然后组装、完善……历经了4个Beta版本之后，程序终于都大功告成了。

本次实验中体会最深刻的就是运用了构件化的方法来测试模块，否则面对如此可观的代码量，如果每次都是编写完一点功能或者编写完所有功能才进行测试，debug的话都不知道从哪儿找起了，特别对于编程水平不高的自己来说，这样做无疑是自掘坟墓，程序完成之日将遥遥无期。

总体来说，虽然题目难度远远超出自身预期，但是仍能凭借两个人奋斗完成，我们对于此次课程设计完成的质量以及自身的表现都感到十分的满意。

（6）课程设计代码： #include #define M 40 int N;

struct Pro//结构体 {

int num,time; };

int Input(int m,Pro p[M])//输入函数 {

cout<<\"请输入实际页数：\"; do {

cin>>m;

if(m>M)cout<<\"数目太多，请重试\"<while(1);

cout<cin>>p[i].num; p[i].time=0; }

return m; }

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

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

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

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

for(int i=0;iint Max(Pro *page1)//找出离现在时间最长的页面

{

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

int e=page[0].time,i=0; while(iif(efor( i=0;iint Compfu(Pro *page1,int i,int t,Pro p[M])//找到最久不使用的页面 {

Pro *page=new Pro[N]; page=page1; int count=0;

for(int j=i;jif(page[t].num==p[j].num )break; else count++; }

return count; }

int main() {

cout<<\"可用内存页面数\"<>N; Pro p[M];

Pro *page=new Pro[N]; char c;

int m=0,t=0; float n=0; m=Input(m,p); do{

for(int i=0;ipage[i].num=0; page[i].time=2-i; } i=0;

cout<<\"f:FIFO页面置换\"<cout<<\"按其它键结束\"<>c;

if(c=='f')//FIFO页面置换 { n=1;

cout<<\"页面置换情况: \"<if(Search(p[i].num,page)>=0)i++;//找到相同的页面 else {

if(t==N)t=0; else { n++;//

page[t].num=p[i].num; print(page); t++; } } }

cout<<\"缺页次数：\"<if(c=='l')//LRU页面置换 { n=1;

cout<<\"页面置换情况: \"<k=t=Search(p[i].num,page); if(t>=0)

page[t].time=0; else { n++;

t=Max(page);

page[t].num=p[i].num; page[t].time=0; }

if(t==0){page[t+1].time++;page[t+2].time++;} if(t==1){page[2].time++;page[0].time++;} if(t==2){page[1].time++;page[0].time++;} if(k==-1) print(page); i++;

}

cout<<\"缺页次数：\"<if(c=='o')//OPT页面置换 { n=1;

while(iif(Search(p[i].num,page)>=0)i++; else {

int temp=0,cn; for(t=0;tif(temptemp=Compfu(page,i,t,p); cn=t; } }

page[cn]=p[i]; n++;

print(page); i++; } }

cout<<\"缺页次数：\"<}while(c=='f'||c=='l'||c=='o'); return 0; }

（7）参考文献

1.严蔚敏，吴伟民，数据结构，清华大学出版社，1997.4

2.张尧学，史美林，计算机操作系统教程，清华大学出版社，2000.8 3.孙静宇，计算机操作系统课程设计指导书，太原理工出版社， 2006.4

4. 汤子瀛，哲凤屏，汤小丹，计算机操作系统，西安电子科技大