lru和lfu算法的区别是什么

常用知识 (25) 3个月前

本教程操作环境:windows7系统、Dell G3电脑。

对于web开发而言,缓存必不可少,也是提高性能最常用的方式。无论是浏览器缓存(如果是chrome浏览器,可以通过chrome:://cache查看),还是服务端的缓存(通过memcached或者redis等内存数据库)。缓存不仅可以加速用户的访问,同时也可以降低服务器的负载和压力。那么,了解常见的缓存淘汰算法的策略和原理就显得特别重要。

常见的缓存算法

  • LRU (Least recently used) 最近最少使用,如果数据最近被访问过,那么将来被访问的几率也更高。
  • LFU (Least frequently used) 最不经常使用,如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小。
  • FIFO (Fist in first out) 先进先出, 如果一个数据最先进入缓存中,则应该最早淘汰掉。

LRU缓存

像浏览器的缓存策略、memcached的缓存策略都是使用LRU这个算法,LRU算法会将近期最不会访问的数据淘汰掉。LRU如此流行的原因是实现比较简单,而且对于实际问题也很实用,良好的运行时性能,命中率较高。下面谈谈如何实现LRU缓存:

  • 新数据插入到链表头部
  • 每当缓存命中(即缓存数据被访问),则将数据移到链表头部
  • 当链表满的时候,将链表尾部的数据丢弃

LRU Cache具备的操作:

  • set(key,value):如果key在hashmap中存在,则先重置对应的value值,然后获取对应的节点cur,将cur节点从链表删除,并移动到链表的头部;若果key在hashmap不存在,则新建一个节点,并将节点放到链表的头部。当Cache存满的时候,将链表最后一个节点删除即可。
  • get(key):如果key在hashmap中存在,则把对应的节点放到链表头部,并返回对应的value值;如果不存在,则返回-1。

LRU和LFU的区别:

LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面!

LFU是最近最不常用页面置换算法(Least Frequently Used),也就是淘汰一定时期内被访问次数最少的页!

比如,第二种方法的时期T为10分钟,如果每分钟进行一次调页,主存块为3,若所需页面走向为2 1 2 1 2 3 4

注意,当调页面4时会发生缺页中断

若按LRU算法,应换页面1(1页面最久未被使用) 但按LFU算法应换页面3(十分钟内,页面3只使用了一次)

总结

可见LRU关键是看页面最后一次被使用到发生调度的时间长短;

而LFU关键是看一定时间段内页面被使用的频率!

更多相关知识,请访问常用知识栏目!

以上就是lru和lfu算法的区别是什么的详细内容,更多请关注兜懂趣百科其它相关文章!

发表评论