實(shí)驗(yàn)五請求頁式存儲管理的頁面置換算法

1、操作系統(tǒng)實(shí)驗(yàn)報(bào)告班級:計(jì)科0801班 姓名：韓偉偉 學(xué)號：08407106 時(shí)間：2011-5-25實(shí)驗(yàn)五 請求頁式存儲管理的頁面置換算法一實(shí)驗(yàn)?zāi)康耐ㄟ^請求頁式存儲管理中頁面置換算法模擬程序，了解虛擬存儲技術(shù)的特點(diǎn)，掌握請求頁式存儲管理的頁面置換算法。二實(shí)驗(yàn)屬性設(shè)計(jì)三實(shí)驗(yàn)內(nèi)容1.通過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共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.計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。 (1) 先進(jìn)先出算法（FIFO） (2) 最近最少使用算法（LRU） (3) 最佳使用算（OPT） 命中率頁面失效次數(shù)頁地址流長度本實(shí)驗(yàn)中，頁地址流長度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時(shí)，該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。四思路 關(guān)于隨機(jī)數(shù)的產(chǎn)生辦法。首先要初始化設(shè)置隨機(jī)數(shù)，產(chǎn)生序列的開始點(diǎn)，例如，通過下列語句實(shí)現(xiàn)： srand ( 400 ) ； (1) 計(jì)算隨機(jī)數(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) 計(jì)算不同算法的命中率 rate1-1.0U/320 ； 其中U為缺頁中斷次數(shù)，320是頁地址流長度。 (4) 輸出格式 k fifo 1ru 4 0.23 0.25 32 1.0 1.0五實(shí)驗(yàn)報(bào)告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 /進(jìn)程大小typedef struct page int num; /*記錄頁面號*/ int time; /*記錄調(diào)入內(nèi)存時(shí)間*/ Page; /* 頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)*/ Page bbsize; /*

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

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

7、eturn -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; /計(jì)數(shù)器置零/*/先進(jìn)先出頁面置換算法/*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) /不存在相同進(jìn)程 if(m != -1) /存在空閑物理塊 phbm = proi; /進(jìn)程號填入該空閑物理塊 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 /存在相同的進(jìn)程 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)存中停留最久的頁面,默認(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;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; /*記錄當(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+) 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)入隊(duì)列為:"); 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 -歡迎進(jìn)入操作系統(tǒng)界面- ttt");printf("ttt-tttn");printf("tttttt"); printf("ttt 虛擬內(nèi)存 ttt");printf("ttt-ttt"); printf("ttt 1、產(chǎn)生隨機(jī)序列 ttt");printf("ttt-ttt"); printf("ttt 2、最久未使用(LRU) ttt&

15、quot;);printf("ttt-ttt"); printf("ttt 3、先進(jìn)先出(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("先進(jìn)先出

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

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