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

操作系统课程第七次实验报告姓名学号系计算机任课教师贺辉指导教师贺辉评阅教师贺辉实验地点综合楼B102实验时间2012-9-26实验课表现出勤和个人表现Q1（15+15（组长评分）=30分）得分：实验总分(Q1+Q2+Q3+Q4)实验完成情况Q2（45分（组长与教师评分的加权平均））得分：实验编号与实验名称：面实验目的：通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。实验内容及要求（详见实验讲义与实验指导书）：要求:1）要求用你熟悉的程序设计语言编写和调试一个页面置换模拟程序；要求在主函数中测试。2）实验报告中必须包括：设计思想、数据定义（包括详细说明）、处理流程（详细算法描述和算法流程图）、源代码、运行结果、体会等部分。3）必须模拟本实验内容中提到的算法中的至少2种页面置换算法。4）比较不同页面置换算法的效率内容：编写一个程序，使用以下页面置换算法中的某2种分别模拟一个分页系统，并统计同一个页面访问序列情况下不同页面置换算法引发的缺页中断次数。1、第二次机会算法（SecondChance）2、最近最少使用算法（LeastRecentlyUsed，LRU）3、最不常用算法（NotFrequentlyUsed，NFU）4、最近未使用算法（NotRecentlyUsed，NRU）5、时钟页面置换算法6、老化算法（aging）页框的数量固定为4,虚拟页面数为8。实验输入为访问页面序列，比如0，1，3，2,7，1

