模拟FIFO和LRU算法试验报告

实验报告实验名称：模拟FIFO和LRU算法学校：长安大学学院：信息学院班级：24060901姓名：日期：2012-5-3实验题目:先进先出（FIFO）页面置换算法和最近最久未使用（LRU）置换算法程序设计二、 实验目的：通过对FIFO,LRU算法的模拟，进一步理解进程的基本概念，加深对进程运行状态和进程调度过程、调度算法的理解。三、 实验设备及环境：硬件设备：PC机一台软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境，如C\C++\Java等编程语言环境。四、 实验内容及要求：（1） 用C/C++语言编程实现对FIFO，LRU算法的模拟。（2） 每个用来标识进程的进程控制块PCB可用结构来描述，包括以下字段：五、 实验方法内容—・算法流程图

主要模块FIFO功能函数设计：Fifo_replace(void);〃构造函数~Fifo_replace(void);//析构函数intfindSpace(void);〃查找是否有空闲内存intfindExist(intcurpage);//查找内存中是否有该页面intfindReplace(void);〃查找应予置换的页面voiddisplay(void);//显示voidFIFO(void);//FIFO算法voidBlockClear(void);//BLOCK恢复pageInfor*block;//物理块pageInfor*page;〃页面号串intmemory_state[Bsize][Psize];ints; //缺页统计三.主要代码设计FIFO部分代码#include<iostream.h>#defineBsize3#definePsize12structpageInfor(intcontent;//页面号inttimer;//被访问标记};classFifo_replace(public:Fifo_replace(void);//构造函数~Fifo_replace(void);〃析构函数intfindSpace(void);//查找是否有空闲内存intfindExist(intcurpage);//查找内存中是否有该页面intfindReplace(void);//查找应予置换的页面voiddisplay(void);//显示voidFIFO(void);//FIFO算法voidBlockClear(void);//BLOCK恢复pageInfor*block;//物理块pageInfor*page;〃页面号串intmemory_state[Bsize][Psize];ints; //缺页统计private:};Fifo_replace::Fifo_replace(void)(intQString[12]={4,3,2,1,4,3,5,4,3,2,1,5};s=0;block=newpageInfor[Bsize];for(inti=0;i<Bsize;i++)//初始化Block(block[i].content=-1;block[i].timer=0;}page=newpageInfor[Psize];for(i=0;i<Psize;i++)(page[i].content=QString[i];page[i].timer=0;}}Fifo_replace::~Fifo_replace()(s=0;}intFifo_replace::findSpace(void)(for(inti=0;i<Bsize;i++)if(block[i].content==-1)returni;//找到空闲内存，return-1;}intFifo_replace::findExist(intcurpage)(for(inti=0;i<Bsize;i++)if(block[i].content==page[curpage].content)returni;//找到内存中有该页面，返回BLOCK中位置return-1;}intFifo_replace::findReplace(void)(intpos=0;for(inti=0;i<Bsize;i++)if(block[i].timer>=block[pos].timer)pos=i;//找到应予置换页面，返回BLOCK中位置returnpos;}voidFifo_replace::display(void)(for(inti=0;i<Bsize;i++)if(block[i].content!=-1)cout<<block[i].content<<”";cout<<endl;}voidFifo_replace::FIFO(void)(intexist,space,position;for(inti=0;i<Psize;i++)(exist=findExist(i);if(exist!=-1)(for(intb=0;b<Bsize;b++)(memory_state[b][i]=memory_state[b][i-1];}s++;//cout<<"不缺页”<<endl;}else(space=findSpace();if(space!=-1)(for(intb=0;b<Bsize;b++)(memory_state[b][i]=memory_state[b][i-1];}block[space]=page[i];memory_state[space][i]=block[space].content;if(space==1)(memory_state[1][0]=0;memory_state[2][0]=0;}else(memory_state[2][1]=0;}//display();}else(for(intb=0;b<Bsize;b++)(memory_state[b][i]=memory_state[b][i-1];position=findReplace();block[position]=page[i];memory_state[position][i]=block[position].content;//display();}}for(intj=0;j<Bsize;j++)block[j].timer++;//BLOCK中所有页面TIMER++}}voidFifo_replace::BlockClear(void)(for(inti=0;i<Bsize;i++)(block[i].content=-1;block[i].timer=0;}}LRU部分代码实现：#include<stdio.h>#include<conio.h>#defineM4#defineN17#defineMyprintfprintf("| + + + + + + + + + + + + + + ++|\n") /*表格控制*/typedefstructpage(int num; /*记录页面号*/int time; /*记录调入内存时间*/}Page; /*页面逻辑结构，结构为方便算法实现设计*/Pageb[M]; /*内存单元数*/intc[M][N]; /*暂保存内存当前的状态：缓冲区*/intqueue[100];/*记录调入队列*/intK; /*调入队列计数变量*//*初始化内存单元、缓冲区*/voidInit(Page*b,intc[M][N])(inti,j;for(i=0;i<N;i++)}for(i=0;i<M;i++)for(j=0;j<N;j++)c[i][j]=-1;}/*取得在内存中停留最久的页面，默认状态下为最早调入的页面*/intGetMax(Page*b)(inti;intmax=-1;inttag=0;for(i=0;i<M;i++)(if(b[i].time>max)(max=b[i].time;tag=i;}}returntag;}/*判断页面是否已在内存中*/intEquation(intfold,Page*b)(inti;for(i=0;i<M;i++)(if(fold==b[i].num)returni;}return-1;}/*LRU核心部分*/voidLru(intfold,Page*b)(inti;intval;val=Equation(fold,b);if(val>=0)

b[val].time=0;for(i=0;i<M;i++)if(i!=val)b[i].time++;}else(queue[++K]=fold;/*记录调入页面*/val二GetMax(b);b[val].num=fold;b[val].time=0;for(i=0;i<M;i++)if(i!=val)b[i].time++;}}/*主程序*/六、实验结果1.执行结果FIFO部分阿选售菜既心<1W用FIFO算法偿>退出h.你选择的是菜单。7772222444001^000033322221^01111000333'缺页率:2/12请选择菜单:@搜狗拼音半;圜皇面@搜狗拼音半;圜皇面LRU部分:2.结果分析由结果可以看出，使用FIFO算法，总是淘汰最先进