頁面置換算法C語言

1、頁面置換算法的演示一.題目要求：設計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，編程序演示下述算法的具體實現(xiàn)過程， 并計算訪問命中率：要求設計主界面以靈活選擇某算法，且以下算法都要實現(xiàn)1）最優(yōu)置換算法（OPT）:將以后永不使用的或許是在最長（未來）時間內(nèi)不再 被訪問的頁面換出。2）先進先出算法（FIFO）:淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留 時間最久的頁面予以淘汰。3）最近最久未使用算法（LRU）:淘汰最近最久未被使用的頁面。4）最不經(jīng)常使用算法（LFU）.實驗目的：1、用C語言編寫OPT、FIFO、LRU，LFU四種置換算法2熟悉內(nèi)存分頁管理策略。3、了解頁面置換的算法。4、掌握一般常用的調(diào)度算法。

2、5、根據(jù)方案使算法得以模擬實現(xiàn)。6、鍛煉知識的運用能力和實踐能力。三. 相關(guān)知識：1. 虛擬存儲器的引入：局部性原理：程序在執(zhí)行時在一較短時間內(nèi)僅限于某個局部；相應的，它所 訪問的存儲空間也局限于某個區(qū)域， 它主要表現(xiàn)在以下兩個方面：時間局限性和 空間局限性。2. 虛擬存儲器的定義：虛擬存儲器是只具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進展 擴大的一種存儲器系統(tǒng)。3. 虛擬存儲器的實現(xiàn)方式：分頁請求系統(tǒng)，它是在分頁系統(tǒng)的根底上，增加了請求調(diào)頁功能、頁面置換 功能所形成的頁面形式虛擬存儲系統(tǒng)。請求分段系統(tǒng)，它是在分段系統(tǒng)的根底上，增加了請求調(diào)段與分段置換功能 后，所形成的段式虛擬存儲系統(tǒng)

3、。4. 頁面分配：平均分配算法，是將系統(tǒng)中所有可供分配的物理塊，平均分配給各個進程。按比例分配算法，根據(jù)進程的大小按比例分配物理塊。考慮優(yōu)先的分配算法，把內(nèi)存中可供分配的所有物理塊分成兩局部：一局部 按比例地分配給各進程；另一局部如此根據(jù)個進程的優(yōu)先權(quán)， 適當?shù)脑黾悠湎鄳?份額后，分配給各進程。5. 頁面置換算法：常用的頁面置換算法有 OPT、FIFO、LRU、Clock、LFU、PBA等。四. 設計思想:選擇置換算法，先輸入所有頁面號，為系統(tǒng)分配物理塊，依次進展置換：OPT根本思想：是用一維數(shù)組pagepSIZE存儲頁面號序列，memerymSIZE是存儲裝入物 理塊中的頁面。數(shù)組nextm

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

5、訪問時間。每當使用頁面時，刷新訪問 時間。發(fā)生缺頁時，就從物理塊中頁面標記最小的一頁，調(diào)出該頁，換入所缺的 頁面。五. 流程圖：如下頁所示六.源代碼：如下頁所示【使用C語言】#i nclude <stdio.h>#i nclude <stdlib.h>/*全局變量*/int mSIZE; /* 物理塊數(shù) */int pSIZE; /*頁面號引用串個數(shù)*/static int memery10=0; /* 物理塊中的頁號 */static int page100=0; /* 頁面號引用串 */static int temp10010=0; /* 輔助數(shù)組 */*置換算法函

