Clock及改进Clock置换算法实现

操作系统课程设计报告书Clock及改进Clock置换算法实现班级姓名学号指导老师2014年3月12日目录一、课程设计目的3二、系统分析与设计3三、算法流程图：4四、函数模块:6五、系统调试与结果：7六、设计心得与体会：9七、源程序代码:15四、函数模块主函数模块函数名称：intmain()功能：显示主菜单，调用函数检测模块函数名称：boolinblock(intnum)、boolinblock2(intnum)功能：检测读入的页号是否存在内存中、检测页号是否在内存中并把访问位和修改位置1修改模块函数名称：boolchange()、intwhichpage()功能：判断页面是否已经被修改、判断内存中第几个需要被置换Clock模块函数名称：voidCLOCK(intnum)功能：实现Clock置换算法，完成页面置换改进型Clock模块函数名称：voidLCOCK(intnum)功能：实现改进的ClockL置换算法，完成页面置换五、系统调试与结果 六、程序清单#include<iostream>#include<stdlib.h>#include<time.h>#defineN20//虚拟内存尺寸usingnamespacestd;intP;intconstblockCount=3;//内存中的物理块数intcount=0;intblock[blockCount];intconstPageCount=15;//总的页面数intPage[PageCount];intstate[blockCount];//clock置换算法中，内存中的每个页面号对应的状态intstate2[blockCount][2];//二维数组，第一行第一列为访问位，第一行的第二列为修改位doublelost=0.0;voidgenerate_list(int*list,inte,intm,intt){ inti,j=0,q=P,r; srand((unsigned)time(NULL)); while(j<e) { for(i=j;i<j+m;i++) { if(i==e) break; list[i]=(q+rand()%e)%N;//保证在虚拟内存的页号内 } j=i; r=rand()%100; if(r<t) q=rand()%N; else q=(q+1)%N; }}//随机生产是否被修改的情况，prop(0……100),prop/100的概率为被修改voidgenerate_modify(int*mo,inte,intprop){ inti,t; for(i=0;i<e;i++) { t=rand()%100; if(t>prop) mo[i]=0; else mo[i]=1; }}//检测页号是否在内存中boolinblock(intnum){ for(inti=0;i<blockCount;i++) { if(block[i]==Page[num]) { state[i]=1; returntrue; } } returnfalse;}//判断页面是否已经被修改boolchange(){ if((rand()%2+1)==1) { printf("该页面被修改!\n"); returntrue; } else returnfalse;}//用于改进型clock置换算法，检测页号是否在内存中并把访问位和修改位置1boolinblock2(intnum){ for(inti=0;i<blockCount;i++){ if(block[i]==Page[num]){ if(change()){ state2[i][0]=1; state2[i][1]=1; } else{ state2[i][0]=1; } returntrue; } } returnfalse;}//用于改进型clock置换算法，判断内存中第几个需要被置换intwhichpage(){ intj; for(j=0;j<blockCount;j++) {if(state2[j][0]==0&&state2[j][1]==0) { returnj; } } for(j=0;j<blockCount;j++) {if(state2[j][0]==0&&state2[j][1]==1) { returnj; } state2[j][0]=0; } for(j=0;j<blockCount;j++) { state2[j][0]=0; } returnwhichpage();}//简单Clock置换算法voidCLOCK(intnum){ intj; if(inblock(num)) { printf("命中!\n"); lost++; for(inti=0;i<blockCount;i++)printf("物理块%d#中内容:%d\n",i,block[i]); } else if(count==blockCount) { //lost++; for(j=0;j<blockCount;) { if(state[j]==0) { break; } else{ state[j]=0; } j++; j=j%3; } block[j]=Page[num]; state[j]=1; for(inti=0;i<blockCount;i++)printf("物理块%d#中内容:%d\n",i,block[i]); } else{ block[count]=Page[num]; count++; for(inti=0;i<blockCount;i++)printf("物理块%d#中内容:%d\n",i,block[i]); }}//改进型clock置换算法voidLCLOCK(intnum){ intj; if(inblock2(num)) { printf("命中!\n");lost++; for(inti=0;i<blockCount;i++)printf("物理块%d#中内容:%d\n",i,block[i]); } else if(count==blockCount) { //lost++; j=whichpage(); block[j]=Page[num]; state2[j][0]=1; for(inti=0;i<blockCount;i++)printf("物理块%d#中内容:%d\n",i,block[i]); } else{ block[count]=Page[num]; count++; for(inti=0;i<blockCount;i++)printf("物理块%d#中内容:%d\n",i,block[i]); }}intmain(){inta[N]; intmo[N];intA=10;inte,m,prop,t,j; printf("页面走向为："); generate_list(a,e,m,t); generate_modify(mo,e,prop);for(inti=0;i<PageCount;i++) { Page[i]=rand()%9+1; printf("%d",Page[i]); } charch; printf("\n"); printf("\t\t1Clock置换算法\n"); printf("\t\t2改进型Clock置换算法\n"); printf("\t\t3退出!\n\n"); printf("请输入算法序号:\t\n");while(1){ scanf("%c",&ch); switch(ch){case'1':{ lost=0; count=0; for(intm=0;m<blockCount;m++) { state[m]=0; } for(intj=0;j<blockCount;j++) { block[j]=0; } for(inti=0;i<PageCount;i++) {printf("读入Page[%d]\n",i);CLOCK(i); } printf("页面访问次数:%d\n缺页次数:%0.lf\n",PageCount,PageCount-lost); printf("缺页率为:%0.001f\n",(PageCount-lost)/PageCount);printf("\n请输入算法序号:\t");}break;case'2':{lost=0; count=0; for(intm=0;m<blockCount;m++) {for(intn=0;n<2;n++) state2[m][n]=0; } for(intj=0;j<blockCount;j++) {block[j]=0; } for(inti=0;i<PageCount;i++) {printf("读入Page[%d]\n",i);LCLOCK(i);} printf("页面访问次数:%d\n缺页次数:%0.lf\n",PageCount,PageCount-lost); printf("缺页率为:%0.001f\n",(PageCount-lost)/PageCount);printf("\n请输入算法序号:\t");}break; case'3':{ exit(0); } }}return0;}七、实验心得通过这两周的课程设计,让我加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对虚拟存储,页面置换有了深入的了解,并能够用高级语言进行模拟演示。不仅提高对操作系统的了解，这次的课程设计也使自己的C语言编程能力加强了不少。虽然自己所做的很少也不够完善，但毕竟是我努力的结果。我也体会到，任何一门