實(shí)驗(yàn)四頁面置換算法代碼(一)

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

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

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

4、ZE記錄物理塊中對應(yīng)頁面的最后訪問時間。每當(dāng)發(fā) 生缺頁時，就從物理塊中找出最后訪問時間最大的頁面，調(diào)出該頁，換入所缺的頁面。【特別聲明】若物理塊中的頁面都不再使用，則每次都置換物理塊中第一個位置的頁面。FIFO基本思想：是用隊(duì)列存儲存中的頁面，隊(duì)列的特點(diǎn)是先進(jìn)先出，與該算法是一致的，所 以每當(dāng)發(fā)生缺頁時，就從隊(duì)頭刪除一頁，而從隊(duì)尾加入缺頁?；蛘呓柚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)出該頁，換入所缺的 頁面。五.流程圖：如下頁所示六.源代碼:如下頁所示【使用C語言】#include <stdio.h>#include <conio.h> #include <stdlib.h>/* 全局變量 */int mSIZE; /* 物理塊數(shù) */int pSIZE; /* 頁面號引用串個數(shù) */static int memery10=0; /* 物理塊中的頁號 */ static int page100=0; /* 頁面號引用串 */ static int temp100

6、10=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(" 1n");pr

7、intf(" >>>");getch();system("cls");system("color 0B");printf(" 請輸入物理塊的個數(shù) (M<=10)： "); scanf("%d",&mSIZE);printf(" 請輸入頁面號引用串的個數(shù) (P<=100)："); scanf("%d",&pSIZE);puts(" 請依次輸入頁面號引用串 (連續(xù)輸入，無需隔開 ) ："); f

8、or(i=0;i<pSIZE;i+) scanf("%1d",&pagei);download();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) printf("%dn&q

9、uot;,pagei);else printf("%d ",pagei);printf("* * * * * * * * * * * * * * * * * * * * * * *n");printf("* 請選擇頁面置換算法： ttt *n");printf("* *n");printf("* 1. 先進(jìn)先出 (FIFO) 2. 最近最久未使用 (LRU) *n"); printf("* 3.最佳 (OPT)4. 退出 *n");printf("* * * * *

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

11、quot;);printf(" 1"1 n");exit(0);default:printf(" 輸入錯誤，請重新輸入： ");printf(" 按任意鍵重新選擇置換算法： >>>");/getch();system("cls");while (code!=4); getch();/* 載入數(shù)據(jù) */void download()int i;system("color 0D");prin tf("i1n");printf("丨正在載入數(shù)據(jù)

12、，請稍候！!！ I n");prin tf("11n");printf("Loading.n");printf("O");for(i=0;i<51;i+)printf("b");for(i=0;i<50;i+)mDelay(pSIZE+mSIZE)/2);printf(">");>>>");printf("nFinish.n 載入成功，按任意鍵進(jìn)入置換算法選擇界面： getch();/* 設(shè)置延遲 */void mDelay(un

13、signed int Delay)unsigned int i;for(;Delay>0;Delay-)for(i=0;i<124;i+)printf(" b");/* 顯示設(shè)計(jì)者信息 */void designBy()printf(" in");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;(i<p

14、SIZE)&&(i<20*(k+1);i+) if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1) printf("%dn",pagei);elseprintf("%d ",pagei);for(j=0;j<mSIZE;j+) for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i+) if(i>=j)printf(" |%d|",tempij);else printf(" | |"); for(

15、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(" ");elseprintf(" |%d|",tempij);/* 每行顯示 20 個*/ if(i%20=0) continue;printf("n");printf("-n");printf("缺頁次數(shù)：%dtt&

16、quot;,t+mSIZE);printf("缺頁率： %d/%dn",t+mSIZE,pSIZE);printf("置換次數(shù)：%dtt",t);printf("訪問命中率： %d%n",(pSIZE-(t+mSIZE)*100/pSIZE);n");printf("/* 計(jì)算過程延遲 */ void compute()int i;printf(" 正在進(jìn)行相關(guān)計(jì)算，請稍候 "); for(i=1;i<20;i+) mDelay(15); if(i%4=0) printf("bb

17、bbbb bbbbbb");elseprin tf(" O"); 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ù) */*前m

18、SIZE個數(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) /* 如果不在物理塊中 */count+;/* 計(jì)算換出頁 */max=time0<time1?0:1;for(m=2;m<mSIZE;m+) if(timem<timema

19、x) max=m; memerymax=pagei; timemax=i; /* 記錄該頁進(jìn)入物理塊的時間 */ for(j=0;j<mSIZE;j+) tempij=memeryj;elsefor(j=0;j<mSIZE;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ù)直接

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) /* 如果不在物理塊中 */count+;/* 計(jì)算換出頁 */max=flag0<flag1?0:1;for(m=2;m<mSIZE;m+) if(fl

21、agm<flagmax) max=m; memerymax=pagei; flagmax=i; /* 記錄該頁的訪問時間 */ for(j=0;j<mSIZE;j+) tempij=memeryj;elsefor(j=0;j<mSIZE;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ù)直接放