操作系统存储管理实验报告.doc

摘 要存储管理是操作系统主要任务之一，它的主要管理对象是内存，内存作为计算机稀有而宝贵的资源，怎样对内存进行高效有序的管理显得极为重要。本文采用虚拟存储技术中常用的请求分页管理对内存的管理进行简要的说明。在请求分页管理中，页面置换算法效率的高低直接影响系统的效率，因此寻求一种高效、稳定的页面置换算法是必须的。本文对页面置换算法常用的几种算法分别进行研究。首先以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;jm;j+) /初始化bj，使其等于-1，表示开始时内存中无页面 bj=-1; i=0; j=0; printf(-n); while(iN) for(k=0;km;k+) /for循环判断内存中是否有该页面 if(bk=ai) printf(%d 内存中有这个页面,直接访问.n,ai); break; if(k=m) if(bm-10) bj=ai; count+; printf(%d 页面进入内存,产生第%d次缺页.n,bj,count); j+; j=j%m; else count+; printf(%d %d被置换出去,产生第%d次缺页.n,ai,bj,count); bj=ai; j+; j=j%m; i+; rate=count;/转换为float型3.3 程序模块设计3.3.1 页面类型和数据结构页面类型typedef struct int pn,pfn,counter,time; pl-type;其中pn 为页号,pfn为面号, counter为一个周期内访问该页面的次数, time为访问时间.页面控制结构pfc-struct int pn,pfn; struct pfc_struct *next; typedef struct pfc_struct pfc_type;pfc_type pfc_structtotal_vp,*freepf_head,*busypf_head;pfc_type *busypf_tail;其中pfctotal_vp定义用户进程虚页控制结构,*freepf_head为空页面头的指针,*busypf_head为忙页面头的指针,*busypf_tail为忙页面尾的指针.3.3.2 函数和变量说明函数定义（1）Void initialize( ):初始化函数,给每个相关的页面赋值.（2）Void FIFO( ):计算使用FIFO算法时的命中率.（3）Void LRU( ):计算使用LRU算法时的命中率.（4）Void OPT( ):计算使用OPT算法时的命中率.（5）Void LFU( ):计算使用LFU算法时的命中率.（6）Void NUR( ):计算使用NUR算法时的命中率.变量定义(1)int atotal_instruction: 指令流数据组.(2)int pagetotal_instruction: 每条指令所属的页号.(3)int offsettotal_instruction: 每页装入10条指令后取模运算页号偏移值.(4)int total_pf: 用户进程的内存页面数.(5)int disaffect: 页面失效次数.3.3.3 初始化函数int initialize(int total_pf) int i;diseffect=0;for(i=0;itotal_vp;i+)pli.pfn=INVALID; /*置页面控制结构中的页号，页面为空*/pli.counter=0; /*页面控制结构中的访问次数为0*/pli.time=-1; /*访问的时间*/for(i=0;itotal_pf-1;i+)/*建立pfci-1和pfci之间的链接*/pfci.next=&pfci+1;pfci.pfn=i; pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0; /*空页面队列的头指针为pfc0*/return 0; 3.3.4 FIFO算法实现int FIFO(int total_pf) /*先进先出算法total_pf:用户进程的内存页面数*/int i,j;pfc_type *p;/*中间变量*/initialize(total_pf); /*初始化相关页面控制用数据结构*/busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/for(i=0;inext; 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;itotal_instruction;i+)if(plpagei.pfn=INVALID) /*页面失效*/diseffect+;if(freepf_head=NULL) /*无空闲页面*/min=32767;/*设置最大值*/for(j=0;jplj.time&plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head=&pfcplminj.pfn; /腾出一个单元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;itotal_instruction;i+) if (plpagei.pfn=INVALID) /*页面失效*/diseffect+;if(freepf_head=NULL) /*无空闲页面*/ cont_flag=TRUE;old_dp=dp;while(cont_flag) if(pldp.counter=0&pldp.pfn!=INVALID)cont_flag=FALSE;elsedp+;if(dp=total_vp)dp=0;if(dp=old_dp)for(j=0;jnext=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;jtotal_vp;j+)plj.counter=0;printf(NUR:%6.4fn,1-(float)diseffect/320);return 0; 3.3.7 OPT算法实现int OPT(int total_pf) /*最佳置换算法*/int i,j, max,maxpage,d,disttotal_vp;pfc_type *t;initialize(total_pf);for(i=0;itotal_instruction;i+) if(plpagei.pfn=INVALID) /*页面失效*/diseffect+;if(freepf_head=NULL) /*无空闲页面*/for(j=0;jtotal_vp;j+)if(plj.pfn!=INVALID)distj=32767;elsedistj=0; for(j=0;jtotal_vp;j+) if(plj.pfn!=INVALID)&(distj=32767)distj=j;max=0;for(j=0;jtotal_vp;j+)if(maxnext=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;itotal_instruction;i+) if(plpagei.pfn=INVALID) /*页面失效*/ diseffect+;if(freepf_head=NULL) /*无空闲页面*/ min=32767;/*获取counter的使用用频率最小的内存*/for(j=0;jplj.counter&plj.pfn!=INVALID)min=plj.counter;minpage=j;freepf_head=&pfcplminpage.pfn;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.8688LRU:0.8531OPT:0.8750LFU:0.8562NUR:0.856230page framesFIFO:0.8781LRU:0.8719OPT:0.8781LFU:0.8750NUR:0.868831page framesFIFO:0.8938LRU:0.8750OPT:0.8844LFU:0.8844NUR:0.890632page framesFIFO:0.9000LRU:0.9000OPT:0.9000LFU:0.9000NUR:0.9000 从上述结果可知，在内存页面数较少（45页）时，五种算法的命中率差别不大，都是30%左右。在内存页面为718个页面之间时，5种算法的访内命中率大致在35%60%之间变化。但是，FIFO算法与OPT算法之间的差别一般在610个百分点左右。在内存页面为2532个页面时，由于用户进程的所有指令基本上都已装入内存，使命中率增加，从而算法之间的差别不大。 比较上述5种算法，以OPT算法的命中率最高，NUR算法次之，再就是LFU算法和LRU算法，其次是FIFO算法。就本问题，在15页之前，FIFO的命中率比LRU的高。4page framesFIFO:0.2594LRU:0.2562OPT:0.2687LFU:0.2437NUR:0.26255page framesFIFO:0.3000LRU:0.3000OPT:0.3000LFU:0.2969NUR:0.2875 6pageframesFIFO:0.3375LRU:0.3281OPT:0.3281LFU:0.3094NUR:0.3281 7page framesFIFO:0.3563LRU:0.3563OPT:0.3688LFU:0.3312NUR:0.34698page framesFIFO:0.4031LRU:0.4094OPT:0.3875LFU:0.3406NUR:0.37819page framesFIFO:0.4156LRU:0.4281OPT:0.4156LFU:0.3656NUR:0.412510page framesFIFO:0.4281LRU:0.4469OPT:0.4313LFU:0.3750NUR:0.440611page framesFIFO:0.4531LRU:0.4688OPT:0.4594LFU:0.4281NUR:0.465612page framesFIFO:0.4656LRU:0.4813OPT:0.4906LFU:0.4375NUR:0.493813page framesFIFO:0.4750LRU:0.5000OPT:0.5219LFU:0.4625NUR:0.531214page framesFIFO:0.4906LRU:0.5125OPT:0.5375LFU:0.4938NUR:0.550015page framesFIFO:0.5312LRU:0.5250OPT:0.5625LFU:0.5281NUR:0.556316page framesFIFO:0.5406LRU:0.5625OPT:0.5813LFU:0.5531NUR:0.584417page framesFIFO:0.5906LRU:0.5813OPT:0.6188LFU:0.5750NUR:0.603118page framesFIFO:0.6000LRU:0.5906OPT:0.6344LFU:0.5906NUR:0.625019page framesFIFO:0.6312LRU:0.6156OPT:0.6438LFU:0.6219NUR:0.643820page framesFIFO:0.6406LRU:0.6344OPT:0.6625LFU:0.6438NUR:0.675021page framesFIFO:0.6969LRU:0.6594OPT:0.6875LFU:0.6656NUR:0.693722page fram