lru1.c

使用LRU方法更新Cache 结合数据结构的相关知识

#include<stdio.h> 
#include<conio.h> 

typedef struct lru 
{ 
	int num;	
	int time;	
}Lru; 
  
Lru b[5]; 
int c[5][10]; 
int queue[100]; 
int K; 
void Init(Lru *b,int c[5][10]) 
{ 
	int i,j; 
	for(i=0;i<10;i++) 
	{ 
		b[i].num=-1; 
		b[i].time=10-i-1; 
	} 
	for(i=0;i<4;i++) 
		for(j=0;j<10;j++) 
			c[i][j]=-1; 
} 
int Max(Lru *b) 
{ 
	int i; 
	int max=-1; 
	int tag=0; 
	for(i=0;i<4;i++) 
	{ 
		if(b[i].time>max) 
		{ 
			max=b[i].time; 
			tag=i; 
		} 
	} 
	return tag; 
} 
int	Equation(int fold,Lru *b) 
{ 
	int i; 
	for(i=0;i<4;i++) 
	{ 
		if (fold==b[i].num) 
			return i; 
	}
	return -1; 
} 
void change(int fold,Lru *b) 
{ 
	int i; 
	int val; 
	val=Equation(fold,b); 
	if (val>=0) 
	{ 
		b[val].time=0; 
        b[4].num=1;
		for(i=0;i<4;i++) 
			if (i!=val) 
				b[i].time++; 
	} 
	else 
	{ 
		queue[++K]=fold; 
		val=Max(b); 
		b[val].num=fold; 
		b[val].time=0;
		b[4].num=-1;
		for(i=0;i<4;i++) 
			if (i!=val) 
				b[i].time++;
	} 
} 
void main() 
{ 
	int i,j;
	int a[10];
	printf("input pages(10):\n");
		for(i=0;i<10;i++)
		{
		   scanf("%d",&a[i]);
		}	 
	K=-1; 
	Init(b, c); 
	for(i=0;i<10;i++) 
	{ 
		change(a[i],b); 
		c[0][i]=a[i];  
		for(j=0;j<5;j++) 
			c[j][i]=b[j].num; 
	} 
	printf("The result：\n"); 
	for(j=0;j<10;j++) 
		printf("%2d ",a[j]);  
	printf("\n");
	for(i=0;i<5;i++) 
	{	for(j=0;j<10;j++) 
		{ 
		if(c[i][j]==-1) 
			printf("%2c ",32); 
		else 
			printf("%2d ",c[i][j]); 
		}
	    printf("\n");
	} 
}