頁面置換算法C語言

1、頁面置換算法的演示一.題目要求：設(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)度算法。

2、5、根據(jù)方案使算法得以模擬實現(xiàn)。6、鍛煉知識的運用能力和實踐能力。三. 相關(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)

3、。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ù)組nextmSI

4、ZE記錄物理塊中對應(yīng)頁面的最后訪問時間。每當(dāng) 發(fā)生缺頁時，就從物理塊中找出最后訪問時間最大的頁面，調(diào)出該頁，換入所缺的頁面?！咎貏e聲明】若物理塊中的頁面都不再使用，則每次都置換物理塊中第一個位置的頁面。FIFO基本思想：是用隊列存儲內(nèi)存中的頁面，隊列的特點是先進(jìn)先出，與該算法是一致的， 所以每當(dāng)發(fā)生缺頁時，就從隊頭刪除一頁，而從隊尾加入缺頁?；蛘呓柚o助數(shù) 組timemSIZE記錄物理塊中對應(yīng)頁面的進(jìn)入時間，每次需要置換時換出進(jìn)入時 間最小的頁面。LRU基本思想：是用一維數(shù)組pagepSIZE存儲頁面號序列，memerymSIZE是存儲裝入物 理塊中的頁面。數(shù)組flag1O標(biāo)記頁面的訪問時間。

5、每當(dāng)使用頁面時，刷新訪問 時間。發(fā)生缺頁時，就從物理塊中頁面標(biāo)記最小的一頁，調(diào)出該頁，換入所缺的 頁面。五. 流程圖：如下頁所示-2 -六.源代碼:載入頁號序列，從第0個得到頁號將頁號放入物理塊中，編號加1根據(jù)選擇的置換算法完成置換如下頁所示【使用C語言】-4 -#i nclude #i nclude /*全局變量*/int mSIZE; /* 物理塊數(shù) */int pSIZE; /*頁面號引用串個數(shù)*/static int memery10=0; /* 物理塊中的頁號 */static int page100=0; /* 頁面號引用串 */static int temp10010=0; /*

6、 輔助數(shù)組 */*置換算法函數(shù)*/void FIFO();void LRU();void OPT();/*輔助函數(shù)*/void print(un sig ned int t);void desig nBy();void dow nl oad();void mDelay (un sig ned int Delay);/*主函數(shù)*/void mai n()int i,k,code;system(color 0A);desig nBy();I n);n);printf( |請按任意鍵進(jìn)行初始化操作 printf( 1printf( );getch();system(cls);system(color

7、 0B);printf(請輸入物理塊的個數(shù)(M=10):);sca nf(%d,&mSIZE);printf(請輸入頁面號引用串的個數(shù)(P=100):);sca nf(%d,&pSIZE);puts(請依次輸入頁面號引用串(連續(xù)輸入，無需隔開)：);for(i=0;ivpSIZE;i+)sca nf(%1d,&pagei);dow nl oad();system(cls);system(color 0E);doputs(輸入的頁面號引用串為：);for(k=0;k=(pSIZE-1)/20;k+)for(i=20*k;(ipSIZE )&(i);getch();system(cls);whil

8、e (code!=4);getch();/*載入數(shù)據(jù)*/void dow nl oad()int i;system(color OD);n);n);n);O);printf( iprintf( |正在載入數(shù)據(jù)，請稍候！! printf( 1prin tf(Loadi ng.n);printf( for(i=0;i51;i+) prin tf(b);for(i=0;i);printf(nFinish.n載入成功，按任意鍵進(jìn)入置換算法選擇界面：)getch();/*設(shè)置延遲*/ void mDelay (un sig ned int Delay) un sig ned int i;for(;Del

9、ay0;Delay-)for(i=0;i I n);printf( |1n); void print(un sig ned 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) prin tf(%dn,pagei);elseprin tf(%d ,pagei);for(j=0;jmSIZE;j+)for(i=20*k;(imSIZE+20*k)&(i=j)prin tf( |%d|,tempij);e

10、lseprin tf( | |);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( );elseprin tf( |%d|,tempij);/*每行顯示20個*/if(i%20=0)con ti nue;prin tf(n);printf(n);printf(缺頁次數(shù)：%dtt,t+mSIZE);printf(缺頁率：d/%dn,t+mSIZE,pSIZE);printf(置換次數(shù)：%dtt,t)

11、;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)prin tf(bbbbbbbbbbbb);elseprintf( O);for(i=0;i+30;pri ntf(b);for(i=0;i+30;pri ntf(” );for(i=0;i+30;pri ntf(b);/*先進(jìn)先出頁面置換算法*/void FIFO()int memery10=0;int tim

12、e10=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) /*如果不在物理塊中*/coun t+;/*計算換出頁*/max=time0ti

13、me1?0:1; for(m=2;mmSIZE;m+) if(timemtimemax) max=m;memerymax=pagei;timemax=i; /*記錄該頁進(jìn)入物理塊的時間*/for(j=0;jmSIZE;j+)tempij=memeryj;elsefor(j=0;jmSIZE;j+) tempij=memeryj;compute。；prin t(co un t);/*最近最久未使用置換算法*/void LRU()int memery10=0;int flag1O=O; /*記錄頁面的訪問時間*/int i,j,k,m;int max=0; /*記錄換出頁*/int count=0

14、; /*記錄置換次數(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+;elseflagj=i; /*刷新該頁的訪問時間*/if(k=mSIZE) /*如果不在物理塊中*/coun t+;/*計算換出頁*/ max=flag0vflag1?0:1;for(m=2;mmSIZE;m+) if(flagmvfl

15、agmax) max=m; memerymax=pagei;flagmax=i; /*記錄該頁的訪問時間*/ for(j=0;jmSIZE;j+) tempij=memeryj;elsefor(j=0;jmSIZE;j+) tempij=memeryj;compute();prin t(co un t);/*最佳置換算法*/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) /*如果不在物