cache 调度算法LRU模拟程序
2013年10月26日
⁄ 综合
⁄ 共 3942字 ⁄ 字号
小 中 大
/**//*++
Copyright (c) 2007 YourCompany
Module Name:
<new>
Abstract:
结合数据结构相关知识使用LRU的策略，对一组访问序列进行内部的Cache更
新LRU置换算法是选择最近最久未使用的页面予以置换。该算法赋予每个页面一个
访问字段，用来记录一个页面自上次被访问以来经历的时间T，当须淘汰一个页面
时，选择现有页面中T值最大的，即最近最久没有访问的页面。这是一个比较合理
的置换算法。
Author:
YourName (YourEmail) 2007-06-12
Revision History:
--*/
/**///////////////////////////////////////////////////////////////
#include<iostream.h>
//#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)
![]()