操作系统 七次实验报告 常用页面置换算法模拟实验.doc

操作系统课程第七次实验报告姓名学号系计算机任课教师贺辉指导教师贺辉评阅教师贺辉实验地点 综合楼B102 实验时间2012-9-26实验课表现出勤和个人表现Q1(15+15（组长评分）=30分)得分：实验总分(Q1+Q2+Q3+Q4)实验完成情况Q2(45分(组长与教师评分的加权平均)得分：实验编号与实验名称：实验七、常用页面置换算法模拟实验实验目的：通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。实验内容及要求（详见实验讲义与实验指导书）：要求：1）要求用你熟悉的程序设计语言编写和调试一个页面置换模拟程序；要求在主函数中测试。2）实验报告中必须包括：设计思想、数据定义（包括详细说明）、处理流程（详细算法描述和算法流程图）、源代码、运行结果、体会等部分。3）必须模拟本实验内容中提到的算法中的至少2种页面置换算法。4） 比较不同页面置换算法的效率内容：编写一个程序，使用以下页面置换算法中的某2种分别模拟一个分页系统，并统计同一个页面访问序列情况下不同页面置换算法引发的缺页中断次数。1、第二次机会算法（Second Chance）2、最近最少使用算法（Least Recently Used，LRU ）3、最不常用算法（Not Frequently Used，NFU）4、最近未使用算法（Not Recently Used ，NRU）5、时钟页面置换算法6、老化算法（aging）页框的数量固定为4，虚拟页面数为8。实验输入为访问页面序列，比如0，1 ，3 ，2，7，1实验用到的软件（：）DevC+,Visio实验内容及关键步骤（代码）Q3（15分）得分：流程图：输入页面访问序列取访问的页号查页表是否缺页？是置缺页标志flag为*按算法不同淘汰一页面调入所访问的页面否FIFO算法流程图 LRU算法流程图：函数关系解释图：实现结果：图1图2代码：#include <stdio.h>#include <stdlib.h>#define MEMORY_SIZE 4 /*物理块数*/#define PROESS_SIZE 8 /*页面号引用串个数*/#include <stdio.h>#include <stdlib.h>/*全局变量*/int mSIZE=4;int pSIZE=8;static int memery4=0; /*物理块中的页号*/static int page8=0; /*页面号引用串*/static int temp84=0; /*辅助数组*/*置换算法函数*/void FIFO();void LRU();void OPT();void designBy();/*辅助函数*/void print(unsigned int t);/*主函数*/int main() int i,k,code; designBy(); system("color 0A");puts("请依次输入页面号(8个)：");for(i=0;i<pSIZE;i+) scanf("%1d",&pagei);system("cls");system("color 0E"); do puts("输入的页面号引用串为：");for(k=0;k<=(pSIZE-1)/20;k+)for(i=20*k;(i<pSIZE)&&(i<20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1)printf("%dn",pagei);elseprintf("%d ",pagei);printf("* * * * * * * * * * * * * * * * * * * * * * *n"); printf("* 请选择页面置换算法：ttt *n");printf("* - *n"); printf("* 1.先进先出(FIFO) 2.最近最久未使用(LRU) *n");printf("* 3.退出 *n");printf("* * * * * * * * * * * * * * * * * * * * * * *n"); printf("请选择操作： bb"); scanf("%d",&code); switch(code) case 1: FIFO(); break; case 2: LRU(); break; case 3:system("cls");system("color 0A"); exit(0);default:printf("输入错误，请重新输入："); printf("按任意键重新选择置换算法：>>>");getch();system("cls"); while (code!=3);getch();void print(unsigned int t)int i,j,k,l;int flag;for(k=0;k<=(pSIZE-1)/20;k+)for(i=20*k;(i<pSIZE)&&(i<20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1)printf("%dn",pagei);elseprintf("%d ",pagei);for(j=0;j<mSIZE;j+)for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i+)if(i>=j)printf(" |%d|",tempij);elseprintf(" | |");for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1);i+)for(flag=0,l=0;l<mSIZE;l+)if(tempil=tempi-1l)flag+;if(flag=mSIZE)/*页面在物理块中*/printf(" ");elseprintf(" |%d|",tempij);/*每行显示20个*/if(i%20=0)continue;printf("n");printf("-n");printf("缺页次数：%dtt",t+mSIZE);printf("缺页率：%d/%dn",t+mSIZE,pSIZE);printf("置换次数：%dtt",t);printf("访问命中率：%d%n",(pSIZE-(t+mSIZE)*100/pSIZE);printf("-n");/*先进先出页面置换算法*/void FIFO() int memery10=0; int time10=0; /*记录进入物理块的时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; timei=i; for(j=0;j<mSIZE;j+)tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理块中*/ count+;/*计算换出页*/ max=time0<time1?0:1;for(m=2;m<mSIZE;m+)if(timem<timemax)max=m; memerymax=pagei; timemax=i; /*记录该页进入物理块的时间*/ for(j=0;j<mSIZE;j+)tempij=memeryj; else for(j=0;j<mSIZE;j+)tempij=memeryj; print(count);/*最近最久未使用置换算法*/void LRU() int memery10=0; int flag10=0; /*记录页面的访问时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; flagi=i; for(j=0;j<mSIZE;j+)tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; else flagj=i; /*刷新该页的访问时间*/ if(k=mSIZE) /*如果不在物理块中*/ count+;/*计算换出页*/ max=flag0<flag1?0:1;for(m=2;m<mSIZE;m+)if(flagm<flagmax)max=m; memerymax=pagei; flagmax=i; /*记录该页的访问时间*/ for(j=0;j<mSIZE;j+)tempij=memeryj; else for(j=0;j<mSIZE;j+)tempij=memeryj; /compute();print(count);/*显示设计者信息*/ void designBy()printf("n");printf(" 实验七：页面置换算法 n");printf(" 学号：1001010042 n");printf(" 姓名：黄浩全 <Dev-C+ 4.9.9.0>n");printf("n");实验过程中遇到的问题解决办法与实验体会Q4（需手写，10分）得分：1、在FIFO算法可以很容易用数组实现，而LRU算法可以用数组实现，不过用结构体会更明显简单。结构体成员变量可以记录页号进入的时间，和最近使用的记录。相对比数组更容易理解和实现。2:首先，FIFO（先进先出）算法和LRU（最近未使用算法）两者之间，FIFO算法明显会比LRU容易理解，而且比LRU算法较容易实现，但在性能方面，LRU的确在优化方面做的比较理想。再且在考虑页框和页表号之间的问题用代码可以容易模拟，但是真是在物理内存块中是如何实现，那确实是很难以理解，需要真正理解到内存内部的知识才知道这两个算法是怎么实现的。评阅教师特殊评语：评阅教师： 日 期：