简介这份资源围绕操作系统内存管理中的LRU页面替换算法展开面向正在学习操作系统课程、准备课程实验或希望理解缓存淘汰策略的学生与开发者。压缩包内共2个文件包含1个cpp源代码与1个txt文本整体约1KB其中cpp文件应为LRU算法的C模拟实现txt文件可能附带算法说明或实验参考资料便于对照代码理解实现细节。资源重点呈现LRU的核心思路基于最近最久未使用原则在缓存满时淘汰访问时间最早的页面并借助链表或哈希表维护页面访问状态涵盖初始化、页面访问判断、缓存未满插入与已满淘汰等关键环节。已有252人学习浏览适合作为操作系统实验的参考实现帮助读者掌握页面替换流程、数据结构选型与缓存优化思路为后续设计高效缓存策略打下基础。1. 页面替换算法里的 LRU为什么它总在面试和线上事故里同时出现LRU 页面替换算法Least Recently Used最近最少使用是操作系统内存管理和缓存系统里最常被拿出来讨论的策略之一。它的核心假设非常朴素如果一个页面最近被访问过那么它在不久的将来被再次访问的概率比那些很久没被碰过的页面要高。基于这个假设当内存或缓存满了需要腾位置时LRU 选择淘汰最久未被访问的那个页面。这个逻辑听起来简单但真正把它落地到生产环境时你会发现两个极端场景面试里手写 LRU 是经典题线上缓存命中率突然暴跌的事故里LRU 的实现细节也经常是元凶。这篇文章面向的是需要自己实现或调优页面替换策略的开发者不管你是做操作系统课程设计、写本地缓存组件还是在分布式缓存里配置淘汰策略下面这些内容都能直接拿去复现和排查。2. LRU 页面替换的底层数据结构选型哈希表加双向链表为什么是标配2.1 从访问序列到淘汰决策LRU 到底在维护什么状态要理解 LRU 的实现先要搞清楚它需要维护什么。每次页面访问发生时LRU 需要做两件事第一判断这个页面是否已经在缓存里第二如果已经在把它标记为“最近使用过”如果不在把它加载进来并在缓存满时踢掉最久未使用的那个。这三个操作——查找、更新位置、淘汰尾部——决定了数据结构的选择。用普通数组或单链表能做吗能但查找是 O(n)淘汰也是 O(n)页面数量一上来性能就崩了。用哈希表单独做呢查找是 O(1)但你没法知道谁是最久未使用的因为哈希表不维护顺序。所以常见做法是把哈希表和双向链表组合起来哈希表负责 O(1) 定位节点双向链表负责 O(1) 调整顺序和删除尾部节点。这个组合是 LRU 实现的标准答案也是很多缓存库比如本地缓存组件的底层结构。这里有一个容易混淆的点LRU 维护的是“访问顺序”不是“加载顺序”。每次 get 操作即使页面已经在缓存里也要把它移到链表头部。很多人第一次实现时只在 put 的时候移动节点结果 get 频繁的热点数据反而被淘汰了这就是典型的翻车现场。2.2 手写一个可运行的 LRUPython 版本与关键注释下面是一个完整的 LRU 实现用 Python 写基于哈希表加双向链表。你可以直接复制运行测试用例也在后面。class DLinkedNode: 双向链表节点存储 key-value 以及前后指针 def __init__(self, key0, value0): self.key key self.value value self.prev None self.next None class LRUCache: def __init__(self, capacity: int): self.capacity capacity self.cache {} # 哈希表key - DLinkedNode # 虚拟头尾节点避免边界判断 self.head DLinkedNode() self.tail DLinkedNode() self.head.next self.tail self.tail.prev self.head def _add_to_head(self, node): 把节点加到链表头部最近使用位置 node.prev self.head node.next self.head.next self.head.next.prev node self.head.next node def _remove_node(self, node): 从链表中摘除一个节点 node.prev.next node.next node.next.prev node.prev def _move_to_head(self, node): 把已有节点移到头部 self._remove_node(node) self._add_to_head(node) def _remove_tail(self): 删除尾部节点最久未使用返回该节点 node self.tail.prev self._remove_node(node) return node def get(self, key: int) - int: if key not in self.cache: return -1 node self.cache[key] self._move_to_head(node) # 关键访问后移到头部 return node.value def put(self, key: int, value: int) - None: if key in self.cache: node self.cache[key] node.value value self._move_to_head(node) else: node DLinkedNode(key, value) self.cache[key] node self._add_to_head(node) if len(self.cache) self.capacity: removed self._remove_tail() del self.cache[removed.key] # 别忘了从哈希表里删掉这段代码里最关键的逻辑在get方法只要命中就必须调用_move_to_head。很多实现漏掉这一步导致 LRU 退化成 FIFO。另一个容易出错的地方是put里淘汰节点时一定要同时从self.cache里删除对应的 key否则哈希表会越积越大内存泄漏。参数方面capacity决定了缓存能容纳多少个页面。设置太小会导致频繁淘汰命中率低设置太大则占用内存过多。一般建议根据实际工作集的活跃页面数量来定或者用监控数据里的 P99 活跃页面数作为参考。2.3 用 OrderedDict 快速验证三行代码跑通 LRU 逻辑如果你只是想快速验证 LRU 的行为不想手写链表Python 的collections.OrderedDict可以直接用。它内部维护了插入顺序配合move_to_end和popitem就能实现 LRU。from collections import OrderedDict class LRUCacheFast: def __init__(self, capacity: int): self.capacity capacity self.cache OrderedDict() def get(self, key: int) - int: if key not in self.cache: return -1 self.cache.move_to_end(key) # 移到末尾表示最近使用 return self.cache[key] def put(self, key: int, value: int) - None: if key in self.cache: self.cache.move_to_end(key) self.cache[key] value if len(self.cache) self.capacity: self.cache.popitem(lastFalse) # 弹出最早插入的最久未使用这个版本适合快速原型验证但要注意OrderedDict的move_to_end和popitem在 CPython 里是 C 实现的性能不差。不过如果你要嵌入到自己的数据结构里或者需要更细粒度的控制比如带过期时间还是得手写链表。3. 把 LRU 放进真实页面替换场景从模拟器到参数调优3.1 页面访问序列模拟用随机序列和局部性序列对比命中率要评估 LRU 的实际效果不能只看单次操作得跑一段页面访问序列。下面是一个简单的模拟器生成两种序列一种是完全随机的一种是带局部性的模拟真实程序访问模式。import random def generate_random_sequence(length, page_range): 完全随机序列没有局部性 return [random.randint(0, page_range - 1) for _ in range(length)] def generate_locality_sequence(length, page_range, hot_ratio0.8): 带局部性的序列80% 的访问集中在 20% 的热页面上 hot_pages random.sample(range(page_range), max(1, page_range // 5)) cold_pages [p for p in range(page_range) if p not in hot_pages] seq [] for _ in range(length): if random.random() hot_ratio: seq.append(random.choice(hot_pages)) else: seq.append(random.choice(cold_pages)) return seq def simulate_lru(sequence, capacity): 模拟 LRU 页面替换返回缺页次数 cache OrderedDict() page_faults 0 for page in sequence: if page in cache: cache.move_to_end(page) else: page_faults 1 cache[page] True if len(cache) capacity: cache.popitem(lastFalse) return page_faults # 跑一组对比 random.seed(42) seq_random generate_random_sequence(10000, 50) seq_locality generate_locality_sequence(10000, 50) for cap in [5, 10, 20]: faults_random simulate_lru(seq_random, cap) faults_locality simulate_lru(seq_locality, cap) print(f容量{cap}: 随机序列缺页{faults_random}, 局部性序列缺页{faults_locality})跑出来的结果通常会显示在局部性序列上LRU 的缺页次数明显低于随机序列而且容量越大差距越明显。这验证了 LRU 的设计假设——它吃的是访问局部性。如果你的实际业务访问模式没有局部性比如完全随机的 key 访问LRU 的效果会大打折扣这时候可能需要考虑 LFU 或者 ARC 之类的策略。3.2 容量设置与命中率曲线怎么找到性价比最高的那个点容量设置是 LRU 调优里最实际的问题。设太小缺页率高设太大内存浪费。下面这段代码可以帮你画出命中率随容量变化的曲线。def hit_rate_curve(sequence, max_capacity): 计算不同容量下的命中率 results [] for cap in range(1, max_capacity 1): cache OrderedDict() hits 0 for page in sequence: if page in cache: hits 1 cache.move_to_end(page) else: cache[page] True if len(cache) cap: cache.popitem(lastFalse) results.append((cap, hits / len(sequence))) return results # 假设 seq_locality 已经生成 curve hit_rate_curve(seq_locality, 30) for cap, rate in curve: print(f容量{cap}, 命中率{rate:.4f})观察曲线你会发现一个拐点容量增加到某个值之后命中率提升变得非常缓慢。这个拐点就是性价比最高的容量。实际生产里你可以用历史访问日志跑这个曲线然后结合内存预算来定。我一般会选拐点附近再留 20% 余量防止突发流量导致命中率骤降。3.3 和 FIFO、LFU 的横向对比什么场景下 LRU 会输LRU 不是万能的。下面这个表格对比了三种常见策略在典型场景下的表现。策略核心思想优点缺点适合场景FIFO先进先出实现最简单可能淘汰热点页面访问模式均匀、无局部性LRU最近最少使用利用时间局部性对扫描式访问不友好有明确热点的场景LFU最不经常使用利用频率局部性新页面难以积累频率热点长期稳定的场景LRU 最怕的是“扫描式访问”比如一次性遍历一个很大的数据集每个页面只访问一次。这种情况下 LRU 会把原本的热点页面全部挤出去导致缓存污染。常见做法是在 LRU 前面加一层过滤或者用 LRU-K 来识别真正的热点。4. LRU 实现和调优的避坑指南五条血泪经验4.1 坑一get 操作忘记移动节点LRU 退化成 FIFO现象缓存命中率始终上不去观察淘汰日志发现被淘汰的往往是刚刚访问过的页面。原因get方法里只返回了值没有把节点移到链表头部。解决在get命中后立即调用move_to_head确保访问顺序被正确更新。这个坑在面试手写时也经常出现写完记得检查一遍。4.2 坑二淘汰时只删链表节点哈希表里还留着现象内存占用持续增长明明设置了容量上限但进程 RSS 一直涨。原因_remove_tail只从链表里摘了节点没有执行del self.cache[removed.key]。解决淘汰逻辑里必须同时清理哈希表建议把删除操作封装成一个方法避免遗漏。4.3 坑三并发环境下链表指针错乱现象多线程压测时出现死循环或者节点丢失CPU 飙高。原因双向链表的指针操作不是原子的多个线程同时修改prev和next会导致链表断裂。解决加锁或者用分段锁降低粒度。如果读多写少可以考虑读写锁如果追求极致性能可以用无锁队列或者分片 LRU。4.4 坑四容量设为 0 或负数导致未定义行为现象传入 capacity0 时put 操作直接崩溃或者行为异常。原因代码里没有对容量做边界检查len(self.cache) self.capacity在容量为 0 时永远为真但淘汰逻辑可能拿到空链表。解决在构造函数里校验capacity 1或者对容量为 0 的情况直接返回不缓存。4.5 坑五用时间戳代替链表顺序精度不够导致误淘汰现象同一毫秒内访问的多个页面淘汰顺序不符合预期。原因用time.time()做时间戳精度只有毫秒级高并发下多个页面时间戳相同无法区分先后。解决要么用单调递增的计数器代替时间戳要么老老实实用双向链表维护顺序。链表方案虽然多写几行代码但顺序是严格确定的。5. 进阶技巧用 LRU-K 和分片 LRU 应对扫描式访问与高并发5.1 LRU-K用访问次数过滤一次性扫描标准 LRU 的一个硬伤是没法区分“只访问一次”和“访问多次”的页面。LRU-K 的思路是只有当页面被访问了 K 次之后才把它放进 LRU 缓存。这样扫描式访问的页面因为只出现一次根本进不了缓存不会污染热点数据。实现上你需要维护一个访问历史队列记录每个页面的访问次数。当次数达到 K 时才把页面插入 LRU 链表。下面是一个简化版的 LRU-2 核心逻辑。class LRUKCache: def __init__(self, capacity, k2): self.capacity capacity self.k k self.cache OrderedDict() # 真正的 LRU 缓存 self.history {} # key - 访问次数 def get(self, key): if key in self.cache: self.cache.move_to_end(key) return self.cache[key] # 记录历史访问 self.history[key] self.history.get(key, 0) 1 if self.history[key] self.k: # 达到 K 次插入缓存 self.cache[key] True if len(self.cache) self.capacity: self.cache.popitem(lastFalse) return -1这个版本里history字典会无限增长实际使用需要加过期清理。K 值一般取 2 或 3太大导致新热点难以进入缓存太小则过滤效果不明显。5.2 分片 LRU把锁竞争降到最低高并发场景下单个 LRU 的锁会成为瓶颈。分片 LRU 的思路是把缓存分成 N 个独立的 LRU 分片每个分片有自己的锁。访问时根据 key 的哈希值路由到对应分片这样锁竞争被分散到 N 个锁上。import hashlib class ShardedLRU: def __init__(self, capacity, shards16): self.shards shards self.per_shard_cap max(1, capacity // shards) self.maps [LRUCache(self.per_shard_cap) for _ in range(shards)] def _shard_index(self, key): h hashlib.md5(str(key).encode()).hexdigest() return int(h, 16) % self.shards def get(self, key): return self.maps[self._shard_index(key)].get(key) def put(self, key, value): self.maps[self._shard_index(key)].put(key, value)分片数量一般取 2 的幂次方便取模。每个分片的容量要单独设置总容量等于各分片之和。注意分片后淘汰是局部的某个分片满了不会影响其他分片所以整体命中率可能略低于单实例 LRU但并发性能提升明显。5.3 验证方法用命中率和 P99 延迟两个指标收口不管你怎么优化最后都要用数据说话。我一般会盯两个指标命中率和 P99 延迟。命中率反映策略效果P99 延迟反映实现质量。测试时用真实访问日志回放对比优化前后的曲线。如果命中率提升但 P99 延迟恶化说明锁竞争或者链表操作成了新瓶颈需要继续调整分片数或者换无锁结构。我自己踩过最狠的一次坑是在一个高并发服务里用了全局锁的 LRU平时 QPS 低的时候一切正常大促流量一上来LRU 的锁直接把整个服务拖垮。后来改成 64 分片P99 从 800ms 降到 12ms。从那以后只要涉及共享状态的缓存结构我都会先问一句锁的粒度够细吗希望帮到你。本文还有配套的精品资源点击获取
