請(qǐng)求頁(yè)式存儲(chǔ)管理的頁(yè)面置換算法

suiqianying 2013-01-14

展開全文

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

一．實(shí)驗(yàn)?zāi)康?/SPAN>

通過(guò)請(qǐng)求頁(yè)式存儲(chǔ)管理中頁(yè)面置換算法模擬程序,，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁(yè)式存儲(chǔ)管理的頁(yè)面置換算法,。

二．實(shí)驗(yàn)屬性

設(shè)計(jì)

三．實(shí)驗(yàn)內(nèi)容

1.通過(guò)隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列,，共320條指令,，指令的地址按下述原則生產(chǎn)：

50％的指令是順序執(zhí)行的；

25％的指令是均勻分布在前地址部分,；

25％的指令是均勻分布在后地址部分,。

2.將指令序列變換成為頁(yè)地址流

設(shè)頁(yè)面大小為1K,；用戶內(nèi)存容量為4頁(yè)到32頁(yè),；用戶虛存容量為32K。

在用戶虛存中，按每K存放10條指令排列虛存地址,，即320條指令在虛存中的存放方式為：第0條至第9條指令為第0頁(yè)；第10條至19條指令為第1頁(yè),；…第310條至319條指令為第31頁(yè),。

3.計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。

(1) 先進(jìn)先出算法（FIFO）

(2) 最近最少使用算法（LRU）

(3) 最佳使用算（OPT）

命中率＝１－頁(yè)面失效次數(shù)／頁(yè)地址流長(zhǎng)度

本實(shí)驗(yàn)中,，頁(yè)地址流長(zhǎng)度為320，頁(yè)面失效次數(shù)為每次訪問(wèn)相應(yīng)指令時(shí),，該指令所對(duì)應(yīng)的頁(yè)不在內(nèi)存的次數(shù)。

四．思路

關(guān)于隨機(jī)數(shù)的產(chǎn)生辦法,。首先要初始化設(shè)置隨機(jī)數(shù)，產(chǎn)生序列的開始點(diǎn)，例如，通過(guò)下列語(yǔ)句實(shí)現(xiàn)：

srand ( 400 ) ,；

(1) 計(jì)算隨機(jī)數(shù)，產(chǎn)生320條指令序列

m＝160；

for (i＝0；i＜80；i++＝

{

j＝i﹡4,；

a[j]＝m；

a[j+1]＝m+1,；

a[j+2]＝a[j] ﹡1.0﹡ rand( )/32767；

a[j+3]＝a[j+2]+1

m＝a[j+3]+(319-a[j+3]) ﹡1.0﹡rand( )/32767,；

}

(2) 將指令序列變換成為頁(yè)地址流

for ( k＝0,；k＜320；k++)

{ pt＝a[k]/10,；

pd= a[k]%10,；

…

}

(3) 計(jì)算不同算法的命中率

rate＝1-1.0﹡U/320 ；

其中U為缺頁(yè)中斷次數(shù),，320是頁(yè)地址流長(zhǎng)度,。

(4) 輸出格式

k fifo 1ru

4 0.23 0.25

…

32 1.0 1.0

五．實(shí)驗(yàn)報(bào)告

1．寫出你編寫的C語(yǔ)言程序。

#include<conio.h>

#include<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; /*記錄頁(yè)面號(hào)*/

int time; /*記錄調(diào)入內(nèi)存時(shí)間*/

}Page; /* 頁(yè)面邏輯結(jié)構(gòu),，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)*/

Page b[bsize]; /*內(nèi)存單元數(shù)*/

int c[bsize][psize]; /*暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū)*/

int queue[100]; /*記錄調(diào)入隊(duì)列*/

int K; /*調(diào)入隊(duì)列計(jì)數(shù)變量*/

int phb[bsize]={0}; //物理塊標(biāo)號(hào)

int pro[psize]={0}; //進(jìn)程序列號(hào)

int flag[bsize] = {0}; //進(jìn)程等待次數(shù)(存放最久未被使用的進(jìn)程標(biāo)志)

int i = 0, j = 0,k = 0; //i表示進(jìn)程序列號(hào),j表示物理塊號(hào)

int m = -1, n = -1; //物理塊空閑和進(jìn)程是否相同判斷標(biāo)志

int max = -1,maxflag = 0; //標(biāo)記替換物理塊進(jìn)程下標(biāo)

int count = 0; //統(tǒng)計(jì)頁(yè)面缺頁(yè)次數(shù)

//**************************************************************//

//**************************************************************//隨機(jī)產(chǎn)生序列號(hào)函數(shù)

//**************************************************************

int* build()

{

printf("隨機(jī)產(chǎn)生一個(gè)進(jìn)程序列號(hào)為：\n");

int i = 0;

for(i=0; i<psize; i++)

{

pro[i] = 10*rand()/(RAND_MAX+1)+1;

printf("%d ",pro[i]);

}

printf("\n");

return(pro);

}

//**************************************************************//查找空閑物理塊

