正文
最近最少使用算法（LRU）——页面置换
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
原创
上一篇博客写了先进先出算法（FIFO）——页面置换：http://www.cnblogs.com/chiweiming/p/9058438.html
此篇介绍最近最少使用算法（LRU）——页面置换，与上一篇的代码大同小异，只是用了不同的方法从页面队列
中选出需要淘汰出的页面。（题目阐述看我上一篇博客）
还是辣个栗子：
现内存页面为： 15 31 24 17 18 5 9 26 4 21
部分地址流为： 4 31 24 17 18 26 17 5 5 9 31 18 18 21 15
页面 8 为下一个需要调入进去的页面，由于内存页面已满，需要使用LRU调出一个最近未被使用页面。
寻找淘汰页面的方式如下：
从页面 8 往前看，遇到与内存页面中相同的页面即把它移除（即不淘汰它），等到移除了 max_page-1 个页面之
后，剩下最后一个未被移除的页面即是需要淘汰出去的。
在上面例子中，依次将 15 21 18 31 9 5 17 26 24 （已经9个），剩下最后一个 4 即是需要淘汰出去的页面。
可以用这样的伪代码去实现：用一个数组 flag 来备份内存页块号中的页面，从 8 往前看，依次将之前的数和数组
里的数比较，若匹配成功，则将数组里面此位置 -1 ，等到置了 max_page-1 个 -1 后跳出；再从 flag 中筛选出不
是 -1 的值（即要淘汰出的页面），再拿此值和当前内存页面队列中的值比较，匹配成功则将此页面调出去，将页
面 8 调入。
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define max_page 10 //内存页面数 int Page[]={}; //虚拟存储区,存储320条指令,32个页面
int Page_flu[]={}; //存储320个页地址流
int count=; //计算随机产生的指令条数
double lack_page=; //记录缺页数
int count_page=max_page; //计算队列空页面个数
int flag[max_page+]={}; //存储内存块中的页面号
int ff=; struct Memo{ //用结构体存储内存页面块
int num; //给每个页面编号,方便将其从队列中找到并调出
int a;
struct Memo *next;
}; int Judge_Page(int value){ //输入指令,返回指令对面的页面号
return value/;
} int scan_queen(struct Memo *hear,int value){ //value代表页面号,扫描队列,缺页返回0,否则返回1
struct Memo *move;
move=hear->next;
while(move!=NULL){
if(move->a==value){
return ;
}
move=move->next;
}
return ;
} void print(struct Memo *hear){ //输出内存页面
struct Memo *move;
move=hear->next;
printf("当前页面队列为： ");
while(move!=NULL){
printf("%d ",move->a);
move=move->next;
}
printf("\n");
} void insert(struct Memo *hear,int value,int ZL,int x){ //将页面value调入内存,ZL为对应指令,x为页面value在页地址流中的序号
if(count_page>=){ //内存页面空间充足
struct Memo *move;
move=hear->next;
while(move->a!=-){
move=move->next;
}
move->a=value; //将页面调入
count_page--;
printf("页面 %d 被调入————对应指令为: %d \n",value,ZL);
}
else{ //内存空间不足，使用LRU选出需调出的页面后，将页面value后调入
struct Memo *move;
move=hear->next;
int i=;
for(i=;i<=max_page;i++){
flag[i]=move->a; //将内存块中的页面号放入flag备份
move=move->next;
}
int t=;
for(t=x-;t>=;t--){ //循环结束后flag里面只有一个不为0,把此页面调出即可
for(i=max_page;i>=;i--){
if(Page_flu[t]==flag[i]){
flag[i]=-;
ff++;
break;
}
}
if(ff==max_page-){
break;
}
}
for(i=;i<=max_page;i++){ //选出被淘汰出的页面号
if(flag[i]!=-){
ff=flag[i]; //备份要淘汰出的页面号
break;
}
}
move=hear->next;
while(move!=NULL){
if(move->a==ff){
int j=;
printf("前20个地址流为：");
for(j=x-;j<=x-;j++){
printf("%d ",Page_flu[j]);
}
printf("\n");
printf("页面 %d 被调出,页面 %d 被调入----指令为：%d \n",ff,value,ZL);
move->a=value; //将页面插入
break;
}
move=move->next;
}
} ff=;
print(hear); //调入后输出内存队列
} void LRU(struct Memo *hear){
int i=;
for(i=;i<=;i++){ //循环扫描页面
if( scan_queen(hear,Page_flu[i])==){ //判断是否缺页
lack_page++;
insert(hear,Page_flu[i],Page[i],i); //缺页将页面调入内存
}
else{ //不缺页
printf("指令 %d 对应页面 %d 已在内存\n",Page[i],Page_flu[i]);
}
//不缺页无需操作
}
} void Pro_Page(){ //形成页地址流函数
int m=; //在[0,319]的指令地址之间随机选取一起点m
m=rand()%; Page[count]=m;
count++;
if(count==){
return;
}
int m_=; //在前地址[0,m+1]中随机选取一条指令并执行
m_=rand()%(m+); Page[count]=m_;
count++;
if(count==){
return;
}
Page[count]=m_+;
count++;
if(count==){
return;
}
int m__=;
m__=(m_+)+rand()%( -(m_+)+ ); //在后地址[m_+2,319]的指令地址之间随机选取一条指令并执行
Page[count]=m__;
count++;
if(count==){
return;
} Pro_Page();
} void Flu(){ //将指令转换为页地址流
int i=;
for(i=;i<=;i++){
Page_flu[i]=Judge_Page( Page[i] );
}
} int main(){
struct Memo Stu[max_page+];
struct Memo *hear;
hear=&Stu[];
//*************************************
int i=;
for(i=;i<=max_page;i++){ //形成内存页面队列
if(i==max_page){
Stu[i].a=-;
Stu[i].next=NULL;
Stu[i].num=i;
break;
}
Stu[i].next=&Stu[i+];
Stu[i].a=-;
Stu[i].num=i;
}
//*************************************
srand(time()); //放在Pro_Page函数外面
Pro_Page(); //形成页地址流
Flu(); //形成页地址流
/*
printf("页地址流：\n");
for(i=0;i<=319;i++){ //输出页地址流
printf("%d ",Page[i]);
if(i%3==0 && i!=0){
printf("\n");
}
}
printf("\n");
*/
//************************************* LRU(hear);
printf("缺页次数为： %0.0lf\n",lack_page);
printf("命中率为：%lf\n",-lack_page/); return ;
}
（部分结果截图）
08:31:06
2018-05-22
