操作系统存储管理实验报告课案

1、实验五存储管理一、实验目的1 、加深对操作系统存储管理的理解2、能过模似页面调试算法，加深理解操作系统对内存的高度管理二、总的设计思想、环境语言、工具等总的设计思想：1、编写函数计算并输出下述各种算法的命中率 OPT页面置换算法OPT所选择被淘汰的页面是已调入内存，且在以后永不使用的，或是在最长时间内不再被访问的页面。因此如何找出这样的页面是该算法的关键。可为每个页面设置一 个步长变量，其初值为一足够大的数，对于不在内存的页面，将其值重置为零，对于 位于内存的页面，其值重置为当前访问页面与之后首次出现该页面时两者之间的距离， 因此该值越大表示该页是在最长时间内不再被访问的页面，可以选择其作为换

2、出页面。 FIFO页面置换算法FIFO总是选择最先进入内存的页面予以淘汰，因此可设置一个先进先出的忙页帧 队列，新调入内存的页面挂在该队列的尾部，而当无空闲页帧时，可从该队列首部取 下一个页帧作为空闲页帧，进而调入所需页面。 LRU页面置换算法LRU是根据页面调入内存后的使用情况进行决策的，它利用“最近的过去”作为“最近的将来”的近似，选择最近最久未使用的页面予以淘汰。该算法主要借助于页面结 构中的访问时间time来实现，time记录了一个页面上次的访问时间，因此，当须淘汰一个页面时，选择处于内存的页面中其time值最小的页面，即最近最久未使用的页面予以淘汰。 LFU页面置换算法LFU要求为每

3、个页面配置一个计数器（即页面结构中的counter），一旦某页被访问，则将其计数器的值加 1,在需要选择一页置换时， 则将选择其计数器值最小的页面， 即内存中访问次数最少的页面进行淘汰。 NURM面置换算法NUR要求为每个页面设置一位访问位（该访问位仍可使用页面结构中的cou nter表示），当某页被访问时，其访问位counter置为1。需要进行页面置换时，置换算法从替换指针开始（初始时指向第一个页面）顺序检查处于内存中的各个页面，如果其 访问位为0，就选择该页换出，否则替换指针下移继续向下查找。如果内存中的所有页面扫描完毕未找到访问位为0的页面，则将替换指针重新指向第一个页面，同时将内存中所

4、有页面的访问位置0,当开始下一轮扫描时，便一定能找到counter为0的页面。2、在主函数中生成要求的指令序列，并将其转换成页地址流；在不同的内存容量下调用上述函数使其计算并输出相应的命中率。环境语言：Linux下的GNU编译环境三、数据结构与模块说明程序中用到的数据结构、类型定义及主要的函数原型如下：1、数据结构(1) 页面结构typedef structint pn, pfn, counter, time; pl_type ;pl_type pltotal_vp;其中pn为页面号(页号)，pfn为页帧号(物理块号)，counter为一个周期内访问该页面的 次数，time为访问时间；plto

5、tal_vp为页面结构数组，由于共有320条指令，每页可装入 10条指令，因此虚页长total_vp 的值为32。(2) 页帧控制结构struct pfc_structint pn, pfn;struct pfc_struct *n ext;typedef struct pfc_struct pfc_type;pfc_type pfctotal_vp, *freepf_head, *busypf_head, *busypf_tail;其中pfctotal_vp定义用户进程的页帧控制结构数组，在该实验中，用户内存工作区是动态变化的，最多可达到用户进程的虚页数目，即32个物理块。*freepf_h

6、ead 为空闲页帧头的指针*busypf_head为忙页帧头的指针*busypf_tail 忙页帧尾的指针2、变量定义(1) int atotal_i nstructio n:指令流数组(2) int diseffect:页面失效次数(3) in t pagetotal_i nstructio n:每条指令所属页面号(4) int offsettotal_instruction:每页装入10条指令后取模运算得出的页内偏移地址3、主要函数(1) void in itialize(i nt):初始化函数该函数主要对页面结构数组pl和页帧结构数组pfc进行初始化，如置页面结构中的页面号pn,初始化页

