實驗五請求頁式存儲管理的頁面置換算法

1、操作系統(tǒng)實驗報告班級:計科0801班 姓名：韓偉偉 學(xué)號：08407106時間：2011-5-25實驗五請求頁式存儲管理的頁面置換算法一.實驗?zāi)康耐ㄟ^請求頁式存儲管理中頁面置換算法模擬程序，了解虛擬存儲技術(shù)的特點，掌握請 求頁式存儲管理的頁面置換算法。二實驗屬性設(shè)計三.實驗內(nèi)容1通過隨機(jī)數(shù)產(chǎn)生一個指令序列，共320條指令，指令的地址按下述原則生產(chǎn)：50%的指令是順序執(zhí)行的；25%的指令是均勻分布在前地址部分；25%的指令是均勻分布在后地址部分。2將指令序列變換成為頁地址流設(shè)頁面大小為1K;用戶內(nèi)存容量為 4頁到32頁；用戶虛存容量為 32K。在用戶虛存中，按每 K存放10條指令排列虛存地址，即

2、320條指令在虛存中的存放方式為：第0條至第9條指令為第0頁；第10條至19條指令為第1頁；第310條至319條指 令為第31頁。3計算并輸出下述各種算法在不同內(nèi)存容量下的命中率。(1) 先進(jìn)先出算法(FIFO)(2) 最近最少使用算法(LRU )(3) 最佳使用算(OPT)命中率=1頁面失效次數(shù)/頁地址流長度本實驗中，頁地址流長度為320,頁面失效次數(shù)為每次訪問相應(yīng)指令時，該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。四思路關(guān)于隨機(jī)數(shù)的產(chǎn)生辦法。首先要初始化設(shè)置隨機(jī)數(shù)，產(chǎn)生序列的開始點，例如，通 過下列語句實現(xiàn)：srand ( 400 )；(1) 計算隨機(jī)數(shù)，產(chǎn)生 320條指令序列m= 160；for (

3、i = 0； i< 80； i+ =j = i * 4； aj = m； aj+1 = m+1 ； aj+2 = aj * 1.0 * rand( )/32767 ； aj+3 = aj+2+1m = aj+3+(319-aj+3)* 1.0* rand( )/32767 ；(2) 將指令序列變換成為頁地址流for ( k = 0; kv320; k+) pt = ak/10 ;pd= ak%10 ；(3) 計算不同算法的命中率rate= 1-1.0* U/320 ;其中 U 為缺頁中斷次數(shù)， 320 是頁地址流長度。(4) 輸出格式kfifo1ru40.230.25321.01.0五實

4、驗報告1 寫出你編寫的 C 語言程序。 #include<conio.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMyprintfPage;/*Page bbsize; /* int cbsizepsize; /*int queue100;/*int K;/*記錄調(diào)入隊列 */調(diào)入隊列計數(shù)變量 */int phbbsize=0; / int propsize=0; / int flagbsize = 0; /int i = 0, j = 0,k = 0; /i int

5、 m = -1, n = -1;/物理塊標(biāo)號進(jìn)程序列號進(jìn)程等待次數(shù) ( 存放最久未被使用的進(jìn)程標(biāo)志 ) 表示進(jìn)程序列號 ,j 表示物理塊號 物理塊空閑和進(jìn)程是否相同判斷標(biāo)志int max = -1,maxflag = 0; /int count = 0;/標(biāo)記替換物理塊進(jìn)程下標(biāo)統(tǒng)計頁面缺頁次數(shù)/*/*/隨機(jī)產(chǎn)生printf("|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|n ") /* 表格控制 */#define bsize 4/物理塊大小#define psize 16/進(jìn)程大小typedef struct pageint num; /*記錄頁面

6、號 */int time; /*記錄調(diào)入內(nèi)存時間 */*/頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實現(xiàn)設(shè)計 內(nèi)存單元數(shù) */ 暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū) */序列號函數(shù)/* int* build()printf(" 隨機(jī)產(chǎn)生一個進(jìn)程序列號為： n"); int i = 0;for(i=0; i<psize; i+)proi = 10*rand()/(RAND_MAX+1)+1; printf("%d ",proi);printf("n"); return(pro);查找空閑/* 物理塊*int searchpb()for(j=0; j&l

7、t;bsize; j+)if(phbj = 0)m = j;return m;break;return -1;查找相同/* 進(jìn)程*int searchpro()for(j = 0; j < bsize; j+)if(phbj = proi)n = j;return j;return -1;*初始化內(nèi)/*void empty()for(i=0;i<bsize;i+)phbi=0;count=0; /計數(shù)器置零/*/ 頁面置換算法/* void FIFO()for(i = 0; i<psize; i+)m=searchpb(); n=searchpro();/ 找 flag 值最

8、大的 for(j = 0; j < bsize;j+) if(flagj>maxflag) maxflag = flagj; max = j;if(n = -1) if(m != -1) 先進(jìn)先出/phbm = proi; / count+;flagm = 0;for(j = 0;j <= m; j+) flagj+;m = -1;else/phbmax = proi; flagmax = 0;不存在相同進(jìn)程存在空閑物理塊進(jìn)程號填入該空閑物理塊不存在空閑物理塊for(j = 0;j < bsize; j+)flagj+;max = -1;maxflag = 0;coun

9、t+;else / 存在相同的進(jìn)程phbn = proi;for(j = 0;j < bsize; j+)flagj+;n = -1;for(j = 0 ;j < bsize; j+)printf("%d ",phbj);printf("n");printf(" 缺頁次數(shù)為： %dn",count);printf("n");/*/*/* 初始化內(nèi)存單元、緩沖區(qū) */void Init(Page *b,int cbsizepsize)int i,j;for(i=0;i<psize;i+)bi.num

