實驗四 頁面置換算法代碼(一).doc

實驗四 頁面置換算法模擬（2）一題目要求：設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，編程序演示下述算法的具體實現(xiàn)過程，并計算訪問命中率：要求設(shè)計主界面以靈活選擇某算法，且以下算法都要實現(xiàn)1) 最佳置換算法(OPT)：將以后永不使用的或許是在最長(未來)時間內(nèi)不再被訪問的頁面換出。2) 先進(jìn)先出算法(FIFO)：淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的頁面。4) 最不經(jīng)常使用算法(LFU)二實驗?zāi)康模?、用C語言編寫OPT、FIFO、LRU，LFU四種置換算法。2、熟悉內(nèi)存分頁管理策略。3、了解頁面置換的算法。4、掌握一般常用的調(diào)度算法。5、根據(jù)方案使算法得以模擬實現(xiàn)。6、鍛煉知識的運(yùn)用能力和實踐能力。三相關(guān)知識：1虛擬存儲器的引入： 局部性原理：程序在執(zhí)行時在一較短時間內(nèi)僅限于某個部分；相應(yīng)的，它所訪問的存儲空間也局限于某個區(qū)域，它主要表現(xiàn)在以下兩個方面：時間局限性和空間局限性。2虛擬存儲器的定義： 虛擬存儲器是只具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲器系統(tǒng)。3虛擬存儲器的實現(xiàn)方式： 分頁請求系統(tǒng)，它是在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能、頁面置換功能所形成的頁面形式虛擬存儲系統(tǒng)。 請求分段系統(tǒng)，它是在分段系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)段及分段置換功能后，所形成的段式虛擬存儲系統(tǒng)。4頁面分配： 平均分配算法，是將系統(tǒng)中所有可供分配的物理塊，平均分配給各個進(jìn)程。 按比例分配算法，根據(jù)進(jìn)程的大小按比例分配物理塊。 考慮優(yōu)先的分配算法，把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)個進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)脑黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。5頁面置換算法：常用的頁面置換算法有OPT、FIFO、LRU、Clock、LFU、PBA等。四設(shè)計思想： 選擇置換算法，先輸入所有頁面號，為系統(tǒng)分配物理塊，依次進(jìn)行置換：OPT基本思想：是用一維數(shù)組pagepSIZE存儲頁面號序列，memerymSIZE是存儲裝入物理塊中的頁面。數(shù)組nextmSIZE記錄物理塊中對應(yīng)頁面的最后訪問時間。每當(dāng)發(fā)生缺頁時，就從物理塊中找出最后訪問時間最大的頁面，調(diào)出該頁，換入所缺的頁面?！咎貏e聲明】若物理塊中的頁面都不再使用，則每次都置換物理塊中第一個位置的頁面。FIFO基本思想：是用隊列存儲內(nèi)存中的頁面，隊列的特點是先進(jìn)先出，與該算法是一致的，所以每當(dāng)發(fā)生缺頁時，就從隊頭刪除一頁，而從隊尾加入缺頁。或者借助輔助數(shù)組timemSIZE記錄物理塊中對應(yīng)頁面的進(jìn)入時間，每次需要置換時換出進(jìn)入時間最小的頁面。LRU基本思想：是用一維數(shù)組pagepSIZE存儲頁面號序列，memerymSIZE是存儲裝入物理塊中的頁面。數(shù)組flag10標(biāo)記頁面的訪問時間。每當(dāng)使用頁面時，刷新訪問時間。發(fā)生缺頁時，就從物理塊中頁面標(biāo)記最小的一頁，調(diào)出該頁，換入所缺的頁面。五流程圖：如下頁所示將頁號放入物理塊中，編號加1引用串編號大于物理塊數(shù)?載入頁號序列，從第0個得到頁號開始頁號在物理塊中?根據(jù)選擇的置換算法完成置換頁號序列載完?結(jié)束是否是是是是六源代碼：如下頁所示【使用C語言】#include #include #include /*全局變量*/int mSIZE; /*物理塊數(shù)*/int pSIZE; /*頁面號引用串個數(shù)*/static int memery10=0; /*物理塊中的頁號*/static int page100=0; /*頁面號引用串*/static int temp10010=0; /*輔助數(shù)組*/*置換算法函數(shù)*/void FIFO();void LRU();void OPT();/*輔助函數(shù)*/void print(unsigned int t);void designBy();void download();void mDelay(unsigned int Delay);/*主函數(shù)*/void main() int i,k,code;system(color 0A);designBy();printf(請按任意鍵進(jìn)行初始化操作. n);printf(n);printf( );getch();system(cls);system(color 0B);printf(請輸入物理塊的個數(shù)(M=10)：);scanf(%d,&mSIZE);printf(請輸入頁面號引用串的個數(shù)(P=100)：);scanf(%d,&pSIZE);puts(請依次輸入頁面號引用串(連續(xù)輸入，無需隔開)：);for(i=0;ipSIZE;i+) scanf(%1d,&pagei);download();system(cls);system(color 0E); do puts(輸入的頁面號引用串為：);for(k=0;k=(pSIZE-1)/20;k+)for(i=20*k;(ipSIZE)&(i);/getch();system(cls); while (code!=4);getch();/*載入數(shù)據(jù)*/void download()int i;system(color 0D);printf(n);printf(正在載入數(shù)據(jù)，請稍候 !n);printf(n);printf(Loading.n);printf( O);for(i=0;i51;i+)printf(b);for(i=0;i);printf(nFinish.n載入成功，按任意鍵進(jìn)入置換算法選擇界面：);getch();/*設(shè)置延遲*/void mDelay(unsigned int Delay) unsigned int i; for(;Delay0;Delay-) for(i=0;i124;i+) printf( b); /*顯示設(shè)計者信息*/ void designBy()printf(n);printf( 頁面置換算法 n);printf(n);void print(unsigned int t)int i,j,k,l;int flag;for(k=0;k=(pSIZE-1)/20;k+)for(i=20*k;(ipSIZE)&(i20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&(i=pSIZE-1)printf(%dn,pagei);elseprintf(%d ,pagei);for(j=0;jmSIZE;j+)for(i=20*k;(imSIZE+20*k)&(i=j)printf( |%d|,tempij);elseprintf( | |);for(i=mSIZE+20*k;(ipSIZE)&(i20*(k+1);i+)for(flag=0,l=0;lmSIZE;l+)if(tempil=tempi-1l)flag+;if(flag=mSIZE)/*頁面在物理塊中*/printf( );elseprintf( |%d|,tempij);/*每行顯示20個*/if(i%20=0)continue;printf(n);printf(-n);printf(缺頁次數(shù)：%dtt,t+mSIZE);printf(缺頁率：%d/%dn,t+mSIZE,pSIZE);printf(置換次數(shù)：%dtt,t);printf(訪問命中率：%d%n,(pSIZE-(t+mSIZE)*100/pSIZE);printf(-n);/*計算過程延遲*/void compute()int i;printf(正在進(jìn)行相關(guān)計算，請稍候);for(i=1;i20;i+)mDelay(15);if(i%4=0)printf(bbbbbb bbbbbb);elseprintf();for(i=0;i+30;printf(b);for(i=0;i+30;printf( );for(i=0;i+30;printf(b);/*先進(jìn)先出頁面置換算法*/void FIFO() int memery10=0; int time10=0; /*記錄進(jìn)入物理塊的時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; timei=i; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理塊中*/ count+;/*計算換出頁*/ max=time0time1?0:1;for(m=2;mmSIZE;m+)if(timemtimemax)max=m; memerymax=pagei; timemax=i; /*記錄該頁進(jìn)入物理塊的時間*/ for(j=0;jmSIZE;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=memeryj; compute();print(count);/*最近最久未使用置換算法*/void LRU() int memery10=0; int flag10=0; /*記錄頁面的訪問時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; flagi=i; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; else flagj=i; /*刷新該頁的訪問時間*/ if(k=mSIZE) /*如果不在物理塊中*/ count+;/*計算換出頁*/ max=flag0flag1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)max=m; memerymax=pagei; flagmax=i; /*記錄該頁的訪問時間*/ for(j=0;jmSIZE;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=memeryj; compute();print(count);/*最佳置換算法*/void OPT() int memery10=0; int next10=0; /*記錄下一次訪問時間*/ int i,j,k,l,m; int max; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理塊中*/ count+;/*得到物理快中各頁下一次訪問時間*/for(m=0;mmSIZE;m+)for(l=i+1;l=next1?0:1;for(m=2;mnextmax)max=m;/*下一次訪問時間都為pSIZE,則置換物理塊中第一個*/memerymax=pagei;for(j=0;jmSI