操作系统原理课程设计模拟存储器管理.doc

上海电力学院课程设计报告课程名称： 操作系统原理 题目名称： 模拟存储器管理 姓 名：  学 号： 班 级： 同 组 姓 名： 实验时间： 11.12.2912.01.5 成 绩：   评 语： 目录目录.2一、 设计内容及要求.3二、 详细设计.32.1原理概述.32.2主要数据结构.32.3算法流程图.42.3.1主程序算法流程图.42.3.2 optimal算法流程图.52.3.3 FIFO算法流程图.62.3.4 LRU算法流程图.7三、 实验结果与分析.83.1 optimal页面置换算法结果与分析.83.2 FIFO 页面置换算法结果与分析.93.3 LRU 页面置换算法结果与分析.93.4 推出界面结果.11四、 设计总结.11附录.12课程设计题目:模拟存储器管理一、设计内容及要求编写程序模拟虚拟存储器管理。假设为M页的作业分配了N块内存（N<M）。输入：系统分配的块数，页面引用序列。输出：显示每一次页面引用内存状态。分别使用下面的页面置换算法：（1）FIFO页面置换算法：（2）LRU页面置换算法：（3）最佳页面置换算法：钱万里负责构思 叶阳伟 负责编写二、详细设计1）原理概述用一个数组page_table存储就绪页面队列的序号和所在物理块号，用另一个数组memory_table存储物理块中页面序号和该物理块被使用情况输出-1表示该物理块未被暂用。2） 主要数据结构结构体：Page结构体存储就绪队列页面的相关情况struct pageint page_num;/页号int memory_num;/所在物理块号int P;/状态位 0表示不在内存物理块中 1表示在物理块中;Memory结构体用来构造物理块的相关使用情况struct memoryint memory_page_num;/物理块中此刻存在的页面序号int page_n;/页面执行顺序号int A;/访问字段;相关参数：page_size用来限定页面就绪队列数由用户键入，memory_size表示分配的物理块数由用户键入page_table500 存储就绪队列，限定该队列最多为500，500可以修改memory_table100表示总共物理块数及每个物理块的使用情况，可用物理块为100，可以修改其大小3） 算法（流程图）主程序流程图：Optimal算法流程图：FIFO算法流程图LRU算法流程图：源程序文件名：虚拟存储器管理.cpp 执行文件名:虚拟存储器管理.exe三、 实验结果与分析1. 当输入t=1时选择 optimal页面置换算法所谓的最佳页面置换算法就是 其选择的被淘汰页面将是以后永不使用，或许是在最长时间内不再被访问的页面。采用最佳页面置换通常可保证获得最低的缺页率。现假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1用最佳页面置换算法就会得到下列物理块使用情况：页面号引用串70120304230321201701物理块使用情况777222227000040001133311前三个7 0 1可以直接进入内存，由于7是未来最长时间不被使用的，所以把7换成2，得到2 0 1序列。由于0 已经在内存中，所以不需要替换，1是未来最长时间不被使用的，所以把1换成3，得到2 0 3序列由于0在内存中则无需替换，又由于0是未来最长时间不被使用的所以把0替换成4，得到2 4 3序列。又由于2、3已在内存中，所以不要替换。由于4在以后不被使用，所以用0 代换4.得到2 0 3序列。又由于3、2已在内存中，所以不需要替换。又由于3在以后不被使用，所以把3替换成1.，得到2 0 1序列。又由于2、0、1已在内存中，所以无需替换。又由于2在以后不被使用，所以把2替换成7，得到7 0 1序列。又由于0、1已在内存中，所以不需替换。实验结果与预想相同。2、当输入2选择FIFO页面置换函数所谓先进先出页面置换算法，就是总是淘汰最先进入内存的页面。假定系统为莫进程分配了三个物理块，并考虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1经FIFO函数预算后将得到下列关系：页面号引用串70120304230321201701物理块使用情况777222444000777000333222111001110003332221前三个7 0 1 可以直接进入内存，由于7最先进入内存，则将7换成2，得到 2 0 1。由于0在内存中，则无需置换。由于0最先进入内存，则把0替换成3得到2 3 1.由于1最先进入内存，则把1换成0得到2 3 0.由于2最先进入内存，则把2换成4，得到4 3 0.由于3最先进入内存，则把3换成2.得到4 2 0。由于0最先进入内存，则把0换成3，得到4 2 3.由于4最先进入内存，则把4换成0，得到0 2 3.由于2 3 已在内存中，则无需置换。由于2最先进入内存，则把2换成1得到0 1 3.由于3最先进入内存，则把3换成2，得到0 1 2。由于0已在内存，则无需置换。由于0最先进入内存，则把0换成7，得到7 1 2.由于1最先进入内存，则把1换成0，得到7 0 2.由于2最先进入内存，则把2换成1，得到7 0 1.实验结果与预想结果一样；3、 输入3进入LRU页面置换算法 所谓的最近最久为使用页面置换算法（LRU）是选择最近最久未使用的页面予以淘汰。该算法富裕每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰； 现假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1经最近最久未使用页面置换算法得到下列信息： 页面号引用串70120304230321201701物理块使用情况777224440111000000333001133222227 前三个7 0 1可以直接 进入内存，由于7最近最久未使用，则把7换成2得到2 0 1.由于0已在内存中，则无需置换。由于1最近醉酒未使用，则把1换成3得到2 0 3.由于0已在内存中，则无需置换。由于2最近最久未使用，则把2换成4得到4 0 3。由于3最近最久未使用，则把3换成2，得到4 0 2.由于0最近最久未使用，则把0换成3得到4 3 2 。由于4最近最久未使用，则把4换成0，得到0 3 2，由于3 2已在内存，则无需置换。由于0最近最久未使用，则把0换成1，得到1 3 2.由于2已在内存中，则无需置换。由于3最近最久未使用，则把3换成0得到1 0 2。由于1已在内存中，则无需置换。由于2最近最久未使用，则把2换成7得到1 0 7.由于0 1已在内存中，则无需置换。实验结果与预想结果相同。假如有以下页面号引用序列：4 7 0 7 1 0 1 2 1 2 6经LRU算法运算之后得出以下结果：页面号引用串47071012126物理块使用情况44444444446777777777700000000011111112222由于前五个序列中有重复的页面号，则不能直接全部调用，先调入前三个4 7 0 ，则后一个7已在内存中，无需置换，然后1进来，0也在内存中，则无需置换，下个1也在内存中则无需置换，然后2进如内存，后面的1 2也都在内存中，所以无需置换，6不在内存中而且物理块全部被暂用，就要考虑置换了，由于4是最近最久未使用使用，则把4换成6得到6 7 0 1 2。4、选择功能0则进入推出界面四、 设计总结通过本次课程设计，我学到不少东西。比如解决多重循环跳出问题，以前没敢用goto语句，因为大家都说它不太好，破坏了程序的结构。不过有时候用起来还蛮方便的，便于编写，也便于理解。这是我这次收获的最大的好处。不过在编写程序的时候也遇到很多问题：1、 optimal算法：首先对这个算法的理解，一开始觉得这个算法真的蛮好的，不过实现起来还真像书上所说的有点难度，如果下一个要执行的页面已在内存中则无需置换，但如果不在内存中，就要考虑到置换了。我先是用memory .page_n记录内存中的页面在以后出现的时间，然后用men记录他们中的最大时间，然后这个最大时间就是说在未来最近一段时间不会被使用，然后我就用下一个页面序号替换内存中的在以后最长时间不被使用的页面。2、 FIFO算法：这个算法是最容易实现的，思路很简单。就是逐个替换内存块中页面，以实现先进先出的功能。如果下一个要执行的页面已在内存中，则无需置换，如果不在内存中，则要考虑置换了。我用m标记将要呗置换的物理块序号，该物理块被替换后，m+1，这样下一次替换的就是下一个物理块，就这样，先进来的总是先出去。3、 LRU算法LRU算法，我感觉也蛮有意思的，我一开始想到的是把进入内存的页面都标记为1，出内存的和不在内存的我都标记为0，然后下一次需要替换的时候，我就从前往后查找为1 的页面，首先找到的肯定是最近最久未使用的，然后把下一个要执行的页面与此页面做置换。然后我又想到了一个方法，就是每执行一次页面，就给每个页面memory .A+1,再用maxcount标记出A最大的物理块，A值越大说明该页面在物理块中呆的时间越长，第一次是把第一块物理块的-1换成等待页面序列的第一个，然后memory0.A置0，这样maxcount标记的就变成第二块物理块了，然后以此类推，每个物理块将被逐个置换。总之，通过这次课程设计，我是学到了很多东西，不仅仅是编程能力提高了，分析问题的能力也有所提高，我会再接再厉。附录：程序源代码/ 本程序内容是关于 页面置换算法的模拟 / 包含 最佳页面置换算法(OPtimal) / 先进先出页面置换算法(FIFO) / / 最近最久未使用页面置换算法(LRU) /#include<iostream>using namespace std;struct pageint page_num;/页号int memory_num;/所在物理块号int P;/状态位 0表示不在内存物理块中 1表示在物理块中;struct memoryint memory_page_num;/物理块中此刻存在的页面序号int page_n;/页面执行顺序号int A;/访问字段;int page_size,memory_size;/页面大小 物理块大小page page_table500;/存储页面memory memory_table100;void reset()/页面 物理块初始化cout<<"请输入页面大小:"cin>>page_size;for(int i=0;i<page_size;i+)page_tablei.page_num=-1;page_tablei.memory_num=-1;page_tablei.P=0;/for(int i=0;i<page_size;i+)cout<<"请输入物理块数:"cin>>memory_size;for(int j=0;j<memory_size;j+)memory_tablej.memory_page_num=-1;memory_tablej.page_n=-1;memory_tablej.A=0;/for(int j=0;j<memory_size;j+)/void reset()void creat()/创建页面和内存分块cout<<"请输入需访问的页面序号:"for(int i=0;i<page_size;i+)cin>>page_tablei.page_num;/for(int i=0;i<page_size;i+)/void creat()/ optimal最佳置换算法 /void optimal()int mem=0;/记录等待队列中与内存中序号相同的队列号int num=0;/页面号计数器for(int i=0;i<memory_size;i+)/前几个未重复的可直接送入内存for(int v=0;v<memory_size;v+)if(page_tablenum.page_num=memory_tablev.memory_page_num)num+;if(num>=page_size)goto begin;/if(page_tablenum.page_num=memory_tablev.memory_page_num)/for(int v=0;v<memory_size;v+)memory_tablei.memory_page_num=page_tablenum.page_num;memory_tablei.page_n=num;page_tablenum.P=1;num+;/cout<<"此时在内存中的页面序号是:"<<endl;for(int j=0;j<memory_size;j+)cout<<memory_tablej.memory_page_num<<" "cout<<endl; /for(int i=0;i<memory_size;i+)begin:while(num<page_size)/如果下一个需要操作的页面在内存中则无需更换for(int m=0;m<memory_size;m+)if(page_tablenum.page_num=memory_tablem.memory_page_num)num+=1;goto begin;/if(page_tablenum.page_num=memory_tablem.memory_page_num)/for(int m=0;m<memory_size;m+)/如果下一个等待页面不在内存中则根据最佳置换准则进行对换int q=0;loopp:for(;q<memory_size;)for(int h=num;h<page_size;h+)if(memory_tableq.memory_page_num=page_tableh.page_num)/找出内存中页面在等待序列中需等待的时间最长的序号if(h>mem)mem=h;/记录与当前内存页面号相等的 在等待序列中第一次出现的等待队列序号memory_tableq.A=1;/如果在等待序列中找到与内存中相等的页面序号 则给该物理块做标记q+;goto loopp;/if(memory_tableq.memory_page_num=page_tableh.page_num)if(h=page_size-1)&&(page_tableh.page_num!=memory_tableq.memory_page_num)/如果内存中此页面在以后不再出现则直接替换掉memory_tableq.memory_page_num=page_tablenum.page_num;num+=1;for(int l=0;l<memory_size;l+)cout<<memory_tablel.memory_page_num<<" "cout<<endl;page_tablenum.memory_num=0;goto begin;/if(h=page_size-1)&&(page_tableh.page_num!=memory_tableq.memory_page_num)/for(int h=num;h<page_size;h+)/for(;q<memory_size;)for(int g=0;g<memory_size;g+)if(memory_tableg.memory_page_num=page_tablemem.page_num)memory_tableg.memory_page_num=page_tablenum.page_num;mem=0;num+=1;for(int l=0;l<memory_size;l+)cout<<memory_tablel.memory_page_num<<" "cout<<endl;page_tablenum.memory_num=0;/if(memory_tableg.memory_page_num=page_tablemem.page_num)/for(int g=0;g<memory_size;g+)for(int gg=0;gg<memory_size;gg+)memory_tablegg.A=0;/while(num<page_size)/void optimal()/ 先进先出页面置换算法 /void FIFO()int num=0;/页面计数器int m=0;/物理块计数器int aa=0;for(int i=0;i<memory_size;i+) for(int v=0;v<memory_size;v+) if(page_tablenum.page_num=memory_tablev.memory_page_num) num+; if(num>=page_size) goto begin; /if(page_tablenum.page_num=memory_tablev.memory_page_num) /for(int v=0;v<memory_size;v+) memory_tablei.memory_page_num=page_tablenum.page_num; memory_tablei.page_n=num; page_tablenum.P=1; num+; /cout<<"此时在内存中的页面序号是:"<<endl; for(int j=0;j<memory_size;j+) cout<<memory_tablej.memory_page_num<<" " cout<<endl; /for(int i=0;i<memory_size;i+)begin:while(num<page_size)for(int k=0;k<memory_size;k+)if(page_tablenum.page_num=memory_tablek.memory_page_num)num+;goto begin;/if(page_tablenum.page_num=memory_tablek.memory_page_num)/for(int k=0;k<memory_size;k+)/如果下一个页面不在内存中，则按照先进先出页面置换方法进行下列操作memory_tablem.memory_page_num=page_tablenum.page_num;num+;m+;m=m%memory_size;for(int l=0;l<memory_size;l+)cout<<memory_tablel.memory_page_num<<" "cout<<endl;/while(num<page_size)/void FIFO()/ LRU页面置换算法 /void LRU()int num=0;for(int i=0;i<memory_size;i+)for(int v=0;v<memory_size;v+)if(page_tablenum.page_num=memory_tablev.memory_page_num)num+;if(num>=page_size)goto begin;/if(page_tablenum.page_num=memory_tablev.memory_page_num)/for(int v=0;v<memory_size;v+)memory_tablei.memory_page_num=page_tablenum.page_num;memory_tablei.page_n=num;page_tablenum.P=1;num+;/cout<<"此时在内存中的页面序号是:"<<endl;for(int j=0;j<memory_size;j+)cout<<memory_tablej.memory_page_num<<" "cout<<endl; /for(int i=0;i<memory_size;i+)begin: while(num<page_size) /cout<<"如果下一个要执行的页面已经在内存中则无需进行页面置换"<<endl;for(int k=0;k<memory_size;k+)if(page_tablenum.page_num=memory_tablek.memory_page_num)page_tablememory_tablek.page_n.P=0;memory_tablek.page_n=num;page_tablenum.P=1;num+;goto begin;/if(page_tablenum.page_num=memory_tablek.memory_page_num)continue;/for(int k=0;k<memory_size;k+)/如果下一个要执行的页面不在内存中 则根据LRU算法执行下列代码for(int l=0;l<page_size;l+)for(int a=0;a<memory_size;a+)if(page_tablel.page_num=memory_tablea.memory_page_num)&&(page_tablel.P=1)page_tablememory_tablea.page_n.P=0;memory_tablea.memory_page_num=page_tablenum.page_num;memory_tablea.page_n=num;page_tablenum.P=1;num+;/cout<<"此时在内存中的页面序号为:"<<endl;for(int b=0;b<memory_size;b+)cout<<memory_tableb.memory_page_num<<" "cout<<endl;goto begin;/if(page_tablel.page_num=memory_tablea.memory_page_num)&&(page_tablel.P=1)continue;/for(int a=0;a<memory_size;a+)/for(int l=0;l<page_size;l+)/void LRU()int main()while(1)int t;cout<<" "<<endl;cout<<" *"<<endl;cout<<" *菜单*"<<endl;cout<<" * 0.退出 1.optimal算法 2.FIFO算法 3.LRU算法 *"<<endl;cout<<" *"<<endl;cout<<" "<<endl;cout<<"请输入你要选择的功能:"cin>>t;switch (t)case 0:cout<<" "<<endl; cout<<" 模拟虚拟存储器管理 "<<endl; cout<<" "<<endl; cout<<" (c)All Right Reserved "<<endl; cout<<" 由2009252班 叶阳伟 钱万里 编写 "<<endl; cout<<" 2012年1月2日完成 "<<endl; cout<<" "<<endl; break;case 1:cout<<"- 欢迎使用 optimal页面置换算法-"<<endl;reset();