#include<iostream>
using namespace std;
//#define MAX_LEN 20
//#define MAX 5
#define true 1
#define false 0
//定义全局变量
typedef struct{
int state; //块状态true满，false为空
int value; //块内的页面号
int count; //块计数器标志块据现在的时间
}Cache;
Cache cache[]={{false,-1,0}, //初始化块信息
{false,-1,0},
{false,-1,0},
{false,-1,0}}; //cache中有四块
int walk_sort[]={1,1,2,4,3,5,2,1,6,7,1,3}; //页面访问序列
int m=4; //cache 块的个数
int n=12; //访问序列的长度
//int n=strlen(walk_sort); //页面置换访问序列的个数??????? strlen 用法??????????????
/**///////////////////////////////////////////////////////////////////////
void delay(); //声明
// cache更新算法,LRU
void up_cache(Cache cache[],int walk_sort[])
{
int i=0; //i为访问序列数组的下标
int x;
int k;
int kk;
//n=strlen(walk_sort); //?????????? strlen 和数组的类型有关吗？
while(i<n)
{
int j=0; //J为cache块的下标
//满么?
while(j<m) //当块没有装满情况
{
if((cache[j].state==false)&&(walk_sort[i]!=cache[j].value)) //装入一块
{
cout<<"cache有空闲块,不考虑是否要置换."<<endl;
cout<<walk_sort[i]<<"被调入cache...."<<endl;
cache[j].value=walk_sort[i++];
cache[j].state=true;
cache[j].count=0;
int kk=0;
for (x=0;x<m;x++)
cout<<"cache块"<<x<<": "<<cache[x].value<<endl;
cout<<endl;
//更新其它cache块没使用时间
while(kk<m)
{
if(kk!=j&&cache[kk].value!=(-1))
cache[kk].count++;
kk++;
}
delay();
break;
}
if(cache[j].value==walk_sort[i]) //命中
{
cout<<endl;
cout<<walk_sort[i]<<"命中!!!"<<endl;
for (x=0;x<m;x++)
cout<<"cache块"<<x<<": "<<cache[x].value<<endl;
cout<<endl;
int kk=0;
i++;
cache[j].count=0;
//更新其它cache块没使用时间
while(kk<m)
{
if(kk!=j&&cache[kk].value!=(-1))
cache[kk].count++;
kk++;
}
}
j++; //块下标加一
}
if(j==m) //考虑cache块已经满的情况
{
cout<<"cache已经满了,考虑是否置换."<<endl;
cout<<endl;
int k=0; //块下标
while(k<m) //遍历块看其中是否有和访问序列相同的页号，有相同的则命中
{
if(cache[k].value==walk_sort[i])
{
cout<<endl;
cout<<walk_sort[i]<<"命中!!!"<<endl;
for (x=0;x<m;x++)
cout<<"cache块"<<x<<": "<<cache[x].value<<endl; //输出各块值
i++;
cache[k].count=0;
int kk=0;
//更新其它cache块没使用时间
while(kk<m)
{
if(kk!=k)
cache[kk].count++;
kk++;
}
break;
}
k++;
}
if(k==m)//cache满且没有命中的情况，考虑置换那一块.
{
int ii=0;
int t=0;//要替换的cache块号.
int max=cache[ii].count;
ii++;
while(ii<m) //LRU
{
if(cache[ii].count>max)
{
max=cache[ii].count;
t=ii;
}
ii++;
}
//置换
cout<<cache[t].value<<"被"<<walk_sort[i]<<"在cache的"<<t<<"号块置换..."<<endl;
cache[t].value=walk_sort[i++];
cache[t].count=0;
for (x=0;x<m;x++)
cout<<"cache块"<<x<<": "<<cache[x].value<<endl;
int kk=0;
//更新其它cache块没使用时间
while(kk<m)
{
if(kk!=t)
cache[kk].count++;
kk++;
}
delay();
}
}
}
}
void delay()
{
int i;
for(i=0;i<100;i++)
;
}
int main(int argc, char* argv[])
{
cout<<"Cache更新LRU置换算法"<<endl;
up_cache(cache,walk_sort);
system("pause");
return 0;
}
