# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# include <string.h>
#include<math.h>
static int blockaddress[500];
static int before[500];
static int t=0;
int misstype(int ba,int nb, int l);
//函数名称：Gen
//作用：生成随机的页面访问序列
//参数定义：虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页数e，
//工作集移动率m（每处理m个页面访问则将起始位置p +1），
//以及一个范围在0和1之间的值t
//que为传入的需要生成序列的数组
//返回生成的大小cnt
//作者：赵洲洋
//时间：2011-05-20
int num, e, N;
int Gen(int que[])
{
double
t = (rand() % 100) * 0.01;
int m =
(rand() % (N / 2)) + 1;
int p =
rand() % (N / 2);
int cnt
= 0;
while(true)
{
e = rand() % (N / 2) +
1;
for(int i = 0; i
< m; i++)
{
que[cnt++] = rand() % e + p;
if (que[cnt - 1] > N - 1) que[cnt
- 1] = N - 1;
if (cnt == num) break;
}
if (cnt == num) break;
double r = (rand() % 100) *
0.01;
if (r <
t)
p = rand() % N;
else p = (p + 1) % N;
}
return
cnt;
}
int main()
{
//srand(time_t(NULL));
FILE *fp;
int cachesize;
int blocksize;
int assoc;
int blockinbyte;
int NOofblock;
int NOofset;
int choice;
float misscount,accesscount,hitcount;
int index,byte,tag,ii;
int i=0,j,x,y,z,cc,c,m;
int bytearray[500],wordaddress[500];
do
{
printf("Cache Simulation Project:");
printf("\n\n1.
Direct_mapped\n2. Set_associate\n3. Fully_associate\n\n: ");
// choice from direct
mapped, set associate and fully associate
scanf("%d",&choice);
if(choice==1||choice==2||choice==3)
break;
printf("Incorrect input.");
}while(1);
do
{
printf("\n\nCache Size from range[64/128/256]: ");
scanf("%d",&cachesize);
if(cachesize==64||cachesize==128||cachesize==256 ||
cachesize==16)// choose cache size
break;
printf("Incorrect input.");
}while(1);
do
{
printf("\n\nBlock Size from range[1/2/4]: ");
scanf("%d",&blocksize);
if(blocksize==1||blocksize==2||blocksize==4) //choose block
size
break;
printf("Incorrect input.");
}while(1);
do
{
printf("\n\nEnter the value for n-way Set value
from[1/2/4/8/16]: ");
scanf("%d",&assoc);
if(assoc==1||assoc==2||assoc==4||assoc==8||assoc==16)
break;
printf("Incorrect input.\n");
}while(1);
//fp= fopen("e:\\project.txt","r");//open the file
printf("输入生成序列的长度N\n");
scanf("%d", &N); num = N;
printf("输入需要测试的次数\n");
int tmp;scanf("%d", &tmp);
int total = tmp;
double myans = 0;
while(tmp--)
{
int
newarray[300][300]={0},lru[300][300]={0};
for(ii = 0; ii
< 500; ii++)
before[ii]=-1;
char ans='y';
int c1c=0,c2c=0,c3c=0;
float missrate=0,
hitrate=0;
i = Gen(bytearray);
blockinbyte=blocksize*4;
//以字节计算出的块体积calculate the block size in bit
NOofblock=cachesize/blockinbyte;
// calculate the # of
blocks
NOofset=NOofblock/assoc;
//calculate the # of
sets
misscount=0;
// initial miss
counter=0
hitcount=0;
// initial hit counter=0
accesscount=0;
// initial access counter=0
for(j=0;j<i;j++)
{
accesscount++;
//increase the access counter
wordaddress[j]=bytearray[j]/4; //计算数据的字地址
//calculate
the word address
blockaddress[j]=wordaddress[j]/blocksize;
//计算数据的块地址 //calculate the block address
index=blockaddress[j]%NOofset; //计算数据所在的set地址
//calculate
the index
tag=blockaddress[j]/NOofset;
//计算数据所在的tag
//calculate the tag
x=y=z=0;
if(choice==1||choice==2) //当为直接映射或集相联映射
//direct
mapped or set associativity
{
//assoc代表n-way的n
while
(z<(assoc*2))
{
cc=0;
c=0;
if(newarray[index][z]==0)
////当cache
中对应位置上的有效位无效，数据不在cache中，失效; check the valid bit
{
newarray[index][z+1]=tag;
//设置tag位 put the tag into a
new array
newarray[index][z]=1;
//设置有效位 set valid bit to 1
misscount++;
c=misstype(blockaddress[j],NOofblock,j);//判断失效类型
decide the type of miss
cc=1;
for(m=0;m<(assoc*2);m=m+2)
//近期最少使用策略lru policy
lru[index][m]++;
//increase the value of lru[index][m] to 1 in
the same index
lru[index][z]=0;
//set the
recent use value to 0
z=(assoc*2);
// while loop out
}
else//当cache
中对应位置上的有效位有效
{
if(newarray[index][z+1]==tag)
////并且tag位一致，数据在cache 中，命中if the tag already in the cache
{
hitcount++;
//hit counter increase
for(m=0;m<(assoc*2);m=m+2)
lru[index][m]++;
lru[index][z]=0;
z=(assoc*2);
}
else//但是tag位不一致
{
if(assoc<2)
//Direct mapped
{
newarray[index][z+1]=tag; //
put the tag into a new array
misscount++;
//c=misstype(blockaddress[j],NOofblock,j);
//decide which miss type this miss belong to
cc=1;
z=(assoc*2);
}
else
{
if(x<lru[index][z])
{
x=lru[index][z];
y=z;
}
if(z==((assoc*2)-2))
{
newarray[index][y+1]=tag;
misscount++;
//c=misstype(blockaddress[j],NOofblock,j);
cc=1;
for(m=0;m<(assoc*2);m=m+2)
lru[index][m]++;
lru[index][y]=0;
}
z=z+2;
}
}
}
}
if(c==1&&cc==1)
c1c++;
if(c==2&&cc==1)
c2c++;
if(c==3&&cc==1)
c3c++;
}
else//当为全相联映射时
//fully associativity
{
while(z<=NOofblock)
{
cc=0;
if(newarray[z][0]==0)
//valid bit is 0
{
newarray[z][1]=blockaddress[j];
// staore the block address in the new
array
newarray[z][0]=1;
// valid bit set to 1
misscount++;
//c=misstype(blockaddress[j],NOofblock,j);
cc=1;
for(m=0;m<=NOofblock;m++)
lru[m][1]++;
lru[z][1]=0;
z=(NOofblock+1);
}
else
// valid bit is 1
{
if(newarray[z][1]==blockaddress[j])// tag already
in the array
{
hitcount++;
for(m=0;m<=NOofblock;m++)
lru[m][1]++;
lru[z][1]=0;
z=NOofblock+1;
}
else
{
if
(x<lru[z][1])
{
x=lru[z][1];
y=z;
}
if(z==NOofblock)
{
newarray[y][1]=blockaddress[j];
misscount++;
//c=misstype(blockaddress[j],NOofblock,j);
cc=1;
for(m=0;m<=NOofblock;m++)
lru[m][1]++;
lru[y][1]=0;
}
z++;
}
}
}
if(c==1&&cc==1)
c1c++;
if(c==2&&cc==1)
c2c++;
if(c==3&&cc==1)
c3c++;
//if(c==1)
c1c++;
//if(c==2)
c2c++;
//if(c==3)
c3c++;
}
}
missrate =
(misscount/accesscount);
hitrate =
(hitcount/accesscount);
myans += misscount;
printf("%d次实验，缺页率%lf\n", total
- tmp, missrate);
}
printf("经过%d次实验，平均缺页率为%lf\n", total, myans / (num *
total));
}
int misstype(int ba, int nb, int l) // this function is used
to decide which miss type it's belong to
{
int u,k=0,b=0,n=0,m,ii;
int blarray[500];
int type;
for (ii=0;ii<500;ii++)
// initila the array
blarray[ii]=9999;
for(u=0;u<=t;u++)
// check
if the block address already in the array
{
if(before[u]==ba)
//if the
block address in the before array
{
k=0;
break;
}
else
k=1;
}
if(k==1)
// compulsory miss
{
type=1;
before[t]=ba;
t++;
}
if(k==0) //capacity or conflict miss
{
for(u=(l-1); u>=0; u--)
{
if(blockaddress[u]==ba) // current address is refered
before
{
break;
}
else
{
n=0;
for(m=0;m<=b;m++)
{
n++;
if(blarray[m]==blockaddress[u]) //it it's not a distinct
address, then break
break;
}
if(n==(b+1))
{
blarray[b]=blockaddress[u]; //store the address in the
blarray
b++;
//blarray[b+1] to store next address
}
}
}
if((b)<nb) //conflict miss
type=2;
else // capacity
miss
type=3;
}
return type;
}
加载中，请稍候......
加载中…
喜欢