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

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

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

3、0；i80；i+ ji4； ajm； aj+1m+1； aj+2aj 1.0 rand( )/32767； aj+3aj+2+1 maj+3+(319-aj+3) 1.0rand( )/32767； (2) 將指令序列變換成為頁地址流 for ( k0；k320；k+) ptak/10； pd= ak%10； (3) 計算不同算法的命中率 rate1-1.0U/320 ； 其中U為缺頁中斷次數(shù)，320是頁地址流長度。 (4) 輸出格式 k fifo 1ru 4 0.23 0.25 32 1.0 1.0五實驗報告1寫出你編寫的C語言程序。#include<conio.h> #incl

4、ude<stdio.h>#include<stdlib.h>#include<string.h>#define Myprintf printf("|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|n") /*表格控制*/ #define bsize 4 /物理塊大小#define psize 16 /進程大小typedef struct page int num; /*記錄頁面號*/ int time; /*記錄調(diào)入內(nèi)存時間*/ Page; /* 頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實現(xiàn)設(shè)計*/ Page bbsize; /*

5、內(nèi)存單元數(shù)*/ int cbsizepsize; /*暫保存內(nèi)存當前的狀態(tài)：緩沖區(qū)*/ int queue100; /*記錄調(diào)入隊列*/ int K; /*調(diào)入隊列計數(shù)變量*/ int phbbsize=0; /物理塊標號int propsize=0; /進程序列號int flagbsize = 0; /進程等待次數(shù)(存放最久未被使用的進程標志)int i = 0, j = 0,k = 0; /i表示進程序列號,j表示物理塊號int m = -1, n = -1; /物理塊空閑和進程是否相同判斷標志int max = -1,maxflag = 0; /標記替換物理塊進程下標int count

6、= 0; /統(tǒng)計頁面缺頁次數(shù)/*/*/隨機產(chǎn)生序列號函數(shù)/*int* build()printf("隨機產(chǎ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<bsize; j+) if(phbj = 0) m = j; return m; break; r

7、eturn -1;/*/查找相同進程/*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值最大的 for(j = 0; j < bsize;j+) if(fl

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

9、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=-1; bi.time=psiz

10、e-i-1; for(i=0;i<bsize;i+) for(j=0;j<psize;j+) cij=-1; /*取得在內(nèi)存中停留最久的頁面,默認狀態(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;i+) if (fo

11、ld=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 queue+K=fold;/*記錄調(diào)入頁面*/ 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; /*記錄當前的內(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+) fo

13、r(j=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 main()i

14、nt sel ; do printf("ttt-ttt");printf("ttt -歡迎進入操作系統(tǒng)界面- ttt");printf("ttt-tttn");printf("tttttt"); printf("ttt 虛擬內(nèi)存 ttt");printf("ttt-ttt"); printf("ttt 1、產(chǎn)生隨機序列 ttt");printf("ttt-ttt"); printf("ttt 2、最久未使用(LRU) ttt&

15、quot;);printf("ttt-ttt"); printf("ttt 3、先進先出(FIFO) ttt");printf("ttt-ttt"); printf("ttt 4、最佳置換算法(OPT) ttt");printf("ttt-ttt");printf("ttt 5、三種算法的比較() ttt");printf("ttt-ttt");printf("ttt 0、退出(Exit) ttt"); printf("ttt

16、tttn"); printf("請選擇所要執(zhí)行的操作(0/1/2/3/4/5):"); scanf("%d",&sel); switch(sel) case0:printf("ttt-再見！- tttn");system("pause");break; case 1:build();break; case 2:printf("最久未使用算n");LRU();empty();printf("n");break; case 3:printf("先進先出

17、算n");FIFO();empty();printf("n");break; case 5:printf("先進先出算法n");FIFO();empty();printf("最久未使用算法n");LRU();empty();break; default: printf("請輸入正確的選項號！");printf("nn");break;while(sel!=0);產(chǎn)生的隨機序列：最近最少使用算法執(zhí)行結(jié)果如下：先進先出FIFO算法執(zhí)行結(jié)果：2總結(jié)體會請求頁式存儲管理的實現(xiàn)原理。請求頁式管理

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