Clock及改进Clock置换算法实现

操作系统课程设计报告书Clock及改进Clock置换算法实现班级姓名学号指导老师2014年3月12日目录一、课程设计目的.................................3二、系统分析与设计................................3三、算法流程图：................................4四、函数模块:......................................6五、系统调试与结果：.............................7六、设计心得与体会：.............................9七、源程序代码:..................................15一、课程设计目的操作系统课程设计是为了对学习的操作系统课程更深刻的理解和巩固，对操作系统的整体进行一个模拟。通过实践加深对各个部分的管理功能的认识，还能进一步分析各个部分之间的联系，最后达到对完整系统的理解。同时，可以提高运用操作系统知识解决实际问题的能力；锻炼实际的编程能力、创新能力及团队组织、协作开发软件的能力；还能提高调查研究、查阅技术文献、资料以及编写软件设计文档的能力。课程设计是自己独立完成一项任务的过程，编程过程中要充分调动个人的积极性，提高自身解决实际问题的能力，发现自身的编程错误习惯，提高编写程序的质量。同时，也为以后深入层次的学习及研究打基础。编程中少不了难题，遇到难题时需要的是用程序员的思维方式去考虑问题解决问题，还需要很大的精力和耐心，对于我们来说都是磨练和提高。二、系统分析与设计在采用请求分页机制的操作系统中，当运行一个程序的时候，若要访问的页面不在内存中而需要把它们调入内存，但此时内存已无空闲空间，为了保证该进程能正常运行，需选择内存中暂时不用的页面调出到磁盘交换区。选择调出哪个页面，由页面算法决定。页面置换算法的好坏，直接影响系统的性能，所以一个好的页面置换算法，应尽可能选择调出较长时间内不会再访问的页面，以保证较低的缺页率。2.1Clock页面置换原理描述Clock算法的思想：当某一页首次装入内存中时，则将该页框的使用位设置为1；当该页随后被访问到时（在访问产生缺页中断之后），它的使用位也会被设置为1。对于页面置换算法，用于置换算法，用于置换的候选页框集合（当前进程：局部范围；整个内存；全局范围）被看做是一个循环缓冲区，并且有一个指针与之相关联。当一页被置换时，该指针被设置成指向缓冲区中的下一页框。当需要置换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一页框。每当遇到一个使用位为1的页框时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有页框的使用位均为0时，则选择遇到的第一个页框置换；如果所有页框的使用位均为1时，则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，置换该页框中的页。2.2改进型Clock页面置换原理描述改进型的Clock算法的思想：在将一个页面换出时，如果该页已被修改过，便须将它重新写到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。同时满足这两条件的页面作为首先淘汰的页。由访问位A和修改位M可以组合成下面四种类型的页面：1类（A=0，M=0）：表示该页最近既未被访问、又未被修改，是最佳淘汰页。2类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。3类（A=1，M=0）：最近已被访问，但未被修改，该页有可能再被访问。4类（A=1，M=1）：最近已被访问且被修改，该页有可能再被访问。在内存中的每个页必定是这四类页面之一，在进行页面置换时，其执行过程可分成以下三步：（1）从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。（2）如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有经过的页面的访问位置0。（3）如果第二步也失败，即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后，重复第一步，如果仍失败，必要时再重复第二步，此时就一定能够找到被淘汰的页。三、算法流程图：Clock置换算法流程图：改进型置换算法流程图：入口查寻指针前进一步，指向下一个表目页面访问位＝0?选择该页面淘汰是返回置页面访问位＝“0”否块号页号访问位指针0124034215650711替换指针算法开始输入页面数为n初始化n个页面是否修改页面把需要修改的页面的修改标志置为1输入页面号第一次扫描，判断是否存在A为0，M为0的页面第二次扫描判断是否存在A为0，M为1的页面，并把扫描后的页面A置为1用输入页面置换该页面用输入页面置换该页面YNYNYN四、函数模块主函数模块函数名称：intmain()功能：显示主菜单，调用函数检测模块函数名称：boolinblock(intnum)、boolinblock2(intnum)功能：检测读入的页号是否存在内存中、检测页号是否在内存中并把访问位和修改位置1修改模块函数名称：boolchange()、intwhichpage()功能：判断页面是否已经被修改、判断内存中第几个需要被置换Clock模块函数名称：voidCLOCK(intnum)功能：实现Clock置换算法，完成页面置换改进型Clock模块函数名称：voidLCOCK(intnum)功能：实现改进的ClockL置换算法，完成页面置换五、系统调试与结果六、程序清单#includeiostream#includestdlib.h#includetime.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(je){for(i=j;ij+m;i++){if(i==e)break;list[i]=(q+rand()%e)%N;//保证在虚拟内存的页号内}j=i;r=rand()%100;if(rt)q=rand()%N;elseq=(q+1)%N;}}//随机生产是否被修改的情况，prop(0……100),prop/100的概率为被修改voidgenerate_modify(int*mo,inte,intprop){inti,t;for(i=0;ie;i++){t=rand()%100;if(tprop)mo[i]=0;elsemo[i]=1;}}//检测页号是否在内存中boolinblock(intnum){for(inti=0;iblockCount;i++){if(block[i]==Page[num]){state[i]=1;returntrue;}}returnfalse;}//判断页面是否已经被修改boolchange(){if((rand()%2+1)==1){printf(该页面被修改!\n);returntrue;}elsereturnfalse;}//用于改进型clock置换算法，检测页号是否在内存中并把访问位和修改位置1boolinblock2(intnum){for(inti=0;iblockCount;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;jblockCount;j++){if(state2[j][0]==0&&state2[j][1]==0){returnj;}}for(j=0;jblockCount;j++){if(state2[j][0]==0&&state2[j][1]==1){returnj;}state2[j][0]=0;}for(j=0;jblockCount;j++){state2[j][0]=0;}returnwhichpage();}//简单Clock置换算法voidCLOCK(intnum){intj;if(inblock(num)){printf(命中!\n);lost++;for(inti=0;iblockCount;i++)printf(物理块%d#中内容:%d\n,i,block[i]);}elseif(count==blockCount){//lost++;for(j=0;jblockCount;){if(state[j]==0){break;}else{state[j]=0;}j++;j=j%3;}block[j]=Page[num];state[j]=1;for(inti=0;iblockCount;i++)printf(物理块%d#中内容:%d\n,i,block[i]);}else{block[count]=Page[num];count++;for(inti=0;iblockCount;i++)printf(物理块%d#中内容:%d\n,i,block[i]);}}//改进型clock置换算法voidLCLOCK(intnum){intj;if(inblock2(num)){printf(命中!\n);lost++;for(inti=0;iblockCount;i++)printf(物理块%d#中内容:%d\n,i,block[i]);}elseif(count==blockCount){//lost++;j=whichpage();block[j]=Page[num];state2[j][0]=1;for(inti=0;iblockCount;i++)printf(物理块%d#中内容:%d\n,i,block[i]);}else{block[count]=Page[num];count++;for(inti=0;iblockCount;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;iPageCount;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;mblockCount;m++){state[m]=0;}for(intj=0;jblockCount;j++){block[j]=