存储管理程序设计报告

一、课程设计的目的和要求存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本课程设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。1．过随机数产生一个指令序列，共320条指令。其地址按下述原则生成：①50％的指令是顺序执行的；②25％的指令是均匀分布在前地址部分；③25％的指令是均匀分布在后地址部分；#具体的实施方法是：A.在[0，B.319]的指C.令地址之间随机选区一起点M;B.顺序执行一条指E.令，F.即执行地址为M+1的指G.令；C.在前地址[0，I.M+1]中随机选取一条指J.令并执行，K.该指L.令的地址为M’;D.顺序执行一条指N.令，O.其地址为M’+1；E.在后地址[M’+2，Q.319]中随机选取一条指R.令并执行；F.重复T.A—E，U.直到执行320次指V.令。2．指令序列变换成页地址流设：（1）页面大小为1K；（2）用户内存容量为4页到32页；（3）用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条—第9条指令为第0页（对应虚存地址为[0，9]）；第10条—第19条指令为第1页（对应虚存地址为[10，19]）；。。。。。。。。。。。。。。。。。。。。。第310条—第319条指令为第31页（对应虚存地址为[310，319]）；按以上方式，用户指令可组成32页。成绩3.计算并输出下述各种算法在不同内存容量下的命中率。A.FIFO先进先出的算法B.LRR最近最少使用算法C.OPT最佳淘汰算法（先淘汰最不常用的页地址）D.LFR最少访问页面算法E.NUR最近最不经常使用算法二、课程设计环境要求1、硬件环境PC机一台，0.99G内存，2.00GHZ主频2、软件环境WindowsXP/2000系统，编程软件VC++。三、设计任务介绍及系统需求分析本课程设计主要的目的是编制页面置换算法FIFO、LRU、LFU、NUR和OPT的模拟程序,并模拟其在内存的分配过程。同时根据页面走向，分别采用FIFO、LRU、LFU、NUR和OPT算法进行页面置换，统计命中率；为简化操作，在淘汰一页时，只将该页在页表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。本程序实现了操作系统中页式虚拟存储管理中缺页中断理想型淘汰算法，该算法在访问串中将来再也不出现的或是在离当前最远的位置上出现的页淘汰掉。这样，淘汰掉该页将不会造成因需要访问该页又立即把它调入的现象。该程序能按要求随机确定内存大小，随机产生页面数，进程数，每个进程的页数，给进程分配的页数等，然后运用理想型淘汰算法对每个进程进行计算缺页数，缺页率，被淘汰的序列等功能。四、概要设计系统分为4个子模块：初始化模块，FIFO、LRU、LFU、NUR和OPT的五个算法模块。初始化模块：initialize()初始化函数，给每个相关的页面赋值。FIFO算法模块：计算使用FIFO算法时的命中率。LRU算法模块：计算使用LRU算法时的命中率。LFU算法模块：计算使用OPT算法时的命中率。NUR算法模块：计算使用LFU算法时的命中率。OPT算法模块：计算使用NUR算法时的命中率。五、详细设计本实验的程序设计基本上按照实验内容进行。即首先用srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。相关定义如下：1数据结构(1)页面类型typedefstruct{intpn,pfn,count,time;Main()FIFO算法模块LRU算法模块LFU算法模块NUR算法模块OPT算法模块initialize()初始化函数}pl-type;其中pn为页号,pfn为面号,count为一个周期内访问该页面的次数,time为访问时间.(2)页面控制结构pfc-struct{intpn,pfn;structpfc_struct*next;}typedefstructpfc_structpfc_type;pfc_typepfc_struct[xy],*free_head,*busy_head;pfc_type*busy_tail;其中pfc[xy]定义用户进程虚页控制结构,*free_head为空页面头的指针,*busy_head为忙页面头的指针,*busy_tail为忙页面尾的指针.2．函数定义（1）Voidinitialize():初始化函数,给每个相关的页面赋值.（2）VoidFIFO():计算使用FIFO算法时的命中率.（3）VoidLRU():计算使用LRU算法时的命中率.（4）VoidOPT():计算使用OPT算法时的命中率.（5）VoidLFU():计算使用LFU算法时的命中率.（6）VoidNUR():计算使用NUR算法时的命中率.3.变量定义(1)inta[zl]:指令流数据组.(2)intpage[zllc]:每条指令所属的页号.(3)intoffset[zllc]:每页装入10条指令后取模运算页号偏移值.(4)intpf:用户进程的内存页面数.(5)intdisaffect:页面失效次数.先进先出算法，即FIFO算法（First-InFirst-Outalgorithm）。这种算法选择最先调入主存储器的页面作为被替换的页面。它的优点是比较容易实现，能够利用主存储器中页面调度情况的历史信息，但是，没有反映程序的局部性。因为最先调入主存的页面，很可能也是经常要使用的页面。近期最少使用算法，即LFU算法（LeastFrequentlyUsedalgorithm）。这种算法选择近期最少访问的页面作为被替换的页面。显然，这是一种非常合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少访问的页面。该算法既充分利用了主存中页面调度情况的历史信息，又正确反映了程序的局部性。但是，这种算法实现起来非常困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时，要从所有计数器中找出一个计数值最大的计数器。因此，通常采用如下一种相对比较简单的方法。最久没有使用算法，即LRU算法（LeastRecentlyUsedalgorithm）。这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LFU算法中要记录数量上的多与少简化成判断有与无，因此，实现起来比较容易。NUR算法NUR在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。只要在页表中增设一个访问位即可实现。当某页被访问时，访问位置1。否则，访问位置0。系统周期性地对所有引用位清零。当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰。如果引用位全0或全1，NRU算法退化为FIFO算法。最优替换算法，即OPT算法（OPTimalreplacementalgorithm）。上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。显然，这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面，这种替换算法的命中率一定是最高的，它就是最优替换算法。要实现OPT算法，唯一的办法是让程序先执行一遍，记录下实际的页地址流情况。根据这个页地址流才能找出当前要被替换的页面。显然，这样做是不现实的。因此，OPT算法只是一种理想化的算法，然而，它也是一种很有用的算法。实际上，经常把这种算法用来作为评价其它页面替换算法好坏的标准。在其它条件相同的情况下，哪一种页面替换算法的命中率与OPT算法最接近，那么，它就是一种比较好的页面替换算法。1.页面调度模拟算法流程示例图2.页面调度模拟算法示例图开始产生指令地址初始化页表访问一个指令地址计算该地址所在的页号该页在主存？页表有无空白条款？所有增令地址已访问完？用FIFO算法淘汰一项打印增令地址，它所在的页号以及页表信息调入当前所需的页结束在主存不在主存有无访问完未访问完六、调试过程程序结果：从上述结果可知，在内存页面数较少（4~5页）时，五种算法的命中率差别不大，都是30%左右。在内存页面为7~18个页面之间时，5种算法的访内命中率大致在35%~60%之间变化。但是，FIFO算法与OPT算法之间的差别一般在6~10个百分点左右。在内存页面为25~32个页面时，由于用户进程的所有指令基本上都已装入内存，使命中率增加，从而算法之间的差别不大。比较上述5种算法，以OPT算法的命中率最高，NUR算法次之，再就是LFU算法和LRU算法，其次是FIFO算法。就本问题，在15页之前，FIFO的命中率比LRU的高。七、结论与体会这个程序基本完成了存储管理程序设计的目的与要求。不过其中也有一些不足之处，例如算法有点麻烦，有些句子不是很能理解。但是我通过上网查找资料，去图书馆借阅相关书籍解决了这些不足之处。本次课程设计主要可以分为两个阶段，在第一个阶段中，要了解五种算法的执行原理，内存的分配策略，内存调页策略；第二个阶段主要是编制程序和运行改善程序。通过编写程序可以更深入的理解算法和算法的特点。这次操作系统的课程设计，让我对实验原理有更深的理解，通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。并且这次课程设计把各个学科之间的知识融合起来，把各门课程的知识联系起来，对计算机整体的认识更加深刻。八、参考文献1、《计算机操作系统》汤子赢等西安电子科技大学出版社2、《操作系统教程题解与实验指导》孟静高等教育出版社2003年3、《C语言程序设计》田祥宏等西安电子科技大学出版社4、《软件工程》张燕李慧等5、《数据结构教程》（第三版）谢希仁等电子工业出版社附件：源程序清单#includestdlib.h#includestdio.h#includetime.h#defineTRUE1#defineFALSE0#defineINVALID-1#defineNULL0#definezllc320/*指令流长*/#definexy32/*虚页长*/#defineclear50/*清0周期*/typedefstruct/*页面结构*/{intpn;//页号logicnumberintpfn;//页面框架号physicalframenumberintcount;//计数器inttime;//时间}pc;pcpl[xy];/*页面线性结构---指令序列需要使用地址*/typedefstructpfc_struct/*页面控制结构，调度算法的控制结构*/{intpn;intpfn;structpfc_struct*next;}pfc_type;pfc_typepfc[xy],*free_head,*busy_head,*busy_tail;intzhihuan,a[zllc];/*a[]为指令序列*/intpage[zllc],offset[zllc];/*地址信息*/intinitialize(int);intFIFO(int);intLRU(int);intLFU(int);intNUR(int);intOPT(int);intmain(){ints,i;srand((unsigned)time(NULL));s=rand()%320;for(i=0;izllc;i+=4)/*产生指令队列*/{if(s0||s319){printf(Wheni==%d,Error,s==%d\n,i,s);exit(0);}a[i]=s;a[i+1]=a[i]+1;a[i+2]=rand()%(a[i+1]+1);a[i+3]=a[i+2]+1;s=rand()%(319-a[i+3])+a[i+3]+1;if((a[i+2]318)||(s319))printf(a[%d+2],anumberwhichis:%dands==%d\n,i,a[i+2],s