实验五--虚拟内存页面置换算法

实验五虚拟内存页面置换算法一：实验目的通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。二：实验内容问题描述：设计程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1,…,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。程序要求：1）利用先进先出FIFO、最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。3）输入：最小物理块数m，页面个数n，页面访问序列P1,…,Pn，算法选择1-FIFO，2-OPI，3-LRU。4）输出：每种算法的缺页次数和缺页率。实现提示：用C++语言实现提示：1）程序中变量定义参考如下：intPageOrder[MaxNumber];intTime[MaxNumber];intSimulate[MaxNumber][MaxNumber];intPageCount[MaxNumber];intPageNum,LackNum,PageMin;doubleLackPageRate;boolfound;2）页面置换的实现过程如下：变量初始化；接收用户输入最小物理块数m，页面个数n，页面序列P1,…,Pn，选择算法1-FIFO，2-OPI，3-LRU；根据用户选择的算法进行页面的分配和置换，输出页面置换算法的模拟过程；计算选择算法的缺页次数和缺页率；输出选择算法的缺页次数和缺页率。三：概要设计输入函数voidinput()初始化函数voidInitial()显示函数voidshow()先进先出算法的函数voidFIFO()最佳置换算法的函数voidOPI()最近最久未使用置换算法voidLRU()主函数voidmain(){input();ints=0;while(s!=4){cout请选择算法：endl;cout1：先进先出；2：最佳值换算法；3：最近最久未使用置换算法；4：退出endl;cins;switch(s){case1:FIFO();show();break;case2:OPI();show();break;case3:LRU();show();break;case4:return;default:cout输入数字不对，请重新输入：;break;}}}四：结果测试和截图以及说明输入：页面个数20页面数列70120304230321201701系统为进程分配的物理块：3输出结果如截图所示：先进先出算法：2.最佳置换算法3.LRU算法说明：—1表示的是物理块中没有页面。相邻的相同的也同时表示出来了并没有空出。五：源代码#includeiostream.h//usingnamespacestd;constintMaxNumber=100;intPageOrder[MaxNumber];intTime[MaxNumber];intSimulate[MaxNumber][MaxNumber];intPageCount[MaxNumber];intPageNum,LackNum,PageMin;doubleLackPageRate;boolfound;//输入voidinput(){cout请输入页面个数：(PageNum)endl;cinPageNum;while(PageNumMaxNumber){cout页面个数太大，请重新输入：(PageNum)endl;cinPageNum;}cout请输入页面序列：endl;for(inti_PageOrder=0;i_PageOrderPageNum;i_PageOrder++){cinPageOrder[i_PageOrder];}cout请输入系统分配的最小页面个数：(PageMin)endl;cinPageMin;while(PageMinMaxNumber){cout页面个数太大，请重新输入：(PageMin)endl;cinPageMin;}}//先进先出页面置换算法voidInitial(){for(inti_Time=0;i_TimePageMin;i_Time++){Time[i_Time]=PageNum;}for(inti_Simulate=0;i_SimulatePageNum;i_Simulate++){for(intj_Simulate=0;j_SimulatePageMin;j_Simulate++){Simulate[i_Simulate][j_Simulate]=-1;}}LackNum=0;LackPageRate=0;found=true;}voidshow(){for(inti=0;iPageNum;i++){coutPageOrder[i]:;for(intk=0;kPageMin;k++){coutSimulate[i][k];}coutendl;}LackPageRate=double(LackNum)/double(PageNum);cout缺页数：LackNumendl;cout缺页率：LackPageRateendl;}voidFIFO(){Initial();inti=0;//指示PageOrder[]的序号intj=0;//指示PageCount[]中要替换的序号intk=0;for(i=0;iPageMin;i++){PageCount[i]=PageOrder[i];for(k=0;k=i;k++){Simulate[i][k]=PageCount[k];}LackNum++;}for(;iPageNum;i++){k=0;found=false;while(kPageMin&&(!found)){if(PageCount[k]==PageOrder[i]){found=true;break;}elsek++;}if(!found){PageCount[j]=PageOrder[i];LackNum++;j++;j=j%PageMin;}for(k=0;kPageMin;k++){Simulate[i][k]=PageCount[k];}}}voidOPI(){Initial();inti=0;//指示PageOrder[]的序号intj=0;//指示PageCount[]中要替换的序号intk=0;for(i=0;iPageMin;i++){PageCount[i]=PageOrder[i];intnum=i+1;//用来找刚刚换进的页面数在后面出现的位置while(numPageNum){if(PageCount[i]==PageOrder[num]){Time[i]=num;break;}elsenum++;}if(num==PageNum)Time[i]=num;for(k=0;k=i;k++){Simulate[i][k]=PageCount[k];}LackNum++;}for(;iPageNum;i++){k=0;found=false;while(kPageMin&&(!found)){if(PageCount[k]==PageOrder[i]){found=true;j=k;break;}elsek++;}if(!found){j=0;for(k=0;kPageMin;k++){if(Time[k]Time[j])j=k;}LackNum++;}PageCount[j]=PageOrder[i];intnum=i+1;//用来找刚刚换进的页面数在后面出现的位置while(numPageNum){if(PageCount[j]==PageOrder[num]){Time[j]=num;break;}elsenum++;}if(num==PageNum)Time[j]=num;for(k=0;kPageMin;k++){Simulate[i][k]=PageCount[k];}}}voidLRU()//最近最久未使用置换算法{Initial();inti=0;//指示PageOrder[]的序号intj=0;//指示PageCount[]中要替换的序号intk=0;for(i=0;iPageMin;i++){PageCount[i]=PageOrder[i];Time[i]=0;for(k=0;k=i;k++){Time[k]++;Simulate[i][k]=PageCount[k];}LackNum++;}for(;iPageNum;i++){k=0;found=false;while(kPageMin&&(!found)){if(PageCount[k]==PageOrder[i]){found=true;j=k;break;}elsek++;}if(!found){j=0;for(k=0;kPageMin;k++){if(Time[k]Time[j])j=k;}LackNum++;}PageCount[j]=PageOrder[i];Time[j]=0;for(k=0;kPageMin;k++){Time[k]++;Simulate[i][k]=PageCount[k];}}}//主函数voidmain(){input();ints=0;while(s!=4){cout请选择算法：endl;cout1：先进先出；2：最佳值换算法；3：最近最久未使用置换算法；4：退出endl;cins;switch(s){case1:FIFO();show();break;case2:OPI();show();break;case3:LRU();show();break;case4:return;default:cout输入数字不对，请重新输入：;break;}}}