请求页式存储管理的页面置换算法

suiqianying 2013-01-14

展开全文

实验五请求页式存储管理的页面置换算法

一．实验目的

通过请求页式存储管理中页面置换算法模拟程序，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。

二．实验属性

设计

三．实验内容

1.通过随机数产生一个指令序列，共320条指令，指令的地址按下述原则生产：

50％的指令是顺序执行的；

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

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

2.将指令序列变换成为页地址流

设页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32K。

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条至第9条指令为第0页；第10条至19条指令为第1页；…第310条至319条指令为第31页。

3.计算并输出下述各种算法在不同内存容量下的命中率。

(1) 先进先出算法（FIFO）

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

(3) 最佳使用算（OPT）

命中率＝１－页面失效次数／页地址流长度

本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。

四．思路

关于随机数的产生办法。首先要初始化设置随机数，产生序列的开始点，例如，通过下列语句实现：

srand ( 400 ) ；

(1) 计算随机数，产生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) 将指令序列变换成为页地址流

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

{ pt＝a[k]/10；

pd= a[k]%10；

…

}

(3) 计算不同算法的命中率

rate＝1-1.0﹡U/320 ；

其中U为缺页中断次数，320是页地址流长度。

(4) 输出格式

k fifo 1ru

4 0.23 0.25

…

32 1.0 1.0

五．实验报告

1．写出你编写的C语言程序。

#include<conio.h>

#include<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; /*记录调入内存时间*/

}Page; /* 页面逻辑结构，结构为方便算法实现设计*/

Page b[bsize]; /*内存单元数*/

int c[bsize][psize]; /*暂保存内存当前的状态：缓冲区*/

int queue[100]; /*记录调入队列*/

int K; /*调入队列计数变量*/

int phb[bsize]={0}; //物理块标号

int pro[psize]={0}; //进程序列号

int flag[bsize] = {0}; //进程等待次数(存放最久未被使用的进程标志)

int i = 0, j = 0,k = 0; //i表示进程序列号,j表示物理块号

int m = -1, n = -1; //物理块空闲和进程是否相同判断标志

int max = -1,maxflag = 0; //标记替换物理块进程下标

int count = 0; //统计页面缺页次数

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

//**************************************************************//随机产生序列号函数

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

int* build()

{

printf("随机产生一个进程序列号为：\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;

}

//**************************************************************//查找相同进程

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

int searchpro()

{

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

{

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

{

n = j;

return j;

}

return -1;

}

//**************************************************************//初始化内存

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

void empty()

{

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

phb[i]=0;

count=0; //计数器置零

}

//**************************************************************//先进先出页面置换算法

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

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) //不存在相同进程

{

if(m != -1) //存在空闲物理块

{

phb[m] = pro[i]; //进程号填入该空闲物理块

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 //存在相同的进程

{

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("缺页次数为：%d\n",count);

printf("\n");

}

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

/*初始化内存单元、缓冲区*/

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;

}

/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/

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;

}

/*判断页面是否已在内存中*/

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;/*记录调入页面*/

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];

/*记录当前的内存单元中的页面*/

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

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

}

/*结果输出*/

printf("内存状态为：\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调入队列为:");

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

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

printf("\n缺页次数为：%6d\n缺页率：%16.6f",K+1,(float)(K+1)/psize);

}

//**************************************************************//主函数

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

void main()

{

int sel ;

do{

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

printf("\t\t\t ☆☆^-^欢迎进入操作系统界面^-^☆☆ \t\t\t");

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

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

printf("\t\t\t☆ 虚拟内存 ☆ \t\t\t");