0111现22回图1©Main()<用FIFO算法实现LRU退出EXIT()FIFO()实现结果:姓名：黄浩全printf(”|printf(”卜匚作者信息显示请依次输入页面号®50111现22回图1©Main()<用FIFO算法实现LRU退出EXIT()FIFO()实现结果:姓名：黄浩全printf(”|printf(”卜匚作者信息显示请依次输入页面号®5(1234567designBy()用LRU算法实I"八5EditSearchViewProjectExecuteDebugToolsCVSWindow旦elp匚主函数，入口/換作至纟.；122222222222222222217218219PRINT()-"■■■.］显示内存页框每次置换结果盹igj壮铝昼仁羔話=*匸<Dev-C++4-9-9.0〉|\nr,);1\nr,);实验七：页面置换算法学号：1001010042姓名：黄浩全<Deu-C+*4.9.9.0>回图2回;bug87567867缺贝率:8/8访冋命中率：0Z1&©旦|「"hq煙名=苦浩卒ViewProjecttxecuteL>ebugJ_oolsCVSWindowHelp独阉昌＜Y—;<Dev-C++4回图2回;bug87567867缺贝率:8/8访冋命中率：0Z1&©旦|「"hq煙名=苦浩卒ViewProjecttxecuteL>ebugJ_oolsCVSWindowHelp独阉昌＜Y—;<Dev-C++4.9.9.0代码:/*物理块数*/按任意键重新选择置换算法：pzintf|printf(ri卜1•先进先岀＜FIFO＞3■退岀［请选择操作="I4：1:：1!2!!2：3:：3::：4输人.的页面号引用串为「12345678*2•最近最久未使用<LRU>**************1-占进先出<r'ro>3-iLLJ?arthViewProjectEKe-cute-D^e-buleaIsCVSWindowHelp#includevstdio・h>#includevstdlib・h>#defineMEMORYSIZE4操作系纟122222222222222222217218219220printf(STprintf("-■C:\Users\Administrator\Desktop'擇作蔡统实验七亡请选择页面直换算法’2-龄近最戈未使用4刖八4肓迤莘操怕“]#definePROESS_SIZE8/*页面号引用串个数*/#includevstdio.h>#includevstdlib.h>/*全局变量*/intmSIZE=4;intpSIZE=8;staticintmemery[4]={0};/*物理块中的页号*/staticintpage[8]={0};/*页面号引用串*/staticinttemp[8][4]={0};/*辅助数组*//*置换算法函数*/voidFIFO();voidLRU();voidOPT();voiddesignBy();/*辅助函数*/voidprint(unsignedintt);/*主函数*/intmain(){inti,k,code;designBy();system("color0A");puts("请依次输入页面号(8个)：");for(i=O;ivpSIZE;i++)scanf("%ld",&page[i]);system("cls");system("color0E");do{puts("输入的页面号引用串为：");for(k=0;kv=(pSIZE-1)/20;k++){for(i=20*k;(ivpSIZE)&&(iv20*(k+1));i++){if(((i+1)%20==0)ll(((i+1)%20)&&(i==pSIZE-1)))printf("%d\n",page[i]);elseprintf("%d",page[i]);}}*\n");printf("*\n");printf（"*请选择页面置换算法：\t\t\t*\n"）;printf("**\n");printf("*1.先进先出(FIFO)2.最近最久未使用(LRU)*\n");printf("*3.退出*\n");printf("***********************\n")；printf("请选择操作：[]\b\b");scanf("%d",&code);switch(code){case1:FIFO();break;case2:LRU();break;case3:system("cls");system("color0A");exit(O);default:printf("输入错误，请重新输入：”)；}printf("按任意键重新选择置换算法：>>>");getch();system("cls");}while(code!=3);getch();}voidprint(unsignedintt){inti,j,k,l;intflag;for(k=0;kv=(pSIZE-l)/20;k++){for(i=20*k;(ivpSIZE)&&(iv20*(k+1));i++){if(((i+1)%20==0)ll(((i+1)%20)&&(i==pSIZE-1)))printf("%d\n",page[i]);elseprintf("%d",page[i]);}for(j=0;j<mSIZE;j++){for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i++){if(i>=j)printf("|%d|",temp[i][j]);elseprintf(“II");}for(i=mSIZE+20*k;(ivpSIZE)&&(iv20*(k+l));i++){for(flag=0,l=0;l<mSIZE;l++)if(temp[i][l]==temp[i-1][l])flag++;if(flag=mSIZE)/*页面在物理块中*/printf("");elseprintf("|%d|",temp[i][j]);}一/*每行显示20个*/if(i%20==0)continue;printf("\n");}}printf("\n");printf("缺页次数：％d\t\t",t+mSIZE);printf("缺页率：％d/%d\n",t+mSIZE,pSIZE);printf("置换次数：%d\t\t",t);printf("访问命中率：％d%%\n",(pSIZE-(t+mSIZE))*100/pSIZE);printf("\n");}/*先进先出页面置换算法*/voidFIFO(){intmemery[10]={0};inttime[10]={0};/*记录进入物理块的时间*/inti,j,k,m;intmax=0;/*记录换出页*/intcount=0;/*记录置换次数*//*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];time[i]=i;for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){/*判断新页面号是否在物理块中*/for(j=0,k=0;jvmSIZE;j++){if(memery[j]!=page[i])k++;}if(k==mSIZE)/*如果不在物理块中*/{count++;/*计算换出页*/max=time[O]vtime[l]?O:l;for(m=2;mvmSIZE;m++)if(time[m]<time[max])max=m;memery[max]=page[i];time[max]=i;/*记录该页进入物理块的时间*/for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}else{for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}}print(count);}/*最近最久未使用置换算法*/voidLRU(){intmemery[10]={0};intflag[10]={0};/*记录页面的访问时间*/inti,j,k,m;intmax=0;/*记录换出页*/intcount=0;/*记录置换次数*//*前mSIZE个数直接放入*/for(i=O;ivmSIZE;i++){memery[i]=page[i];flag[i]=i;for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}for(i=mSIZE;ivpSIZE;i++)/*判断新页面号是否在物理块中*/for(j=0,k=0;jvmSIZE;j++){if(memery[j]!=page[i])k++;elseflag[j]=i;/*刷新该页的访问时间*/}if(k==mSIZE)/*如果不在物理块中*/{count++;/*计算换出页*/max=flag[O]vflag[l]?O:l;for(m=2;mvmSIZE;m++)if(flag[m]<flag[max])max=m;memery[max]=page[i];flag[max]=i;/*记录该页的访问时间*/for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}else{for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}}//compute。；print(count);}/*显示设计者信息*/voiddesignBy(){printf("|1\n");printf("|㊣实验七：页面置换算法㊣I\n");printf("|学号：1001010042|\n");printf("|姓名：黄浩全vDev-C++4.9.9.0〉|\n");printf("|1\n");}实验过程中遇到的问题解决办法与实验体会Q4（需手写，10得分:分）1、在FIFO算法可以很容易用数组实现，而LRU算