7、帧号 pfn为空，访问次数counter为0，访问时间time为-1 ;同样对页帧数组进行初始化，形成一个空闲页帧队列。 void OPT(i nt):计算使用最佳贝面算法时的命中率 void FIFO(i nt):计算使用先进先出页面置换算法时的命中率 void LRU(i nt):计算使用最近最久未使用页面置换算法时的命中率(5) void LFU(int):计算使用最少使用置换算法时的命中率 void NUR(i nt):计算使用最近未使用置换算法时的命中率四、主要算法的设计与实现void FIFO(int total_pf)/*先进先出页面置换算法 */int i,j;pfc_type

8、 *p;in itialize(total_pf);busypf_head=busypf_tail=NULL;for(i=0;i<total_i nstructio n; i+)if(plpagei.pfn=INVALID)/*页面失效 */diseffect=diseffect+1;if(freepf_head=NULL) /* 无空闲页帧 */p=busypf_head->n ext;plbusypf_head->p n.pfn=INVALID; /将忙页帧队首页面作为换出页面freepf_head=busypf_head;freepf_head->n ext=NU

9、LL;busypf_head=p; /忙页帧头指针后移p=freepf_head->n ext; /有空闲页帧freepf_head->n ext=NULL;freepf_head->p n=pagei; /*将所需页面调入空闲页帧*/plpagei.pfn=freepf_head->pfn;if(busypf_tail=NULL) /*若忙页帧队列为空，则将其头尾指针都指向刚调入页面所在的页帧*/busypf_head=busypf_tail=freepf_head;else /否则，将刚调入页面所在的页帧挂在忙页帧队列尾部busypf_tail->n ext=

