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

,.实验五 虚拟内存页面置换算法一、需求分析 21.输入的形式和输入值的范围 32.输出的形式 43.程序所能达到的功能 44.测试数据 5二、概要设计 61.抽象数据类型的定义 62.主程序的流程 73.程序各模块之间的层次(调用)关系 8三、详细设计 81.voidFIFO() 82.voidOPI() 103.voidLRU() 13四、调试分析 161.发现的问题 162.算法的性能分析(包括基本操作和其它算法的时间复杂度和空间复杂度的分析)及其改谢谢阅读进设想； 163.解决方法 164.经验和体会 17,.五、用户使用说明 17六、测试结果 17七．附录 19一、需求分析需求在进程运行过程中，若其所访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出，需根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。置换算法的好坏，将直接影响到系统的性能。一个好的页面置换算法，应具有较低的更好频率。从理论上讲，应将那些以后不再访问的页面换出，或把那些在较长时间内不再访问的页面调出。谢谢阅读实验目的通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出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）输出：每种算法的缺页次数和缺页率。1.输入的形式和输入值的范围dos控制台界面按照输入提示输入数据（红色的数字即为输入的内容）：物理块(LackNum)：3谢谢阅读页号数（PageNum）：20页面序列(PageOrder)：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2谢谢阅读0 1 7 0 1进程的最大页号数为100，物理块、页面序列的值为int类型的范围。精品文档放心下载,.2.输出的形式输入数据后，按ENTER键就可在dos控制台界面得到结果。按照实验要求分别感谢阅读输出程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的精品文档放心下载工作过程。结果如下：首行是算法的名称，第二行是页号序列，接下来的3行数字是模仿物理块的情况，感谢阅读竖着看才是正确的结果，此图显示的是3块物理块时内存占用情况。之后显示缺页次谢谢阅读数和缺页率。3.程序所能达到的功能程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作精品文档放心下载过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的谢谢阅读页面个数为n，页面访问序列为P1,…,Pn，分别利用不同的页面置换算法调度进程的精品文档放心下载页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。感谢阅读,.4.测试数据,.二、概要设计1.抽象数据类型的定义程序中进程调度时间变量描述如下：constintMaxNumber=100;int PageOrder[MaxNumber];int Simulate[MaxNumber][MaxNumber];谢谢阅读int PageCount[MaxNumber];int PageNum,LackNum;double LackPageRate;boolfound;主要函数：voidprint();voidinit();voidoriginal();voidFIFO();voidOPI();voidLRU();2.主程序的流程Init()输入aa=1否否 a=2否a=3否a=4是

,.初始化全局变量：最小物理块数，页面个数，页面访问序列输出缺页次数和缺页率及模拟过程是 FIFO()是 OPI()是 LRU()结束,.3.程序各模块之间的层次(调用)关系1main() 调用 Init() 23

