LRU算法具体怎么算的,有没有例子

发布网友 发布时间：2022-04-29 07:08

我来回答

共2个回答

热心网友 时间：2022-06-20 23:50

LRU算法参考例子如下：
include<iostream>
using namespace std;

int ans[1000];//存放原序列
int block[1000];//机器分给程序的内存块
int num[1000];//每个页面在内存中待的时间
int n; //页面流数
int m; //内存块数
int sum;//命中次数
//初始化函数
void Init()
{
cout<<"输入页面数"<<endl;
cin>>n;
cout<<"输入原页面流"<<endl;
for(int i=0;i<n;i++)
cin>>ans[i];
cout<<"输入分给程序的内存块数"<<endl;
cin>>m;
sum=0;
}

//扫描block中是否已存在该块
int saomiao(int k,int now)
{
int i;
for(i=0;i<k;i++)
{
if(block[i]==now)return i;
}
return -1;
}

//打印内存中的页面情况
void print(int k,int now)
{
cout<<"被调用的页面号 "<<now<<endl;
cout<<"内存中的页面号 ";
for(int i=0;i<k;i++)
cout<<block[i]<<" ";
cout<<"对应在内存的时间 ";
for(i=0;i<k;i++)
cout<<num[i]<<" ";
cout<<endl;
}

//LRU
void LRU()
{
int i,j,k,p;
k=0;//计算已用的内存块数
for(i=0;i<n;i++)
{
if(k<m)
{
p=saomiao(k,ans[i]);
if(p>=0)
{
sum++;
cout<<"命中"<<endl;
print(k,ans[i]);//打印内存中的页面情况
for(j=0;j<k;j++)
num[j]++;//修改各页在内存中待的时间
num[p]=1;
}
else
{
cout<<"未命中"<<endl;
print(k,ans[i]);//

block[k]=ans[i];
for(j=0;j<k;j++)
num[j]++;
num[k++]=1;
}
}
else
{
p=saomiao(m,ans[i]);
if(p>=0)
{
sum++;
cout<<"命中"<<endl;
print(m,ans[i]);//
for(j=0;j<m;j++)
num[j]++;
num[p]=1;
}
else
{
int max=-1;
int p1=0;
for(j=0;j<m;j++)//扫描找出时间最长的页面，用来替换
if(num[j]>max)
{
max=num[j];
p1=j;
}

cout<<"未命中"<<endl;
print(m,ans[i]);//
cout<<"将被替换的叶号和时间"<<block[p1]<<" "<<num[p1]<<endl<<endl;
block[p1]=ans[i];//替换
for(j=0;j<m;j++)//修改时间
num[j]++;
num[p1]=1;
}
}
}
}

int main()
{
Init();
LRU();
cout<<"命中次数 "<<sum<<endl;
cout<<"命中率 "<<(double)sum/(double)n*100<<"%"<<endl;
return 0;
}

热心网友 时间：2022-06-20 23:50

有例子 LRU（least recently used）最近最久未使用。
假设 序列为 4 3 4 2 3 1 4 2
物理块有3个 则
首轮 4调入内存 4
次轮 3调入内存 3 4
之后 4调入内存 4 3
之后 2调入内存 2 4 3
之后 3调入内存 3 2 4
之后 1调入内存 1 3 2（因为最近最久未使用的是4，从这里向前找最近最久未使用的）
之后 4调入内存 4 1 3（原理同上）
最后 2调入内存 2 4 1

过程就是这样的，楼主只要明白最近最久未使用这个道理，再回去参考书上的例子就明白是怎么算的啦！呵呵！