欢迎您光临本小站。希望您在这里可以找到自己想要的信息。。。

LRU与LFU比较

数据结构算法 water 2557℃ 0评论

提到缓存,有两点是必须要考虑的:
(1)缓存数据和目标数据的一致性问题。
(2)缓存的过期策略(机制)。

 其中,缓存的过期策略涉及淘汰算法。常用的淘汰算法有下面几种:
(1)FIFO:First In First Out,先进先出
(2)LRU:Least Recently Used,最近最少使用
(3)LFU:Least Frequently Used,最不经常使用
      注意LRU和LFU的区别。LFU算法是根据在一段时间里数据项被使用的次数选择出最少使用的数据项,即根据使用次数的差异来决定。而LRU是根据使用时间的差异来决定的。

一、概念介绍

LRU和LFU都是内存管理的页面置换算法。

LRU,即:最近最少使用淘汰算法(Least Recently Used)。LRU是淘汰最长时间没有被使用的页面。

LFU,即:最不经常使用淘汰算法(Least Frequently Used)。LFU是淘汰一段时间内,使用次数最少的页面。

二、例子详解

假设LFU方法的时期T为10分钟,访问如下页面所花的时间正好为10分钟,内存块大小为3。

若所需页面顺序依次如下:

2  1  2  1  2  3  4 

—————————————->

当需要使用页面4时,内存块中存储着1、2、3,内存块中没有页面4,就会发生缺页中断,而且此时内存块已满,需要进行页面置换。

若按LRU算法,应替换掉页面1。因为页面1是最长时间没有被使用的了,页面2和3都在它后面被使用过。

若按LFU算法,应换页面3。因为在这段时间内,页面1被访问了2次,页面2被访问了3次,而页面3只被访问了1次,一段时间内被访问的次数最少。

可见LRU关键是看页面最后一次被使用到发生替换的时间长短,时间越长,页面就会被置换; 而LFU关键是看一定时间段内页面被使用的频率(次数),使用频率越低,页面就会被置换。

也就是说: LRU算法适合:较大的文件比如游戏客户端(最近加载的地图文件) LFU算法适合:较小的文件和教零碎的文件比如系统文件、应用程序文件 其中:LRU消耗CPU资源较少,LFU消耗CPU资源较多。

转载请注明:学时网 » LRU与LFU比较

喜欢 (1)or分享 (0)

您必须 登录 才能发表评论!