FIFO() Print()OPI() Print()LRU() Print()三、详细设计1.voidFIFO()original();Simulate[0][0]=PageOrder[0];谢谢阅读inttemp=0,flag=0;for(i=1;i<PageNum;i++){//判断该页面是否存在内存中for(j=0;j<BlockNum;j++){if(PageOrder[i]==Simulate[flag][j])感谢阅读,.break;}if(j==BlockNum){//该页面不在内存中for(k=0;k<BlockNum;k++){//模拟置换过程if(Simulate[flag][k]==NULL)谢谢阅读break;elseSimulate[i][k]=Simulate[flag][k];精品文档放心下载}//淘汰最先进入内存的页面temp++;temp=temp%BlockNum;Simulate[i][temp]=PageOrder[i];谢谢阅读LackNum++;flag=i;}//该页面在内存中else,.continue;}2.voidOPI()original();Simulate[0][0]=PageOrder[0];精品文档放心下载inttemp,flag=0;//flag表示上一个模拟内存的下标感谢阅读for(i=1;i<PageNum;i++){//判断该页面是否存在内存中for(j=0;j<BlockNum;j++){if(PageOrder[i]==Simulate[flag][j])谢谢阅读break;}//j!=BlockNum表示该页面已经在内存中if(j!=BlockNum)continue;,.//模拟置换过程for(k=0;k<BlockNum;k++){if(Simulate[flag][k]==NULL)精品文档放心下载break;elseSimulate[i][k]=Simulate[flag][k];感谢阅读}//内存中页面进行选择//两种情况：内存已满和内存未满for(j=0;j<BlockNum;j++){if(Simulate[i][j]==NULL){Simulate[i][j]=PageOrder[i];谢谢阅读LackNum++;flag=i;break;}},.if(j!=BlockNum)//内存未满continue;//内存已满temp=0;//temp表示要置换的页面内存下标谢谢阅读for(j=0;j<BlockNum;j++){//选取要置换的页面内存下标for(k=i+1;k<PageNum;k++){//最长时间内不被访问的页面if(Simulate[i][j]==PageOrder[k])精品文档放心下载{PageCount[j]=k;break;}}if(k==PageNum)//之后没有进行对该页面的访问PageCount[j]=PageNum;精品文档放心下载if(PageCount[temp]<PageCount[j])精品文档放心下载{,.temp=j;}}Simulate[i][temp]=PageOrder[i];精品文档放心下载LackNum++;flag=i;}3.voidLRU()original();Simulate[0][0]=PageOrder[0];精品文档放心下载inttemp,flag=0;//flag表示上一个模拟内存的下标PageCount[0]=0;//最近的页面下标谢谢阅读for(i=1;i<PageNum;i++){//判断该页面是否存在内存中for(j=0;j<BlockNum;j++),.{if(PageOrder[i]==Simulate[flag][j])谢谢阅读{PageCount[j]=i;break;}}//j!=BlockNum表示该页面已经在内存中if(j!=BlockNum)continue;//模拟置换过程for(k=0;k<BlockNum;k++){if(Simulate[flag][k]==NULL)谢谢阅读break;elseSimulate[i][k]=Simulate[flag][k];精品文档放心下载}//内存中页面进行选择,.//两种情况：内存已满和内存未满for(j=0;j<BlockNum;j++){if(Simulate[i][j]==NULL){//内存未满Simulate[i][j]=PageOrder[i];谢谢阅读PageCount[j]=i;LackNum++;flag=i;break;}}if(j!=BlockNum)continue;//内存已满temp=0;//temp表示要置换的页面内存下标精品文档放心下载for(j=0;j<BlockNum;j++){//最近最久时间内不被访问的页面if(PageCount[temp]>PageCount[j])精品文档放心下载temp=j;},.Simulate[i][temp]=PageOrder[i];感谢阅读PageCount[temp]=i;LackNum++;flag=i;}}四、调试分析1.发现的问题在编写程序的最初，界面不是很好，看着很乱。最后求的缺页率也不是谢谢阅读用百分数表示。2.算法的性能分析(包括基本操作和其它算法的时间复杂度和空间复感谢阅读杂度的分析)及其改进设想；该程序的的时间复杂度还算理想，是O(m*n),空间复杂度也是一样，复杂谢谢阅读度为O(m*n),均不需要再改进了。3.解决方法界面使用空格填充，使各行各列对齐。,.对于输出百分数，将缺页率乘以100，后加%输出。4.经验和体会通过二次编程，又一次加深了对先进先出（FIFO）页面置换算法，最佳感谢阅读（OPI）置换算法，最近最久未使用（LRU）置换算法的理解。感谢阅读同时，也掌握了一些使界面输出看起来更工整的办法。还有，在平时做作业的时候，总是默认为物理块数是3，其实只是比较感谢阅读常用而已，并不是每次都是3.这个在编程中有体现，在今后做题中会更注意。感谢阅读五、用户使用说明(1)用户根据提示输入物理块数(2)输入页面个数(3)依次输入页面访问个数(4)根据提示选择算法，输入对应的数字。六、测试结果列出测试结果，包括输入和输出。,.,.七．附录#include<iostream>#include<iomanip>usingnamespacestd;constintMaxNumber=100;int PageOrder[MaxNumber];//页面序列P1,…,Pn，感谢阅读int Simulate[MaxNumber][MaxNumber];//模拟页面置换过程谢谢阅读int PageCount[MaxNumber];//谢谢阅读int PageNum,LackNum;//页面数，缺页数感谢阅读double LackPageRate;//缺页率boolfound;,.intBlockNum;inti,j,k;voidprint();voidinit();voidoriginal();voidFIFO();voidOPI();voidLRU();voidmain(){//cout<<setw(2)<<"";init();boold=true;while(d){cout<<"算法选择\nFIFO:输入'1'\nOPI: 输入'2'\nLRU: 输入感谢阅读'3'\nexit:输入'4'\n";intc;cin>>c;switch(c){,.case1:cout<<endl<<"先进先出FIFO页面置换算法：\n";精品文档放心下载FIFO();print();break;case2:cout<<endl<<"最佳页面OPI置换算法：\n";感谢阅读OPI();print();break;case3:cout<<endl<<"最近最久未使用LRU置换算法：\n";谢谢阅读LRU();print();break;case4:d=false;break;default:cout<<"你的输入有问题请重新输入！\n";break;},.}}voidinit(){cout<<"物理块数m: ";cin>>BlockNum;cout<<"页面个数n: ";cin>>PageNum;cout<<"页面访问序列P1,…,Pn\n";感谢阅读for(i=0;i<PageNum;i++)cin>>PageOrder[i];}voidoriginal(){for(i=0;i<PageNum;i++)for(j=0;j<BlockNum;j++)Simulate[i][j]=NULL;LackNum=1;},.voidprint(){//模拟三种算法的页面置换过程，//给出每个页面访问时的内存分配情况//每种算法的缺页次数和缺页率。LackPageRate=(double)LackNum/PageNum;精品文档放心下载for(i=0;i<PageNum;i++)cout<<setw(4)<<"";for(i=0;i<PageNum;i++)cout<<setw(4)<<PageOrder[i];感谢阅读for(i=0;i<PageNum;i++)cout<<setw(4)<<"";for(j=0;j<BlockNum;j++){//for(i=0;i<PageNum;i++)//cout<<setw(4)<<"";for(i=0;i<PageNum;i++)if(Simulate[i][j]==NULL)cout<<setw(4)<<'';elsecout<<setw(4)<<Simulate[i][j];感谢阅读cout<<endl;,.}//cout<<endl;cout<<"缺页次数:"<<LackNum<<endl<<"缺页率:"<<LackPageRate*100<<"%"<<endl<<endl;}感谢阅读voidFIFO(){//先进先出:最早出现的置换算法，总是淘汰最先进入内存的页面。谢谢阅读original();Simulate[0][0]=PageOrder[0];谢谢阅读inttemp=0,flag=0;for(i=1;i<PageNum;i++){//判断该页面是否存在内存中for(j=0;j<BlockNum;j++){if(PageOrder[i]==Simulate[flag][j])谢谢阅读break;},.if(j==BlockNum){//该页面不在内存中for(k=0;k<BlockNum;k++){//模拟置换过程if(Simulate[flag][k]==NULL)精品文档放心下载break;elseSimulate[i][k]=Simulate[flag][k];感谢阅读}//淘汰最先进入内存的页面temp++;temp=temp%BlockNum;Simulate[i][temp]=PageOrder[i];精品文档放心下载LackNum++;flag=i;}//该页面在内存中elsecontinue;}}voidOPI(){,.//最佳置换:选择的被淘汰的页面都是以后永不使用或者在最长（未来）时间内不被访问的页面。谢谢阅读original();Simulate[0][0]=PageOrder[0];感谢阅读inttemp,flag=0;//flag表示上一个模拟内存的下标谢谢阅读for(i=1;i<PageNum;i++){//判断该页面是否存在内存中for(j=0;j<BlockNum;j++){if(PageOrder[i]==Simulate[flag][j])精品文档放心下载break;}//j!=BlockNum表示该页面已经在内存中if(j!=BlockNum)continue;//模拟置换过程for(k=0;k<BlockNum;k++),.{if(Simulate[flag][k]==NULL)谢谢阅读break;elseSimulate[i][k]=Simulate[flag][k];感谢阅读}//内存中页面进行选择//两种情况：内存已满和内存未满for(j=0;j<BlockNum;j++){if(Simulate[i][j]==NULL){Simulate[i][j]=PageOrder[i];感谢阅读LackNum++;flag=i;break;}}if(j!=BlockNum)//内存未满continue;,.//内存已满temp=0;//temp表示要置换的页面内存下标谢谢阅读for(j=0;j<BlockNum;j++){//选取要置换的页面内存下标for(k=i+1;k<PageNum;k++){//最长时间内不被访问的页面if(Simulate[i][j]==PageOrder[k])感谢阅读{PageCount[j]=k;break;}}if(k==PageNum)//之后没有进行对该页面的访问PageCount[j]=PageNum;精品文档放心下载if(PageCount[temp]<PageCount[j])精品文档放心下载{temp=j;}},.Simulate[i][temp]=PageOrder[i];精品文档放心下载LackN