还剩8页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
实验七存储器管理实验.实验目的理解操作系统虚拟存储管理的原理,理解程序执行局部性的概念.实验内容设计一个虚拟存储区和内存工作区,并使用下列算法计算访问命中率1进先出的算法FIFO2最近最少使用的算法LRU3最佳淘汰算法OPT命中率=一页面失效次数/页地址流长度♦实验要求理解FIFOLRU算法原理,理解参考程序的原理和实现思路完成程序的设计,重点完成FIFOLRU算法分析运算结果,在分配不同的物理块情况下,各算法的缺页情况有什么规律?
3.实验指导FIFO先进先出页面置换算法原理阐述这是最早出现的置换算法该算法总是淘汰最先进入内存的页面,即选择在内存中驻pp_control[i-1].next=pp_control|i];〃建立pp_control[i-l]和之间的链接pp_control[i-1].no_ofLpp-i-1;pp_control[i-1].no_ofLvp=-1;pp_control[total_pf-1].next=NULL;pp_control[total_pf-1].no_oflpp=total_pf-1;pp_control[total_pf-1].no_oflvp=-1;free_pp_head=pp_control[01;return;留时间最久的页面予以淘汰该算法实现简单只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面1在分配内存页面数AP小于进程页面数PP时,当然是最先的AP个页面放入内存;2这时有需要处理新的页面,则将原理在内存中的AP个页面中最先进入的调出是以称为FIFO然后放入新页面;3以后如果有新页面需要调入,按2之规则进行算法特点所使用的内存页面构成一个队列图标描述假设某个进程在硬盘上被化为5个页面PP=5以
1、
2、
3、
4、5分别表示,而下面是处理机调用它们的顺序这取决于进程本身
1、
4、
2、
5、
3、
3、
2、
4、
2、5而内存可以控制的页面数为3AP=3那么在使用FIFO算法时,这3个页面的内存使用情况应该是这样的不难看出本例共换入页面8次,diseffect=8o算法设计voidFIFOinttotal_pfintij;pp_typeinitializetotal_pf;busy_pp_head=busy_pp_tail=NULL;fori=0;iNUMBER_OF_INSTRUCTION;i++counter_page_default+=l;iffree_pp_head==NULLp=busy_pp_head-next;vp_array[busy_pp_head-no_ofLvp].no_of_pp=INVALID;free_pp_head=busy_pp_head;free_pp_head-next=NULL;busy_pp_head=p;p=free_pp_head-next;free_pp_head-next=NULL;free_pp_head-no_ofLvp=page_ofLinstruction[i];vp_array[page_ofLinstruction[i]].no_oCpp-frce_pp_head-no_ofLpp;ifbusy_pp_tail==NULLbusy_pp_head=busy_pp_tail=free_pp_head;elsebusy_pp_tail-next=free_pp_head;busy_pp_tail=free_pp_head;free_pp_head=p;printfHFIFO缺页率%
6.4fnfloatcounter_page_default/320;return;LRU最近最少使用页面置换算法原理阐述在采用该算法时,应为在内存中的每个页面设置一个移位寄存器骼来记录该页面被访问的频率该置换算法选择在最近时期使用最少的页面为淘汰页⑴在分配内存页面数AP小于进程页面数PP时,当然是最先的AP个页面放入内存;⑵然则当需要调页面进入内存,而当前分配的内存页面全部不空闲时,选择其中最长时间没有用到那个页面调出,以空出内存来放置新调入的页面是以称为LRU;算法特点每个页面都有属性表示有多长时间未被CPU使用的信息表描述为了便于比较学习,例子和前面的一样某进程在硬盘上被划为5个页面,用
1、
2、
3、
4、5表示,而处理机处理它们的顺序为
1、
4、
2、
5、
3、
3、
2、
4、
2、5而内存可以控制的页面数为3AP=3那么在使用FIFO算法时,这3个页面的内存使用情况应该是这样的不难看出页面换入共7次,diseffect=7o算法设计voidLRUinttotal_pfintminminjijpresent_time;〃访问时亥ijinitializetotal_pf;present_time=O;fori=0;ivNUMBER_OF_INSTRUCTION;i++ifvp_array[page_oLinstruction[i]].no_oflpp-=INVALIDcounter_page_default++;iffree_pp_head==NULL〃无空闲页面min二MAXI;forj=0;jNUMBER_OF_VP;j++ifminvp_array[j].timevp_array[j].no_ofLpp!=INVALIDminj=j;}free_pp_head=pp_control[vp_array[minj].no_ofLpp];vp_array[minj].no_of_pp=INVALID;vp_array[minj].time=-l;free_pp_head-next=NULL;vp_array[page_oOnstruction[i]].no_ofLpp-free_pp_head-no_oflpp;//vp_array[page_ofl_instruction[i]].time=present_time;free_pp_head=free_pp_head-next;}elsevp_array[page_oL.instruction[i]].time=present_time;//使用present_time++;printfnLRU缺页率%
6.4fnfloatcounter_page_default/320;return;参考程序采用C++程序实现#includewindows.h#includestdio.h#includeprocess.hdefineTRUE1defineFALSE0defineINVALID-1defineNULL0defineNUMBER_OF_INSTRUCTION320〃指令流的指令条数#defineNUMBER_OF_VP32〃进程的虚页页数//#defineLINEARADDRESS//有选择性的打开该宏开关typedefstructintno_of_vp;〃虚拟页号intno_oflpp;〃物理页号intcounter_in_period;〃一周期内访问的次数inttime;〃访问时间}vp_struct;〃页面类型vp_structvp_array[NUMBER_OF_VP];structpp_struct〃物理页面结构intno_ofLvp;intno_oflpp;structpp_struct*next;;typedefstructpp_structpp_type;pp_typepp_control[NUMBER_OF_VP|^free_pp_head*busy_pp_head:l:busy_pp_tail;intcounter_page_default;intaddress_of_instruction[NUMBER_OF_INSTRUCTION];intpage_oLinstruction[NUMBER_OF_INSTRUCTION]offset_oLinstruction[NUMBER_OF_INSTRUCTION];intMAXI=2147483647;//l«30-l*2+l;//2A31-12147483647voidinitializeint;voidFIFOint;〃先进先出voidLRUint;〃最近最久未使用页面淘汰算法leastrecentlyused//voidOPTint;〃最佳淘汰算法intmainintSi;srandintgetpid;S=intrand%200;//#ifndefLINEAR_ADDRESSfori=0;iNUMBER_OF_INSTRUCTION;i++/*产生指令队列*/address_oCinstruction[i]=S;/*任选一指令访问点*/address_oCinstruction[i+1]=address_ofLinstruction[i]+1;/*顺序执行一条指令*/address_ofLinstruction[i4-2]=intrand%200;/*执彳亍前地址指令m*/address_ofLinstruction[i+3]=address_ofLinstruction[i+2]+l;/*执行后地址指令*/S=intrand%200;//#else////fori=0;iNUMBER_OF_INSTRUCTION;i+=1/*产生指令队列*///{//address_ofLinstruction[i]=i;////#endiffori=0;iNUMBER_OFJNSTRUCTION;i++/*将指令序列变换成页地址流*/page_of_instruction[i]=address_oCinstruction[i]/10;offset_ofLinstruction[i]=address_ofLinstruction[i]%10;fori=4;i=32;i++/*用户内存工作区从4个页面到32个页面*/printfH%2d物理块”i;FIFOi;LRUi;//OPTi;printf\nn;//getchar;return0;}〃先进先出淘汰算法voidFIFOinttotal_pfintij;pp_typeinitializetotal_pf;busy_pp_head=busy_pp_tail=NULL;fori=0;iNUMBER_OF_INSTRUCTION;i++ifvp_array[page_ofLinstruction[i]].no_oflpp==INVALIDcounter_page_default+=1;iffree_pp_head==NULLp=busy_pp_head-next;vp_array[busy_pp_head-no_ofLvp].no_ofLpp=INVALID;free_pp_head=busy_pp_head;free_pp_head-next=NULL;busy_pp_head=p;p=free_pp_head-next;free_pp_head-next=NULL;free_pp_head-no_ofLvp=page_oCinstruction[i];vp_array[page_of_instruction[i]].no_ofl_pp=free_ppifbusy_pp_tail==NULLbusy_pp_head=busy_pp_tail=free_pp_head;elsebusy_pp_tail-next=free_pp_head;busy_pp_tail=free_pp_head;free_pp_head=p;printfnFIFO缺页率%
6.4fnfloatcounter_page.return;〃最近最少淘汰使用算法voidLRUinttotal_pfintminminjijprc3cnt_timc;〃访问时亥Uinitializetotal_pf;present_time=O;fori=0;iNUMBER_OF_INSTRUCTION;i4-+counter_page_default+4-;iffree_pp_head==NULL〃无空闲页面min=MAXI;forj=0;jNUMBER_OF_VP;j++ifminvp_array[j].timevp_array[j].no_ofLpp!-INVALIDmin=vp_array|j].time;minj=j;free_pp_head=pp_control[vp_array[minj].no_ofLpp];vp_array[minj].no_ofLpp-INVALID;vp_array[minj].time=-l;free_pp_head-next=NULL;vp_array[page_ofLinstruction[i]].no_ofLpp=free_pp_head-no_oflpp;//vp_array[page_ofLinstruction[i]].time=present_time;free_pp_head=free_pp_head-next;elsevp_array[page_ofLinstruction[iJ].time=present_time;//使用present_time++;printfLRU缺页率%
6.4fnfloatcounter_page_default/320;return;voidinitializeinttotal_pfinti;counter_page_default=0;fori=0;iNUMBER_OF_VP;i++vp_array|i].no_ofLvp=i;vp_array[i].no_ofLpp=INVALID;vp_array[i].counter_in_period=0;vp_array[i].time=-1;。