页面置换算法：最佳适配+FIFO+LRU

#include"stdio.h" #include"stdlib.h" #include"time.h" void FIFO(void); void LRU(void); char a; int m,n,i,y[100]; /*m为物理块数，n为要访问的页面数*/ typedef struct page{ int num; int time; }Page; Page x[10]; int GetMax(page *x) /*求出那个物理块中的页面呆的时间最长，返回物理块号*/ { int i; int max=-1; int tag=0; for(i=0;i<m;i++) { if(x[i].time>max) { max=x[i].time; tag=i; } } return tag; } void Xunhuan() { printf("Please select 1:FIFO算法\n 2:LRU算法\n"); scanf("%s",&a); printf("请输入物理块数："); scanf("%d",&m); for(i=0;i<m;i++) /*将空的物理块中数据置为-1*/ { x[i].num=-1; } printf("请输入所要访问的页面数："); scanf("%d",&n); srand(time(NULL)); for(i=0;i<n;i++) { y[i]=rand()%10; /*随机生成要访问的页面流*/ } printf("所要访问的页面号序列为："); for(i=0;i<n;i++) printf("%d ",y[i]); printf("\n"); printf("页面置换步骤如下：\n"); switch(a) { case '1':FIFO();break; case '2':LRU(); break; } } void main() { char a; Xunhuan(); while(1) { printf("Continue or Exit:C/Anykey:\n"); scanf("%s",&a); if(a=='c'||a=='C') Xunhuan(); else break; } exit(0); } void FIFO(void) { int i,j,u; for(i=0;i<m;i++) x[i].time=0; x[0].num=y[0]; x[0].time=1; printf(" %d \n",x[0].num); for(i=1;i<n;i++) { u=0; for(j=0;j<m;j++) if(x[j].num==y[i]) { u=1; break; } if(u!=1&&x[m-1].num!=-1) { j=GetMax(x); x[j].num=y[i]; x[j].time=0; } if(u!=1&&x[m-1].num==-1) { for(j=0;j<m;j++) { if(x[j].num==-1) {x[j].num=y[i]; break;} } } for(j=0;j<m;j++) if(x[j].num!=-1) x[j].time++; for(j=0;j<m;j++) if(x[j].num==-1) printf("%2c ",32); else printf("%2d ",x[j].num); printf("\n"); } } void LRU() { int i,j,u; for(i=0;i<m;i++) x[i].time=0; x[0].num=y[0]; x[0].time=1; printf(" %d \n",x[0].num); for(i=1;i<n;i++) { u=0; for(j=0;j<m;j++) if(x[j].num==y[i]) /*物理块中存在相同页面*/ { x[j].time=0; /*将相同的物理块的time置为0*/ u=1; break; } if(u!=1&&x[m-1].num!=-1) /*物理块中无相同页面且物理块已填满*/ { j=GetMax(x); x[j].num=y[i]; x[j].time=0; /*将刚替换的页面所在的物理块time置为0*/ } if(u!=1&&x[m-1].num==-1) /*物理块中无相同页面且物理块未填满*/ { for(j=0;j<m;j++) { if(x[j].num==-1) {x[j].num=y[i]; break;} } } for(j=0;j<m;j++) if(x[j].num!=-1) x[j].time++; /*每执行完一次time加1*/ for(j=0;j<m;j++) if(x[j].num==-1) printf("%2c ",32); else printf("%2d ",x[j].num); printf("\n"); /*格式化输出*/ } }