请求页式存储管理及请求页式存储管理中常用页面置换算法模拟

软件学院操作系统实验报告专业：软件工程班级：RB软工互学号：学生姓名：指导教师：PAGE第16页共16页实验四：请求页式存储管理一．实验目的深入理解请求页式存储管理的原理，重点认识其中的地址变换、缺页中断、置换算法等实现思想。二．实验属性该实验为综合性、设计性实验。三．实验仪器设备及器材普通PC386以上微机四．实验要求本实验要求4学时完成。本实验要求完成如下任务：（1）建立相关的数据结构：存储块表、页表等；（2）实现基本分页存储管理，如分配、回收、地址变换；（3）在基本分页的基础上实现请求分页存储管理；（4）给定一批作业/进程，选择一个分配或回收模拟；（5）将整个过程可视化显示出来。实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告（参见附录A），并要求用正规的实验报告纸和封面装订整齐，按时上交。五、实验提示1、本实验虽然不以前面实验为基础，但建议在其界面中继续增加请求页式存储管理功能。2、数据结构：内存分配表、页表空间（用数组实现），修改PCB结构增加页表指针、页表长度。3、存储管理：编写内存分配、内存回收算法、页面置换算法。4、主界面设计：在界面上增加一个请求分页内存分配按钮、请求分页内存回收按钮、装入指定进程的指定页按钮。触发请求分页内存分配按钮，弹出作业大小输入框，输入后调用内存分配函数，在内存分配表和页表中看到分配的存储块。触发请求分页内存回收按钮，弹出进程ID输入框，输入后调用内存回收函数，在内存分配表中看到回收后的状态改变。功能测试：从显示出的内存分配表和页表，可查看操作的正确与否。六、实验步骤任务分析：1.最佳页面置换算法（OPT）：其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。2.最近最久未使用（LRU）算法：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。程序设计：程序功能模块图如下：请求分页式储存管理最近最久未使用算法先进先出算法请求分页式储存管理最近最久未使用算法先进先出算法（1）在同一进程中的各个线程，都可以共享该进程所拥有的资源，这表现在：所有线程都具有相同的地址空间（进程的地址空间）。此外我们应该还要用控制语句，控制线程的同步执行。

2.

这个实验是要求我们采用算法模拟分页存储管理技术的FIFO和LRU算法。所以我们应该先生成地址序列，有了地址序列，我们要找到它所在的虚页，然后通过查找实页，再判断下一步动作。假如要访问的虚页不在内存中，不命中，我们要替换实页内容。根据FIFO算法，直接替换最早进入内存中的那一页就可以了。所以可以设立一个循环指针，记录那个最早进入内存中的那页。而对于LRU算法，我们要替换是到现在为止最长时间没被访问的页，在这里我们可以用一个队列来表示内存。把最久没使用的页放在队头，然后替换进去的页放在队尾就可以了。假如要访问的虚页在内存中，明显是命中。对于FIFO算法，不处理，而对于LRU算法，我们还要把他的权值置0。开始（2）系统功能流程图：开始开始开始还有指令？还有指令？NN还有指令？还有指令？YY找到了吗？计算页号计算页号找到了吗？找到了吗？计算页号计算页号找到了吗？YYNN新页进入计算过程数组第一位，其余为一次下移计算命中率结束比较现有页面计数项的大小，新页面替换最大项页面计算命中率结束新页进入计算过程数组第一位，其余为一次下移计算命中率结束比较现有页面计数项的大小，新页面替换最大项页面计算命中率结束（3）算法分析1.先进先出

定义一个队列存放页面，头指针记录最先进入队列的页面的位置，每次替换头指针指向的页面。2.最近最少使用

