当前位置: 代码迷 >> C语言 >> [讨论]模拟Cache工作模式(FIFO调度)!
  详细解决方案

[讨论]模拟Cache工作模式(FIFO调度)!

热度:386   发布时间:2006-10-17 18:46:13.0
[讨论]模拟Cache工作模式(FIFO调度)!
设计一个模拟Cache测试程序。

要求:可输入改变调度算法配置参数,如页面大小,内存大小,访存地址流,并计算输出每次访问的命中率。

内存大小可控制在100到1000之间,页面大小可选择小于内存大小的任意值。但为了计算方便,内存可选择100、200、300、……900,页面大小可以选择100、200、300、400,且页面大小能够被整除。

访存地址流可以是形如“21354653410”之类的字符串。

初步的想法:
整个内存可分为(内存大小/页面大小)块,可以用循环队列表示。第一次肯定不命中,因为内存中是空的,如果内存中有数,则把需要比较的数与已存在的数进行比较,如果存在相同的,则算命中一次,如果不相同,则需去除首先进入内存的数,把新数入队(这要判定队列是否已满,如果满则直接入队)。

打个比方:
如果页面大小100,内存大小400,地址流“21354653410”,则内存可分为4块。
2首先进入,1再进入,3再进入,5再进入,4再进入(这时2出队),6再进入(这时1出队),5则与所有数比较,这里命中1次,3与所有数比较,命中2次,4与所以数比较,命中3次,1再进入(这时3出队),0再进入(这时5出队)。
注意:每个数进入之前都要与所以数比较,不管命中与否!

我写的程序不对,希望高手给予指点!


[此贴子已经被作者于2006-10-17 18:47:37编辑过]

搜索更多相关的解决方案: Cache  FIFO  模式  模拟  

----------------解决方案--------------------------------------------------------
都没人回啊
----------------解决方案--------------------------------------------------------
你给源程序看看,虽然本人不一定懂,可能向你请教,但从中学习。
----------------解决方案--------------------------------------------------------

我的程序得出的结果是错的
#include "Stdio.h"
#include "Conio.h"

typedef struct battery
{
char *data;
int front,rear;
int size;
}Battery;

void Initqueue(Battery *Q,int size)
{ /*初始化链表队列*/
Q->data=(Battery *)malloc(sizeof(Battery));
if (!Q->data) printf("Application failed!");
Q->front=Q->rear=0;
Q->size=size;
}

void Enqueue(Battery *Q,char elem)
{ /*入队操作*/
if ((Q->rear+1)%(Q->size)==Q->front) return;
Q->data[Q->rear]=elem;
Q->rear=(Q->rear+1)%(Q->size);
}

char Dequeue(Battery *Q)
{ /*出队操作*/
char ret;
if (Q->front==Q->rear) return;
ret=Q->data[Q->front];
Q->front=(Q->front+1)%(Q->size);
return ret;
}

char Get(Battery *Q)
{
return Q->data[Q->front];
}

char Index(Battery *Q,int i)
{
return Q->data[Q->front+i-1];
}

int Isfull(Battery *Q)
{
if ((Q->rear+1)%(Q->size)==Q->front)
return 1;
}

