几种分页错误算法(FIFO、LRU和LFU ) )的实现流程2015-09-05 20:34:02分类: LINUX
最近,虚拟存储管理中的几种缺页中断算法正在编写经常被试验的问题。 这样的问题可以说非常简单,但在概念上很容易混淆,如果没有掌握正确的做法就很容易出错,所以我认为有必要对这三种算法的实现过程进行一次梳理,从源代码层面考虑它们的实现。 首先我推荐博客。 为这两个算法给出了不易出错的运算步骤,也给了我们提示。 该博客也显示了源代码,但没有验证。 33558 www.cn blogs.com/free yiyi 1993/archive/2013/05/18/3084956.html重新提交腾讯问题:基于页面的虚拟存储管理系统,用户按照该顺序访问的页面序列是1。5 .假设分配给该作业的页数是3,在作业的初始时没有加载页面,则使用FIFO调度算法时的页面错误数是多少,lrror FIFO算法: (First In First Out ),先进先出,一般来说,看到这样的思想,首先想到的数据结构必须是队列,但是这里最好使用vector。 为什么这么说呢,是因为在页面移动中需要遍历队列,检查该页面是否已经存在。 如果算法的存储结构是队列或堆栈,但在实现过程中总是需要遍历所有队列或所有堆栈的内容,则最好使用vector。到此为止,我认为给出访问序列仿真算法非常简单,但需要花费时间存取序列: 1、2、3、4、1、2、5、1、2、3、4、5、1、2、3先调入存储器,存储器结构: 32缺页次数: 3 4缺页次数,调用1,记录内存结构:14缺页次数内存配置:2 1 4缺页次数:6 5缺页次数,4调用,内存配置:5 2 1缺页次数:7 1存在,内存配置无变化2存在,内存配置无变化3缺页次数,1调用,备注2调用,无内存配置更改4 3 5缺页次数:9 5存在,共9次缺页中断率=缺页中断次数/总访问页数=9/12 LRU算法:最近最低使用(Least Recently Used ),首先1、2、2
word"> 1,2,3先调入内存,内存结构:3 2 1 缺页次数:34调入内存,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