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

实验五虚拟内存页面置换算法一、需求分析.................................................................................................................................11.输入的形式和输入值的范围................................................................................................22.输出的形式............................................................................................................................23.程序所能达到的功能............................................................................................................34.测试数据................................................................................................................................4二、概要设计.................................................................................................................................51.抽象数据类型的定义............................................................................................................52.主程序的流程........................................................................................................................63.程序各模块之间的层次(调用)关系.....................................................................................7三、详细设计.................................................................................................................................71.voidFIFO()............................................................................................................................72.voidOPI()..............................................................................................................................83.voidLRU()...........................................................................................................................10四、调试分析...............................................................................................................................111.发现的问题..........................................................................................................................112.算法的性能分析(包括基本操作和其它算法的时间复杂度和空间复杂度的分析)及其改进设想；.................................................................................................................................113.解决方法..............................................................................................................................114.经验和体会..........................................................................................................................12五、用户使用说明.........................................................................................................................12六、测试结果.................................................................................................................................12七．附录.........................................................................................................................................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.主程序的流程Init()输入aa=1a=2a=3a=4结束初始化全局变量：最小物理块数，页面个数，页面访问序列输出缺页次数和缺页率及模拟过程FIFO()OPI()LRU()否是否否是是是否3.程序各模块之间的层次(调用)关系main()Init()FIFO()OPI()LRU()Print()Print()Print()调用123三、详细设计1.voidFIFO()original();Simulate[0][0]=PageOrder[0];inttemp=0,flag=0;for(i=1;iPageNum;i++){//判断该页面是否存在内存中for(j=0;jBlockNum;j++){if(PageOrder[i]==Simulate[flag][j])break;}if(j==BlockNum){//该页面不在内存中for(k=0;kBlockNum;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;}2.voidOPI()original();Simulate[0][0]=PageOrder[0];inttemp,flag=0;//flag表示上一个模拟内存的下标for(i=1;iPageNum;i++){//判断该页面是否存在内存中for(j=0;jBlockNum;j++){if(PageOrder[i]==Simulate[flag][j])break;}//j!=BlockNum表示该页面已经在内存中if(j!=BlockNum)continue;//模拟置换过程for(k=0;kBloc