操作系统存储管理实验介绍

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

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

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

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

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

6、为忙页帧头的指针*busypf_tail忙页帧尾的指针2、变量定义intatotal_instruction:指令流数组(2) intdiseffect:页面失效次数(3) intpagetotal_instruction:每条指令所属页面号(4) intoffsettotal_instruction:每页装入10条指令后取模运算得出的页内偏移地址(5) int total_pf:用户进程的内存页帧数3、主要函数voidinitialize(int):初始化函数该函数主要对页面结构数组pl和页帧结构数组pfc进行初始化，如置页面结构中的页面号pn,初始化页帧号pfn为空，访问次数counter

7、为0,访问时间time为-1;同样对页帧数组进行初始化，形成一个空闲页帧队列。(2)voidOPT(int):计算使用最佳页面算法时的命中率voidFIFO(int):计算使用先进先出页面置换算法时的命中率(4)voidLRU(int):计算使用最近最久未使用页面置换算法时的命中率(5) void LFU(int):计算使用最少使用置换算法时的命中率(6) void NUR(int):计算使用最近未使用置换算法时的命中率四、主要算法的设计与实现voidFIFO(inttotal_pf)/*先进先出页面置换算法*/inti,j;pfc_type*p;initialize(total_pf);bu

8、sypf_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-next=NULL;freepf_head-pn=pagei;/*将所需页面调入空闲页帧*/plpagei.pfn=freepf_head-pfn;if(busypf_tail=NULL)/*若忙页帧队列为空，则将其头

9、尾指针都指向刚调入页面所在的页帧*/busypf_head=busypf_tail=freepf_head;else否则，将刚调入页面所在的页帧挂在忙页帧队列尾部busypf_tail-next=freepf_head;busypf_tail=freepf_head;freepf_head=p;/空闲页帧头指针后移printf(FIFO:%6.4f,1-(float)diseffect/320);void LRU(int total_pf) /*最近最久未使用页面置换算法*/int i,j；int min,minj,present_time;initialize(total_pf);prese

10、nt_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=-1;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn; /

11、plpagei.time=present_time; /腾出一个单元有空闲页面，改为有效 修改页面的访问时间河南师范大学计算机与信息技术学院实验报告freepf_head=freepf_head-next;/减少一个free页面elseplpagei.time=present_time;/命中则修改该单元的访问时间present_time+;printf(LRU:%6.4f,1-(float)diseffect/320);voidNUR(inttotal_pf)/*最近未使用页面置换算法*/inti,j,dp,cont_flag,old_dp;initialize(total_pf);dp=0

12、;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)/*若内存中所有页面扫描完毕未找到访问位为。的页面，将内存中所有页面

13、的访问位置0*/for(j=0;jnext=NULL;plpagei.pfn=freepf_head-pfn;/有空闲页面,改为有效freepf_head=freepf_head-next;/减少一个free页面elseplpagei.counter=1;/命中则将访问位置1if(i%clear_period=0)/清零周期到，将所有访问位清零for(j=0;jtotal_vp;j+)plj.counter=0;printf(NUR:%6.4f,1-(float)diseffect/320);voidOPT(inttotal_pf)/*最佳页面置换算法*/inti,j,max,maxpage,

14、d,disttotal_vp;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;else/不在内存的页面变量则置为0distj=0;d=1;/*对于位于内存且在当前访问页面之后将再次被访问的页面，dist重置为当前页面与之后首次出现该页面时两者之间的距离*/f

15、or(j=i+1;jtotal_instruction;j+)if(plpage皿pfn!=INVALID&distpagej=32767)distpagej=d;d+;max=-1;/查找dist变量值最大的页面作为换出页面for(j=0;jtotal_vp;j+)if(maxnext=NULL;plmaxpage.pfn=INVALID;plpagei.pfn=freepf_head-pfn;/有空闲页面，改为有效freepf_head=freepf_head-next;/减少一个free页面printf(OPT:%6.4f,1-(float)diseffect/320);voidLFU(

16、inttotal_pf)/*最少使用页面置换算法*/inti,j,min,minpage;initialize(total_pf);for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID)/页面失效diseffect+;if(freepf_head=NULL)/无空闲页帧min=32767;for(j=0;jplj.counter&plj.pfn!=INVALID)河南师范大学计算机与信息技术学院实验报告min=plj.counter;minpage=j;plj.counter=0;freepf_head=&pfcplminpage.pfn;/

17、腾出一个单元plminpage.pfn=INVALID;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn;/有空闲页面，改为有效plpagei.counter+;/增加页面访问次数freepf_head=freepf_head-next;/减少一个free页面elseplpagei.counter+;/命中增加页面访问次数printf(LFU:%6.4f,1-(float)diseffect/320);五、运行结果本实验的运行结果如下图所示(以OPTFIFO、LRU为例)：4pageframesOPT0.6563FIFOQ.5687LRU0.5

18、65635pagefrancsOPT&.6813FIFO&.5844LRU0.59066pageframesOPT&.7063FIFO&.5906LRU&.60317pagefrancsOPT&.7312FIFO&.6188LRU&.61888pageframesOPT&.7500FIFO&.6250LRU&.64069pagefrancsOPT0.7656FIFO&.6438LRU&.659410pageframesOPT0.7813FIFO&.6563LRU&.668711pagefrancsOPT0.7937FIFO&.6625LRU&.675012pageframesOPT0.8031

19、FIFO&.6719LRU&.675013pagefrancsOPT0.8125FIFO&.7031LRU&.684414pageframesOPT0.8219FIFO&.7063LRU&.703115pagefrancsOPT0.8313FIFO&.7344LRU&.718816pageframesOPT0.8406FIFO&.7438LRU&.737517pagefrancsOPT0.8500FIFO&.7625LRU&.746918pageframesOPT0.8594FIFO&.7656LRU&.768819pagefrancsOPT0.8656FIFO&.7688LRU&.781320pageframesOPT0.8688FIFO&.7875LRU&.787521pageframesOPT0.8719FIFO&.7844LRU0.800022pageframesOPT0.8750FIFOQ.8000LRUQ.815623pageframesOPT0.8781FIFO&.8375LRU0.825024pagefra