博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LRU LFU FIFO 转载
阅读量:5132 次
发布时间:2019-06-13

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

--------------------------------------》href--------------------------》

http://blog.chinaunix.net/uid-13246637-id-5185352.html

 

 最近在做笔试题,其中虚拟存储管理中几种缺页中断算法经常考到,虽然这类题可说非常简单,但概念上却容易混淆而且如果不掌握正确的做法很容易出错,因此觉得有必要把这三种算法的实现过程理一遍,并从源代码级别去思考它们的实现。

 首先推荐一个博客,对这两个算法给出了不易错的演算步骤,也给了我一些启示,这篇博客也给出了源代码,但我没有去验证。
 http://www.cnblogs.com/freeyiyi1993/archive/2013/05/18/3084956.html
 再给出腾讯的笔试题原题:在一个采用页式虚拟存储管理的系统中,有一用户作业,它依次要访问的页面序列是1,2,3,4,1,2,5,1,2,3,4,5.假定分配给该作业的页数为3且作业初始时未装载页面,那么采用FIFO调度算法产生的缺页中断数为多少,采用LRU调度算法产生的缺页中断数为多少?
 FIFO算法:(First In First Out),先进先出,一般看到这类思想,首先想到的数据结构应当是队列,但是我们这里最好是用vector,因为调页过程中需要遍历队列检查该页是否已存在,当算法的存储结构是队列或栈,但实现过程中需要经常遍历全队列或全栈的内容时,最好用vector,这是《剑指Offer》面试题25给我的启发。给出一个访问序列的模拟算法到此应该非常简单了,为了节省时间,下面仅给出题目计算步骤,代码今后再补。
           访问序列:1,2,3,4,1,2,5,1,2,3,4,5
                   1,2,3先调入内存,内存结构:3      2      1    缺页次数:3  
                   4调入内存,1调出,  内存结构:4      3      2    缺页次数:4
                   1调入内存,2调出,  内存结构:1      4      3    缺页次数:5
                   2调入内存,3调出,  内存结构:2      1      4    缺页次数:6
                   5调入内存,4调出,  内存结构:5      2      1    缺页次数:7
                   1存在,内存结构不改变
                   2存在,内存结构不改变
                   3调入内存,1调出,  内存结构:3      5      2    缺页次数:8
                   4调入内存,2调出,  内存结构:4      3      5    缺页次数:9
                   5存在,内存结构不改变
            共缺页9次,缺页中断率 = 缺页中断次数 / 总访问页数 = 9 / 12    
LRU算法:最近最少使用(Least Recently Used),先看一下调页过程
           访问序列:1,2,3,4,1,2,5,1,2,3,4,5
                1,2,3先调入内存,内存结构:3      2      1    缺页次数:3  
                4调入内存,1调出,  内存结构:4      3      2    缺页次数:4
                1调入内存,2调出,  内存结构:1      4      3    缺页次数:5
                2调入内存,3调出,  内存结构:2      1      4    缺页次数:6
                5调入内存,4调出,  内存结构:5      2      1    缺页次数:7
           到这一步其实和FIFO并没有区别
              1调入内存,由于内存中存在1,故没有缺页中断,但由于1最近被访问过,所以要将其位置调换,
              使它最后一个被淘汰,内存结构:1      5      2
              2调入内存,没有缺页中断,但内存位置要变化,内存结构:2      1      5
                  3调入内存,5调出,  内存结构:3      2      1    缺页次数:8
                  4调入内存,1调出,  内存结构:4      3      2    缺页次数:9
                  5调入内存,2调出,  内存结构:5      4      3    缺页次数:10
           共缺页10次,缺页中断率:10/12
算法总结:数据结构应该还是一个队列,开始内存页面不满时按序把页面填入,之后如果调入的页不存在,则按照先进先出顺序,淘汰队头页面,如果调入的页存在,则将该页换至页尾,该页之后的元素前移,这个最好用什么数据结构?
其实觉得腾讯这道题的序列没有代表性,要真正理解LRU过程中内存存储页面结构的变化情况,还是推荐看一下上面的博客。
LFU算法:最近最不经常使用(Least Frequently Used),相比于前两个,LFU算法的资料要少得多,因为它的实现更加复杂,在网上搜到这个博客,http://www.cnblogs.com/tingyuxuan007/p/3823537.html,这个博客有这三个算法思想的讨论及图解,有利于初学者去彻底弄懂这个问题,现摘录一些它的语句来说清楚这个算法的思想:
“这是一个基于访问频率的算法.与LRU不同,LRU是基于时间的,会将时间上最不常访问的数据淘汰;LFU为将频率上最不常访问的数据淘汰.既然是基于频率的,就需要有存储每个数据访问的次数.从存储空间上,较LRU会多出一些持有计数的空间.”,它描述这个算法的图也很经典

 

 

我想有这幅图就已经不需要再多说什么了,如果还有不明白的,去原博客看一下叙述就行了。

还是把腾讯这道题用LFU算法再做一遍:
   访问序列:1,2,3,4,1,2,5,1,2,3,4,5  
     最初:                3(1)      2(1)      1(1)       缺页次数:3      括号中是其访问次数   
        调入4                 4(1)       3(1)      2(1)       淘汰1,缺页次数:4 
        调入1                 1(1)       4(1)      3(1)       淘汰2,缺页次数:5 
        调入2                 2(1)       1(1)      4(1)       淘汰3,缺页次数:6 
        调入5                 5(1)       2(1)      1(1)       淘汰4,缺页次数:7
        调入1                 1(2)       5(1)      2(1)
        调入2                 2(2)       1(2)      5(1)
        调入3                 2(2)       1(2)      3(1)       淘汰5,缺页次数:8 
        调入4                 2(2)       1(2)      4(1)       淘汰3,缺页次数:9
        调入5                 2(2)       1(2)      5(1)       淘汰4,缺页次数:10
    共缺页10次,缺页中断率:10/12

 

转载于:https://www.cnblogs.com/13224ACMer/p/6202883.html

你可能感兴趣的文章
NAT地址转换
查看>>
Nhibernate 过长的字符串报错 dehydration property
查看>>
Deque - leetcode 【双端队列】
查看>>
gulp插件gulp-ruby-sass和livereload插件
查看>>
免费的大数据学习资料,这一份就足够
查看>>
clientWidth、clientHeight、offsetWidth、offsetHeight以及scrollWidth、scrollHeight
查看>>
企业级应用与互联网应用的区别
查看>>
itext jsp页面打印
查看>>
Perl正则表达式匹配
查看>>
DB Change
查看>>
nginx --rhel6.5
查看>>
Eclipse Python插件 PyDev
查看>>
selenium+python3模拟键盘实现粘贴、复制
查看>>
第一篇博客
查看>>
typeof与instanceof的区别
查看>>
网站搭建(一)
查看>>
SDWebImage源码解读之SDWebImageDownloaderOperation
查看>>
elastaticsearch
查看>>
postgreSQL 简单命令操作
查看>>
Spring JDBCTemplate
查看>>