页面置换算法OPT+FIFO+LRU+clock

#includeiostream#includefstreamusingnamespacestd;#defineBlockSize10#definePageSize100intpage[PageSize];//页面数组存放页面intblock[BlockSize];//物理块数组intresult[PageSize][BlockSize];//存放页面和物理块二维数组intpSize=0;//用户使用页面数intbSize=0;//用户使用物理块数intblockFlag[BlockSize];//用于LRU与最佳置换算法中，辅助判断该换出的页面intnoPageCount=0;//缺页次数//输入数据voidinputData(){coutendl请输入物理块数(1=bSize=BlockSize')'endl;cinbSize;cout请输入页面数(1=pSize=PageSize')'endl;cinpSize;while(bSize=0||bSizeBlockSize||pSize=0||pSizePageSize){//判断用户输入是否在范围内cout输入范围错误，请重新输入：endl;cout请输入物理块数(1=F=BlockSize')';cinbSize;coutendl请输入页面数(1=p=PageSize')';cinpSize;}cout请输入页面走向endl;for(inti=0;ipSize;i++)cinpage[i];}//初始化page数组voidinitPage(){for(inti=0;iPageSize;i++)page[i]=-1;}//初始化block与result数组voidinitBlockResult(){inti=0;for(i=0;iBlockSize;i++)block[i]=-1;for(i=0;iPageSize;i++)for(intj=0;jBlockSize;j++)result[i][j]=-1;}//查找物理块中是否存在要调用的页面intExist(inti){for(intj=0;jbSize;j++)if(block[j]==i)returnj;return-1;}//显示结果voiddisplay(intnoPageCount){for(inti=0;ipSize;i++){coutpage[i];for(intj=0;jbSize;j++){if(result[i][j]==-1)break;elsecout'['result[i][j]']''';}coutendl;}cout____________________________________endl;coutendl缺页次数：noPageCountendl;cout缺页率：((double)noPageCount/pSize)*100'%'endl;cout====================================endl;}//最佳置换算法OPTvoidOPT(){inti=0,j=0;intposition=0,noPageCount=0;intpageFlag=0,resultFlag=0;//页面标记（下标）指向下一个页面,结果标记表示结果的行，即result数组的行标for(i=0;iBlockSize;i++)blockFlag[i]=0;while(pageFlagpSize){if(Exist(page[pageFlag])!=-1)//判断页面是否已经存在resultFlag++;else{if(positionbSize)//判断有无空闲物理块{//若有则将页面放入空闲块block[position]=page[pageFlag];position++;noPageCount++;for(i=0;iposition;i++)result[resultFlag][i]=block[i];resultFlag++;}else{for(i=0;ibSize;i++){for(j=pageFlag+1;jpSize;j++){if(block[i]==page[j]){blockFlag[i]=j;break;}}if(j==pSize)blockFlag[i]=999;}intoptPos=0,max=blockFlag[0];for(inti=0;ibSize;i++)if(maxblockFlag[i]){max=blockFlag[i];optPos=i;}block[optPos]=page[pageFlag];noPageCount++;for(i=0;ibSize;i++)result[resultFlag][i]=block[i];resultFlag++;}}pageFlag++;}coutendl最佳置换算法:endl;display(noPageCount);return;}//先进先出页面置换算法FIFOvoidFIFO(){intblockFlag=0,pageFlag=0,resultFlag=0;//物理块标记，确定该换出的物理块下标inti=0,j=0,noPageCount=0;intposition=0;//指示物理块，查找有无空闲while(pageFlagpSize){if(Exist(page[pageFlag])!=-1)resultFlag++;else{if(positionbSize){block[position]=page[pageFlag];position++;noPageCount++;for(i=0;i=position;i++)result[resultFlag][i]=block[i];resultFlag++;}else{block[blockFlag]=page[pageFlag];//blockFlag指示要换出的页面noPageCount++;for(i=0;ibSize;i++)result[resultFlag][i]=block[i];resultFlag++;blockFlag++;blockFlag=blockFlag%bSize;}}pageFlag++;}coutendl先进先出页面置换算法FIFO:endl;display(noPageCount);return;}//最近最久未用算法LRUvoidLRU(){inti=0,noPageCount=0;intpageFlag=0,resultFlag=0,position=0;for(i=0;iBlockSize;i++)//初始化时间记录数组blockFlag[i]=0;while(pageFlagpSize){if(Exist(page[pageFlag])!=-1){//判断页面是否已经在主存中resultFlag++;blockFlag[Exist(page[pageFlag])]=0;//若在则将时间记录数组对应位置为0}else{if(positionbSize){block[position]=page[pageFlag];blockFlag[position]=0;position++;noPageCount++;for(i=0;i=position;i++)result[resultFlag][i]=block[i];resultFlag++;}else{intlast=0,min=blockFlag[0];for(inti=0;ibSize;i++)if(minblockFlag[i]){min=blockFlag[i];last=i;}block[last]=page[pageFlag];//置换最久未用页面blockFlag[last]=0;noPageCount++;for(i=0;ibSize;i++)result[resultFlag][i]=block[i];resultFlag++;}}for(i=0;ibSize;i++)blockFlag[i]++;pageFlag++;}coutendl最近最久未用算法LRU:endl;display(noPageCount);return;}//时钟(clock)置换算法voidclock(){inti=0,position=0,noPageCount=0;boolboolBlockFlag[BlockSize];intflag=0;//访问位循环标记intpageFlag=0,resultFlag=0;while(pageFlagpSize){if(Exist(page[pageFlag])!=-1){resultFlag++;boolBlockFlag[Exist(page[pageFlag])]=true;}else{if(positionbSize){block[position]=page[pageFlag];noPageCount++;boolBlockFlag[position]=true;position++;for(i=0;iposition;i++)result[resultFlag][i]=block[i];resultFlag++;}else{while(true){//无限循环，找出访问位为false的页面if(boolBlockFlag[flag]==false)break;boolBlockFlag[flag]=false;//若为true，置为falseflag++;flag=flag%bSize;}block[flag]=page[pageFlag];boolBlockFlag[flag]=true;flag++;flag=flag%bSize;noPageCount++;for(i=0;iposition;i++)result[resultFlag][i]=block[i];resultFlag++;}}pageFlag++;}coutendl时钟(clock)置换算法:endl;display(noPageCount);return;}intmain(){initPage();intfunc;while(func!=5){cout请选择所需要的功能：endl;cout0.输入数据endl;cout1.最佳（optimal）置换算法endl;cout2.先进先出（FIFO）置换算法endl;cout3.最近最久未用（LRU）置换算法endl;cout4.时钟（clock）置换算法endl;cout5.退出endl;switch(func){case0:inputData();break;case1:initBlockResult();OPT();break;case2:initBlockResult();FIFO();break;case3:initBlockResult();LRU();break;case4:initBlockResult();clock();break;case5:break;}cout请选择功能:;cinfunc;system(cls);}return0;}