操作系统课程设计存储管理

1、河南城建学院操作系统课程设计说明书设计题目： 存储管理 专 业： 计算机科学与技术 指导教师： 邵国金、薛冰、郭猛 班 级： 学 号： 姓 名： 李二萌 同 组 人： 杨森林、杨鹏飞、王伟超 计算机科学与工程系2013年 01 月 10 日前言本模拟系统实现了先进先出页面淘汰算法（FIFO）、最近最少使用LRU页面淘汰算法、最近未使用算法NUR、最少访问页面算法LFU和最佳淘汰算法OPT。同时系统可以随意设置当前分配给作业的物理块数。系统运行时，任意输入一个页面访问序列，可以设定不同的页面置换算法和物理块数，输出其页面淘汰的情况，计算其缺页次数和缺页率。系统结束后，比较同一个页面访问序列，可以

2、得出在不同的页面置换算法和物理块数的情况下，其产生的缺页次数和缺页率。使用FIFO算法，由于测试数据相同的页面比较少，所以采用FIFO算法时，需要置换的页面多，比较繁琐，没有优化效果，所以FIFO算法性能不好。使用LRU的算法，此组数据显示LRU的算法使用比较繁琐，总的来说，NUR、LFU、LRU算法介于FIFO和Optimial之间。通过系统模拟得出，optimal算法的性能高，LRU、NUR、LRU算法的性能次之，FIFO的算法性能最差，较少应用；由于optimal算法在实际上难于实现，所以实际应用一般用LRU算法。本设计的目的是是熟悉存储管理的设计方法，加深对请求分页式存储管理的认识。设

3、计中用到了数据结构中的相关知识，链表的操作，通过本设计可以加深的数据结构的理解。设计代码语言用到的是C语言，使用起来比较方便，可以在虚拟机和VC上直接运行。目录目录3一、系统环境41.1、硬件环境41.2、软件环境4二、设计目的5三、总体设计63.1、程序设计组成框图63.2、流程图7四、详细设计114.1、数据结构114.1.1页面类型114.1.2页面控制结构114.2.函数定义124.3.变量定义124.4.算法分析12五、调试与测试145.1、调试方法145.2、测试结果的分析与讨论14六、设计中遇到的问题15七、源程序清单16八、总结，收获与体会25九、参考文献26一、系统环境1.1

4、、硬件环境PC机一台，内存，2.0GHZ主频1.2、软件环境设计和实验将Windows环境下，gcc和虚拟机软件VMWare。 二、设计目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。要求：(1)通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：50%的指令是顺序执行的；25%的指令是均匀分布在前地址部分；25%的指令是均匀分布在后地址部分。具体的实施方法是：在0，319的指令地址之间随机选取一起点m；顺序执行一条指令，

5、即执行地址为m+l的指令；在前地址0，m+1中随机选取一条指令并执行，该指令的地址为m；顺序执行一条指令，其地址为m+1；在后地址m+2，319中随机选取一条指令并执行；重复上述步骤，直到执行320次指令。(2)将指令序列变换成为页地址流。设:页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32K。在用户虚存中，按每页存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条第9条指令为第0页(对应虚存地址为0，9)；第10条第19条指令为第1页(对应虚存地址为10，19)； 第310条第319条指令为第31页(对应虚存地址为310，319)。按以上方式，用户指令可组成3

6、2页。(3)计算并输出下述各种算法在不同内存容量下的命中率（要为以下各种算法定义数据结构）。先进先出的算法(FIFO)；最近最少使用算法(LRU)；最近最不经常使用算法(NUR/NRU/CLOCK)。三、总体设计3.1、程序设计组成框图Initialize()初始化函数Main()FIFO算法模块LRU算法模块LFU算法模块NUR算法模块OPT算法模块程序设计组成框图3.2、流程图开始还有指令吗结束计算出命中率在实存队列查找该页号计算出页号FIFO LRU开始还有指令吗计算出页号把新页放入栈顶，同时向下移动其余页号YYY在实存堆栈中查找该页号Y新页号按序加入实存队列N结束计算出命中率找到了吗找

