博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
最近最少使用算法(LRU)——页面置换
阅读量:5863 次
发布时间:2019-06-19

本文共 5164 字,大约阅读时间需要 17 分钟。

原创


上一篇博客写了先进先出算法(FIFO)——页面置换:

此篇介绍最近最少使用算法(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

页面 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
#include
#include
#define max_page 10 //内存页面数int Page[320]={
0}; //虚拟存储区,存储320条指令,32个页面 int Page_flu[320]={
0}; //存储320个页地址流int count=0; //计算随机产生的指令条数double lack_page=0; //记录缺页数 int count_page=max_page; //计算队列空页面个数 int flag[max_page+1]={
0}; //存储内存块中的页面号 int ff=0;struct Memo{ //用结构体存储内存页面块 int num; //给每个页面编号,方便将其从队列中找到并调出 int a; struct Memo *next;};int Judge_Page(int value){ //输入指令,返回指令对面的页面号 return value/10;}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 1; } move=move->next; } return 0;}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>=1){ //内存页面空间充足 struct Memo *move; move=hear->next; while(move->a!=-1){ 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=0; for(i=1;i<=max_page;i++){ flag[i]=move->a; //将内存块中的页面号放入flag备份 move=move->next; } int t=0; for(t=x-1;t>=0;t--){ //循环结束后flag里面只有一个不为0,把此页面调出即可 for(i=max_page;i>=1;i--){ if(Page_flu[t]==flag[i]){ flag[i]=-1; ff++; break; } } if(ff==max_page-1){ break; } } for(i=1;i<=max_page;i++){ //选出被淘汰出的页面号 if(flag[i]!=-1){ ff=flag[i]; //备份要淘汰出的页面号 break; } } move=hear->next; while(move!=NULL){ if(move->a==ff){ int j=0; printf("前20个地址流为:"); for(j=x-20;j<=x-1;j++){ printf("%d ",Page_flu[j]); } printf("\n"); printf("页面 %d 被调出,页面 %d 被调入----指令为:%d \n",ff,value,ZL); move->a=value; //将页面插入 break; } move=move->next; } } ff=0; print(hear); //调入后输出内存队列 }void LRU(struct Memo *hear){ int i=0; for(i=0;i<=319;i++){ //循环扫描页面 if( scan_queen(hear,Page_flu[i])==0){ //判断是否缺页 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; //在[0,319]的指令地址之间随机选取一起点m m=rand()%320; Page[count]=m; count++; if(count==320){ return; } int m_=0; //在前地址[0,m+1]中随机选取一条指令并执行 m_=rand()%(m+1); Page[count]=m_; count++; if(count==320){ return; } Page[count]=m_+1; count++; if(count==320){ return; } int m__=0; m__=(m_+2)+rand()%( 319-(m_+2)+1 ); //在后地址[m_+2,319]的指令地址之间随机选取一条指令并执行 Page[count]=m__; count++; if(count==320){ return; } Pro_Page();}void Flu(){ //将指令转换为页地址流 int i=0; for(i=0;i<=319;i++){ Page_flu[i]=Judge_Page( Page[i] ); }}int main(){ struct Memo Stu[max_page+1]; struct Memo *hear; hear=&Stu[0]; //************************************* int i=0; for(i=0;i<=max_page;i++){ //形成内存页面队列 if(i==max_page){ Stu[i].a=-1; Stu[i].next=NULL; Stu[i].num=i; break; } Stu[i].next=&Stu[i+1]; Stu[i].a=-1; Stu[i].num=i; } //************************************* srand(time(0)); //放在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",1-lack_page/320); return 0;}

(部分结果截图)

08:31:06

2018-05-22

转载于:https://www.cnblogs.com/chiweiming/p/9066722.html

你可能感兴趣的文章
HTTP协议
查看>>
C#如何实现在PPT文档中插入、编辑和删除表格的操作
查看>>
比特币如何挖矿(挖矿原理)-工作量证明
查看>>
Nginx负载均衡
查看>>
ICDE:POLARDB定义云原生数据库
查看>>
Java字符流文件读写
查看>>
架构漫谈(一):什么是架构?
查看>>
php7不再支持HTTP_RAW_POST_DATA,微信支付$GLOBALS[‘HTTP_RAW_POST_DATA’]获取不到数据,...
查看>>
xshell使用xftp传输文件,使用pure-ftpd搭建ftp服务
查看>>
spring给静态变量使用@Autowired注入
查看>>
win32学习01.编程基础
查看>>
主成分分析(PCA)中的误差表示
查看>>
你了解ABBYY PDF Transformer+吗
查看>>
怎么给PDF文档和扫描文件里的机密信息提高保护
查看>>
Mysql提供sequence服务
查看>>
前嗅ForeSpider教程:采集需要登陆的网页内容
查看>>
SID 的变化
查看>>
Python学习--subprocess
查看>>
基于bootstrap的简单响应式菜单
查看>>
如何在同一篇文章里不同位置引用同一篇参考文献
查看>>