fifo.c

银行家算法是从当前状态出发

#include <stdio.h>

int work[20];
int pos=0;
struct Page{
int id;
int cout;
}page[3];

int max() //找出在内存中存在时间最长的或最长未用的页面
{
int m=-1,t,MAX;
for(t=0;t<3;t++)
if(m<page[t].cout)
{
m=page[t].cout;
MAX=t;
}
return MAX;
}

int check(int i) //查询当前访问页面是否在内存中
{
int t;
for(t=0;t<pos;t++)
if(work[i]==page[t].id) return t;
if(t==pos) return -1;
}

int find(int p,int i) //理想算法中找出内存页面在以后被访问的时间
{
for(;i<20;i++)
if(page[p].id==work[i])return i;
if(i==20)
return 20;
}

void fifo() //先进先出
{
int i,j;
for(i=0;i<20;i++)
{
if(pos<3)
{
if(check(i)==-1)
{
page[pos].id=work[i];
page[pos].cout=0;
pos++;
}
for(j=0;j<=pos;j++)
page[j].cout+=1;
}
else
{
if(check(i)==-1)
{
j=max();
page[j].id=work[i];
page[j].cout=0;
}
for(j=0;j<3;j++)
page[j].cout+=1;
}
printf("%d|",work[i]);
for(j=0;j<pos;j++)
printf("%d ",page[j].id);
printf("\n");
}
}

void longest() //最近最久未使用
{
int i,j;
for(i=0;i<20;i++)
{
if(pos<3)
{
if(check(i)==-1)
{
page[pos].id=work[i];
page[pos].cout=0;
pos++;
}
else
page[check(i)].cout=0;
for(j=0;j<=pos;j++)
page[j].cout+=1;
}
else
{
if(check(i)==-1)
{
j=max(page);
page[j].id=work[i];
page[j].cout=0;
}
else
page[check(i)].cout=0;
for(j=0;j<3;j++)
page[j].cout+=1;
}
printf("%d|",work[i]);
for(j=0;j<pos;j++)
printf("%d ",page[j].id);
printf("\n");
}
}

void best() //理想置换算法
{
int i,j,k;
int last,a,b,c;
for(i=0;i<19;i++)
{
if(pos<3)
{
if(check(i)==-1)
{
page[pos].id=work[i];
pos++;
}
}
else
if(check(i)==-1)
{
a=find(0,i+1);
b=find(1,i+1);
c=find(2,i+1);
last=a;
k=0;
if(last<b){last=b;k=1;}
if(last<c){last=c;k=2;}
page[k].id=work[i];
}
printf("%d|",work[i]);
for(j=0;j<pos;j++)
printf("%d ",page[j].id);
printf("\n");
}
if(check(19)==-1)
page[rand()%3].id=work[19];
printf("%d|%d %d %d",work[19],page[0].id,page[1].id,page[2].id);
}

main()
{
int i;
FILE *pfile;
char choice;
if(!(pfile=fopen("work.txt","r")))
{
printf("Open file failed!");
exit(0);
}
for(i=0;i<20;i++) //从文件获取请求页面序列
{
fscanf(pfile,"%d ",&work[i]);
printf("%d ",work[i]);
}
do{
printf("Please choice:");
scanf("%s",&choice);
switch(choice)
{
case 'f':
pos=0;
fifo();
break;
case 'b':
pos=0;
best();
break;
case 'l':
pos=0;
longest();
break;
case 'q':
break;
default:
printf("Input error!\n");
break;
}
}while(choice!='q');
}