6、數(shù)*/void FIFO();void LRU();void OPT();/*輔助函數(shù)*/void print(un sig ned int t);void desig nBy();void dow nl oad();void mDelay(unsigned int Delay);/*主函數(shù)*/void mai n()int i,k,code;system("color 0A");desig nBy();I n");n");printf(" |請按任意鍵進展初始化操作printf(" 1printf(" >>&g

7、t;");getch();system("cls");system("color 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("%

8、1d",&pagei);dow nl oad();system("cls");system("color 0E");doputs("輸入的頁面號引用串為：");for(k=0;k<=(pSIZE-1)/20;k+)for(i=20*k;(i<pSIZE )&&(i<20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1)prin tf("%dn",pagei);elseprin tf("%d&quo

9、t;,pagei);prin tf("* * * * * * * * * * * * * * * * * * * * * * *n")printf("*請選擇頁面置換算法：ttt *n");prin tf("*n");printf("* 1.先進先出(FIFO)2.最近最久未使用(LRU) *n");printf("* 3.最優(yōu)(OPT)4.退出*n");prin tf("* * * * * * * * * * * * * * * * * * * * * * *n")prin

10、 tf("請選擇操作：bb");sca nf("%d",&code);switch(code)case 1:FIFO();break;case 2:LRU();break;case 3:OPT();break;case 4:system("cls");system("color 0A");designBy(); /*顯示設計者信息后退出*/printf(" |謝謝使用頁面置換算法演示器！正版授權(quán)I n");printf(" 1n");exit(0);default:p

11、rintf("輸入錯誤，請重新輸入：");printf("按任意鍵重新選擇置換算法：>>>"); getch();system("cls");while (code!=4);getch();/*載入數(shù)據(jù)*/void dow nl oad()int i;system("color 0D");printf(" i1n");printf(" |正在載入數(shù)據(jù)，請稍候川丨n");prin tf(" 11n");O")；prin tf(&q

12、uot;Loadi ng.n");printf("for(i=0;i<51;i+)prin tf("b");for(i=0;i<50;i+)mDelay(pSIZE+mSIZE)/2);prin tf(">");printf("nFinish.'n載入成功，按任意鍵進入置換算法選擇界面：>>>");getch();/*設置延遲*/void mDelay (un sig ned int Delay)un sig ned int i;for(;Delay>0;Delay

13、-)for(i=0;i<124;i+)prin tf(" b");/*顯示設計者信息*/void desig nBy()1n");課題三：頁面置換算法丨n");學號：081001117| n");某某：邢磊Wisual C+ 6.0> | n");1n");printf(" iprintf(" | printf(" |printf(" | printf(" |void print(un sig ned int t)int i,j,k,l;int flag;for(

14、k=0;k<=(pSIZE-1)/20;k+)for(i=20*k;(i<pSIZE )&&(i<20*(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;j<mSIZE;j+)for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i+)if(i>=j)prin tf(" |%d|"

15、;,tempij);elseprin tf(" | |");for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1);i+)for(flag=0,l=0;l<mSIZE;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(

16、"n");prin tf("缺頁次數(shù):%dtt",t+mSIZE);prin tf("缺頁率:%d/%dn",t+mSIZE,pSIZE);prin tf("置換次數(shù):%dtt",t);prin tf("訪問命中率:%d%n",(pSIZE-(t+mSIZE)*100/pSIZE); printf("n");/*計算過程延遲*/void pute()int i;printf("正在進展相關(guān)計算，請稍候");for(i=1;i<20;i+)mDelay

17、(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");/*先進先出頁面置換算法*/void FIFO()int memery10=0;int time10=0; /*記錄進入物理塊的時間*/int i,j,k,m;int max=0; /*記錄換出頁*/int count=

18、0; /*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/for(i=0;i<mSIZE;i+)memeryi=pagei;timei=i;for(j=0;j<mSIZE;j+) tempij=memeryj;for(i=mSIZE;i<pSIZE;i+)/*判斷新頁面號是否在物理塊中*/for(j=0,k=0;j<mSIZE;j+)if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理塊中*/ coun t+;/*計算換出頁*/max=time0<time1?0:1;for(m=2;m<mSIZE;m+) if(timem&l

19、t;timemax) max=m; memerymax=pagei; timemax=i; /*記錄該頁進入物理塊的時間*/ for(j=0;jvmSIZE;j+) tempij=memeryj;elsefor(j=0;j<mSIZE;j+) tempij=memeryj;pute();prin t(co un t);/*最近最久未使用置換算法*/void LRU()int memery10=0;int flag10=0; /*記錄頁面的訪問時間*/int i,j,k,m;int max=0; /*記錄換出頁*/int count=0; /*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/

20、for(i=0;i<mSIZE;i+)memeryi=pagei;flagi=i;for(j=0;j<mSIZE;j+)tempij=memeryj; for(i=mSIZE;i<pSIZE;i+)/*判斷新頁面號是否在物理塊中*/for(j=0,k=0;j<mSIZE;j+)if(memeryj!=pagei)k+;elseflagj=i; /*刷新該頁的訪問時間*/if(k=mSIZE) /*如果不在物理塊中*/coun t+;/*計算換出頁*/ max=flag0vflag1?0:1;for(m=2;m<mSIZE;m+) if(flagmvflagmax) max=m; memerymax=pagei;flagmax=i; /*記錄該頁的訪問時間*/ for(j=0;j<mSIZE;j+) tempij=memeryj;elsefor(j=0;j<mSIZE;j+) tempij=memeryj;pute()