要求：可输入改变调度算法配置参数，如页面大小，内存大小，访存地址流，并计算输出每次访问的命中率。
内存大小可控制在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编辑过]
----------------解决方案--------------------------------------------------------
都没人回啊
----------------解决方案--------------------------------------------------------
你给源程序看看，虽然本人不一定懂，可能向你请教，但从中学习。
----------------解决方案--------------------------------------------------------
我的程序得出的结果是错的
#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;
}
----------------解决方案--------------------------------------------------------