Clock及改进Clock置换算法实现.doc

操作系统课程设计报告学院：学生:＿＿学号:题目：Clock 及改进 Clock置换算法实现指导教师:一、 课程设计目的操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会l 进一步巩固和复习操作系统的基础知识l 培养学生结构化程序、模块化程序设计的方法和能力l 提高学生调试程序的技巧和软件设计的能力l 提高学生分析问题、解决问题以及综合利用 C 语言进行程序设计的能力二、 课程设计容与要求：模拟实现Clock及改进Clock置换算法，程序应按照Clock置换算法及改进Clock置换算法模拟实现页面的置换1．不同的功能使用不同的函数实现〔模块化〕，对每个函数的功能和调用接口要注释清楚对程序其它部分也进行必要的注释2．对系统进行功能模块分析、画出总流程图和各模块流程图3．用户界面要求使用方便、简洁明了、美观大方、格式统一所有功能可以反复使用，最好使用菜单4．通过命令行相应选项能直接进入某个相应菜单项选择项的功能模块5．所有程序需调试通过三、 算法及关键数据结构设计(1)Clock置换算法：当采用简单Clock算法是只需为每页设置一位访问位，再将存中的所用页面都通过指针成一个循环队列。

当某页被访问时，其访问位被置1置换算法在选择一页淘汰时，只需检查页的访问位如果是0，就选择该页换出；假设为1，那么重新将他置0,暂不换出，而给该页第二次驻留存的机会,在按照FIFO 算法检查下一个页面当检查到队列中的最后一个页面是，假设其访问位仍为1，那么再返回到队首去检查第一个页面〔2〕算法流程图〔3〕改进型Clock置换算法在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上；但如果该页未被修改过，那么不必将它拷回磁盘在改进型Clock算法中，除须考虑页面的使用情况外，还须在增加一个因素，即置换代价，这样页面换出时，既要是未使用过的页面，又要是未被修改过的页面把同时满足这两个条件的页面作为首选淘汰的页面由访问位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置换算法代码实现void CLOCK(int num){ int j; if(isInside(num)){ cout<<"命中"<#includeusing namespace std;#define M 2int const A = 4;//存中存放的页面数int count = 0;int Inside[A];int const PageCount =10;//总的页面数int Page[PageCount];int insert = 0;//先到先出置换算法fcfo中表示 当存满的时候，新进入的页号放的位置int suiji = 0; //随机置换算法randchange 当存满的时候，新进入的页号放的位置int state[A];//clock置换算法中，存中的每个页面号对应的状态int state2[A][M];// 二维数组，第一行第一列为访问位，第一行的第二列为修改位double lost = 0.0;//检测页号是否在存中bool isInside(int num){ for(int i = 0; i < A; i++){ if(Inside[i] == Page[num]){ state[i] = 1; return true; } } return false;}//判断页面是否已经被修改bool change(){ if((rand()%2+1) == 1 ){ cout<<"该页面被修改"<