void Cache(int Page_size/*页面大小*/,int Mainmen_size/*主存大小*/,char *string/*输入的数据*/,int num/*需输入的元素个数*/)
{
int size=Mainmen_size/Page_size,segment=Page_size/100;
Battery *p;
int i=0,j=0,count1=0,count2=0,count3=0,count=0,m,n;
Initqueue(p,size);

for (i=0;i<size;i++)
{
switch(Page_size)
{
case 100:
if ('0'<=string[i]<segment+48)
string[i]='0';
if (segment+48<=string[i]<2*segment+48)
string[i]=segment+48;
if (2*segment+48<=string[i]<3*segment+48)
string[i]=2*segment+48;
if (3*segment+48<=string[i]<4*segment+48)
string[i]=3*segment+48;
if (4*segment+48<=string[i]<5*segment+48)
string[i]=4*segment+48;
if (5*segment+48<=string[i]<6*segment+48)
string[i]=5*segment+48;
if (6*segment+48<=string[i]<7*segment+48)
string[i]=6*segment+48;
if (7*segment+48<=string[i]<8*segment+48)
string[i]=7*segment+48;
if (8*segment+48<=string[i]<9*segment+48)
string[i]=8*segment+48;
if (9*segment+48==string[i])
string[i]=9*segment+48;
break;
case 200:
if ('0'<=string[i]<segment+48)
string[i]='0';
if (segment+48<=string[i]<2*segment+48)
string[i]=segment+48;
if (2*segment+48<=string[i]<3*segment+48)
string[i]=2*segment+48;
if (3*segment+48<=string[i]<4*segment+48)
string[i]=3*segment+48;
if (4*segment+48<=string[i]<5*segment+48)
string[i]=4*segment+48;
break;
case 300:
if ('0'<=string[i]<segment+48)
string[i]='0';
if (segment+48<=string[i]<2*segment+48)
string[i]=segment+48;
if (2*segment+48<=string[i]<3*segment+48)
string[i]=2*segment+48;
if (3*segment+48==string[i])
string[i]=3*segment+48;
break;
case 400:
if ('0'<=string[i]<segment+48)
string[i]='0';
if (segment+48<=string[i]<2*segment+48)
string[i]=segment+48;
if (2*segment+48<=string[i]<3*segment+48)
string[i]=2*segment+48;
break;
}
}
if (num<=size)
{
Enqueue(p,string[0]);
for (i=1;i<=num;i++)
{
if (string[i]==Index(p,i))
{
count1++;
break;
}
else
{
Enqueue(p,string[i]);
}
}
printf("%d",count1);
return;
}
else
{
Enqueue(p,string[0]);
for (i=0;i<num;i++)
{
if (Isfull(p))
for (j=1;j<=segment;j++)
{
if (Index(p,j)==string[i])
{
count2++;
break;
}
else if (j==segment && string[i]!=Index(p,j))
{
Dequeue(p);
Enqueue(p,string[i]);
}
}
else
{
for (n=1;n<=segment;n++)
{
if (string[i]==Index(p,n))
{
count3++;
break;
}
else
{
Enqueue(p,string[i]);
}
}
}
}
count=count1+count2+count3;
printf("Target:%d\n",count1);
printf("Target:%d\n",count2);
printf("Target:%d\n",count3);
printf("Target:%d\n",count);
/*for (i=0;i<num;i++)
{
for (j=0;j<size;j++)
{
if (battery[j].data==-1)
{
full=0;
break;
}
if (battery[size-1].data!=-1)
full=1;
}
switch (full)
{
case 1:
if (num>=p[i].min && num<p[i].max)
{
p[i].data=num;
full=1;
flag++;
}
else if (num>p[i].max)
{

}
break;
case 0:
p[count].
if (num>=p[i].min && num<p[i].max)
{
p[i].data=num;

flag++;
}
else if (num>p[i].max)
{

}
break;
}}}*/
}
}

int main(void)
{
int pagesize,mainmensize,num=3;
char s[3]={'5','0','3'};
printf("Please input Pagesize:");
scanf("%d",&pagesize);
printf("\n");
printf("Please input Mainmensize:");
scanf("%d",&mainmensize);
printf("\n");
Cache(pagesize,mainmensize,s,num);
getch();
return 0;
}


----------------解决方案--------------------------------------------------------

我感觉我的非常乱,现在自己检错都难啊


----------------解决方案--------------------------------------------------------
为什么不加注释呢
----------------解决方案--------------------------------------------------------

#include "Stdio.h"
#include "Conio.h"

typedef struct battery
{
char *data;
int front,rear;
int size;
}Battery;

void Initqueue(Battery *Q,int size)
{ /*初始化链表队列*/
Q->data=(Battery *)malloc(sizeof(Battery));
if (!Q->data) printf("Application failed!");
Q->front=Q->rear=0;
Q->size=size;
}

void Enqueue(Battery *Q,char elem)
{ /*入队操作*/
if ((Q->rear+1)%(Q->size)==Q->front) return;
Q->data[Q->rear]=elem;
Q->rear=(Q->rear+1)%(Q->size);
}

char Dequeue(Battery *Q)
{ /*出队操作*/
char ret;
if (Q->front==Q->rear) return;
ret=Q->data[Q->front];
Q->front=(Q->front+1)%(Q->size);
return ret;
}

char Get(Battery *Q)
{
return Q->data[Q->front];
}

char Index(Battery *Q,int i) /*返回第i个元素*/
{
return Q->data[Q->front+i-1];
}

int Isfull(Battery *Q) /*队列满则返回1*/
{
if ((Q->rear+1)%(Q->size)==Q->front)
return 1;
}