10、freepf_head;busypf_tail=freepf_head;freepf_head=p; II空闲页帧头指针后移prin tf("FIFO:%6.4f ",1-(float)diseffect/320);void LRU(i nt total_pf)/*最近最久未使用页面置换算法*/int i,j;int min, minj,prese nt_time;in itialize(total_pf);prese nt_time=0;for(i=0;i<total_i nstructio n;i+)页面失效*/if(plpagei.pfn=INVALID) /*

11、diseffect+;if(freepf_head=NULL) /*无空闲页帧*/min=32767;for(j=0;j<total_vp;j+) /*找出位于内存且time值最小的页面作为置换页腾出一个单元有空闲页面，改为有效面*/if(min>plj.time && plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head=&pfcplminj.pfn; / plminj.pfn=INVALID;plminj.time=-1;freepf_head->n ext=NULL;plpagei.pfn=freepf

12、_head->pfn; /freepf_head=freepf_head->next; /减少一个 free 页面elseplpagei.time=prese nt_time; /命中则修改该单元的访问时间prese nt_time+;prin tf("LRU:%6.4f ",1-(float)diseffect/320);void NUR(i nt total_pf)/*最近未使用页面置换算法*/int i,j,dp,c on t_flag,old_dp;in itialize(total_pf);dp=0;for(i=0;i<total_i nstru

13、ctio n; i+)if(plpagei.pfn=INVALID)/*页面失效 */diseffect+;if(freepf_head=NULL) /* 无空闲页帧 */con t_flag=TRUE;old_dp=dp;while(c on t_flag)if(pldp.cou nter=0&&pldp.pfn!=INVALID)con t_flag=FALSE; /找到位于内存且未被访问的页面elsedp+;if(dp=total_vp) dp=0; /将替换指针重新指向第一个页面if(dp=old_dp)/*若内存中所有页面扫描完毕未找到访冋位为0的页面，将内存中所有页

14、面的访问位置0 */for(j=0;j<total_vp;j+)plj.co un ter=0;freepf_head=&pfcpldp.pfn; /腾出一个单元pldp.pfn=INVALID; freepf_head->n ext=NULL;plpagei.pfn=freepf_head->pfn; /有空闲页面，改为有效freepf_head=freepf_head->next; /减少一个 free 页面elseplpagei.cou nter=1; /命中则将访问位置 1if(i%clear_period=0) /清零周期到，将所有访问位清零for(j

15、=0;j<total_vp;j+)plj.co un ter=0;prin tf("NUR:%6.4f ",1-(float)diseffect/320);void OPT( int total_pf)/*最佳页面置换算法*/int i,j,max,maxpage,d,disttotal_vp;in itialize(total_pf);for(i=0;i<total_i nstructio n;i+)if(plpagei.pfn=INVALID) /*页面失效 */diseffect+;if(freepf_head=NULL) /* 无空闲页面 */for(j

16、=0;j<total_vp;j+)if(plj.pfn!=INVALID)所有位于内存页面的距离变量赋一足够大的数distj=32767;else II不在内存的页面该变量则置为0distj=0;d=1;I*对于位于内存且在当前访问页面之后将再次被访问的页面，dist重置为当前页面与之后首次出现该页面时两者之间的距离*/for(j=i+1;j<total_ in struct ion ;j+)if(plpagej.pfn!=INVALID && distpagej=32767) distpagej=d;d+;max=-1;/查找dist变量值最大的页面作为换出页面

17、for(j=0;j<total_vp;j+) if(max<distj) max=distj; maxpage=j;freepf_head=&pfcplmaxpage.pfn; /腾出一个单元freepf_head->n ext=NULL;有空闲页面，改为有效减少一个free页面plmaxpage.pfn=INVALID;plpagei.pfn=freepf_head->pfn; / freepf_head=freepf_head->n ext; /prin tf("OPT:%6.4f ",1-(float)diseffect/320)

18、;void LFU(i nt total_pf)/*最少使用页面置换算法*/int i,j,mi n,min page;in itialize(total_pf);for(i=0;i<total_i nstructio n;i+)if(plpagei.pfn=INVALID) /页面失效diseffect+;if(freepf_head=NULL) /无空闲页帧min=32767;for(j=0;j<total_vp;j+) /查找位于内存且访问次数最少的页面作为换出页面if(mi n>plj.cou nter&& plj.pfn!=INVALID)min=p

19、lj.co un ter;min page=j;plj.co un ter=0;freepf_head=&pfcplm in page.pfn; /腾出一个单元plmi npage.pfn=INVALID; freepf_head->n ext=NULL;/有空闲页面，改为有效增加页面访问次数/减少一个free 页面 plpagei.pfn=freepf_head->pfn; plpagei.co un ter+;/freepf_head=freepf_head->n ext;elseplpagei.cou nter+; /命中增加页面访问次数prin tf(&quo

20、t;LFU:%6.4f ",1-(float)diseffect/320);五、运行结果OPT FIFO、LRU为例）：本实验的运行结果如下图所示（以4frames OPT6.6563 FIFA0.5&87 LRU0.56565 page frames OPTB.£S13 FIFOU.b«44 LRU6 nage frames OPT0.7063 FIFAU.bVOE LRU8.60317 Daqe frames OPT0.7312 FIFOo.bisa LRUe.fiies8 naqeOPT0.7500 FIFOB.6250 LRU9 Daqe fram

21、es OPT0.7656 FIFCtB.6438 LRU.G59410 naqe frames OPT0.7813 FIF<tB.6Sb3 LRUe.G6S711 page frames OPT0.7937 FIFCtB.6625 LRU0.675(912 pa<fe frames OPT0.S031 FIF<tB.b719 LRU0.675013 aq-e尸耳耐乞OPT0.8125 FIFCtB.7331 LRUfl.684414 mite fr'anies OPT0.8219 FIF<tB.?0b3 LRU0.703115Frames OPT0.8313 F

22、IFCt0.7344 LRU0.71SS16 XffE fr-ames OPT0.8406 FIFOB.7433 LRU0.737517fr-ames OPT0.S5S0 FIFOLRU思.?4t918 pae fr-aniES OPT歐S594 FIFO；Q7656 LRUS.76S819 page fraines OPT0.8656 FIFOQ.7&BS LRUQ.781320 pasfeOPT0.86S8 FIFO；Q7875 LRU0.787521 wsfe fvanes OPT0.8719 FIFO:<.?844 LRUB.8M22 puse frames OPT0.8750 FIFOa.*088 LRUB.B1S6