1、Clock及改进Clock置换算法实现Clock-及改进-Clock置换算法实现LT(1)Clock置换算法:当采用简单Clock算法是只需为每页设置一位访问位,再将内存中的所用页面都通过链接指针链接成一个循环队列。当某页被访问时,其访问位被置1。置换算法在选择一页淘汰时,只需检查页的访问位。如果是0,就选择该页换出;若为1,则重新将他置0,暂不换出,而给该页第二次驻留内存的机会,在按照FIFO 算法检查下一个页面。当检查到队列中的最后一个页面是,若其访问位仍为1,则再返回到队首去检查第一个页面。(2)算法流程图(3)改进型Clock置换算法在将一个页面换出时,如果该页已被修改过,便须将该页重
2、新写回到磁盘上;但如果该页未被修改过,则不必将它拷回磁盘。在改进型Clock算法中,除须考虑页面的使用情况外,还须在增加一个因素,即置换代价,这样 页面换出时,既要是未使用过的页面,又要是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页面。由访问位A和修改位M可以组合成下面四种类型的页面:1类(A=0,M=0):表示该页最近既未被访问,又未被修改,是最佳淘汰页。2类(A=0,M=0):表示该页最近未被访问,但已被修改,并不是很好的淘汰页。3类(A=1,M=0):表示该页最近已被访问,但未被修改,该页有可能在被访问。4类(A=1,M=1):表示该页最近已被访问且被修改,该页可能再被访
3、问。,执行过程: 从查寻指针当前位置起扫描内存分页循环队列,选择A=0且M=0的第一个页面淘汰;若未找到,转 开始第二轮扫描,选择A=0且M=1的第一个页面淘汰,同时将经过的所有页面访问位置0;若不能找到,转一、程序代码分析(1)Clock置换算法代码实现void CLOCK(int num) int j; if(isInside(num) cout命中endl; for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl; else if(count = A) lost+; for(j=0; j A; ) if(statej = 0) break; el
4、se statej = 0; j+; j = j %3; Insidej = Pagenum; statej = 1; for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl; else Insidecount = Pagenum; count+; for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl; (2)改进Clock置换算法实现void LCLOCK(int num) int j; if(isInside2(num) cout命中endl; for(int i=0 ; i A; i+)cout物理块i
5、#中内容:Inside iendl; else if(count = A) lost+; j =whichpage(); Insidej = Pagenum; state2j0 = 1; for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl; else Insidecount = Pagenum; count+; for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl; 五程序截图运行截图:六程序代码#include#includeusing namespace std;#define M 2int cons
6、t A = 4;/内存中存放的页面数int count = 0;int InsideA;int const PageCount =10;/总的页面数int PagePageCount;int insert = 0;/先到先出置换算法fcfo中表示 当内存满的时候,新进入的页号放的位置int suiji = 0; /随机置换算法randchange 当内存满的时候,新进入的页号放的位置int stateA;/clock置换算法中,内存中的每个页面号对应的状态int state2AM;/ 二维数组,第一行第一列为访问位,第一行的第二列为修改位double lost = 0.0;/检测页号是否在内存
7、中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; else return false;/用于改进型clock置换算法,检测页号是否在内存中并把访问位和修改位置1bool isInside2(int num) for(int i = 0; i A; i+) if(Insidei =
8、Pagenum) if(change() state2i0 = 1; state2i1 = 1; else state2i0 = 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+ ) if(state2j0 = 0&state2j1 = 1) return j; state2j0 = 0 ; for(j=0; j A;j+ ) state2
9、j0 = 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; else if(count = A) lost+; for(j=0; j A; ) if(statej = 0) break; else statej = 0; j+; j = j %3; Insidej = Pagenum; statej = 1; for(int i=0 ; i A; i+) cout物
10、理块i#中内容:Inside iendl; else Insidecount = 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; else if(count = A) lost+; j =whichpage(); Insidej = Pagenum; state2j0 =
11、 1; for(int i=0 ; i A; i+) cout物理块i#中内容:Inside iendl; else Insidecount = 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.Clock置换算法(CLOCK)-endl; cout-2.改进
12、型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)nendl; 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;
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2