页式虚拟存储管理缺页中断的模拟系统的设计

《操作系统》课程设计报告书-1-燕山大学课程设计说明书课程设计名称：操作系统OS题目：页式存储管理中页面置换（淘汰）的模拟程序班级：计算机应用二班开发小组名称：CAMPUS课题负责人：课题组成员：姓名学号班级自评成绩课题开发日期：2011-1-10至2011-1-14《操作系统》课程设计报告书-2-一．概述1目的通过分析、设计和实现页式虚拟存储管理缺页中断的模拟系统，熟悉和掌握请求分页式存储管理的实现过程，重点掌握当请求页面不在内存而内存块已经全部被占用时的替换算法，熟悉常见替换算法的原理和实现过程，并利用替换算法的评价指标——缺页次数和缺页率，来对各种替换算法进行评价比较。2.主要完成的任务自行输入实际页数、内存可用页面数、存取内存时间、存取快表时间及缺页中断时间，然后由用户随机输入各页面号，模拟系统自动运行出FIFO、LRU、OPT、LFU四种算法的缺页次数、缺页率、命中率、总存取时间、存取平均时间等结果。3使用的开发工具（1）使用系统：Windows7（2）使用语言：C++（3）开发工具：VisualC++6.04解决的主要问题设计的结果程序能实现FIFO、OPT、LRU、LFU算法模拟页式存储管理缺页中断，主要能够处理以下的问题：(1)用户能够输入给作业分配的内存块数；(2)用户能够输入给定的页面，并计算发生缺页的次数以及缺页率；(3)程序可由用户输入页面序列；(4)系统自动计算总存取时间及平均存取时间。二使用的基本概念和原理1.概念FIFO即先进先出页面置换算法，该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。《操作系统》课程设计报告书-3-LRU即最近最久未使用页面置换算法，该算法选择最近最久未使用的页面予以淘汰。OPT即最佳值换算法，其选择淘汰的页面是在最长时间内不再被访问的页面。LFU即最近使用最少页面置换算法，其淘汰的页面是最近一段时间内使用最少的页面。缺页中断存取页面时页面不在内存中需从外存调入的现象。缺页次数即在存取页面过程中发生缺页中断的次数。命中率在存取过程中页面在内存中次数占页面存取总次数的百分比。总存取时间即存取所有页面所消耗的总时间。存取平均时间即存取一次页面平均所用的时间。2.原理页式存储管理把内存分割成大小相等位置固定的若干区域，叫内存页面，内存的分配以“页”为单位，一个程序可以占用不连续的页面，逻辑页面的大小和内存页面的大小相同，内外存的交换也以页为单位进行，页面交换时，先查询快表，若快表中找不到所需页面再去查询页表，若页表中仍未找到说明发生了缺页中断，需先将所需页面调入内存再进行存取。三．总体设计通过对所解决的问题的实质的分析，即使用不同的算法对页表进行查询，分查到和查不到两种情况进行处理，主要是采用面向过程的技术路线，把解决问题的方法进行分步处理。软件主要采用函数调用的总体结构，把各种替换算法分别用函数实现，在主函数中进行调用，各函数之间相互独立。整个程序的主要流程就是先输入问题中需要用到的各种数据，如页面序列，实际页数，内存中的页数和存取时间等等。然后我们可以选择相应的替换算法进行分析替换，得到相应的存取时间和缺页情况。具体的流程图如下：图1请求分页流程图《操作系统》课程设计报告书-4-开始请求页面序列结束？内存块已满？利用替换算法，选择内存块中应该被替换的页面进行替换，修改页表选择将要调入页面放入未被占用的内存块中,修改页表NYN结束Y页面在内存中？NY四．详细设计具体的设计使用的函数除了主函数中的输入输出函数外，大部分使用函数调用，所用的函数主要有四种替换算法函数FIFO,LRU,OPT,LFU以及所有替换算法中都要用到的查询函数Search,LFU中的使用次数最少函数Min,OPT中计算使用距离的函数Compfu,LRU中的最久未使用时间函数Max，各算法使用函数具体如下：voidmain(){intm=0,t=0,N=0;cout请输入实际页数：;cinm;Pro*p=newPro[m];//p是用来放页面的地方cout可用内存页面数endl;cinN;《操作系统》课程设计报告书-5-Pro*page=newPro[N];//page是放物理块的地方charc;intx,y,z;cout请输入存取内存时间(ns)endl;cinx;cout请输入访问快表时间(ns)endl;ciny;cout请输入缺页中断时间(ns)endl;cinz;floatn=0;Input(m,N,p,page);//m是页面的总长，N是物理块的长度do{coutf:FIFO页面置换endl;coutl:LRU页面置换endl;couto:OPT页面置换endl;coutu:LFU页面置换endl;cout按其它键结束endl;cinc;if(c=='f')//FIFO页面置换{FIFO(p,page,m,N,x,y,z);}if(c=='l')//LRU页面置换{LRU(p,page,m,N,x,y,z);}if(c=='o')//OPT页面置换{OPT(p,page,m,N,x,y,z);}if(c=='u')//OPT页面置换{LFU(p,page,m,N,x,y,z);}}while(c=='f'||c=='l'||c=='o'||c=='u');}以上为主函数的内容。下面为所调用的函数intSearch(inte,Pro*page,intN){for(inti=0;iN;i++){if(e==page[i].num)《操作系统》课程设计报告书-6-returni;}return-1;}查询函数Search的参数为所要查询的页号e，快表中的页号page、以及快表中页数N，最后的返回值为所要查询页号在快表中的位置i或查不到的返回值-1.voidFIFO(Prop[],Propage[],intm,intN,intx,inty,intz){inta=0;floatn=0;inti=0;intt=0;for(i=0;iN;i++){page[i].num=0;}cout页面置换情况:endl;for(i=0;im;i++){if(Search(p[i].num,page,N)=0){a+=(x+y);continue;}else{t=t%N;n++;page[t].num=p[i].num;t++;a+=(3*x+z);}}cout缺页次数：n缺页率：n/m命中率：1-n/m总存取时间：ans存取平均时间：a/mnsendl;}FIFO替换算法中使用的参数有实际页表p[],快表page[],实际页数m,内存可用页面数N,快表存取时间x,内存存取时间y,缺页中断时间z，最后的返回值是缺页次数n，缺页率，命中率，总存取时间以及平均存取时间。voidLRU(Prop[],Propage[],intm,intN,intx,inty,intz){inta=0;floatn=0;inti=0;intt=0;《操作系统》课程设计报告书-7-for(i=0;iN;i++){page[i].num=0;page[i].time=N+2-i;}cout页面置换情况:endl;while(im){//intk;t=Search(p[i].num,page,N);if(t=0){a+=(x+y);page[t].time=0;}Else{n++;t=Max(page,N);page[t].num=p[i].num;page[t].time=0;a+=(3*x+z);}for(intj=0;jN;j++){if(j==t)continue;page[t].time++;}i++;}cout缺页次数：n缺页率：n/m命中率：1-n/m总存取时间：ans存取平均时间：a/mnsendl;}LRU置换算法中的参数有实际页号p[],快表中的页号page[],实际页数m,内存可用页面数N,快表存取时间x,内存存取时间y,缺页中断时间z。返回值为缺页次数n，缺页率，命中率，总存取时间以及平均存取时间。intMax(Pro*page,intN){inte=page[0].time,i=0;intk=0;while(iN){《操作系统》课程设计报告书-8-if(epage[i].time){k=i;}i++;}returnk;}Max函数中的参数有快表中页号page,内存可用页数N。返回值是最近最久未使用的页面位置k。voidOPT(Prop[],Propage[],intm,intN,intx,inty,intz){inta=0;floatn=0;inti=0;intt=0;for(i=0;iN;i++){page[i].num=0;}while(im){a+=(x+y);if(Search(p[i].num,page,N)=0)i++;else{inttemp=0,cn;for(t=0;tN;t++){if(tempCompfu(page,i,t,p,m)){temp=Compfu(page,i,t,p,m);cn=t;}}page[cn]=p[i];n=n+1;i++;a+=(3*x+z);}}cout缺页次数：n缺页率：n/m命中率：1-n/m总存取时间：ans存取平均时间：a/mnsendl;《操作系统》课程设计报告书-9-}OPT置换算法中的参数有实际页号p[],快表中的页号page[],实际页数m,内存可用页面数N,快表存取时间x,内存存取时间y,缺页中断时间z。返回值为缺页次数n，缺页率，命中率，总存取时间以及平均存取时间。intCompfu(Pro*page,inti,intt,Prop[],intm){intcount=0;for(intj=i;jm;j++){if(page[t].num==p[j].num)break;elsecount++;}returncount;}Compfu函数中参数为快表中页号page,页面位置i,页面在快表中位置t,实际页表p[],实际页数m，返回值为下次使用的步数count。voidLFU(Prop[],Propage[],intm,intN,intx,inty,intz){inta=0;floatn=0;inti=0;intt=0;for(i=0;iN;i++){page[i].num=0;}for(i=0;iN;i++)page[i].time=0;cout页面置换情况:endl;for(i=0;im;i++){if(Search(p[i].num,page,N)=0){a+=(x+y);page[i].time++;continue;//}else{t=Min(page,N);tpage[t].num=p[i].num;page[t].time=0;《操作系统》课程设计报告书-10-n++;a+=(3*x+z);}}cout缺页次数：n缺页率：n/m命中率：1-n/m总存取时间：ans存取平均时间：a/mnsendl;}LFU置换算法中的参数有实际页号p[],快表中的页号page[],实际页数m,内存可用页面数N,快表存取时间x,内存存取时间y,缺页中断时间z。返回值为缺页次数n，缺页率，命中率，总存取时间以及平均存取时间。intMin(Propage[],intN){intk=0;intmin=page[0].time;for(inti=0;iN;i++){if(minpage[i].time)k=i;}returnk;}Min函数使用的参数为实际页号page[],内存可用页数N，返回值为置换位置k。五．编码设计1.开发环境的设置和建立本程序所使用的开发环境为Vi