#include<stdio.h> 
#include<conio.h> 
#define M 4 
#define N 17 
#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")      /*表格控制*/ 
typedef struct page 
{ 
    int num;  /*記錄頁面號*/ 
    int time;   /*記錄調入內存時間*/ 
}Page;                   /* 頁面邏輯結構，結構為方便算法實現設計*/ 
Page b[M];            /*內存單元數*/ 
int c[M][N];   /*暫保存內存當前的狀態：緩沖區*/ 
int queue[100];       /*記錄調入隊列*/ 
int K;             /*調入隊列計數變量*/ 
/*初始化內存單元、緩沖區*/ 
void Init(Page *b,int c[M][N]) 
{ 
    int i,j; 
    for(i=0;i<N;i++) 
	{ 
        b[i].num=-1; 
        b[i].time=N-i-1; 
	} 
    for(i=0;i<M;i++) 
    for(j=0;j<N;j++) 
		c[i][j]=-1; 
} 
/*取得在內存中停留最久的頁面,默認狀態下為最早調入的頁面*/ 
int GetMax(Page *b) 
{ 
    int i; 
    int max=-1; 
    int tag=0; 
	for(i=0;i<M;i++) 
	{
		if(b[i].time>max)
		{ 
           max=b[i].time; 
           tag=i; 
        } 
    } 
    return tag; 
} 
/*判斷頁面是否已在內存中*/ 
int    Equation(int fold,Page *b) 
{ 
    int i; 
    for(i=0;i<M;i++) 
    { 
      if (fold==b[i].num) 
          return i; 
    } 
    return -1; 
} 
/*LRU核心部分*/ 
void Lru(int fold,Page *b) 
{ 
    int i; 
    int val; 
    val=Equation(fold,b); 
    if (val>=0) 
    { 
       b[val].time=0; 
       for(i=0;i<M;i++) 
          if (i!=val) 
             b[i].time++; 
    } 
    else 
	{ 
       queue[++K]=fold;/*記錄調入頁面*/ 
       val=GetMax(b); 
       b[val].num=fold; 
       b[val].time=0; 
       for(i=0;i<M;i++) 
          if (i!=val) 
             b[i].time++; 
	} 
} 
/*主程序*/ 
void main() 
{ 
    int a[N]={1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4}; 
    int i,j; 
start: 
    K=-1; 
    Init(b, c); 
    for(i=0;i<N;i++) 
    { 
       Lru(a[i],b); 
       c[0][i]=a[i]; 
       /*記錄當前的內存單元中的頁面*/ 
       for(j=0;j<M;j++) 
          c[j][i]=b[j].num; 
    } 
    /*結果輸出*/ 
    printf("內存狀態為：\n"); 
    Myprintf; 
    for(j=0;j<N;j++) 
       printf("|%2d ",a[j]); 
    printf("|\n"); 
    Myprintf; 
    for(i=0;i<M;i++) 
    {     
		for(j=0;j<N;j++) 
        { 
           if(c[i][j]==-1) 
               printf("|%2c ",32); 
           else 
               printf("|%2d ",c[i][j]); 
        } 
        printf("|\n"); 
    } 
    Myprintf; 
    printf("\n調入隊列為:"); 
    for(i=0;i<K+1;i++) 
       printf("%3d",queue[i]); 
    printf("\n缺頁次數為：%6d\n缺頁率：%16.6f",K+1,(float)(K+1)/N); 
    printf("\nAre you continuing!\ty?"); 
    if(getche()=='y') 
		goto start; 
}