模擬FIFO和LRU算法試驗(yàn)報(bào)告

實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：模擬FIFO和LRU算法學(xué)校：長(zhǎng)安大學(xué)學(xué)院：信息學(xué)院班級(jí)：24060901姓名：日期：2012-5-3實(shí)驗(yàn)題目:先進(jìn)先出（FIFO）頁(yè)面置換算法和最近最久未使用（LRU）置換算法程序設(shè)計(jì)二、 實(shí)驗(yàn)?zāi)康模和ㄟ^(guò)對(duì)FIFO,LRU算法的模擬，進(jìn)一步理解進(jìn)程的基本概念，加深對(duì)進(jìn)程運(yùn)行狀態(tài)和進(jìn)程調(diào)度過(guò)程、調(diào)度算法的理解。三、 實(shí)驗(yàn)設(shè)備及環(huán)境：硬件設(shè)備：PC機(jī)一臺(tái)軟件環(huán)境：安裝Windows操作系統(tǒng)或者Linux操作系統(tǒng)，并安裝相關(guān)的程序開(kāi)發(fā)環(huán)境，如C\C++\Java等編程語(yǔ)言環(huán)境。四、 實(shí)驗(yàn)內(nèi)容及要求：（1） 用C/C++語(yǔ)言編程實(shí)現(xiàn)對(duì)FIFO，LRU算法的模擬。（2） 每個(gè)用來(lái)標(biāo)識(shí)進(jìn)程的進(jìn)程控制塊PCB可用結(jié)構(gòu)來(lái)描述，包括以下字段：五、 實(shí)驗(yàn)方法內(nèi)容—?算法流程圖

主要模塊FIFO功能函數(shù)設(shè)計(jì)：Fifo_replace(void);〃構(gòu)造函數(shù)~Fifo_replace(void);//析構(gòu)函數(shù)intfindSpace(void);〃查找是否有空閑內(nèi)存intfindExist(intcurpage);//查找內(nèi)存中是否有該頁(yè)面intfindReplace(void);〃查找應(yīng)予置換的頁(yè)面voiddisplay(void);//顯示voidFIFO(void);//FIFO算法voidBlockClear(void);//BLOCK恢復(fù)pageInfor*block;//物理塊pageInfor*page;〃頁(yè)面號(hào)串intmemory_state[Bsize][Psize];ints; //缺頁(yè)統(tǒng)計(jì)三.主要代碼設(shè)計(jì)FIFO部分代碼#include<iostream.h>#defineBsize3#definePsize12structpageInfor(intcontent;//頁(yè)面號(hào)inttimer;//被訪問(wèn)標(biāo)記};classFifo_replace(public:Fifo_replace(void);//構(gòu)造函數(shù)~Fifo_replace(void);〃析構(gòu)函數(shù)intfindSpace(void);//查找是否有空閑內(nèi)存intfindExist(intcurpage);//查找內(nèi)存中是否有該頁(yè)面intfindReplace(void);//查找應(yīng)予置換的頁(yè)面voiddisplay(void);//顯示voidFIFO(void);//FIFO算法voidBlockClear(void);//BLOCK恢復(fù)pageInfor*block;//物理塊pageInfor*page;〃頁(yè)面號(hào)串intmemory_state[Bsize][Psize];ints; //缺頁(yè)統(tǒng)計(jì)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;//找到空閑內(nèi)存，return-1;}intFifo_replace::findExist(intcurpage)(for(inti=0;i<Bsize;i++)if(block[i].content==page[curpage].content)returni;//找到內(nèi)存中有該頁(yè)面，返回BLOCK中位置return-1;}intFifo_replace::findReplace(void)(intpos=0;for(inti=0;i<Bsize;i++)if(block[i].timer>=block[pos].timer)pos=i;//找到應(yīng)予置換頁(yè)面，返回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<<"不缺頁(yè)”<<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中所有頁(yè)面TIMER++}}voidFifo_replace::BlockClear(void)(for(inti=0;i<Bsize;i++)(block[i].content=-1;block[i].timer=0;}}LRU部分代碼實(shí)現(xiàn)：#include<stdio.h>#include<conio.h>#defineM4#defineN17#defineMyprintfprintf("| + + + + + + + + + + + + + + ++|\n") /*表格控制*/typedefstructpage(int num; /*記錄頁(yè)面號(hào)*/int time; /*記錄調(diào)入內(nèi)存時(shí)間*/}Page; /*頁(yè)面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)*/Pageb[M]; /*內(nèi)存單元數(shù)*/intc[M][N]; /*暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū)*/intqueue[100];/*記錄調(diào)入隊(duì)列*/intK; /*調(diào)入隊(duì)列計(jì)數(shù)變量*//*初始化內(nèi)存單元、緩沖區(qū)*/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;}/*取得在內(nèi)存中停留最久的頁(yè)面，默認(rèn)狀態(tài)下為最早調(diào)入的頁(yè)面*/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;}/*判斷頁(yè)面是否已在內(nèi)存中*/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;/*記錄調(diào)入頁(yè)面*/val二GetMax(b);b[val].num=fold;b[val].time=0;for(i=0;i<M;i++)if(i!=val)b[i].time++;}}/*主程序*/六、實(shí)驗(yàn)結(jié)果1.執(zhí)行結(jié)果FIFO部分阿選售菜既心<1W用FIFO算法償>退出h.你選擇的是菜單。7772222444001^000033322221^01111000333'缺頁(yè)率:2/12請(qǐng)選擇菜單:@搜狗拼音半;圜皇面@搜狗拼音半;圜皇面LRU部分:2.結(jié)果分析由結(jié)果可以看出，使用FIFO算法，總是淘汰最先進(jìn)