设计一个虚拟存储区和内存工作区

齐齐哈尔大学操作系统课程综合实践题目：_主界面以灵活选择某算法_班级： 计本093 : 学号： 2009021114 指导教师： 韩金库 2008年12月主界面以灵活选择某算法实验摘要：计算机应用专业的学生全面了解和掌握系统软件,一般软件设计方法和技术的必不可少的综合课程,也是了解计算机硬件和软件如何衔接的必经之路。我觉得此次实验最大的亮点以及不同于别人的地方就是将三种页面置换算法按照课本上老师讲的方式直观简便的输出，在采用输出算法时，我摒弃了常人所用的一维数组输出法，而别出心裁的采用了二维数组的输出算法，模拟了内存的物理块，清晰直观的表达了页面是如何在外存中被调入内存中的，以及各页面在调入过程中是否命中或在置换时又置换了内存中哪个页面。在软件工程的角度来看，我的系统具有高内聚低耦合的优点，即各种算法之间，并不影响彼此的函数调用，而在各算法的内部，内聚度很高。关键词：设计原理,设计方案,流程图,源代码，测试结果，结束语，参考文献课题运行环境操作系统：WindowsXP编程环境：MicrosoftVisualC++6.01.1实验内容：通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。熟悉虚拟存储管理的各种液面置换算法，并辨析恶魔你程序实现请求页式存储管理的页面置换算法。设计一个虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程,并计算访问命中率。设计要求：主界面以灵活选择某算法，且以下算法都要实现1、 先进先出算法（FIFO）2、 最近最久未使用算法（LRU）3、 最佳置换算法（OPT）2.1运行环境1） 操作系统：WindowsXP2） 编程环境：MicrosoftVisualC++6.03.1设计原理：3.1.1先进先出算法（FIFO）最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。该算法将所有使用的内存页面构成一个循环列队，每次置换时将队列中的队首唤出，队首指针后移一位即可，算法容易实现牡丹石最先进入内存的野末必将来就不用再到，甚至可能很快就会用到，所以不能保证有效的缺页率，算法性能较差。3.2.2最近最久未使用算法（LRU）FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（LeastRecentlyUsed，LRU）。LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时,LRU算法选择过去一段时间里最久未被使用的页面。LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：（1） 计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。这样做，不仅要查页表，而且当页表改变时（因CPU调度）要维护这个页表中的时间，还要考虑到时钟值溢出的问题。（2） 栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。一种LRU近似算法是最近未使用算法(NotRecentlyUsed,NUR)。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在最近一段时间里它未被访问过。3.3.3最佳置换算法(OPT)最优置换(OptimalReplacement)是在理论上提出的一种算法。其实质是：当调入新的一页而必须预先置换某个老页时，所选择的老页应是将来不再被使用，或者是在最远的将来才被访问。采用这种页面置换算法，保证有最少的缺页率。但是最优页面置换算法的实现是困难的，因为它需要人们预先就知道一个进程整个运行过程中页面走向的全部情况。不过，这个算法可用来衡量(如通过模拟实验分析或理论分析)其他算法的优劣。该算法能保证有最低的缺页率，所以称为最佳置换算法，但是该算法紧紧是一种理想状况下的算法，因为在进程实际运行过程中，将来会执行到那儿页是不可预知的，所以无法选择该置换那个页出去。因此，本算法在实际中无法使用，只能作为一种标准来衡量其他算法的性能4.1设计方案1）主界面：设置页面产生算法选择界面和页面置换算法选择界面；2）子界面：页面产生算法分为两个界面，分别是随机产生算法和自己输入产生算法。页面置换算法分为三个子界面，分别是先进先出算法界面、最近最久未使用算法界面、最佳置换算法界面。5.1流程图主流程图图（1）FIFO函数流程图：•退出■图（2）LRU函数流程图：startstartvoidInitL()qval=Equation(fold,b);Oval>=0Tb[val].time=0;Getmax()for(i=0;i<Bsize；i++)if(i!=val)b[i].time++;Getmax()endl图（4）OPT函数流程图：1rfindExist(i)1rfindExist(i)1rfindSpace()1rfindReplace()rStart退出图（5）源代码程序代码#include<iostream>#include<time.h>#include<math.h>#defineBsize3#definePsize12#include<string>usingnamespacestd;intQString[Psize];intNum=0;structpageInfor{intcontent;inttimer;};classYZ_replace{public:YZ_replace();~YZ_replace();intfindSpace();intfindExist(intcurpage);intfindReplace();voidFIFO();voidOPT();voidBlockClear();voidinitia1(intstring[]);pageInfor*block;intmemory_state[Bsize][Psize];ints;private:};voidP_String(intQString[]){inti;srand((unsigned)time(NULL));for(i=0;i<Psize;i++){QString[i]=rand()*9/RAND_MAX+1;}cout<<"页面走向：”；for(i=0;i<Psize;i++){cout<<QString[i]<<"";}cout<<endl;}YZ_replace::YZ_replace()s=0;block=newpageInfor[Bsize];for(inti=0;i<Bsize;i++){block[i].content=-1;