void Cache(int Page_size/*页面大小*/,int Mainmen_size/*主存大小*/,char *string/*输入的数据*/,int num/*需输入的元素个数*/)
{
int size=Mainmen_size/Page_size,segment=Page_size/100; /*segment是需要分的段数。如Page_size=200,则0、1属于一段*/
Battery *p;
int i=0,j=0,count1=0,count2=0,count3=0,count=0,m,n;
Initqueue(p,size);

for (i=0;i<size;i++) /*简化地址流*/
{
switch(Page_size)
{
case 100:
if ('0'<=string[i]<segment+48)
string[i]='0';
if (segment+48<=string[i]<2*segment+48)
string[i]=segment+48;
if (2*segment+48<=string[i]<3*segment+48)
string[i]=2*segment+48;
if (3*segment+48<=string[i]<4*segment+48)
string[i]=3*segment+48;
if (4*segment+48<=string[i]<5*segment+48)
string[i]=4*segment+48;
if (5*segment+48<=string[i]<6*segment+48)
string[i]=5*segment+48;
if (6*segment+48<=string[i]<7*segment+48)
string[i]=6*segment+48;
if (7*segment+48<=string[i]<8*segment+48)
string[i]=7*segment+48;
if (8*segment+48<=string[i]<9*segment+48)
string[i]=8*segment+48;
if (9*segment+48==string[i])
string[i]=9*segment+48;
break;
case 200:
if ('0'<=string[i]<segment+48)
string[i]='0';
if (segment+48<=string[i]<2*segment+48)
string[i]=segment+48;
if (2*segment+48<=string[i]<3*segment+48)
string[i]=2*segment+48;
if (3*segment+48<=string[i]<4*segment+48)
string[i]=3*segment+48;
if (4*segment+48<=string[i]<5*segment+48)
string[i]=4*segment+48;
break;
case 300:
if ('0'<=string[i]<segment+48)
string[i]='0';
if (segment+48<=string[i]<2*segment+48)
string[i]=segment+48;
if (2*segment+48<=string[i]<3*segment+48)
string[i]=2*segment+48;
if (3*segment+48==string[i])
string[i]=3*segment+48;
break;
case 400:
if ('0'<=string[i]<segment+48)
string[i]='0';
if (segment+48<=string[i]<2*segment+48)
string[i]=segment+48;
if (2*segment+48<=string[i]<3*segment+48)
string[i]=2*segment+48;
break;
}
}
if (num<=size) /*地址流数小于页数*/
{
Enqueue(p,string[0]);
for (i=1;i<=num;i++) /*边入队边与队列中所有数比较*/
{
for (j=1;j<=i;j++)
if (string[i]==Index(p,j))
{
count1++;
break;
}
else
{
Enqueue(p,string[i]);
}
}
printf("%d",count1);
return;
}
else
{
Enqueue(p,string[0]);
for (i=0;i<num;i++)
{
if (Isfull(p)) /*队列已满*/
for (j=1;j<=segment;j++) /*与队列中数比较*/
{
if (Index(p,j)==string[i]) /*命中,但不入队*/
{
count2++;
break;
}
else if (j==segment && string[i]!=Index(p,j)) /*最后一个数不命中,则出队,并把新数入队*/
{
Dequeue(p);
Enqueue(p,string[i]);
}
}
else /*队列不满*/
{
for (n=1;n<=segment;n++) /*与队列这数比较*/
{
if (string[i]==Index(p,n)) /*命中,但不入队*/
{
count3++;
break;
}
else /*不命中,则入队*/
{
Enqueue(p,string[i]);
}
}
}
}
count=count1+count2+count3;
printf("Target:%d\n",count1);
printf("Target:%d\n",count2);
printf("Target:%d\n",count3);
printf("Target:%d\n",count);
}
}

int main(void)
{
int pagesize,mainmensize,num=3;
char s[3]={'5','0','3'};
printf("Please input Pagesize:");
scanf("%d",&pagesize);
printf("\n");
printf("Please input Mainmensize:");
scanf("%d",&mainmensize);
printf("\n");
Cache(pagesize,mainmensize,s,num);
getch();
return 0;
}

加注释了!


----------------解决方案--------------------------------------------------------

此问题已解决!代码如下:
#include "Stdio.h"
#include "Conio.h"

typedef struct battery
{
char *data;
int front,rear;
int size;
}Battery;

void Initqueue(Battery *Q,int size)
{ /*初始化链表队列*/

Q->data=(char *)malloc(sizeof(char)*size);
if (!Q->data) printf("Application failed!");
Q->front=Q->rear=0;
Q->size=size;
}

void Enqueue(Battery *Q,char elem)
{ /*入队操作*/
if ((Q->rear+1)%(Q->size)==Q->front) return;
Q->data[Q->rear]=elem;
Q->rear=(Q->rear+1)%(Q->size);
}

char Dequeue(Battery *Q)
{ /*出队操作*/
char ret;
if (Q->front==Q->rear) return;
ret=Q->data[Q->front];
Q->front=(Q->front+1)%(Q->size);
return ret;
}

char Get(Battery *Q)
{ /*得到队头元素*/
return Q->data[Q->front];
}

char Index(Battery *Q,int i)
{ /*定位第i个元素*/
return Q->data[Q->front+i-1];
}