//**************************************************************

int searchpb()

{

for(j=0; j<bsize; j++)

{

if(phb[j] == 0)

{

m = j;

return m;

break;

}

return -1;

}

//**************************************************************//查找相同進(jìn)程

//**************************************************************

int searchpro()

{

for(j = 0; j < bsize; j++)

{

if(phb[j] == pro[i])

{

n = j;

return j;

}

return -1;

}

//**************************************************************//初始化內(nèi)存

//**************************************************************

void empty()

{

for(i=0;i<bsize;i++)

phb[i]=0;

count=0; //計(jì)數(shù)器置零

}

//**************************************************************//先進(jìn)先出頁(yè)面置換算法

//**************************************************************

void FIFO()

{

for(i = 0; i<psize; i++)

{

m=searchpb();

n=searchpro();

//找flag值最大的

for(j = 0; j < bsize;j++)

{

if(flag[j]>maxflag)

{

maxflag = flag[j];

max = j;

}

if(n == -1) //不存在相同進(jìn)程

{

if(m != -1) //存在空閑物理塊

{

phb[m] = pro[i]; //進(jìn)程號(hào)填入該空閑物理塊

count++;

flag[m] = 0;

for(j = 0;j <= m; j++)

{

flag[j]++;

}

m = -1;

}

else //不存在空閑物理塊

{

phb[max] = pro[i];

flag[max] = 0;

for(j = 0;j < bsize; j++)

{

flag[j]++;

}

max = -1;

maxflag = 0;

count++;

}

else //存在相同的進(jìn)程

{

phb[n] = pro[i];

for(j = 0;j < bsize; j++)

{

flag[j]++;

}

n = -1;

}

for(j = 0 ;j < bsize; j++)

{

printf("%d ",phb[j]);

}

printf("\n");

}

printf("缺頁(yè)次數(shù)為：%d\n",count);

printf("\n");

}

//**************************************************************

/*初始化內(nèi)存單元,、緩沖區(qū)*/

void Init(Page *b,int c[bsize][psize])

{

int i,j;

for(i=0;i<psize;i++)

{

b[i].num=-1;

b[i].time=psize-i-1;

}

for(i=0;i<bsize;i++)

for(j=0;j<psize;j++)

c[i][j]=-1;

}

/*取得在內(nèi)存中停留最久的頁(yè)面,默認(rèn)狀態(tài)下為最早調(diào)入的頁(yè)面*/

int GetMax(Page *b)

{

int i;

int max=-1;

int tag=0;

for(i=0;i<bsize;i++)

{

if(b[i].time>max)

{

max=b[i].time;

tag=i;

}

return tag;

}

/*判斷頁(yè)面是否已在內(nèi)存中*/

int Equation(int fold,Page *b)

{

int i;

for(i=0;i<bsize;i++)

{

if (fold==b[i].num)

return i;

}

return -1;

}

/*LRU核心部分*/

void Lruu(int fold,Page *b)

{

int i;

int val;

val=Equation(fold,b);

if (val>=0)

{

b[val].time=0;

for(i=0;i<bsize;i++)

if (i!=val)

b[i].time++;

}

else

{

queue[++K]=fold;/*記錄調(diào)入頁(yè)面*/

val=GetMax(b);

b[val].num=fold;

b[val].time=0;

for(i=0;i<bsize;i++)

if (i!=val)

b[i].time++;

}

void LRU()

{

int i,j;

K=-1;

Init(b, c);

for(i=0;i<psize;i++)

{

Lruu(pro[i],b);

c[0][i]=pro[i];

/*記錄當(dāng)前的內(nèi)存單元中的頁(yè)面*/

for(j=0;j<bsize;j++)

c[j][i]=b[j].num;

}

/*結(jié)果輸出*/

printf("內(nèi)存狀態(tài)為：\n");

Myprintf;

for(j=0;j<psize;j++)

printf("|%2d ",pro[j]);

printf("|\n");

Myprintf;

for(i=0;i<bsize;i++)

{ for(j=0;j<psize;j++)

{

if(c[i][j]==-1)

printf("|%2c ",32);

else

printf("|%2d ",c[i][j]);

}

printf("|\n");

}

Myprintf;

printf("\n調(diào)入隊(duì)列為:");

for(i=0;i<K+1;i++)

printf("%3d",queue[i]);

printf("\n缺頁(yè)次數(shù)為：%6d\n缺頁(yè)率：%16.6f",K+1,(float)(K+1)/psize);

}

//**************************************************************//主函數(shù)

//**************************************************************

void main()

{

int sel ;

do{

printf("\t\t\t--------------------------------------\t\t\t");

printf("\t\t\t ☆☆^-^歡迎進(jìn)入操作系統(tǒng)界面^-^☆☆ \t\t\t");

printf("\t\t\t--------------------------------------\t\t\t\n");

printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\t\t\t");

printf("\t\t\t☆ 虛擬內(nèi)存 ☆ \t\t\t");