fifo算法

1实验报告2011–2012学年第2学期任课老师：课程名称计算机操作系统班级座号08姓名实验题目实验4内存管理实验时间实验开始日期：2011-5-8报告提交日期：2011-5-8实验目的、要求实验目的：请求页式存储管理中常用页面置换算法模拟，理会操作系统对内存的调度管理。实验类型：设计性实验实验设计内容及实现步骤实验步骤假设有一程序某次运行访问的页面依次是：0,1,2,4,3,4,5,1,2,5,1,2,3,4,5,6，试计算当内存为4～20页时，下列不同页面调度算法的命中率。①先进先出算法(FIFO)；②最近最少使用算法(LRU)；命中率的算法为：命中率=1-缺页中断次数/总页数。#includestdio.h#defineINVALID-1#defineN16#definetotal_vp7#definetotal_pfc10#defineclear_period100typedefstruct{intpn,pfn,counter,time;}pl_type;pl_typepl[total_vp];typedefstructpfc_struct{intpn,pfn;structpfc_struct*next;}pfc_type;pfc_typepfc[total_pfc],*freepf_h,*busypf_t,*busypf_h;2intdiseffect;intpage[N]={0,1,2,4,3,4,5,1,2,5,1,2,3,4,5,6};intinitialize(inttotal_pf){inti;diseffect=0;for(i=0;itotal_vp;i++){pl[i].pn=i;pl[i].pfn=INVALID;pl[i].counter=0;pl[i].time=-1;}for(i=0;itotal_pf-1;i++){pfc[i].next=&pfc[i+1];pfc[i].pfn=i;}pfc[total_pf-1].next=NULL;pfc[total_pf-1].pfn=total_pf-1;freepf_h=&pfc[0];return0;}voidprint_page(inttotal_pf){intk;for(k=0;ktotal_pf;k++){printf(pfc[%d]=%d,k,pfc[k].pn);if(k==total_pf-1)printf(\n);}}/*先进先出*/intfifo(inttotal_pf){inti;pfc_type*p;initialize(total_pf);busypf_h=busypf_t=NULL;for(i=0;iN;i++){if(pl[page[i]].pfn==INVALID){3diseffect++;if(freepf_h==NULL){p=busypf_h-next;pl[busypf_h-pn].pfn=INVALID;freepf_h=busypf_h;freepf_h-next=NULL;busypf_h=p;}p=freepf_h-next;freepf_h-next=NULL;freepf_h-pn=page[i];pl[page[i]].pfn=freepf_h-pfn;if(busypf_t==NULL)busypf_h=busypf_t=freepf_h;else{busypf_t-next=freepf_h;busypf_t=freepf_h;}freepf_h=p;}print_page(total_pf);/*显示当前内存分配情况*/}printf(FIFO:%6.4f\n,1-(float)diseffect/N);return0;}/*最近最少用(最久未使用)*/intlru(inttotal_pf){intmin,minj,i,j,present_time;initialize(total_pf);present_time=0;/*以计数变量当时间使用*/for(i=0;iN;i++){if(pl[page[i]].pfn==INVALID)/*未命中*/{diseffect++;if(freepf_h==NULL){min=32767;for(j=0;jtotal_vp;j++)if(minpl[j].time&&pl[j].pfn!=INVALID){4min=pl[j].time;minj=j;}freepf_h=&pfc[pl[minj].pfn];pl[minj].pfn=INVALID;pl[minj].time=-1;freepf_h-next=NULL;}pl[page[i]].pfn=freepf_h-pfn;pl[page[i]].time=present_time;freepf_h-pn=page[i];freepf_h=freepf_h-next;}else/*命中*/pl[page[i]].time=present_time;present_time++;print_page(total_pf);/*显示当前内存分配情况*/}printf(LRU:%6.4f\n,1-(float)diseffect/N);return0;}intmain(){inti=5;fifo(i);lru(i);getch();}(1)先进先出算法(FIFO)算法的详细流程图；5当N=5时;(2)最近最少使用算法(LRU)；输入页面访问序列取访问的页号查页表是否缺页？是Diseffect++淘汰在链表头的页面调入所访问的页面否6当N=5时;取访问的页号查页表是否缺页？是Diseffect++淘汰presenttime最大的值的页面调入所访问的页面否7调试过程记录实验结果记录以及与预期结果比较以及分析总结以及心得体会指导老师评阅意见指导老师：年月日