定义一个二维数组，一维用来记录页面号，一维用来记录该页面被使用的次数，每次替换最近最少使用的页面（3）程序结果：在运行界面选择某个算法，运行结果，如图1，图2所示：图1图2调试与测试：1.第一道涉及线程的题编译时总是发生错误，原来编译这类程序在原有的编译语言后要加上-pthread.2.第二个分页算法我们在系统结构课已经做过这个实验，所以有了一定的了解，加上一点修改就能够使用了。所以没太花功夫。七、实验总结通过实现请求页式存储管理的几种基本页面置换算法，了解了虚拟存储技术的特点。通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解，也知道了几种算法的效率，也验证了LRU算法的命中率平均的比FIFO算法要高。通过本次实验，我收获了很多。我了解到编写程序不是首要任务，而是一种实现手段。我们最重要的是如何做好需求分析和理清思路，做出正确、简介的流程设计，这样可以达到事半功倍的效果。八、附录//#include<windows.h>//#include<iostream>#include"stdio.h"#include<conio.h>#include<malloc.h>#defineN16#definenum5/*进程分配物理块数目*/intA[N]={1,2,3,4,5,6,7,8,5,2,3,2,7,8,1,4};/*页表映像*/typedefstructpage{intaddress;/*页面地址*/structpage*next;}page;structpage*head,*run,*rear;voidjccreat()/*进程分配物理块*/{inti=1;page*p,*q;head=(page*)malloc(sizeof(page));p=head;for(i=1;i<=num;i++){q=(page*)malloc(sizeof(page));p->next=q;q->address=0;q->next=NULL;p=q;}rear=p;}intsearch(intn){page*p;inti=0;p=head;while(p->next){if(p->next->address==n){printf("Getitatthepage%d\n",i+1);run=p;return1;}p=p->next;i++;}return0;}voidchangeOPT(intn,intposition){inti;inttotal=0;intflag=1;intdistance[num];intMAX;intorder=0;page*p,*q;p=head->next;q=head->next;for(i=0;i<num;i++)distance[i]=100;i=0;while(p){if(p->address==0){flag=0;break;}p=p->next;i++;}if(!flag){p->address=n;printf("Changethepage%d\n",i+1);}else{while(q)}for(i=position;i<N;i++){if(q->address==A[i])distance[total]=i-position;}total++;q=q->next;}MAX=distance[0];for(i=0;i<num;i++){if(distance[i]>MAX){MAX=distance[i];order=i;}}printf("Changethepage%d\n",order+1);i=0;while(p){if(i==order)p->address=n;i++;p=p->next;}}voidchangeLRU(intn){inti=0;intflag=1;page*p,*delect;p=head->next;while(p){if(p->address==0){flag=0;p->address=n;printf("Changethepage%d\n",i+1);break;}p=p->next;i++;}if(flag){delect=head->next;head->next=delect->next;printf("Delectfromthehead,andaddnewtotheend.\n");delect->address=n;rear->next=delect;rear=delect;rear->next=NULL;}}floatOPT(){inti;intlose=0;floatlosef;floatpercent;for(i=0;i<N;i++){if(search(A[i])==0){lose++;changeOPT(A[i],i);}}losef=lose;percent=1-(losef/N);returnpercent;}floatLRU(){inti;intlose=0;floatlosef;floatpercent;page*p;for(i=0;i<N;i++){if(search(A[i])==0){lose++;changeLRU(A[i]);}else{p=run->next;run->next=p->next;rear->next=p;rear=p;rear->next=NULL;printf("Moveittoendofqueue.\n");}}losef=lose;percent=1-(losef/N);returnpercent;}main()/*主函数部分*/{floatpercent;intchoice;printf("Selectthearithmetic:\n(1)OPT\n(2)LRU\nyourchoiceis:");scanf("%d",&choice);/*选择页面置换算法*/jccreat();/*创建进程*/if(choice==1)/*采用OPT算法置换*/{percent=OPT();/*计算OPT时的缺页率*/printf("ThepercentofOPTis%f",percent);}elseif(choice==2)/*采用LRU算法置换*/{percent=LRU();/*计算LRU时的缺页率*/printf("ThepercentofOPTis%f",percent);elseprintf("Yourchoiceisinvalid.");getch();}信息工程学院实验报告成绩：课程名称：操作系统成绩：指导教师（签名）：实验项目名称：请求页式存储管理中常用页面置换算法模拟实验时间：指导教师（签名）：班级姓名：学号：一、实验目的:了解内存分页管理策略掌握调页策略掌握一般常用的调度算法学会各种存储分配算法的实现方法。了解页面大小和内存实际容量对命中率的影响。二、实验环境:PC机、windows2000操作系统、VC++6.0三、实验要求：本实验要求4学时完成。采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响；实现OPT算法(最优置换算法)