7、到了吗新页块压入栈顶，栈底页号移出 LRU算法NYY是否有空闲页面？找到？在面中查找是否存在开始还有指令吗？计算出页号count+将该页导入内存页面，count=1从内存页面找出使用最少的页面当空闲页面计算出命中率结束NYN NUR算法NYY是否有空闲页面？找到？在页面中查找是否存在开始还有指令吗？计算出页号count=1将该页导入内存页面，count=1从内存页面找出最近未使用的页面当空闲页面计算出命中率结束NYN OPT算法NY是否有空闲页面？按早指令队列查找以后指令出每一面命中的距离，找出最大的或没命中的当空闲页面找到？在面中查找是否存在开始还有指令吗？计算出页号将该页导入空闲页面计算出

8、命中率结束NYYN四、详细设计本程序设计基本按照题目的要求进行。即首先用srand()和rand()函数定义和产生指令序列，然后将指令序列变成相应的页地址流，并针对不同的算法计算出相应的命中率。4.1、数据结构4.1.1页面类型Typedef structInt pn,pfn,count,time;pl_type;其中pn为页号,pfn为面号,count为个周期内访问该页面次数time为访问时间。4.1.2页面控制结构pfc_structintpn,pfn;struct pfc_struct*next;typedefstruct pfc_struct pfc_type;pfc_typepfcx

9、y,*free_head,*busy_head;pfc_type*busy_tail;其中：pfcxy定义用户进程虚页控制结构,*free_head为空页面头的指针,*busy_head为忙页面头的指针,*busy_tail为忙页面尾的指针。4.2.函数定义(1)void initialize():初始化函数,给每个相关的页面赋值。(2)void FIFO():计算使用FIFO算法时的命中率。(3)void LRU():计算使用LRU算法时的命中率。(4)void OPT():计算使用OPT算法时的命中率。(5)void LFU():计算使用LFU算法时的命中率。(6)void NUR():计

10、算使用NUR算法时的命中率。4.3.变量定义(1)int azllc;指令流数据组。(2)int pagezllc;每条指令所属页号。(3)int offsetzllc;每页装入10条指令后取模运算页号偏移值。(4)int pf:用户进程的内存页面数。(5)int zhihuan:页面失效次数。4.4.算法分析先进先出算法，即FIFO算法（First-In First-Out algorithm）。这种算法选择最先调入主存储器的页面作为被替换的页面。它的优点是比较容易实现，能够利用主储存器中页面调度情况的历史信息，但是没有反应程序的局部性。因为最先调入主存的页面，很有可能是经常使用的页面。最近

11、最少使用算法，即LFU（Least Frequently used algorithm）。这种算法选择近期最少访问的页面作为被替换的页面。显然这是一种非常合理的算法，因为到目前为止最少使用的页面，和可能也是将来最少访问的页面。该算法即充分利用了主存中吗调度的历史信息，又正确反映了程序的局部性。但是这种算法实现起来非常的困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时，要从所有的计数器中选择一个计数值最大的计数器。因此，通常使用如下一种简单的方法。最久没有使用算法。即LRU(Least Recently Used Algorithm)。这

12、种算法把近期最久没有被访问的页面作为被替换的页面。它把LFU算法中要记录数量上的多与少简化成判断有于无，因此实现起来比较容易。NUR算法在需要淘汰一页时，从哪些最近一个时期内未被访问的页面中任选一页淘汰。只要在页面中增加一个访问位即可实现。当某页被访问时，访问位置1.否则，访问位置0.系统周期性第对所有的引用位清零。当须淘汰一页时从那些访问位为0 的页中选择一页进行淘汰。如果引用位全为1或0，NRU算法退化为FIFO算法。最优替换算法，即OPT(Optimal Replacement Algorithm).s上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来

