LRU和LFU 算法(页面置换算法)

LRU和LFU 算法(页面置换算法)LRU 和 LFU 的区别 LRU 和 LFU 都是内存管理的页面置换算法

大家好,欢迎来到IT知识分享网。

LRU和LFU的区别

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 (最长时间)

最近最久未使用算法, LRU是淘汰最长时间没有被使用的页面

功能

  1. 缓存容量capacity为正整数,缓存的key、value均为int类型
  2. 读缓存func get(key int) int
    • key已存在,返回对应value
    • key不存在,返回-1
  3. 写缓存func put(key int, value int):
    • key已存在,修改对应value
    • key不存在,写入该组缓存,若写入前缓存容量已达上限,则应淘汰最久未使用的缓存(强调:读、写缓存均视为使用)

数据结构

  • 使用双向链表维护缓存的上一次使用时间:
    • 约定:链表正方向(从头部到尾部)节点按照使用时间排序——越早使用(即久未使用)的节点,越靠近链表尾部
    • 维护:每使用一次缓存,就将该缓存对应的链表节点移动到链表头部;缓存淘汰时,只需要删除尾部节点即可
  • 增加一个map,记录key链表节点的映射关系; 解决如果只使用双向链表,每次判断key是否存在时,都要遍历链表
  1. cache:map[int]*listNodekey到节点的映射; 其中 listNode data:key, value
  2. list:*listNode,双向链表,维护缓存的上一次使用时间
  3. capacity:int,链表容量

伪代码

  • 读缓存
    1. key存在:
      • 在原链表中删除该缓存节点,重新插入到链表头部,
      • 返回对应的value
    2. key不存在:
      • 返回-1
  • 写缓存(更新缓存)
    1. Key存在:
      • 更新缓存节点的value值
      • 在原链表中删除该缓存节点,并把该重新插入到链表头部
    2. Key不存在:
      1. 容量已达上限:
        • 在链表中删除尾部节点(记录该节点的key)
        • 根据上一步中记录的key,删除对应的映射关系
        • 根据输入参数构造新的节点:
        • 将新的节点插入链表头部
        • 新增key到新的节点的映射关系
      2. 容量未达上限:
        • 根据输入参数构造新的节点:
        • 将新的节点插入链表头部
        • 新增key到新的节点的映射关系

Golang代码实现

// 双向链表节点 type doublyListNode struct { key int value int prev *doublyListNode next *doublyListNode } // 构造一个双向空链表(首尾几点都是空节点) func newDoublyList() *doublyListNode { headNode := &doublyListNode{} tailNode := &doublyListNode{} headNode.next = tailNode tailNode.prev = headNode return headNode } // 把节点添加到链表头部 func (dl *doublyListNode) addToHead(node *doublyListNode) { dl.next.prev = node node.next = dl.next dl.next = node node.prev = dl } // 删除链表中的节点 func removeNode(node *doublyListNode) { node.next.prev = node.prev node.prev.next = node.next } // LRUCache 具体的缓存 type LRUCache struct { cache map[int]*doublyListNode head *doublyListNode tail *doublyListNode capacity int } // Constructor 构建缓存容器 func Constructor(capacity int) LRUCache { dl := newDoublyList() return LRUCache{ cache: make(map[int]*doublyListNode), head: dl, tail: dl.next, capacity: capacity, } } func (lruCache *LRUCache) Get(key int) int { // 根据key 获取缓存 v, ok := lruCache.cache[key] // 如果没有缓存, 返回-1 if !ok { return -1 } // 如果有缓存 removeNode(v) // 移除该缓存 lruCache.head.addToHead(v) // 把缓存添加双向链表头部 return v.value } // Put 新建缓存 func (lruCache *LRUCache) Put(key int, value int) { // 已经有缓存 if v, ok := lruCache.cache[key]; ok { // v 是双链表中的节点 v.value = value // 更新链表节点中的值 lruCache.cache[key] = v // 更新缓存中映射关系 removeNode(v) // 移除该缓存 lruCache.head.addToHead(v) // 把缓存添加双向链表头部 return } // 缓存超长 淘汰缓存 if len(lruCache.cache) >= lruCache.capacity { node := lruCache.tail.prev removeNode(node) // 删除该节点 delete(lruCache.cache, node.key) // 清除 最近最少使用的缓存 } newNode := &doublyListNode{ key: key, value: value, } lruCache.cache[key] = newNode lruCache.head.addToHead(newNode) } 

LFU (最少次)

功能

  1. 缓存容量capacity、缓存的key和value均为自然数(可以为0,代码中单独处理)
  2. 读缓存func get(key int) int:(与lru相同)
    • key已存在,返回对应value
    • key不存在,返回-1
  3. 写缓存func put(key int, value int):
    • key已存在,修改对应value
    • key不存在,写入该组缓存,若写入前缓存容量已达上限,则应淘汰使用次数最少的缓存(记其使用次数为n);
    • 若使用次数为n的缓存数大于一个,则淘汰最久未使用的缓存(即,此时遵守lru规则)

数据结构

// LFUCache 具体的缓存 frequency 是使用次数 type LFUCache struct { 
   

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/127890.html

(0)
上一篇 2025-09-04 16:20
下一篇 2025-09-04 16:33

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信