Clock及改进Clock置换算法实现

《Clock及改进Clock置换算法实现》由会员分享，可在线阅读，更多相关《Clock及改进Clock置换算法实现（18页珍藏版）》请在装配图网上搜索。

1、word操作系统课程设计报告学院：学生某某:学号:题目：Clock 与改良 Clock置换算法实现指导教师:一、 课程设计目的操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。l 进一步巩固和复习操作系统的根底知识。l 培养学生结构化程序、模块化程序设计的方法和能力。l 提高学生调试程序的技巧和软件设计的能力。l 提高学生分析问题、解决问题以与综合利用 C 语言进展程序设计的能力。二、 课程设计内容与要求：模拟实现Clock与改良Clock置换算法，程序应按照Clock置换算法与改良Clock置换算

2、法模拟实现页面的置换。1不同的功能使用不同的函数实现模块化，对每个函数的功能和调用接口要注释清楚。对程序其它局部也进展必要的注释。2对系统进展功能模块分析、画出总流程图和各模块流程图。3用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。4通过命令行相应选项能直接进入某个相应菜单项选择项的功能模块。5所有程序需调试通过三、 算法与关键数据结构设计(1)Clock置换算法：当采用简单Clock算法是只需为每页设置一位访问位，再将内存中的所用页面都通过指针成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选

3、择该页换出；假如为1，如此重新将他置0,暂不换出，而给该页第二次驻留内存的机会,在按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面是，假如其访问位仍为1，如此再返回到队首去检查第一个页面。2算法流程图3改良型Clock置换算法在将一个页面换出时，如果该页已被修改正，便须将该页重新写回到磁盘上；但如果该页未被修改正，如此不必将它拷回磁盘。在改良型Clock算法中，除须考虑页面的使用情况外，还须在增加一个因素，即置换代价，这样页面换出时，既要是未使用过的页面，又要是未被修改正的页面。把同时满足这两个条件的页面作为首选淘汰的页面。由访问位A和修改位M可以组合成下面四种类型的页面:1类A=

4、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置换算法代码实现void CLOCK(int num)int j;if(isIns

5、ide(num)cout命中endl;for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl;elseif(count = A)lost+;for(j=0; j A; )if(statej = 0)break;elsestatej = 0;j+;j = j %3;Insidej = Pagenum;statej = 1;for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl;elseInsidecount = Pagenum;count+;for(int i=0 ; i A; i+) cout物理块i#中内容:

6、Inside iendl;（2） 改良Clock置换算法实现void LCLOCK(int num)int j;if(isInside2(num)cout命中endl;for(int i=0 ; i A; i+)cout物理块i#中内容:Inside iendl;elseif(count = A)lost+;j =whichpage();Insidej = Pagenum;state2j0 = 1;for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl;elseInsidecount = Pagenum;count+;for(int i=0 ; i A

7、; i+)cout物理块i#中内容:Inside iendl;五程序截图运行截图：六程序代码#include#includeusing namespace std;#define M 2int const A = 4;/内存中存放的页面数int count = 0;int InsideA;int const PageCount =10;/总的页面数int PagePageCount;int insert = 0;/先到先出置换算法fcfo中表示 当内存满的时候，新进入的页号放的位置int suiji = 0; /随机置换算法randchange 当内存满的时候，新进入的页号放的位置int st

8、ateA;/clock置换算法中，内存中的每个页面号对应的状态int state2AM;/ 二维数组，第一行第一列为访问位，第一行的第二列为修改位double lost = 0.0;/检测页号是否在内存中bool isInside(int num)for(int i = 0; i A; i+)if(Insidei = Pagenum)statei = 1;return true;return false;/判断页面是否已经被修改bool change()if(rand()%2+1) = 1 )cout该页面被修改endl;return true;elsereturn false;/用于改良型c

9、lock置换算法，检测页号是否在内存中并把访问位和修改位置1bool isInside2(int num)for(int i = 0; i A; i+)if(Insidei = Pagenum)if(change()state2i0 = 1;state2i1 = 1;elsestate2i0 = 1;return true;return false;/用于改良型clock置换算法，判断内存中第几个需要被置换int whichpage()int j;for(j=0; j A;j+) if(state2j0 = 0&state2j1 = 0)return j;for(j=0; j A;j+ ) i

10、f(state2j0 = 0&state2j1 = 1)return j;state2j0 = 0 ;for(j=0; j A;j+ )state2j0 = 0 ;return whichpage();/简单Clock置换算法void CLOCK(int num)int j;if(isInside(num)cout命中endl;for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl;elseif(count = A)lost+;for(j=0; j A; )if(statej = 0)break;elsestatej = 0;j+;j = j %3;I

11、nsidej = Pagenum;statej = 1;for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl;elseInsidecount = Pagenum;count+;for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl;/改良型clock置换算法void LCLOCK(int num)int j;if(isInside2(num)cout命中endl;for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl;elseif(count = A)lost+;j

12、=whichpage();Insidej = Pagenum;state2j0 = 1;for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl;elseInsidecount = Pagenum;count+;for(int i=0 ; i A; i+)cout物理块i#中内容:Inside iendl;int main() char ch ; cout默认的页号为endl; for(int i = 0; i PageCount; i+) Pagei =rand()%9 + 1;coutPagei ; coutendl; while(1)cout-1.

13、Clock置换算法CLOCK-endl;cout-2.改良型Clock置换算法-endl;cout-0.退出-endl;cout-输入进展选择-ch;switch(ch) case 1: lost = 0;count = 0;for(int m = 0; m A; m+)statem = 0;for(int j = 0; j A; j+)Insidej = 0;for(int i = 0; i PageCount; i+) cout读入Pagei=Pageiendl; CLOCK(i); coutn页面访问次数PageCountn缺页中断次数lostn缺页率lost/(PageCount)ne

14、ndl; break; case 2: lost = 0;count = 0;for(int m = 0; m A; m+) for(int n = 0; n 2;n+)state2mn = 0;for(int j = 0; j A; j+) Insidej = 0;for(int i = 0; i PageCount; i+) cout读入Pagei=Pageiendl; LCLOCK(i); coutn页面访问次数PageCountn缺页中断次数lostn缺页率lost/(PageCount)nendl; break;case 0:exit(0); break; return 0;18 / 18