13、主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。当然这种假设不总是正确的。最好的算法是选择将来醉酒不被访问的页面作为被替换的页面，这种算法的命中率是最高的，它就是最有替换算法。要实现OPT算法，唯一的办法就是让程序先执行一遍，记录下实际的页地址流情况。根据这个页地址流才能找到药被替换的页面。显然这样做是不现实的。因此OPT算法只是一种理想化的算法，然而它也是一种很用的算法。实际上，经常把这种算法作为评价其他页面替换算法好坏的标准。在其他条件相同的情况下，哪一种算法的命中率与OPT算法最接近，那么，它就是一种比较好的页面替换算法。五、调试与测试5.1、调试方法 利用Vw

14、are虚拟机的命令，用touch创建文件，vi 进入文件，然后编写代码，运行程序。2、测试结果的分析与讨论 调试运行结果图5.2、测试结果的分析与讨论使用FIFO算法需要置换的页面多，比较繁琐，没有优化效果，所以FIFO算法性能不好。LRU的算法，此组数据显示LRU的算法使用比较繁琐，总的来说，NUR、LFU、LRU算法介于FIFO和Optimial之间。通过系统模拟得出，optimal算法的性能高，LRU、NUR、LRU算法的性能次之，FIFO的算法性能最差，较少应用；由于optimal算法在实际上难于实现，所以实际应用一般用LRU算法。六、设计中遇到的问题本次课程设计中我们遇到的问题是，一

15、开始没有弄清楚rand和sand函数的使用方法，以至于运行时的到的结果与实际算起来的不相符，后来查阅资料，上网浏览搜索相关信息后，终于弄明白了是怎么回事。函数rand()是真正的随机数生成器，而srand()会设置供rand()使用的随机数种子。如果你在第一次调用rand()之前没有调用srand()，那么系统会为你自动调用srand()。而使用同种子相同的数调用 srand()会导致相同的随机数序列被生成。 srand(unsigned)time(NULL)则使用系统定时/计数器的值做为随机种子。每个种子对应一组根据算法预先生成的随机数，所以，在相同的平台环境下，不同时间产生的随机数会是不同

16、的，相应的，若将srand（unsigned）time(NULL)改为srand(TP)（TP为任一常量），则无论何时运行、运行多少次得到的“随机数”都会是一组固定的序列，因此srand生成的随机数是伪随机数。还有就是开始代码编写完了之后，运行时OPT算法结果出错。这个问题是在我们讨论并仔细查看OPT算法的内容后修改的。七、源程序清单#include#include#include#define TRUE 1#define FALSE 0#define INVALID -1#define zllc 320 /指令流长#define xy 32 /虚页长#define clear 50 /清零周

17、期typedef struct /页面结构int pn;/页号int pfn;/页面框架号int count; /计数器int time;/时间pc;pc plxy;/页面线性结构typedef struct pfc_struct/页面控制结构，调度算法的控制结构int pn;int pfn;struct pfc_struct *next;pfc_type;pfc_type pfcxy,*free_head,*busy_head,*busy_tail;int zhihuan,azllc;/a 为指令序列int pagezllc,offsetzllc;/地址信息int initialize(in

18、t);/初始化模块int FIFO(int);/FIFO调度算法int LRU(int);/LRU调度算法int LFU(int);/LFU调度算法int NUR(int);/NUR调度算法int OPT(int);/OPT调度算法/*主函数*/int main()int s,i;srand(unsigned)time(NULL);s = rand()%320;for(i=0;izllc;i += 4)if(s319)printf(When i = %d,Error,s=%d,i,s);exit(0);ai = s;ai+1 = ai+1;ai+2 = rand()%(ai+1+1);ai+3

19、 = ai+2 + 1;s = rand()%(319-ai+3) +ai+3+1;if(ai+2318|s319)printf(a%d+2,a number which is:%d and s = %dn,i,ai+2,s);for(i=0;izllc;i+)/将指令序列变换为页地址流pagei = ai/10;offseti = ai%10;for(i=4;i=32;i+)printf(%2d page frames:t,i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);return 0;/*初始化相关的数据结构，pf表示内存的块数*/int initializ

