Clock 及改进 Clock置换算法实现

1操作系统课程设计报告学院：学生姓名:＿＿学号:题目：Clock及改进Clock置换算法实现指导教师:2一、课程设计目的操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。进一步巩固和复习操作系统的基础知识。培养学生结构化程序、模块化程序设计的方法和能力。提高学生调试程序的技巧和软件设计的能力。提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。二、课程设计内容与要求：模拟实现Clock及改进Clock置换算法，程序应按照Clock置换算法及改进Clock置换算法模拟实现页面的置换。1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。2．对系统进行功能模块分析、画出总流程图和各模块流程图。3．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。5．所有程序需调试通过三、算法及关键数据结构设计3(1)Clock置换算法：当采用简单Clock算法是只需为每页设置一位访问位，再将内存中的所用页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将他置0,暂不换出，而给该页第二次驻留内存的机会,在按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面是，若其访问位仍为1，则再返回到队首去检查第一个页面。（2）算法流程图（3）改进型Clock置换算法在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。在改进型Clock算法中，除须考虑页面的使用情况外，还须在增加一个因素，即置换代价，这样页面换出时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页4面。由访问位A和修改位M可以组合成下面四种类型的页面:1类（A=0，M=0）：表示该页最近既未被访问，又未被修改，是最佳淘汰页。2类（A=0，M=0）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。3类（A=1，M=0）：表示该页最近已被访问，但未被修改，该页有可能在被访问。4类（A=1，M=1）：表示该页最近已被访问且被修改，该页可能再被访问。，执行过程：①从查寻指针当前位置起扫描内存分页循环队列，选择A=0且M=0的第一个页面淘汰；若未找到，转②②开始第二轮扫描，选择A=0且M=1的第一个页面淘汰，同时将经过的所有页面访问位置0；若不能找到，转①四、程序代码分析（1）Clock置换算法代码实现voidCLOCK(intnum){intj;if(isInside(num)){cout命中endl;for(inti=0;iA;i++)cout物理块i#中内容:Inside[i]endl;5}elseif(count==A){lost++;for(j=0;jA;){if(state[j]==0){break;}else{state[j]=0;}j++;j=j%3;}Inside[j]=Page[num];state[j]=1;for(inti=0;iA;i++)cout物理块i#中内容:Inside[i]endl;}else{Inside[count]=Page[num];6count++;for(inti=0;iA;i++)cout物理块i#中内容:Inside[i]endl;}}（2）改进Clock置换算法实现voidLCLOCK(intnum){intj;if(isInside2(num)){cout命中endl;for(inti=0;iA;i++)cout物理块i#中内容:Inside[i]endl;}elseif(count==A){lost++;j=whichpage();Inside[j]=Page[num];state2[j][0]=1;for(inti=0;iA;i++)7cout物理块i#中内容:Inside[i]endl;}else{Inside[count]=Page[num];count++;for(inti=0;iA;i++)cout物理块i#中内容:Inside[i]endl;}}五．程序截图运行截图：89六．程序代码#includeiostream#includestdlib.husingnamespacestd;#defineM2intconstA=4;//内存中存放的页面数intcount=0;intInside[A];intconstPageCount=10;//总的页面数intPage[PageCount];intinsert=0;//先到先出置换算法fcfo中表示当内存满的时候，新进入的页号放的位置10intsuiji=0;//随机置换算法randchange当内存满的时候，新进入的页号放的位置intstate[A];//clock置换算法中，内存中的每个页面号对应的状态intstate2[A][M];//二维数组，第一行第一列为访问位，第一行的第二列为修改位doublelost=0.0;//检测页号是否在内存中boolisInside(intnum){for(inti=0;iA;i++){if(Inside[i]==Page[num]){state[i]=1;returntrue;}}returnfalse;}//判断页面是否已经被修改boolchange(){if((rand()%2+1)==1){cout该页面被修改endl;11returntrue;}elsereturnfalse;}//用于改进型clock置换算法，检测页号是否在内存中并把访问位和修改位置1boolisInside2(intnum){for(inti=0;iA;i++){if(Inside[i]==Page[num]){if(change()){state2[i][0]=1;state2[i][1]=1;}else{state2[i][0]=1;}returntrue;}}returnfalse;12}//用于改进型clock置换算法，判断内存中第几个需要被置换intwhichpage(){intj;for(j=0;jA;j++){if(state2[j][0]==0&&state2[j][1]==0){returnj;}}for(j=0;jA;j++){if(state2[j][0]==0&&state2[j][1]==1){returnj;}state2[j][0]=0;}for(j=0;jA;j++){state2[j][0]=0;}returnwhichpage();}13//简单Clock置换算法voidCLOCK(intnum){intj;if(isInside(num)){cout命中endl;for(inti=0;iA;i++)cout物理块i#中内容:Inside[i]endl;}elseif(count==A){lost++;for(j=0;jA;){if(state[j]==0){break;}else{state[j]=0;}j++;14j=j%3;}Inside[j]=Page[num];state[j]=1;for(inti=0;iA;i++)cout物理块i#中内容:Inside[i]endl;}else{Inside[count]=Page[num];count++;for(inti=0;iA;i++)cout物理块i#中内容:Inside[i]endl;}}//改进型clock置换算法voidLCLOCK(intnum){intj;if(isInside2(num)){cout命中endl;for(inti=0;iA;i++)15cout物理块i#中内容:Inside[i]endl;}elseif(count==A){lost++;j=whichpage();Inside[j]=Page[num];state2[j][0]=1;for(inti=0;iA;i++)cout物理块i#中内容:Inside[i]endl;}else{Inside[count]=Page[num];count++;for(inti=0;iA;i++)cout物理块i#中内容:Inside[i]endl;}}16intmain(){charch;cout默认的页号为endl;for(inti=0;iPageCount;i++){Page[i]=rand()%9+1;coutPage[i];}coutendl;while(1){cout------------1.Clock置换算法（CLOCK）-----endl;cout------------2.改进型Clock置换算法--------endl;cout------------0.退出-----------------------endl;cout-------------输入进行选择----------------endl;cinch;switch(ch){case'1':{lost=0;count=0;for(intm=0;mA;m++){state[m]=0;}17for(intj=0;jA;j++){Inside[j]=0;}for(inti=0;iPageCount;i++){cout读入Page[i]=Page[i]endl;CLOCK(i);}cout\n页面访问次数PageCount\n缺页中断次数lost\n缺页率lost/(PageCount)\nendl;}break;case'2':{lost=0;count=0;for(intm=0;mA;m++){for(intn=0;n2;n++)state2[m][n]=0;}for(intj=0;jA;j++){Inside[j]=0;}for(inti=0;iPageCount;i++){18cout读入Page[i]=Page[i]endl;LCLOCK(i);}cout\n页面访问次数PageCount\n缺页中断次数lost\n缺页率lost/(PageCount)\nendl;}break;case'0':{exit(0);}break;}}return0;}