页面置换算法的模拟实现二

1、页面置换算法的模拟实现二专业班级：计算机学生姓名：张三学 号：指导教师：日 期：目录一、设计目的2二、设计题目22.1 设计内容22.2 设计要求2三、相关知识 2四、设计过程34.1 OPT （最佳置换算法） 34.2 LFU 4五、设计思想5六、完整代码5七、实验结果 12八、总结 .14九、参考文献 14一、设计目的操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。 操作系统质量的好坏， 直接影响整个计算机系统的性能和用户对计算机的使用。 一个精心设计的操作系统能极大地扩充计算机系统的功能， 充分发挥系统中各种设备的使用效率， 提高系统工作的可靠性。 由于操

2、作系统涉及计算机系统中各种软硬件资源的管理， 内容比较繁琐， 具有很强的实践性。 要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果。进一步巩固和复习操作系统的基础知识。培养学生结构化程序、模块化程序设计的方法和能力。提高学生调试程序的技巧和软件设计的能力。提高学生分析问题、解决问题以及综合利用 C 语言进行程序设计的能力。二、设计题目 ： 页面置换算法模拟程序2.1 设计内容根据设计要求实现对页面置换算法的模拟2.2 设计要求设计一个虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程，并计算访问命中率。用 C 语言实现，要求设计主界面以灵活选择某算法，且以下算法都要实现1

3、. 最佳淘汰算法（OPT）2. 最少访问页面算法（ LFU ）三相关知识：2.1 虚拟存储器的引入：局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域， 它主要表现在以下两个方面： 时间局限性和 空间局限性。2.2 虚拟存储器的定义：虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。2.3 虚拟存储器的实现方式：分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。四.设

4、计过程4.1 OPT （最佳置换算法）设计原理：需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现在最远的页面换出。流程图4.2 LFU页面置换算法结束五设计思想：选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：OPT 基本思想：是用一维数组 pagepSIZE 存储页面号序列， memerymSIZE 是存储装入物理块中的页面。数组nextmSIZE 记录物理块中对应页面的最后访问时间。每当发生缺页时， 就从物理块中找出最后访问时间最大的页面， 调出该页， 换入所缺的页面。【特别声明】若物理块中的页面都不再使用，则每次都置换物理块中第一个位置的页面。LFU 基本思

5、想：LFU 即最不经常使用页置换算法，要求在页置换时置换引用计数最小的页，因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多， 但以后就不再使用， 这类页将会长时间留在内存中， 因此可以将引用计数寄存器定时右移一位，形成指数衰减的平均使用次数。六完整代码#include #include #include /*全局变量 */int queye=0;/记录缺页次数int mSIZE; /* 物理块数 */int pSIZE; /*页面号引用串个数*/static int memery10=0; /* 物理块中的页号*/static int page100=0; /* 页面号

6、引用串 */static int temp10010; /*辅助数组 */* 载入数据 */void download（）printf（nFinish.n 载入成功，按任意键进入置换算法选择界面： ）;getch（）;/* 显示设计者信息*/void designBy（）printf（ 课题：页面置换算法n）;printf（ 学号： 20111202075n）;printf（姓名：周涛n）;void begin()for(int i=0;i100;i+)for(int j=0;j10;j+)memeryj=-1;tempij=-1;void print(unsigned int t)int i

7、,j,p;for(p=0;ppSIZE;p+)printf(%d ,pagep);printf(n);for(j=0;jmSIZE;j+)for(i=0;ipSIZE;i+)if(tempij=-1)printf( );elseprintf(|%d| ,tempij);printf(n);printf(n);printf( 缺页次数： %dtt,queye);printf(缺页率：d/%dn,queye,pSIZE);printf(置换次数：dtt,t);printf(访问命中率：d%n”,(pSIZE-queye)*100/pSIZE);printf(n);/* 最佳置换算法*/void O

8、PT()begin();queye=0;int next10=0; /* 记录下一次访问时间 */int i,j,l,m;int t=-1,n=-1;int max; /* 记录换出页*/int count=0; /*记录置换次数*/for(i=0; ipSIZE;i+)for(j=0;jmSIZE;j+)/ 找到一个空闲物理块,找到后跳出循环if(memeryj=-1)t=j;break;for(j=0;jmSIZE;j+)/ 找到进程相同标号if(memeryj=pagei)/ 找到相同物理块，n=j;次访if(t=-1)/ 说明没有空闲物理块找到 /*得到物理快中各页下一次访*/for(

9、m=0;mmSIZE;m+)for(l=i+1;l=next1?0:1; for(m=2;mnextmax) max=m;if(n=-1)/ 没有相同物理块if(t!=-1)/ 而且有空闲物理块memeryt=pagei;t=-1;for(j=0;jmSIZE;j+) tempij=memeryj; queye+;else/般有空闲物理块memerymax=pagei; count+;for(j=0;jmSIZE;j+) tempij=memeryj; queye+;else/相同物理块n=-1;print(count);函数分界线/*/*void LFU() begin();queye=0;

10、int flag10=0; /* 记录页面的访问次数*/int i,j,m;int t=-1,n=-1;int min;int count=0; /*记录置换次数*/for(i=0;ipSIZE;i+) for(j=0;jmSIZE;j+)/ 找到一个空闲物理块,找到后跳出循环if(memeryj=-1)t=j;break;for(j=0;jmSIZE;j+)/ 找到进程相同标号if(memeryj=pagei)/ 找到相同物理块，n=j;flagj+;if(t=-1)/ 说明没有空闲物理块找到min=flag0flag1?1:0;for(m=2;mflagm) min=m;if(n=-1)i

11、f(t!=-1)/ 而且有空闲物理块memeryt=pagei;t=-1;for(j=0;jmSIZE;j+) tempij=memeryj; queye+;elsememerymin=pagei; count+;for(j=0;j);getch();system(cls);/system(color 0B);do printf( 请输入物理块的个数(M10|mSIZE0)printf( 输出错误 ! 请重新输入 n);flag1=1;while(flag1=1);do printf( 请输入页面号引用串的个数(P=100)： );scanf(%d,&pSIZE);flag2=0;if(pSI

12、ZE100)printf( 输出错误 ! 请重新输入n);flag2=1;while(flag2=1);printf(请依次输入页面号引用用n);for(i=0;ipSIZE;i+)scanf(%1d,&pagei);download();system(cls);/system(color 0E);doputs(输入的页面号引用用为：);for(k=0;k);getch();system(cls);while (code!=4);getch();七 . 实验结果运行环境 Visual C+ 6.01. 按任意键进行初始化：2. 载入数据：3. 进入置换算法选择界面：八 总结通过这次课程设计，不仅让我了解了两种页面置换算法，即 OPT（最佳置换）算法、LFU （最不经常使用）算法。同时使我对操作系统这门课程有了更深入的研究、对很多重要的概念有了巩固和掌握。通过努力， 两个页面置换算法程序都已经完成。 让我们不但对专业知识有了更深的理解，