lru.cpp

lru源码 具体算法思想和思路 用c语言编的 很好的哦

#include<stdio.h>
#include<conio.h>
#define M 4 //表示页数
#define N 6 //表示N个页面序列
#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;
}

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];
int i,j,k;
k=N;
printf("输入%d个页面访问序列:\n",k);
for(i=0;i<N;i++)
   {
   scanf("%d",&a[i]);
   }
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("\nq缺页次数:%6d\n缺页率:%16.6f",K+1,(float)(K+1)/N);
       if(getche()=='y')
         goto start;
}