搜索
实验4页式存储管理的页面置换算法模拟1.实验目的通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。2.实验环境装有操作系统WindowsXP和开发工具VC++6.0，内存在256M以上的微机；或者：装有Linux(Fedora7)操作系统和gcc编译器，内存在256M以上的微机。3.实验内容（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：①50%的指令是顺序执行的；②25%的指令是均匀分布在前地址部分；③25%的指令是均匀分布在后地址部分；具体的实施方法是：①在[0，319]的指令地址之间随机选取一起点m；②顺序执行一条指令，即执行地址为m+1的指令；③在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’；④顺序执行一条指令，其地址为m’+1的指令；⑤在后地址[m’+2，319]中随机选取一条指令并执行；⑥重复上述步骤①～⑤，直到执行320次指令。（2）将指令序列变换为页地址流①设页面大小为1K；②分配内存容量为4K到32K；③用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条～第9条指令为第0页（对应虚存地址为[0，9]）；第10条～第19条指令为第1页（对应虚存地址为[10，19]）；…………第310条～第319条指令为第31页（对应虚存地址为[310，319]）。按以上方式，用户指令可组成32页。（3）计算先进先出（FIFO）算法或最近最少使用（LRU）算法在不同内存容量下的命中率。其中，命中率=1-页面失效次数/页地址流长度4.实验要求(1)将FIFO或者LRU算法的源程序及程序执行结果写入实验报告；(2)将FIFO和LRU算法的工作机理写入实验报告。代码：#includestdio.h#includestdlib.h#includestring.h#ifndef_UNISTD_H#define_UNISTD_H#includeIO.H#includePROCESS.H#endif#defineTRUE1#defineFALSE0#defineINVALID-1#definetotal_instruction320//指令流长#definetotal_vp32//虚页长#defineclear_period50//清周期typedefstruct//页面结构{intpn,//页面序号pfn,//页面所在内存区的帧号counter,//单位时间内访问次数time;//上次访问的时间}pl_type;pl_typepl[total_vp];//页面结构数组structpfc_struct{//页面控制结构intpn,//页面号pfn;//内存区页面的帧号structpfc_struct*next;//页面指针，用于维护内存缓冲区的链式结构};typedefstructpfc_structpfc_type;//主存区页面控制结构别名pfc_typepfc[total_vp],//主存区页面控制结构数组*freepf_head,//主存区页面控制结构的空闲页面头指针*busypf_head,//主存区页面控制结构的忙页面头指针*busypf_tail;//主存区页面控制结构的忙页面尾指针intdiseffect;//页错误计数器，初次把页面载入主存时也当做页错误inta[total_instruction];//随即指令流数组intpage[total_instruction];//指令对应的页面号intoffset[total_instruction];//指令所在页面中的偏移量intinitialize(int);//初始化页面结构数组和页面控制结构数组intFIFO(int);//先进先出算法intLRU(int);//最近最久未使用算法intOPT(int);//最佳置换算法intCLOCK(int);//简单时钟(钟表)算法intmain(){ints;//随机数inti;srand(10*getpid());/*每次运行时进程号不同，用来作为初始化随机数队列的种子*/s=(int)((float)(total_instruction-1)*(rand()/(RAND_MAX+1.0)));printf(\n------------随机产生指令流------------\n);for(i=0;itotal_instruction;i+=4)//产生指令队列{a[i]=s;//任选一指令访问点ma[i+1]=a[i]+1;//顺序执行一条指令a[i+2]=(int)((float)a[i]*(rand()/(RAND_MAX+1.0)));//执行前地址指令m'a[i+3]=a[i+2]+1;//顺序执行一条指令printf(%6d%6d%6d%6d\n,a[i],a[i+1],a[i+2],a[i+3]);s=(int)((float)((total_instruction-1)-a[i+2])*(rand()/(RAND_MAX+1.0)))+a[i+2];}printf(--------------------------------------\n);for(i=0;itotal_instruction;i++)//将指令序列变换成页地址流{page[i]=a[i]/10;offset[i]=a[i]%10;}printf(\n--不同页面工作区各种替换策略的命中率表--\n);printf(Page\tFIFO\tLRU\tOPT\tCLOCK\n);for(i=4;i=32;i++)//用户内存工作区从个页面到个页面{printf(%2d\t,i);FIFO(i);LRU(i);OPT(i);CLOCK(i);printf(\n);}return0;}//初始化页面结构数组和页面控制结构数组//total_pf;用户进程的内存页面数intinitialize(inttotal_pf){inti;diseffect=0;for(i=0;itotal_vp;i++){pl[i].pn=i;pl[i].pfn=INVALID;//置页面所在主存区的帧号为-1.表示该页不在主存中pl[i].counter=0;//置页面结构中的访问次数为pl[i].time=-1;//置页面结构中的上次访问的时间为-1}for(i=0;itotal_pf-1;i++){pfc[i].next=&pfc[i+1];//建立pfc[i-1]和pfc[i]之间的链接pfc[i].pfn=i;//初始化主存区页面的帧号}pfc[total_pf-1].next=NULL;pfc[total_pf-1].pfn=total_pf-1;freepf_head=&pfc[0];//主存区页面控制结构的空闲页面头指针指向pfc[0]return0;}//最近最久未使用算法//inttotal_pf;用户进程的内存页面数intLRU(inttotal_pf){intMinT;//最小的访问时间，即很久没被访问过intMinPn;//拥有最小的访问时间的页的页号inti,j;intCurrentTime;//系统当前时间initialize(total_pf);//初始化页面结构数组和页面控制结构数组CurrentTime=0;diseffect=0;for(i=0;itotal_instruction;i++){if(pl[page[i]].pfn==INVALID)//页面失效{diseffect++;//页错误次数加if(freepf_head==NULL)//无空闲页面{MinT=100000;for(j=0;jtotal_vp;j++){//找出time的最小值，表明该页很久没被访问过if(MinTpl[j].time&&pl[j].pfn!=INVALID){MinT=pl[j].time;MinPn=j;}}freepf_head=&pfc[pl[MinPn].pfn];//最久没被访问过的页被释放pl[MinPn].pfn=INVALID;//最久没被访问过的页被换出主存pl[MinPn].time=-1;//最久没被访问过的页的访问时间置为无效freepf_head-next=NULL;}pl[page[i]].pfn=freepf_head-pfn;//有空闲页面,把相应的页面换入主存，并把pfn改为相应的帧号pl[page[i]].time=CurrentTime;//令访问时间为当前系统时间freepf_head=freepf_head-next;//减少一个空闲页面}elsepl[page[i]].time=CurrentTime;//命中则刷新该单元的访问时间CurrentTime++;//系统当前时间加}printf(%6.3f\t,1-(float)diseffect/320);return0;}//最佳置换算法//inttotal_pf;用户进程的内存页面数intOPT(inttotal_pf){inti,j;intMaxD;//将来最近一次访问的距离的最大值（以时间单元度量）intMaxPn;//将来最近一次访问的距离的最大值的页号intdis;//距离计数器intdist[total_vp];//距离数组，保存距离上一次访问的时间差距个数initialize(total_pf);//初始化页面结构数组和页面控制结构数组diseffect=0;for(i=0;itotal_instruction;i++){if(pl[page[i]].pfn==INVALID)//页面失效{diseffect++;//页错误次数加if(freepf_head==NULL)//无空闲页面{for(j=0;jtotal_vp;j++){if(pl[j].pfn!=INVALID)//如果该页在主存中dist[j]=100000;//该页关联的距离值改为最大值elsedist[j]=0;//如果不在该页主存中，该页关联的距离值改为}dis=1;//初始距离值为for(j=i+1;jtotal_instruction;j++)//从要替换的指令的下一条算起，{if(pl[page[j]].pfn!=INVALID&&pl[page[j]].counter==0)//如果该页在主存中,并且是将要最近访问的页//if(pl[page[j]].pfn!=INVALID&&dist[page[j]]==100000)//此条语句原理与上相同{dist[page[j]]=dis;//距离值改为displ[page[j]].counter=1;//使访问次数标志加，区别第一次访问和第二次访问}dis++;}MaxD=-1;for(j=0;jtotal_vp;j++){pl[j].counter=0;//重置访问次数为if(MaxDdist[j])//查找将来最近一次访问的距离的最大值及其序号{MaxD=dist[j];MaxPn=j;}}freepf_head=&pfc[pl[MaxPn].pfn];//替换将来一段时间最久访问的页freepf_head-next=NULL;pl[MaxPn].pfn=INVALID;}pl[page[i]].pfn=freepf_head-pfn;//把当前页换入主存中，并且把当前页的pfn改为换入页的帧号，freepf_head=freepf_head-next;//减少一个空闲页面}//if}//forprintf(%6.3f\t,1-(float)diseffect/320);return0;}//简单时钟算法//inttotal_pf;用户进程的内存页面数intCLOCK(inttotal_pf){inti;intuse[total_vp];//使用位intswap;swap=