《面置换算法设计.docx》由会员分享，可在线阅读，更多相关《面置换算法设计.docx（30页珍藏版）》请在课桌文档上搜索。
1、舔作东挑锦福软计策兼题目页面置换算法专业计算机科学与技术小组组员:目录L设计目B2 .课设规定3 .系统分析34 .系统设计34.1 问题分析34.2程序整体框图54.3FIFO算法54.4LRU64. 5OPT算法75.功能与测试85. 1开始界面85. 2FIFO算法95.3LRU算法10105.4OPT算法6.结论11127.附录1.设计目的1、存储管理的重要功能之一是合理地分派空间。祈求页式管理是一种常用B虚拟存储管理技术。本次设计的目的是通过祈求页式存储管理中页面置换算法模拟设计，理解虚拟存储技术B特点，掌握祈求页式管理0页面置换算法。2、提高自己的程序设计能力、提高算法设计质量与程
2、序设计素质；2.课设规定设计一种祈求页式存储管理方案。并编写模拟程序实现之。规定包括：1 .过随机数产生一种指令序列，共320条指令。其地址按下述原则生成：5O%0指令是次序执行的；25%0指令是均匀分布在前地址部分；25%0指令是均匀分布在后地址部分；详细的实行措施是：在0,319的指令地址之间随机选区一起点M;次序执行一一条指令，即执行地址为M+10指令；在前地址O,M+1中随机选用一条指令并执行，该指令的地址为;次序执行一条指令，其地址为什+1；在后地址M+2,319中随机选用一条指令并执行；反复AE,直到执行320次指令。2.指令序列变换成页地址流设：（1）页面大小为1K；顾客内存容量
3、为4页到32页；顾客虚存容量为32K。在顾客虚存中，按每K寄存10条指令排列虚存地址，即320条指令在虚存中的寄存方式为：第0条一第9条指令为第0页（对应虚存地址为0,9）;第10条一第19条指令为第1页（对应虚存地址为10,19）；OOOOOOOOOOOOOOOOOOOOO第310条一第319条指令为第31页（对应虚存地址为310,319）;按以上方式，顾客指令可构成32页。3.计算并输出下述多种算法在不同样内存容量下的命中率。FIFO先进先出的J算法1.RU近来至少使用算法OPT最佳淘汰算法（先淘汰最不常用的页地址）3 .系统分析在多道程序环境下，要使程序运行，必须先为之创立进程。而创立进
4、程0第一步是将程序和数据装入内存。存储器实现的功能重要是内存分派等功能，本模拟系统所要实现日勺就是将进程的程序和数据装入内存（物理块）。详细需要实现B功能如下:1、读入进程大小，进行分页，确定每一页B指令地址范围；2、读入一种指令，确定其所在页面，读入内存物理块中。物理块空闲直接读入，物理块已满，指向下步操作。3、物理块已满，将要淘汰本来首先进入到内存中的J页面，即换出；然后将目前的指令地址页面读入物理块中，即换入。4 .系统设计4.1 问题分析分页存储管理，是将一种进程的逻辑地址空间提成若干个大小相等的片，称为页面或页，并为各页加以编号。对应地，也把内存空间提成与页面相似大小0若干个存储块，
5、称为物理块，在为进程分派内存时，以块为单位将进程中0若干个页分别装入到多种可以不相邻接B物理块中系统为每个进程建立一种页表，页表给出逻辑页号和详细内存块号对应的关系。一种页表中包括若干个表目，表目的自然序号对应于顾客程序中的页号，表目中的块号是该页对应的J物理块号。祈求页式存储管理方式是一种实现虚拟存储器0方式，是指在进程开始运行之前，不是装入所有页面，而是装入一种或零个页面，之后根据进程运行日勺需要,动态装入其他页面。当内存空间已满，而又需要装入新B页面时，则根据某种算法淘汰某个页面，以便装入新的页面。祈求页式存储管理重要需要处理如下问题:系统怎样获知进程目前所需页面不在主存；当发现缺页时，
6、怎样把所缺页面调入主存；当主存中没有空闲日勺页框时，为了要接受一种新页，需要把老0一页淘汰出去，根据什么方略选择欲淘汰的页面。4.2 程序整体框图Maillo函数图4-1程序整体框图由于该算法规模较小，可以将该系统划分为三块，分别是：FlFO算法模块、LRU算法模块、OPT算法模块。4.3 FIFO算法基于程序总是按线形次序来访问物理空间这一假设，总是淘汰最先调入主存0页面，即淘汰在主存中驻留时间最长0页面。LRIJ置换算法，是根据页面调入内存后的使用状况进行决策的J。由于无法预测各页面未来0使用状况，只能运用“近来0过去”作为“近来0未来B近似，因此，LRU置换算法是选择近来最久未使用B页面
7、予以淘汰。该算法赋予每个页面一种访问字段，用来记录一种页面自上次被访问以来所经历0次数count,当须淘汰一种页面时，选择既有页面中其COUnt值最大的，即近来最久未使用的页面予以淘汰。4.5OPT算法当要调入一页而必须淘汰旧页时，应当淘汰后来不再访问的页，或距目前最长时间后要访问的页。它所产生的缺页数至少。这只是一种理想的状况。图4-4OPT算法程序流程图5 .功能与测试5.1 界面顾客进入系统之后，会有一种选择算法的界面，如下图所示:选择内存容量，然后点击“随机生成页地址流”按钮，生成页地址流与页面走向，如下图所示：图5-1选择界面5.2FIFO算法顾客点击“FIFO算法”按钮，如下图所示
8、:5.3LRU算法顾客点击“LRU算法”按钮，如下图所示:5.4OPT算法顾客点击“OPT算法”按钮，如下图所示:6 .结论对于页面算法，我们平时上课时，只是懂得了页面置换算法是怎么做B,并没有想怎样去实现这些算法。在真正要做B时候才发现了问题。在这次课程设计0过程中，由于之前大家对可视化程序设计不怎么熟悉，在写代码的时候有了许多的麻烦。最终，在小组组员耐心看了某些C#的书，并且多方实践，终于完毕了这次课程设计。通过该设计，我们学会了存储器的管理内容，运用C#语言实现进程装入内存00过程，同步也对存储器管理0多种装入方式及内存分区有了更深0理解，尤其是页面置换算法的应用。但也应看到对于实际0存
9、储器应用尚有诸多地方不能实现真实，在此后B学习中应对所学知识做更深入B挖掘，对于多种算法应用更好的运用。7.附录程序源代码usingSystem;usingSystem-Collections.Generic;usingSystem-ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Linq;usingSystem.Text;usingSyStem.WindowsForms;namespacePageReplace(publicpartialclassForml:Form(publicintpage=newint32
10、0;publicstructStruPagepublicinipageNum;publicintflag;publicintcount;publicintdistance;)publicStruPageStruPage=newStrUPage32;外存上的)页面publicForm1()(InitializeComponentO;ComboBox1.DropDownStyle=ComboBoxStyle.DropDownList;for(inti=4;i=32;i+)(ComboBox1.Items.Add(i);)1privatevoidbtnRand_Click(objectsender,
11、EventArgse)intaddress=newint3201;this.rtboxAddress.Textthis.rtboxPage.Text=,;Randomram=newRandom();for(inti=0J317;)生成页地址流intm=ram.Next(319);addressi+=m+1;intm_=ram.Next(0,m+1);addressi+=m_+1;addressi+=ram.Next(m_+2,319);)for(intj=0;j320;j+)将页地址流转换为页面走向并输出pagej=addressj/10;this.rtboxAddress.Text+=add
12、ressj.ToString()+,t;this.rtboxPage.Text+=pagej.ToStringQ+t;this.btnFCFS.Visible=true;this.btnLRU.Visible=true;this.btnOPT.Visible=true;1privatevoidbtnFCFS_Click(objectsender,EventArgse)(/lhis.btnFCFS.BackColor=Color.Yellow;for(inti=O;i32;i+)初始化构造体struPagei.pageNum=i;struPagei.flag=O;struPagei!.count
13、=O;struPagei.distance=320;)intPageReplaceNum=O;/替代H勺页面数doubleShootRate;命中率intmemorySize=lnl32.Parse(ComboBoxLTexl);/内存的容量StringOutpulString=每次替代后的内存状态intpageLoadedNuin=0;己装入内存的页面数intarray=newinlmemorySize;暂存已装入内存的!页面号for(inti=O;imemorySize;i+)arrayi=-1;for(intj=0;j320;j+)(if(struPagepagejJ.flag=0)(P
14、ageReplaceNum+;ifCpageLoadedNum=memorySize)/内存空间已满(struPagearrayO.flag=O;for(intk=O;kmemorySize-1;k+)araykl=array!k+1;arraypageLoadedNum-1=pagej;struPagepagej.flag=1;1else/内存空间尚有空闲(struPagepagejl.flag=1;arraypageLoadedNum+=pagej;for(inti=0;imemorySize;i+)if(arrayi=-1)OutputString+=,;elseOUtputString
15、+=arrayi.ToSlring()+t;1OutputString+=n;ShootRate=1-pageReplaceNum/320.0;this.rtboxMemory.Text=;this.shooRateBox.Text=shootRate.ToString();this.rtboxMemory.Text=outputstring;)privatevoidbtnLRU_Click(objectsender,EventArgse)(for(inti=O;i32;i+)初始化构造体struPagei.pageNum=i;struPagei.flag=O;struPagei.count=
16、0;struPagei.distance=320;)intpageReplaceNum=O;/替代的I页面数doubleShe)OtRate;命中率intmemorySize=Inl32.Parse(comboBoxl.Texl);/内存R9容量Stringoutputstring=每次替代后的内存状态intPageLOadedNUm=0;已装入内存0页面数intarray=newintmemorySize;暂存已装入内存的J页面号for(inti=O;imemorySize;i+)arrayi=-1;for(intj=0;j320;j+)(struPagepagej.count=0;if(s
17、truPagepagej.flag=0)页面未曾装入内存(pageReplaceNum+;if(pageLoadedNum=memorySize)/内存空间已满intmax=O;for(intk=1;kstruPagearraymax.count)max=k;1进行页面替代struPagearraymax.flag=;struPagepagejl.flag=1;arraymax=pagej;fbr(intn=0;npageLoadedNum;n+)struPagearrayn.count+;)else/内存尚有空闲(struPagepagej.flag=l;arraypageLoadedNum
18、+=pagej;fbr(ints=0;spageLoadedNum;s+)StruPagefarraysiI.count+;else页面已转入内存for(intt=0;tpageLoadedNum;t+)struPagearrayt.count+;for(inti=0;imemorySize;i+)(if(arrayil=-1)OUtputString+=,t;elseOutputString+=arrayi.ToString()+t;1OutputString+=nn;1ShootRate=1-pageReplaceNum/320.0;this.rtboxMemory.Text=,r;thi
19、s.shootRatcBox.Text=shootRate.ToString();this.rtboxMemory.Text=OutputString;privatevoidbtnOPT_Click(objectsender,EventArgse)for(inti=0;i32;i+)初始化构造体struPagei.pageNum=i;struPagei.flag=0;struPagei.count=0;struPageli.distance=320;)intpageReplaceNum=0,替代H勺页面数doubleShootRate;命中率intmemorySize=Int32.Parse(
20、ComboBoxLText);/内存的容量StringOUtPUtStriIg=;每次替代后的内存状态intpageLoadedNum=0;已装入内存的页面数intarray=newinlmemorySize;暂存已装入内存FfJ页面号for(inti=O;imemorySize;i+)arrayi=-1;for(intj=O;j320;j+)(if(struPageagej.flag=O)页面未曾装入内存pageReplaceNum+;ifCpageLoadedNum=memorySize)内存空间已满intmax=O;for(intk=1;kstruPagearraymax.distanc
21、e)max=k;)进行页面替代struPagearraymax.flag=O;struPagelpage(jJ.flag=I;arraymax=agej;intn;for(n=j+1;n320;n+)求出替代页面的distanceif(pagen=pageljj)break;struPagepagej.distance=n-j;else内存尚有空闲struPagepagej.flag=1;arraypageLoadedNum+=pagej;intm;for(m=j+1;m320;m+)求出装入页面於JdiSlanCeif(pagem=pagej)break;1struPagepagej.dis
22、tance=m-j;)1else/页面已转入内存(intt;for(t=j+l;t320;t+)求出装入页面的Jdistanceif(paget=pagej)break;struPagepagej1.distance=t-j;)for(inti=O;imemorySize;i+)(if(arrayi=-1)OutputString+=,t;elseOUtputString+=arrayi.ToStringO+t;)OutputString+=n;1ShootRate=1-pageReplaceNum/320.0;this.rtboxMemory.Text=,;this.shootRateBox.Text=shootRate.ToString();this.rtboxMemory.Text=OutputString;
