虚拟内存页面置换算法

...wd......wd......wd...实验五虚拟内存页面置换算法TOC\o"1-3"\h\u16277一、需求分析1161181.输入的形式和输入值的范围292002.输出的形式225883.程序所能到达的功能374204.测试数据417955二、概要设计5203671.抽象数据类型的定义5261342.主程序的流程614873.程序各模块之间的层次(调用)关系718856三、详细设计7282221.voidFIFO() 7257342.voidOPI() 8307883.voidLRU() 1012603四、调试分析11250771.发现的问题11215922.算法的性能分析(包括基本操作和其它算法的时间复杂度和空间复杂度的分析)及其改进设想；11269213.解决方法11147814.经历和体会1225112五、用户使用说明121329六、测试结果1218459七．附录14需求分析需求在进程运行过程中，假设其所访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出，需根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。置换算法的好坏，将直接影响到系统的性能。一个好的页面置换算法，应具有较低的更好频率。从理论上讲，应将那些以后不再访问的页面换出，或把那些在较长时间内不再访问的页面调出。实验目的通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出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)：70120304230321201701进程的最大页号数为100，物理块、页面序列的值为int类型的范围。2.输出的形式输入数据后，按ENTER键就可在dos控制台界面得到结果。按照实验要求分别输出程序模拟先进先出FIFO、最正确置换OPI和最近最久未使用LRU页面置换算法的工作过程。结果如下：首行是算法的名称，第二行是页号序列，接下来的3行数字是模仿物理块的情况，竖着看才是正确的结果，此图显示的是3块物理块时内存占用情况。之后显示缺页次数和缺页率。3.程序所能到达的功能程序模拟先进先出FIFO、最正确置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1,…,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。4.测试数据概要设计1.抽象数据类型的定义程序中进程调度时间变量描述如下：constintMaxNumber=100;intPageOrder[MaxNumber];intSimulate[MaxNumber][MaxNumber]; intPageCount[MaxNumber]; intPageNum,LackNum; doubleLackPageRate; boolfound;主要函数：voidprint();voidinit();voidoriginal();voidFIFO();voidOPI();voidLRU();2.主程序的流程3.程序各模块之间的层次(调用)关系详细设计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; else Simulate[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; else Simulate[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; else Simulate[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;intPageOrder[MaxNumber];//页面序列P1,…,Pn，intSimulate[MaxNumber][MaxNumber];//模拟页面置换过程intPageCount[MaxNumber];//intPageNum,LackNum;//页面数，缺页数doubleLackPageRate;//缺页率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)<<''; else cout<<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; else Simulate[i][k]=Simulate[flag][k]; } //淘汰最先进入内存的页面 temp++; temp=temp%BlockNum; Simulate[i][temp]=PageOrder[i]; LackNum++; flag=i; }//该页面在内存中 else continue; }}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; else Simulate[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; } } Simulat