模擬FIFO和LRU算法試驗報告

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

主要模塊FIFO功能函數(shù)設計：Fifo_replace(void);〃構造函數(shù)~Fifo_replace(void);//析構函數(shù)intfindSpace(void);〃查找是否有空閑內存intfindExist(intcurpage);//查找內存中是否有該頁面intfindReplace(void);〃查找應予置換的頁面voiddisplay(void);//顯示voidFIFO(void);//FIFO算法voidBlockClear(void);//BLOCK恢復pageInfor*block;//物理塊pageInfor*page;〃頁面號串intmemory_state[Bsize][Psize];ints; //缺頁統(tǒng)計三.主要代碼設計FIFO部分代碼#include<iostream.h>#defineBsize3#definePsize12structpageInfor(intcontent;//頁面號inttimer;//被訪問標記};classFifo_replace(public:Fifo_replace(void);//構造函數(shù)~Fifo_replace(void);〃析構函數(shù)intfindSpace(void);//查找是否有空閑內存intfindExist(intcurpage);//查找內存中是否有該頁面intfindReplace(void);//查找應予置換的頁面voiddisplay(void);//顯示voidFIFO(void);//FIFO算法voidBlockClear(void);//BLOCK恢復pageInfor*block;//物理塊pageInfor*page;〃頁面號串intmemory_state[Bsize][Psize];ints; //缺頁統(tǒng)計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部分代碼實現(xiàn)：#include<stdio.h>#include<conio.h>#defineM4#defineN17#defineMyprintfprintf("| + + + + + + + + + + + + + + ++|\n") /*表格控制*/typedefstructpage(int num; /*記錄頁面號*/int time; /*記錄調入內存時間*/}Page; /*頁面邏輯結構，結構為方便算法實現(xiàn)設計*/Pageb[M]; /*內存單元數(shù)*/intc[M][N]; /*暫保存內存當前的狀態(tài)：緩沖區(qū)*/intqueue[100];/*記錄調入隊列*/intK; /*調入隊列計數(shù)變量*//*初始化內存單元、緩沖區(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;}/*取得在內存中停留最久的頁面，默認狀態(tài)下為最早調入的頁面*/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.執(zhí)行結果FIFO部分阿選售菜既心<1W用FIFO算法償>退出h.你選擇的是菜單。7772222444001^000033322221^01111000333'缺頁率:2/12請選擇菜單:@搜狗拼音半;圜皇面@搜狗拼音半;圜皇面LRU部分:2.結果分析由結果可以看出，使用FIFO算法，總是淘汰最先進