block[i].timer=0;}}voidYZ_replace::initia1(intQString[]){intj;page=newpageInfor[Psize];for(inti=0;i<Psize;i++){page[i].content=QString[i];page[i].timer=0;}for(i=0;i<Psize;i++)for(j=0;j<Bsize;j++)memory_state[j][i]=0;}YZ_replace::~YZ_replace()s=0;intYZ_replace::findSpace(){for(inti=0;i<Bsize;i++)if(block[i].content==-1)returni;return-1;}intYZ_replace::findExist(intcurpage){for(inti=0;i<Bsize;i++)if(block[i].content==page[curpage].content)returni;return-1;}intYZ_replace::findReplace(){intpos=0;for(inti=0;i<Bsize;i++)if(block[i].timer>=block[pos].timer)pos=i;returnpos;}voidYZ_replace::FIFO(){intexist,space,position;for(inti=0;i<Psize;i++){exist=findExist(i);if(exist!=-1){for(intb=0;b<Bsize;b++){memory_state[b][i]=memory_state[b][i-1];}s++;}elsespace=findSpace();if(space!=-1){for(intb=0;b<Bsize;b++){memory_state[b][i]=memory_state[b][i-1];}block[space]=page[i];memory_state[space][i]=block[space].content;}else{for(intb=0;b<Bsize;b++){memory_state[b][i]=memory_state[b][i-1];}position=findReplace();block[position]=page[i];memory_state[position][i]=block[position].content;}}for(intj=0;j<Bsize;j++)block[j].timer++;voidYZ_replace::BlockClear(){for(inti=0;i<Bsize;i++){block[i].content=-1;block[i].timer=0;}}typedefstructpage{intnum;inttime;}Page;Pageb[Bsize];Pagecall[Bsize];intc[Bsize][Psize];intqueue[100];intK;voidInitL(Page*b,intc[Bsize][Psize]){inti,j;for(i=0;i<Bsize;i++){b[i].num=-1;b[i].time=Psize-i-1;}for(i=0;i<Bsize;i++)for(j=0;j<Psize;j++)c[i][j]=-1;}intGetMax(Page*b){inti;intmax=-1;inttag=0;for(i=0;i<Bsize;i++)if(b[i].time>max)max=b[i].time;tag=i;}}returntag;}intEquation(intfold,Page*b){inti;for(i=0;i<Bsize;i++){if(fold==b[i].num)returni;}return-1;}voidLru(intfold,Page*b){inti;intval;val=Equation(fold,b);if(val>=0){b[val].time=0;for(i=0;i<Bsize;i++)if(i!=val)b[i].time++;}else{queue[++K]=fold;val=GetMax(b);b[val].num=fold;b[val].time=0;for(i=0;i<Bsize;i++)if(i!=val)b[i].time++;}}voidYZ_replace::OPT()intexist,space,position;for(inti=0;i<Psize;i++){exist=findExist(i);if(exist!=-1){for(intb=0;b<Bsize;b++){memory_state[b][i]=memory_state[b][i-1];}s++;}else{space=findSpace();if(space!=-1){for(intb=0;b<Bsize;b++){memory_state[b][i]=memory_state[b][i-1];}block[space]=page[i];memory_state[space][i]=block[space].content;else{for(intk=0;k<Bsize;k++){memory_state[k][i]=memory_state[k][i-1];for(intj=i;j<Psize;j++){if(block[k].content!=page[j].content){block[k].timer=1000;}else{block[k].timer=j;break;}}}position=findReplace();block[position]=page[i];memory_state[position][i]=block[position].content;}}intdecide(stringstr){for(inti=0;i<str.size();i++){if(str[i]<'0'||str[i]>'9'){return0;break;}}returni;}inttrans(stringstr){intsum=0;for(inti=0;i<str.size();i++)sum=sum+(str[i]-'0')*pow(10,str.size()-i-1);returnsum;}intput()inta,d;stringstr;cin>>str;a=decide(str);while(a==0){cout<<"输入错误，请重新输入！"<<endl;cin>>str;a=decide(str);}d=trans(str);returnd;}voidPut(){cout<<"请选择产生页面的方法a:随机产生b输入产生"<<endl;cout<<"您选择的菜单是:";charF;cin>>F;while(F!='a'&&F!='b')cout<<"输入错误，请重新输入:";cin>>F;}if(F=='a')P_String(QString);if(F=='b'){cout<<"请输入各页面号:"<<endl;for(inti=0;i<Psize;i++){QString[i]=put();}}cout<<endl;cout<<"| --|"<<endl;}voidmain(){cout<<"|页面置换算法cout<<"|页面置换算法|"<<endl;cout<<"|--|"<<endl;intt=1;while(t){Put();YZ_replacetest1;YZ_replacetest3;charselect;do{<3>OPTcout<<"请选择要应用的算法:<1>FIFO算法<2>LRU算法<3>OPT算法<0>退出"<<endl;intp,q;cout<<"请您输入菜单号:";cin>>select;while(select!='0'&&select!='1'&&select!='2'&&select!='3'){cout<<"您的输入无效请重新输入:"<<endl;cin>>select;}if(select=='0')

cout<<"您选择的是菜单<0>"<<endl;cout<<"完成退出."<<endl;t=0;}if(select=='1'){cout<<"您选择的是菜单<1>"<<endl;cout<<"FIFO算法状态:"<<endl;test1.initia1(QString);test1.FIFO();"<<endl;test1.BlockClear();"<<endl;cout<<" for(p=0;p<Bsize;p++){for(q=0;q<Psize;q++)cout<<test1.memory_state[p][q]<<cout<<endl;}cout<<"<<endl;cout<<"命中率:"<<test1.s<<7"<<Psize<<endl;test1.~YZ_replace();cout<<endl;}if(select=='2'){inti,j;K=-1;InitL(b,c);for(i=0;i<Psize;i++){Lru(QString[i],b);c[0][i]=QString[i];for(j=0;j<Bsize;j++)c[j][i]=b[j].num;}cout<<"您选择的是菜单<2>"<<endl;cout<<"LRU算法状态:"<<endl;cout<<"<<endl;cout<<for(i=0;i<Bsize;i++)for(j=0;j<Psize;j++){if(c[i][j]==-1)cout<<"0";elsecout<<""<<c[i][j];}cout<<""<<endl;}cout<<" "<<endl;cout<<"命中率:"<<(Psize-(K+1))<<7"<<Psize;cout<<'\t';cout<<endl;}if(select=='3'){cout<<"您选择的是菜单<3>"<<endl;cout<<"OPT算法状态:"<<endl;test3.initia1(QString);test3.OPT();test3.BlockClear();cout<<"<<endl;for(p=0;p<Bsize;p++){for(q=0;q<Psize;q++)cout<<test3.memory_state[p][q]<<cout<<endl;}cout<<" "<<endl;cout<<"命中率:"<<test3.s<<7"<<Psize<<endl;test3.~YZ_replace();cout<<endl;}}while(select=='1'||select=='2'||select=='3');}}测试结果页面选择测试：亡“C:\DocuMcntaandSettings\Ad*inist工氐七口工'桌面\赵硏秋kz—qOl\DGb*ug\zMqO1・cse| |贝直|置挟算法 ht选拌产空贝旬的方法制迫机产空m输入产三亠肉菜单是m飞丢，请重新输入:a口：241948684499<2讪註<3>0PTMfe絢腿出图（7.1）图（图（7.1）图（7.2）分析：页面产生的方法有两种选择，分别是随机产生和自己输入产生，选择菜单的时候有对异常输入的处理，如果输入错误，有错误提示，当输入正确菜单的时候，选择a,自动产生页面走向，如果选择b,自己可以任意输入，如果输入错误，有错误提示。应用算法选择测试-IIA.F 页面置换箒法—IA.麻命云空亍面語去红补随初产ZEb：^A产王ho的菜单是5页面走口：36/2751/73213清淸您FI尊:1<1旳清淸您FI尊:1<1旳0蚤-用单桑丹荚是试要入的、迄□33222277711B6666S553333B07777999222

图（7.3）分析：选择算法时，有异常处理，即如果输入错误，有错误提示。如果选择菜单1，即选择了FIFO算法，展示此算法的置换状态并显示命中率。置换状态以二维数组的形式输出，既直观又清晰。讥、C-\DocuMen±sandSettings\AdMin.istrator\^®1\Debug\_ziLqO1aezes埠Fs埠FI>F■1海>當江<1的蒼一:月鱼蕙应栗是杭SA^fe<2>LRU^/J<3>0PI^法<0》退出命屮率：2/12帚远拝应月药算Yt：<l>EiFU^i<2>LKU^袪Mu算址IX态：33322ZS992Z206655555333300???7777711图（7.4）分析：算法一进行完以后，界面自动跳到应用算法的选择界面，即可以再次选择置换算法，选择菜单2，即选择了LRU算法，展示此算法的置换状态并显示命中率，可以和第一个算法进行对比，找出两种算法的不同。图（7.5）分析：算法二进行完以后，界面自动跳到应用算法的选择界面，即可以再次选择置换算法，选择菜单3,即选择了OPT算法，展示此算法的置换状态并显示命中率，可以和第二个算法进行对比