C++模拟LRU页面置换算法

实验五 C++模拟LRU页面置换算法

一、实验目的：用c++模拟LRU页面置换算法

二、实验内容：随机一访问串和驻留集的大小，通过模拟程序显示淘汰的页号并统计命中率。示例：

输入访问串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1

驻留集大小：3

算法的实现：由于LRU算法淘汰的是上次使用距离t时刻最远的页，故需记录这个距离。

计数器：可使用计数器，给每一个页帧增设一个计数器。每访问一页，就把对应页帧的计数器清零，其余页帧的计数器加1.因此，计数器值为最大的页即上次访问距当前最远的页。

7 0 1 2 0 3 0 4 2 3 0 3 2 0/7 1/7 2/7 0/2 1/2 2/2 3/2 0/4 1/4 2/4 0/0 1/0 2/0 0/0 1/0 2/0 0/0 1/0 0/0 1/0 2/0 0/3 1/3 0/31/3 0/1 1/1 2/1 0/3 1/3 2/3 0/2 1/2 2/2 3/2 0/2 缺 缺 缺 缺 命 缺 命 缺 缺 缺 缺 命 命

红色表示：每个页帧对应的计数器值

通过模拟程序输出淘汰的页号分别为：7 1 2 3 0 4 命中率为：4/13

四、代码：

#include <iostream>

using namespace std;

struct node

{

char data;

int time;

};

void init(char str[],int n,struct node zhuliuji[],int m) {

for(int i = 0;i<m;i++)

{

zhuliuji[i].data = '\0';

zhuliuji[i].time = 0;

}

for(int i =0;i<n;i++)

{

cin>>str[i];

}

}

void addtime(struct node zhuliuji[],int m) {

for(int i=0;i<m;i++)

{

zhuliuji[i].time++;

}

}

char addzhuliuji(struct node zhuliuji[],int m,char c) {

char ch = '\0';

int max = zhuliuji[0].time;

int temp = 0; //标记时间最长的驻留级 for(int i=0;i<m;i++)

{

if(max<zhuliuji[i].time&&zhuliuji[i].data!=c) {

max = zhuliuji[i].time;

temp = i;

}

if(zhuliuji[i].data==c)

{

zhuliuji[i].time =0;

// cout<<"zhuliuji存在"<<c<<endl; return ch;

}

}

ch = zhuliuji[temp].data;

zhuliuji[temp].data = c;

zhuliuji[temp].time = 0;

return ch;

}

void LRU(char str[],int n,struct node zhuliuji[],int m) {

int jtemp=0;

for(int i =0;i<n;i++)

{

if(i<m)

{

zhuliuji[jtemp].data = str[i]; addtime(zhuliuji,m);

zhuliuji[jtemp].time = 0;

jtemp ++;

}else

{

addtime(zhuliuji,m);

char ch = addzhuliuji(zhuliuji,m,str[i]); // if(ch!='\0')

//cout<<"淘汰的页数为："<<ch<<endl; }

cout<<"驻留级为：";

for(int j=0;j<m;j++)

{

cout<<zhuliuji[j].data<<'\t'; }

cout<<endl;

}

cin>>jtemp; //显示结果，以便观察 }

int main()

{

struct node zhuliuji[20];

char str[20];

int n,m;

cout<<"请输入访问串的大小："<<endl; cin>>n;

cout<<"请输入驻留级大小："<<endl; cin>>m;

cout<<"请输入访问串的内容："<<endl; init(str,n,zhuliuji,m);

LRU(str,n,zhuliuji,m);

return 0;

}

五．运行结果

本文来源：https://www.bwwdw.com/article/sv11.html