资源预览内容
第1页 / 共28页
第2页 / 共28页
第3页 / 共28页
第4页 / 共28页
第5页 / 共28页
第6页 / 共28页
第7页 / 共28页
第8页 / 共28页
第9页 / 共28页
第10页 / 共28页
亲,该文档总共28页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
摘 要存储管理是操作系统主要任务之一,它的主要管理对象是内存,内存作为计算机稀有而宝贵的资源,怎样对内存进行高效有序的管理显得极为重要。本文采用虚拟存储技术中常用的请求分页管理对内存的管理进行简要的说明。在请求分页管理中,页面置换算法效率的高低直接影响系统的效率,因此寻求一种高效、稳定的页面置换算法是必须的。本文对页面置换算法常用的几种算法分别进行研究。首先以FIFO 算法为例,分别对不同物理块数、页面数进行模拟,得出增大物理块数可以有效的降低页面缺页率。其次,改变物理块数对不同的算法进行比较,得出以 OPT 算法的命中率最高,NUR 算法次之,再就是 LFU 算法和 LRU 算法,其次是 FIFO 算法。并对其中出现反常现象:有时候 FIFO 的命中率竟然比 OPT 的还高,和 FIFO 算法产生的 Belady 现象进行分析。【关键字】存储管理 虚拟存储 请求分页 页面置换算法 Belady 现象存储管理模拟实验报告一、 问题重述存储管理作为操作系统的主要任务之一,其管理的效率直接影响整个系统的效率。存储管理最常用的技术是虚拟存储技术,虚拟存储技术分为三类:请求分页、请求分段、请求段页存储管理。其中请求分页比较常用。为提高请求分页的命中率产生了许多优秀的算法,这些算法的效率如何、各自有什么特点、是否存在一种最好的算法等等。因此有必要对这下算法进行模拟找出这些算法的各自特点。二、 实验原理2.1 内存扩充就是借助大容量的辅存在逻辑上实现内存的扩充,来解决内存容不的问题。常用的内存扩充技术 :盖技术、换技术。2.2 局部性原理局部性原理是虚拟存储技术的理论前提。所谓局部性原理,是指程序执行较短时间内,所执行的指令地址和指令操作数地址分别局限在一定的区域,主要表现为:时间局部性 空间局部性局部性原理只要体现在:(1) 程序中的大部分指令是顺序执行的指令,少部分是转移和跳转指令。(2) 过程调用的嵌套深度不超过 5 层(3) 程序中存在相当多的循环结构。(4) 程序中存在相当多的对一定数据结构的操作2.3 系统流图三、 实验过程3.1, 命中率计算:命中率=(1-页面失效次数)/页地址流长度 算法符号说明(1) 进先出的算法(FIFO)(2) 最近最少使用的算法(LRU)(3) 最佳淘汰算法(OPT)(4) 最少访问页面算法(LFU)(5) 最近最不经常使用算法(NUR)3.2 FIFO 初探不采用模块设计。独自观察 FIFO 算法,代码如下:M 表示物理块数,n 表示页面数 an存储个页面进入顺序。for(j=0;jnext; plbusypf_head-pn.pfn=INVALID;freepf_head=busypf_head; /*释放忙页面队列的第一个页面*/freepf_head-next=NULL; /*表明还是缺页*/busypf_head=p;p=freepf_head-next; freepf_head-pn=pagei;plpagei.pfn=freepf_head-pfn;freepf_head-next=NULL; /*使 busy 的尾为 null*/if(busypf_tail=NULL)busypf_tail=busypf_head=freepf_head;elsebusypf_tail-next=freepf_head;busypf_tail=freepf_head;freepf_head=p;printf(FIFO:%6.4fn,1-(float)diseffect/320);return 0;3.3.5 LRU 算法实现int LRU (int total_pf) /*最近最久未使用算法 least recently used*/int min,minj,i,j,present_time; /*minj 为最小值下标*/initialize(total_pf);present_time=0;for(i=0;iplj.time&plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head= /腾出一个单元plminj.pfn=INVALID;plminj.time=0;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn; /有空闲页面,改为有效plpagei.time=present_time;freepf_head=freepf_head-next; /减少一个 free 页面elseplpagei.time=present_time; /命中则增加该单元的访问次数present_time+;printf(LRU:%6.4fn,1-(float)diseffect/320);return 0;3.3.6 NUR 算法实现 int NUR(int total_pf ) /*最近未使用算法 Not Used recently count 表示*/ int i,j,dp,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;inext=NULL;plpagei.pfn=freepf_head-pfn;freepf_head-pn=pagei;freepf_head=freepf_head-next;elseplpagei.counter=1;if(i%clear_period=0)for(j=0;jnext=NULL;plmaxpage.pfn=INVALID;plpagei.pfn=freepf_head-pfn;freepf_head=freepf_head-next;printf(OPT:%6.4fn,1-(float)diseffect/320);return 0;3.3.8 LFU 算法实现int LFU(int total_pf) int i,j,min,minpage;pfc_type *t;initialize(total_pf);for(i=0;iplj.counter&plj.pfn!=INVALID)min=plj.counter;minpage=j;freepf_head=plminpage.pfn=INVALID;plminpage.counter=0;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn; /有空闲页面,改为有效plpagei.counter+;freepf_head=freepf_head-next; /减少一个 free 页面elseplpagei.counter;plpagei.counter=plpagei.counter+1;printf(LFU:%6.4fn,1-(float)diseffect/320);return 0;四、实验结果分析4.1 独自观测 FIFO 结果 由图可知,适当的增加物理块数可以降低缺页率。4.2 各类算法的比较 为处理方便将结果输出到 ans.txt 中,方便观察。如下:4page framesFIFO:0.2562LRU:0.2531OPT:0.3031LFU:0.2812NUR:0.28125page framesFIFO:0.2969LRU:0.2906OPT:0.3500LFU:0.3219NUR:0.30946page framesFIFO:0.3375LRU:0.3281OPT:0.3844LFU:0.3375NUR:0.33447page framesFIFO:0.3563LRU:0.3563OPT:0.4031LFU:0.3563NUR:0.35008page framesFIFO:0.3937LRU:0.3750OPT:0.4531LFU:0.3937NUR:0.37199page framesFIFO:0.4219LRU:0.4094OPT:0.4844LFU:0.4156NUR:0.406210page framesFIFO:0.4375LRU:0.4313OPT:0.5062LFU:0.4313NUR:0.425011pageframes FIFO:0.4813LRU:0.4625OPT:0.5531LFU:0.4500NUR:0.465612page framesFIFO:0.5406LRU:0.4875OPT:0.5687LFU:0.4938NUR:0.487513page framesFIFO:0.5500LRU:0.5188OPT:0.5969LFU:0.5062NUR:0.543714page framesFIFO:0.5594LRU:0.5531OPT:0.6344LFU:0.5281NUR:0.546915page framesFIFO:0.5687LRU:0.5844OPT:0.6687LFU:0.5469NUR:0.581316page framesFIFO:0.5781LRU:0.5938OPT:0.6813LFU:0.5719NUR:0.596917page framesFIFO:0.5906LRU:0.6156OPT:0.6969LFU:0.6156NUR:0.615618page framesFIFO:0.6156LRU:0.6312OPT:0.7156LFU:0.6344NUR:0.653119page framesFIFO:0.6687LRU:0.6656OPT:0.7344LFU:0.6531NUR:0.671920Page framesFIFO:0.6875LRU:0.6969OPT:0.7500LFU:0.6719NUR:0.690621page framesFIFO:0.6906LRU:0.7094OPT:0.7688LFU:0.6969NUR:0.718822page framesFIFO:0.7125LRU:0.7219OPT:0.7969LFU:0.7156NUR:0.734423page framesFIFO:0.7156LRU:0.7406OPT:0.8125LFU:0.7250NUR:0.781224page framesFIFO:0.7281LRU:0.7625OPT:0.8187LFU:0.7406NUR:0.771925page framesFIFO:0.7469LRU:0.7750OPT:0.8344LFU:0.7594NUR:0.800026page framesFIFO:0.8125LRU:0.8000OPT:0.8500LFU:0.7812NUR:0.806327page framesFIFO:0.8313LRU:0.8187OPT:0.8594LFU:0.8031NUR:0.828128page framesFIFO:0.8438LRU:0.8375OPT:0.8688LFU:0.8344NUR:0.846929pageframes FIFO:0.868
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号