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

1、 实验五 虚拟内存页面置换算法一：实验目的通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。二：实验内容问题描述：设计程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。程序要求：1）利用先进先出FIFO、最佳置换OPI和最近最久未使用LRU三种页面置换算法模

2、拟页面访问过程。2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。3）输入：最小物理块数m，页面个数n，页面访问序列P1, ,Pn，算法选择1-FIFO，2-OPI，3-LRU。4）输出：每种算法的缺页次数和缺页率。实现提示：用C+语言实现提示：1）程序中变量定义参考如下：int PageOrderMaxNumber;int TimeMaxNumber;int SimulateMaxNumberMaxNumber;int PageCountMaxNumber;int PageNum,LackNum,PageMin;double LackPageRate;bool found;2

3、）页面置换的实现过程如下： 变量初始化； 接收用户输入最小物理块数m，页面个数n，页面序列P1, ,Pn，选择算法1-FIFO，2-OPI，3-LRU； 根据用户选择的算法进行页面的分配和置换，输出页面置换算法的模拟过程； 计算选择算法的缺页次数和缺页率； 输出选择算法的缺页次数和缺页率。三：概要设计输入函数void input()初始化函数void Initial()显示函数void show()先进先出算法的函数void FIFO()最佳置换算法的函数void OPI()最近最久未使用置换算法void LRU()主函数void main()input();int s=0;while(s!=

4、4)cout请选择算法：endl;cout1：先进先出；2：最佳值换算法；3：最近最久未使用置换算法；4：退出s;switch(s)case 1:FIFO();show();break;case 2:OPI();show();break;case 3:LRU();show();break;case 4:return;default:cout输入数字不对，请重新输入：;break;四：结果测试和截图以及说明输入：页面个数 20 页面数列 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 系统为进程分配的物理块：3输出结果如截图所示：先进先出算法：2.最佳置换算法 3

5、.LRU算法 说明：1表示的是物理块中没有页面。 相邻的相同的也同时表示出来了并没有空出。五：源代码#include/using namespace std;const int MaxNumber=100;int PageOrderMaxNumber;int TimeMaxNumber;int SimulateMaxNumberMaxNumber;int PageCountMaxNumber;int PageNum,LackNum,PageMin;double LackPageRate;bool found;/输入void input()cout请输入页面个数：(PageNum)PageNum

6、;while(PageNumMaxNumber)cout页面个数太大，请重新输入：(PageNum)PageNum;cout请输入页面序列：endl;for(int i_PageOrder=0;i_PageOrderPageOrderi_PageOrder;cout请输入系统分配的最小页面个数：(PageMin)PageMin;while(PageMinMaxNumber)cout页面个数太大，请重新输入：(PageMin)PageMin;/先进先出页面置换算法void Initial()for(int i_Time=0;i_TimePageMin;i_Time+)Timei_Time=Pag

7、eNum;for(int i_Simulate=0;i_SimulatePageNum;i_Simulate+)for(int j_Simulate=0;j_SimulatePageMin;j_Simulate+)Simulatei_Simulatej_Simulate=-1;LackNum=0;LackPageRate=0;found=true;void show()for(int i=0;iPageNum;i+)coutPageOrderi: ;for(int k=0;kPageMin;k+)coutSimulateik ;coutendl;LackPageRate=double(Lack

8、Num)/double(PageNum);cout缺页数：LackNumendl;cout缺页率：LackPageRateendl;void FIFO()Initial();int i=0;/指示PageOrder的序号int j=0;/指示PageCount中要替换的序号int k=0;for(i=0;iPageMin;i+)PageCounti=PageOrderi;for(k=0;k=i;k+)Simulateik=PageCountk;LackNum+;for(;iPageNum;i+)k=0;found=false;while(kPageMin&(!found)if(PageCoun

9、tk=PageOrderi)found=true;break;elsek+;if(!found)PageCountj=PageOrderi;LackNum+;j+;j=j % PageMin;for(k=0;kPageMin;k+)Simulateik=PageCountk;void OPI()Initial();int i=0;/指示PageOrder的序号int j=0;/指示PageCount中要替换的序号int k=0;for(i=0;iPageMin;i+)PageCounti=PageOrderi;int num=i+1;/用来找刚刚换进的页面数在后面出现的位置while(numP

10、ageNum)if(PageCounti=PageOrdernum)Timei=num;break;elsenum+;if(num=PageNum)Timei=num;for(k=0;k=i;k+)Simulateik=PageCountk;LackNum+;for(;iPageNum;i+)k=0;found=false;while(kPageMin&(!found)if(PageCountk=PageOrderi)found=true;j=k;break;elsek+;if(!found)j=0;for(k=0;kTimej)j=k;LackNum+;PageCountj=PageOrde

11、ri;int num=i+1;/用来找刚刚换进的页面数在后面出现的位置while(numPageNum)if(PageCountj=PageOrdernum)Timej=num;break;elsenum+;if(num=PageNum)Timej=num;for(k=0;kPageMin;k+)Simulateik=PageCountk;void LRU()/最近最久未使用置换算法Initial();int i=0;/指示PageOrder的序号int j=0;/指示PageCount中要替换的序号int k=0;for(i=0;iPageMin;i+)PageCounti=PageOrde

12、ri;Timei=0;for(k=0;k=i;k+)Timek+;Simulateik=PageCountk;LackNum+;for(;iPageNum;i+)k=0;found=false;while(kPageMin&(!found)if(PageCountk=PageOrderi)found=true;j=k;break;elsek+;if(!found)j=0;for(k=0;kTimej)j=k;LackNum+;PageCountj=PageOrderi;Timej=0;for(k=0;kPageMin;k+)Timek+;Simulateik=PageCountk;/主函数void main()input();int s=0;while(s!=