int Isfull(Battery *Q)
{ /*队满返回1*/
if ((Q->rear+1)%(Q->size)==Q->front)
return 1;
}

int Length(Battery *Q)
{ /*返回队列长度*/
return (Q->rear-Q->front+Q->size)%(Q->size);
}

void Cache(int Page_size/*页面大小*/,int Mainmen_size/*主存大小*/,char *string/*输入的数据*/,int num/*需输入的元素个数*/)
{
int size=Mainmen_size/Page_size; /*segment是需要分的段数。如Page_size=200,则0、1属于一段*/
Battery *p,*q;
int i=0,j=0,count1=0,count2=0,count3=0,count=0,n;
Initqueue(p,size+1);

for (i=0;i<num;i++) /*简化地址流*/
{
switch(Page_size)
{
case 100:
if ('0'==string[i])
string[i]='0';
if ('1'==string[i])
string[i]='1';
if ('2'==string[i])
string[i]='2';
if ('3'==string[i])
string[i]='3';
if ('4'==string[i])
string[i]='4';
if ('5'==string[i])
string[i]='5';
if ('6'==string[i])
string[i]='6';
if ('7'==string[i])
string[i]='7';
if ('8'==string[i])
string[i]='8';
if ('9'==string[i])
string[i]='9';
break;
case 200:
if ('0'==string[i] || '1'==string[i])
string[i]='0';
if ('2'==string[i] || '3'==string[i])
string[i]='2';
if ('4'==string[i] || '5'==string[i])
string[i]='4';
if ('6'==string[i] || '7'==string[i])
string[i]='6';
if ('8'==string[i] || '9'==string[i])
string[i]='8';
break;
case 300:
if ('0'==string[i] || '1'==string[i] || '2'==string[i])
string[i]='0';
if ('3'==string[i] || '4'==string[i] || '5'==string[i])
string[i]='3';
if ('6'==string[i] || '7'==string[i] || '8'==string[i])
string[i]='6';
if ('9'==string[i])
string[i]='9';
break;
case 400:
if ('0'==string[i] || '1'==string[i] || '2'==string[i] || '3'==string[i])
string[i]='0';
if ('4'==string[i] || '5'==string[i] || '6'==string[i] || '7'==string[i])
string[i]='4';
if ('8'==string[i] || '9'==string[i])
string[i]='8';
break;
}
}
if (num<=size) /*地址流数小于页数*/
{
Enqueue(p,string[0]);
for (i=1;i<num;i++) /*边入队边与队列中所有数比较*/
{
for (j=1;j<=i;j++)
if (string[i]==Index(p,j))
{
count1++;
break;
}
Enqueue(p,string[i]);
}
printf("Target:%d ",count1);
printf("Rate:%d%%\n",100*count1/num);
return;
}
else
{
Enqueue(p,string[0]);
for (i=1;i<num;i++)
{
if (Isfull(p)) /*队列已满*/
{
for (j=1;j<=size;j++) /*与队列中数比较*/
{
if (Index(p,j)==string[i]) /*命中,但不入队*/
{
count2++;
break;
}
else if (j==size && string[i]!=Index(p,j)) /*最后一个数不命中,则出队,并把新数入队*/
{
Dequeue(p);
Enqueue(p,string[i]);
}
}

}
else /*队列不满*/
{
for (n=1;n<=Length(p);n++) /*与队列所有数比较*/
{
if (string[i]==Index(p,n)) /*命中,但不入队*/
{
count3++;
break;
}
}
if (string[i]==Index(p,n)) /*确定无重复数入队*/
continue;
Enqueue(p,string[i]);
}
}
count=count2+count3;
printf("Target:%d ",count);
printf("Rate:%d%%\n",100*count/num);
}
}

int main(void)
{
int pagesize,mainmensize,num=0,i=0;
char s[50];
while (getch!='*')
{
num=0;i=0;pagesize=0;mainmensize=0;
gotoxy(5,3);
printf("Welcome to cache test! Now you can input the Address flow(End with ' '):\n");
gotoxy(5,5);
for (i=0;i<50;i++)
{
scanf("%c",&s[i]);
if (s[i]!=' ')
num++;
else
break;
}
gotoxy(5,8);
printf("OK! You can input Pagesize:");
scanf("%d",&pagesize);
printf("\n");
gotoxy(5,10);
printf("Good! You can input Mainmensize:");
scanf("%d",&mainmensize);
printf("\n");
gotoxy(5,12);
printf("The result is:\n");
gotoxy(5,14);
Cache(pagesize,mainmensize,s,num);
gotoxy(5,16);
getch();
clrscr();
}
return 0;
}


----------------解决方案--------------------------------------------------------
  相关解决方案