、LRU算法(LeastRecently)

、FIFO算法(FirstINFirstOut)的模拟；会使用某种编程语言。实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告，按时上交。四、实验内容和步骤：编写程序，实现请求页式存储管理中常用页面置换算法LRU算法的模拟。要求屏幕显示LRU算法的性能分析表、缺页中断次数以及缺页率。在上机环境中输入程序，调试，编译。设计输入数据，写出程序的执行结果。根据具体实验要求，填写好实验报告。五、实验结果及分析：实验结果截图如下：利用一个特殊的栈来保存当前使用的各个页面的页面号。当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，栈底是最近最久未被使用的页面号。当访问第5个数据“5”时发生了缺页，此时1是最近最久未被访问的页，应将它置换出去。同理可得，调入队列为：123456713205，缺页次数为12次，缺页率为80%。六、实验心得：本次实验实现了对请求页式存储管理中常用页面置换算法LRU算法的模拟。通过实验，我对内存分页管理策略有了更多的了解。最近最久未使用（LRU）置换算法的替换规则：是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。最佳置换算法的替换规则：其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。先进先出(FIFO)页面置换算法的替换规则：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。三种替换算法的命中率由高到底排列OPT>LRU>FIFO。本次的程序是在网上查找的相关代码然后自己进行修改，先自己仔细地研读了这段代码，在这过程中我对C++代码编写有了更深的了解。总之，本次实验使我明白要学会把课堂上的理论应用到实际操作中。我需要在今后熟练掌握课堂上的理论基础，只有坚实的基础，才能在实际操作中更得心应手。附录：#include"iostream.h"#include<iomanip.h>constintDataMax=100;constintBlockNum=10;intDataShow[BlockNum][DataMax];//用于存储要显示的数组boolDataShowEnable[BlockNum][DataMax];//用于存储数组中的数据是否需要显示intData[DataMax];//保存数据intBlock[BlockNum];//物理块intcount[BlockNum];//计数器intN;//页面个数intM;//最小物理块数intChangeTimes;voidDataInput();//输入数据的函数voidDataOutput();voidLRU();//LRU函数///*intmain(intargc,char*argv[]){DataInput();//DataInput();LRU();return0;}//*/voidDataInput(){cout<<"请输入最小物理块数：";cin>>M;while(M>BlockNum)//大于数据个数{cout<<"物理块数超过预定值，请重新输入：";cin>>M;}cout<<"请输入页面的个数：";cin>>N;while(N>DataMax)//大于数据个数{cout<<"页面个数超过预定值，请重新输入：";cin>>N;}cout<<"请输入页面访问序列："<<endl;for(inti=0;i<N;i++)cin>>Data[i];}voidDataOutput(){inti,j;for(i=0;i<N;i++)//对所有数据操作{cout<<Data[i]<<””;}cout<<"\n"<<endl;for(j=0;j<M;j++){cout<<"";for(i=0;i<N;i++)//对所有数据操作{if(DataShowEnable[j][i])cout<<DataShow[j][i]<<"|";elsecout<<"|";}cout<<endl;}cout<<"\n缺页次数:"<<ChangeTimes<<endl;cout<<"缺页率:"<<ChangeTimes*100/N<<"%"<<endl;}voidLRU(){inti,j;boolfind;intpoint;