存储器管理实验

实验七存储器管理实验.实验目的：理解操作系统虚拟存储管理的原理，理解程序执行局部性的概念。.实验内容：设计一个虚拟存储区和内存工作区，并使用下列算法计算访问命中率。(1)进先出的算法(FIFO)(2)最近最少使用的算法(LRU)(3)最佳淘汰算法(OPT)命中率=(一页面失效次数)/页地址流长度♦实验要求理解FIFO,LRU算法原理，理解参考程序的原理和实现思路。完成程序的设计，重点完成FIFO,LRU算法分析运算结果，在分配不同的物理块情况下，各算法的缺页情况有什么规律？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而内存可以控制的页面数为3(AP=3),那么在使用FIFO算法时，这3个页面的内存使用情况应该是这样的：队列第1位142队列第1位1425333425队列第2位142555342队列第3位14222534先进入的页面1被调出1页面3进入，而此 处理，但是页面本时3个页面中最 身以在内存中，不先进入的页面4 需再调入了被调出不难看出本例共换入页面8次，diseffect=8o算法设计voidFIFO(inttotal_pf)inti,j;pp_typeinitialize(total_pf);busy_pp_head=busy_pp_tail=NULL;for(i=0;i<NUMBER_OF_INSTRUCTION;i++)counter_page_default+=l;if(free_pp_head==NULL)(p=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；if(busy_pp_tail==NULL)busy_pp_head=busy_pp_tail=free_pp_head;else(busy_pp_tail->next=free_pp_head;busy_pp_tail=free_pp_head;)free_pp_head=p;))printf(HFIFO缺页率：%6.4fn,(float)counter_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而内存可以控制的页面数为3(AP=3),那么在使用FIFO算法时，这3个页面的内存使用情况应该是这样的：不难看出页面换入共7次，diseffect=7o算法设计voidLRU(inttotal_pf)(intmin,minj,i,j,present_time;〃访问时亥ijinitialize(total_pf)；present_time=O;for(i=0;ivNUMBER_OF_INSTRUCTION;i++)(if(vp_array[page_oLinstruction[i]].no_oflpp-=INVALID)(counter_page_default++;if(free_pp_head==NULL)〃无空闲页面(min二MAXI;for(j=0;j<NUMBER_OF_VP;j++)if(min>vp_array[j].time&&vp_array[j].no_ofLpp!=INVALID)minj=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++;)printf(nLRU缺页率：%6.4fn,(float)counter_page_default/320);return;)参考程序：采用C++程序实现：#include<windows.h>#include<stdio.h>#include<process.h>defineTRUE1defineFALSE0defineINVALID-1defineNULL0defineNUMBER_OF_INSTRUCTION320〃指令流的指令条数#defineNUMBER_OF_VP32 〃进程的虚页页数//#defineLINEAR,ADDRESS //有选择性的打开该宏开关typedefstruct(intno_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-12147483647voidinitialize(int);voidFIFO(int);〃先进先出voidLRU(int); 〃最近最久未使用页面淘汰算法(leastrecentlyused)//voidOPT(int); 〃最佳淘汰算法intmain()(intS,i;srand((int)getpid());S=(int)rand()%200;//#ifndefLINEAR_ADDRESSfor(i=0;i<NUMBER_OF_INSTRUCTION;i++)/*产生指令队列*/(address_oCinstruction[i]=S; /*任选一指令访问点*/address_oCinstruction[i+1]=address_ofLinstruction[i]+1; /*顺序执行一条指令*/address_ofLinstruction[i4-2]=(int)rand()%200; /*执彳亍前地址指令m'*/address_ofLinstruction[i+3]=address_ofLinstruction[i+2]+l;/*执行后地址指令*/S=(int)rand()%200;)//#else////for(i=0;i<NUMBER_OF_INSTRUCTION;i+=1)/*产生指令队列*///{//address_ofLinstruction[i]=i;//)//#endiffor(i=0;i<NUMBER_OFJNSTRUCTION;i++) /*将指令序列变换成页地址流*/(page_of_instruction[i]=address_oCinstruction[i]/10;offset_ofLinstruction[i]=address_ofLinstruction[i]%10;)for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/(printf(H%2d物理块：”,i);FIFO(i);LRU(i);//OPT(i);printf(,'\nn);)//getchar();return0;}〃先进先出淘汰算法voidFIFO(inttotal_pf)(intij;pp_typeinitialize(total_pf)；busy_pp_head=busy_pp_tail=NULL;for(i=0;i<NUMBER_OF_INSTRUCTION;i++)(if(vp_array[page_ofLinstruction[i]].no_oflpp==INVALID)counter_page_default+=1;if(free_pp_head==NULL)

p=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_ppif(busy_pp_tail==NULL)busy_pp_head=busy_pp_tail=free_pp_head;else(busy_pp_tail->next=free_pp_head;busy_pp_tail=free_pp_head;)free_pp_head=p;))printf(nFIFO缺页率：%6.4fn,(float)counter_page.return;)〃最近最少淘汰使用算法voidLRU(inttotal_pf)(intmin,minj,i,j,prc3cnt_timc;〃访问时亥Uinitialize(total_pf)；present_time=O;head->no_oCpp；default/320);head->no_oCpp；default/320);counter_page_default+4-；if(free_pp_head==NULL)〃无空闲页面(min=MAXI;for(j=0;j<NUMBER_OF_VP;j++)if(min>vp_array[j].time&&vp_array[j].no_ofLpp!-INVALID)(min=vp_array