20、e(int pf)int i;zhihuan = 0;for(i=0;ixy;i+)pli.pn = i;pli.pfn = INVALID;/质页面控制结构中的页号，页面为空pli.count = 0;/页面控制结构中访问次数pli.time = -1;/访问时间for(i=0;ipf-1;i+)/建立pfci-1与pfci之间的联系pfci.next = &pfci+1;pfci.pfn = i;pfcpf-1.next = NULL;pfcpf-1.pfn = pf-1;free_head = &pfc0;/空页面队列的头指针为pfc0return 0;/*先进先出算法，pf为用户进程的

21、内存页面数*/int FIFO(int pf)int i;pfc_type *p;/中间变量initialize(pf);/初始化数据结构busy_head = busy_tail = NULL;/忙页面头队列，为队列链接for(i=0;inext;/保存忙页面的下一个页面plbusy_head-pn.pfn = INVALID;/把这个页面换出，更新它的数据成员free_head = busy_head;/释放忙页面队列的第一个页面free_head-next = NULL;/表明此页面是空的组后一面busy_head = p;/更新页面的头队列指针p = free_head-next;fr

22、ee_head-pn = pagei;plpagei.pfn = free_head-pfn;free_head-next = NULL;/使busy的尾为空if(busy_tail = NULL)busy_tail = busy_head = free_head;else/把刚刚换进来的接在busy_tail的后面busy_tail-next = free_head;busy_tail = free_head;free_head = p;/下一个空页面printf(FIFO:%6.4f|,1-(float)zhihuan/320);return 0;/*最近最久未使用算法*/int LRU(

23、int pf)int min,minj,i,j,present_time;/minj为最小值下标initialize(pf);present_time=0;for(i=0;izllc;i+)if(plpagei.pfn = INVALID)/页面失效zhihuan+;if(free_head = NULL)/无空闲页面min = 32767;/设置最大值for(j=0;jplj.time&plj.pfn!=INVALID)min = plj.time;minj = j;free_head = &pfcplminj.pfn;/腾出一个单元plminj.pfn = INVALID;plminj.t

24、ime = 0;free_head-next= NULL;plpagei.pfn = free_head-pfn;/有空闲页面改为有效plpagei.time =present_time;free_head = free_head-next;/减少一个free页面elseplpagei.time = present_time;/命中则增加该页面的访问次数present_time+;printf(LRU:%6.4f|,1-(float)zhihuan/320);return 0;/*最近未使用算法*/int NUR(int pf)int i,j,dp,cont_flag,old_dp;/这个算法

25、用count用于访问位initialize(pf);dp = 0;for(i=0;inext = NULL;plpagei.pfn = free_head-pfn;plpagei.count = 1;free_head-pn = pagei;free_head = free_head-next;elseplpagei.count = 1;if(i%clear = 0)for(j=0;jxy;j+)plj.count = 0;printf(NUR:%6.4f|,1-(float)zhihuan/320);return 0;/*最少访问页面算法*/int LFU(int pf)int i,j,mi

26、n,minpage;initialize(pf);for(i=0;izllc;i+)if(plpagei.pfn = INVALID)/页面失效zhihuan+;if(free_head = NULL)/无空闲页面min = 32767;/获取count的使用频率最小的内存for(j=0;jplj.count&plj.pfn!=INVALID)min = plj.count;minpage=j;free_head = &pfcplminpage.pfn;plminpage.pfn = INVALID;plminpage.count=0;free_head-next=NULL;plpagei.p

27、fn = free_head-pfn;plpagei.count+;free_head = free_head-next;/减少一个free页面elseplpagei.count = plpagei.count+1;printf(LFU:%6.4f,1-(float)zhihuan/320);return 0;/*最佳置换算法*/int OPT(int pf)int i,j,k,l,max,maxpage;initialize(pf);for(i = 0; i zllc; i+)if(plpagei.pfn = INVALID)/页面失效 zhihuan+;max = maxpage = 0;if(free_head = NULL)/无页面空闲for(j = 0; j pf; j+