10、=-1;bi.time=psize-i-1;for(i=0;i<bsize;i+)for(j=0;j<psize;j+) cij=-1;/* 取得在內(nèi)存中停留最久的頁面 , 默認(rèn)狀態(tài)下為最早調(diào)入的頁面 */ int GetMax(Page *b)int i;int max=-1;int tag=0;for(i=0;i<bsize;i+) if(bi.time>max) max=bi.time; tag=i;return tag;/* 判斷頁面是否已在內(nèi)存中 */ int Equation(int fold,Page *b)int i;for(i=0;i<bsize

11、;i+)if (fold=bi.num) return i;return -1;/*LRU 核心部分 */void Lruu(int fold,Page *b)int i;int val; val=Equation(fold,b);if (val>=0)bval.time=0; for(i=0;i<bsize;i+) if (i!=val) bi.time+;else記錄調(diào)入頁面 */queue+K=fold;/* val=GetMax(b); bval.num=fold; bval.time=0;for(i=0;i<bsize;i+)if (i!=val) bi.time+

12、;void LRU()int i,j;K=-1;Init(b, c); for(i=0;i<psize;i+) Lruu(proi,b);c0i=proi;/* 記錄當(dāng)前的內(nèi)存單元中的頁面 */ for(j=0;j<bsize;j+) cji=bj.num;/* 結(jié)果輸出 */printf(" 內(nèi)存狀態(tài)為： n");Myprintf; for(j=0;j<psize;j+) printf("|%2d ",proj);printf("|n");Myprintf;for(i=0;i<bsize;i+) for(j=

13、0;j<psize;j+) if(cij=-1) printf("|%2c ",32);else printf("|%2d ",cij); printf("|n");Myprintf; printf("n 調(diào)入隊列為 :");for(i=0;i<K+1;i+) printf("%3d",queuei);printf("n 缺頁次數(shù)為： %6dn 缺頁率： %16.6f",K+1,(float)(K+1)/psize);主函數(shù)*void mai n()int sei

14、 ;doprintf("tttttt");printf("ttt A-A 歡迎進(jìn)入操作系統(tǒng)界面A-A ttt");printf("tttttt n");prin tf("ttt ttt");prin tf("ttt 虛擬內(nèi)存 ttt");prin tf("ttt ttt");prin tf("ttt1、產(chǎn)生隨機(jī)序列ttt");prin tf("ttt ttt");printf("ttt2、最久未使用(LRU)ttt"

15、);prin tf("ttt ttt");printf("ttt3、先進(jìn)先出(FIFO)ttt");prin tf("ttt ttt");printf("ttt4、最佳置換算法(OPT)ttt");prin tf("ttt ttt");prin tf("ttt5、三種算法的比較()ttt");prin tf("ttt ttt");printf("ttt0、退出(Exit)ttt");prin tf("ttttttn"

16、);printf(”請選擇所要執(zhí)行的操作(0/1/2/3/4/5):");scan f("%d", &sel);switch(sel) 再見! a-a tttn");system("pause");break;caseO:pri ntf("tttA-A case 1:build();break;case 2:pri ntf(”case 3:pri ntf(”case 5:pri ntf(”prin tf("最久未使用算法default: printf("while(sel!=O);最久未使用算 n

17、");LRU();empty();printf("n");break; 先進(jìn)先出算 n");FIFO();empty();printf("n");break;先進(jìn)先出算法 n");FIFO();empty();n ");LRU();empty();break;請輸入正確的選項號！");pri ntf("nn ”);break;產(chǎn)生的隨機(jī)序列:隨機(jī)產(chǎn)生二個進(jìn)穩(wěn)序列號為:最近最少使用算法執(zhí)行結(jié)果如下:1作 一 6 操 -; 的 一 ? 虐+-， aw k 2 要用為1 I 所使態(tài)一 6 俘乘L ;

18、霎帝一 1 清氏I8 I 6 ! 4 ： 18 264 ! 9 I 9 ： 9 5 9 : 9為為 籟: 隊枕率 入頁頁先進(jìn)先出FIFO算法執(zhí)行結(jié)果:2 總結(jié)體會請求頁式存儲管理的實現(xiàn)原理。請求頁式管理的基本原理是將邏輯地址空間分成大小相同的頁，將存儲地址空間分塊， 頁和塊的大小相等，通過頁表進(jìn)行管理。頁式系統(tǒng)的邏輯地址分為頁號和頁內(nèi)位移量。頁表包括頁號和塊號數(shù)據(jù)項， 它們一一對應(yīng)。根據(jù)邏輯空間的頁號， 查找頁表對應(yīng)項找到對應(yīng)的 塊號，塊號乘以塊長，加上位移量就行成存儲空間的物理地址。每個作業(yè)的邏輯地址空間是連續(xù)的，重定位到內(nèi)存空間后就不一定連續(xù)了。3.寫出這三種頁面置換算法的實現(xiàn)思想。FIFO算法總是淘汰最先調(diào)入主存的頁面，即淘汰在主存中駐留時間最長的頁面，認(rèn)為 駐留時間最長的頁不再使用的可能性較大。LRU算法淘汰的頁面是最近一段時間內(nèi)最久未被訪問的那一頁，它是基于程序局部性 原理來考慮的，認(rèn)為那些剛被使用過的頁面可能還要立即被使用，而那