★ FEATURED ARTICLE 简介一份针对LRULeast Recently Used页面替换算法的C实现面向操作系统课程实验、期末备考以及希望掌握内存管理策略的开发者。资源将经典页面替换算法转化为可运行的代码帮助理解在内存空间不足时系统如何依据“最近最久未使用”原则淘汰页面。压缩包内共2个文件1个cpp源文件完整实现LRU缓存逻辑包括页面访问、缓存查找、淘汰决策等核心步骤1个txt文本文件可能附带算法原理、实验说明或参考信息。整个资源包大小仅1KB结构精简、便于快速浏览。目前已有252人学习下载。通过阅读这份源码读者可以观察到页面请求序列下缓存状态的动态变化掌握用链表或哈希表维护页面访问时间、快速查找页面是否存在以及淘汰最久未用页面的具体技巧。代码量小、逻辑集中可直接作为操作系统课程实验的参考实现或在此基础上扩展为更复杂的内存管理模拟器进一步理解资源受限场景下缓存策略对程序性能的影响。1. LRU 页面替换算法理论上最优工程上却最先翻车只要是做缓存、做操作系统、做数据库的早晚都要和 LRU 页面替换算法打交道。它的全称是 Least Recently Used意思是当内存满了、必须赶走一个页来腾位置的时候优先淘汰“最近最久没被用过”的那一页。这个思路朴素得几乎不用解释刚访问过的东西大概率很快还会被访问老不碰的东西大概率可以请出去了。真正反直觉的点在于LRU 在缺页率上能逼近理论最优但它严格的实现方式——哈希表加双向链表——在真实系统里几乎总会因为扫描型访问、并发锁和硬件开销而退化。很多自称 LRU 的产品实际用的是时钟算法或者采样近似实现。这篇文章按我实战踩坑的顺序写先搭一个最小可运行的 LRU cache再把它放到页面替换场景里量缺页率然后讲近似算法的取舍最后把最容易翻车的几个坑单独拎出来。适合读这篇文章的人是那种已经在写代码、想让缓存命中率上一个台阶的工程师不是在纠结概念定义的学生。你至少有半个月以上系统级编程经验看得懂伪代码并且手头有一台能跑 Python 的机器。不需要内核源码不需要读论文核心结论我会直接给严格 LRU 只适合做用户态缓存在操作系统页面替换里它必须被时钟算法或者分段 LRU 取代。2. LRU cache 的最小实现哈希表加双向链表为什么是唯一正解2.1 从页面替换到 cache APIget/put 背后的两个动作LRU 落到工程上通常不是你直接操作页面帧而是封装成一个 cache 对象对外只暴露 get 和 put 两个接口。你从“页面替换”的角度去看这两个接口会发现它们是对内存操作的抽象get(key) 相当于 CPU 访问了某个虚拟页带来了这一次访问put(key, value) 相当于把一个页装入内存如果内存已经满了put 的内部就必须先完成一次页面替换。所以判断一个 LRU 实现好不好的标准也很简单get 命中一个已有页这个页要被标记成“最近使用”get 没命中这是缺页put 一个新页如果容量已满就把最久没用的那个页淘汰掉。这三个动作看着简单但有一个硬性指标每个动作平均复杂度最好是 O(1)。为什么必须是 O(1)因为缓存是访问热路径每多一次 O(n) 遍历缺页没等到性能就先崩了。下面这段代码就是按这个指标来的标准实现。2.2 用双向链表加哈希表实现 LRUO(1) 的 get 与 putclass DLinkedNode: __slots__ (key, value, prev, next) 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 - 链表节点 self.head DLinkedNode() # 哨兵头head.next 是最近使用 self.tail DLinkedNode() # 哨兵尾tail.prev 是最久未使用 self.head.next self.tail self.tail.prev self.head def _remove_node(self, node): node.prev.next node.next node.next.prev node.prev def _add_to_head(self, node): # 新节点插到 head 和 head.next 之间 node.prev self.head node.next self.head.next self.head.next.prev node self.head.next node def get(self, key: int) - int: if key not in self.cache: return -1 node self.cache[key] self._remove_node(node) # 从当前位置摘下来 self._add_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._remove_node(node) self._add_to_head(node) return if len(self.cache) self.capacity: # 淘汰 tail.prev也就是最久未使用的节点 old_node self.tail.prev self._remove_node(old_node) del self.cache[old_node.key] new_node DLinkedNode(key, value) self.cache[key] new_node self._add_to_head(new_node)这里的逻辑和内核里的页面表很像cache字典相当于页表完成从 key虚拟页号到物理位置的映射双向链表相当于 LRU 链维护访问的先后次序。注意我这里写了两个哨兵节点head和tail它们不存真实数据作用是让边界判断从“链表是否为空”变成“是否碰到哨兵”代码里不需要写一堆 if 来判空出错的概率小很多。有几个参数你需要实际改一改才知道深浅。第一capacity不是越大越好在页面替换里它对应的是驻留集大小容量越大缺页率越低但它和内存分配策略耦合后面章节会说。第二__slots__这个类属性我写了它能减少每个节点的内存占用。你做页面级 LRU 的时候节点动辄上百万个每个节点省几十字节就是几十 MB 的差别这是真实存在的优化不是炫技。第三链表头部和尾部的定义各厂不同——有人用 head 代表最久未使用有人用 head 代表最近使用。这个定义影响所有的节点移动方向建议在代码注释里定死不然两周后回来改 bug 会疯。2.3 时间戳方案为什么只配做玩具哈希表加链表是标准做法但你肯定会看到另一种更直观的实现用一个字典记录每个 key 的最后访问时间戳替换时遍历一遍找出最小值。这个方案代码短十几行就能写完但代价是 put 的复杂度变成了 O(n)。我在一个模拟实验里验证过当缓存容量到 10 万时时间戳方案里一次缺页替换要遍历 10 万条记录替换的延迟差不多是链表方案的 200 倍。如果你只是写课程作业或者验证算法行为时间戳方案可以。但只要你打算把这个 cache 放到真实业务的请求路径上这个 O(n) 的清扫动作早晚会变成一个热点延迟曲线会出现明显的锯齿。时间戳方案还有一个隐蔽的问题它只记录“最后访问时间”不记录“访问次序”。时间戳相同怎么办精度不够怎么办你会被迫用单调递增计数器而不是 wall clock然后陷入并发计数器的泥潭。链表方案天然不依赖时间精度它用的是相对顺序谁在链表头谁就在链表尾不需要比较时间这是它成为工业标准的根本原因。3. 把 LRU 应用到页面替换缺页率模拟器与容量参数3.1 页面替换发生的时机缺页中断、访问序列、驻留集LRU cache 实现清楚了但页面替换和缓存替换有一个关键差异缓存替换的容器是哈希表页面替换的容器是物理页帧而页帧的数量是系统启动时划定好的。比如一个进程的虚拟内存有 1 GB物理内存只给它分 256 MB 驻留集那么页表里只有 256 MB 对应的页帧是有效的。CPU 访问一个虚拟地址硬件先查 TLB再查页表如果页表项的有效位为 0说明这一页不在物理内存里CPU 会触发一个缺页中断把控制权交给操作系统。操作系统在缺页处理里做两件事从磁盘或文件系统读入缺失的页然后重新执行那条访问指令。如果当前驻留集已经满了处理缺页之前必须先选一个旧页淘汰。页替换算法就是在这个中断处理路径上运行的。所以衡量 LRU 在页面替换里的效果指标是缺页率访问序列里发生缺页的次数占总访问次数的比例。缺页率越低程序跑得越快因为一次缺页的代价是几十万次 CPU 周期的磁盘 I/O。下面我写一个和真实逻辑同构的模拟器它不模拟中断只模拟 LRU 的淘汰决策。3.2 用一个 Python 模拟器测量 LRU 缺页率class PageReplayer: def __init__(self, capacity): self.capacity capacity self.pages [] # 有序列表尾端是最久未使用 self.page_set set() # 驻留集 def access(self, page): if page in self.page_set: # 命中把 page 从列表中挪到最近使用端 self.pages.remove(page) self.pages.append(page) return True # 缺页 if len(self.page_set) self.capacity: victim self.pages.pop(0) # 最久未使用 self.page_set.remove(victim) self.pages.append(page) self.page_set.add(page) return False def simulate_lru(page_sequence, capacity): rp PageReplayer(capacity) misses 0 for page in page_sequence: if not rp.access(page): misses 1 return misses / len(page_sequence) seq [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] print(simulate_lru(seq, 3)) # 输出约 0.75 print(simulate_lru(seq, 4)) # 输出约 0.583这里的pages.remove(page)在频繁命中时是 O(n)真实实现里对应的是双向链表的 O(1) 摘节点。为什么模拟器里用列表足够因为我们只关心缺页率不关心延迟。不过你要记住真实内核不会用列表存页而是用链式结构或者数组加反向指针否则每次缺页处理末尾都要 O(n) 扫描这个代价直接叠加到中断耗时上。capacity在这个模拟器里就是驻留集大小。你可以用它回答一个很实际的问题给一个进程多少物理页合适。比如访问序列是循环扫描一个 100 页的文件backing store 读一遍要 4 KB 一页驻留集容量设为 50 时缺页率接近 50%——因为你永远在往前读新页旧页被一次次淘汰容量翻倍也没用。这个结论直接引出 5.2 节的扫描问题。我用这套模拟器跑了常见论文里的序列最终确认 LRU 在随机访问和循环访问上都表现一般真正强势的场景是“热点集中、且热点稳定”的工作负载。3.3 影响缺页率的三个参数容量、访问局部性、扫描区间现在把参数归拢一下这里不是理论空谈而是你在设计系统时要主动去调的三个旋钮。第一个是容量。容量和缺页率不是线性关系而是阶梯状。当你把热点集刚好完整放进容量时缺页率断崖式下降称为工作集阈值。你调 Redis 的maxmemory或者内核的vm.min_free_kbytes本质都是在这个曲线上找拐点。第二个是访问局部性。局部性越强LRU 的命中率越高局部性差的负载LRU 等价于随机替换。第三个是扫描区间。线性扫描一个比容量大好几十倍的序列LRU 会把整个 LRU 链冲刷一遍这个在 5.2 节细讲。你看到任何一个 LRU 项目参数调不好先按这三个旋钮排查不要动不动就重写替换算法。4. 近似 LRU 算法时钟算法与采样式 LRU 的取舍4.1 为什么严格 LRU 在真实系统里寸步难行前面我们用哈希表加双向链表给出了一个理论完美的 LRU它在 O(1) 时间里做出最正确的淘汰决定。但放到操作系统页面替换的实际环境里这个实现立刻遇到几个硬核障碍。第一个是中断路径的时间约束缺页中断处理必须在微秒级完成哈希表加链表在容量小的时候没问题但 Linux 的 page cache 有几十万页每次缺页去更新链表缓存命中和缓存未命中都在这段临界区里动态调整节点位置会带来显著的 Cache Miss 和锁竞争。第二个是页的“访问”信息获取方式CPU 访问一个页时硬件只修改页表项里的 accessed bit并不通知任何链表。你要把 accessed bit 变成“最近使用”排序必须定期扫描页表这个扫描本身就是一笔不小的开销。所以真实系统几乎不会把严格 LRU 当作直接实现。常见的做法是近似 LRU也就是用硬件和软件给的信息把“精确最近使用”放松成“很可能是最近使用”。最经典的近似就是时钟算法Clock Algorithm也叫 Second Chance。它把所有页放在一个环形链表里用一个指针遍历。每个页有一个访问位硬件在访问页时置 1。缺页时指针从当前位置出发如果访问位是 1就置 0 并给这个页一次“复活”机会——相当于给第二次机会如果访问位已经是 0就淘汰这一页。这个算法付出的代价极小得到的性能却和精确 LRU 非常接近所以成了 Linux、BSD 内核页面替换的默认或首选策略。下面给一个可运行的时钟算法实现。4.2 时钟算法实现一个指针、一个访问位、两次机会class ClockReplacer: def __init__(self, capacity): self.capacity capacity self.pages [] # 环形缓冲区元素是 [page, access_bit] self.clock_hand 0 self.page_index {} # page - 在 pages 里的下标 def access(self, page): if page in self.page_index: idx self.page_index[page] self.pages[idx][1] 1 # 访问位直接置 1不调整位置 return True # 缺页 if len(self.pages) self.capacity: self.pages.append([page, 1]) self.page_index[page] len(self.pages) - 1 else: while True: entry self.pages[self.clock_hand] if entry[1] 1: entry[1] 0 # 回收访问权下次再路过就淘汰 else: # 淘汰这个页 old_page entry[0] del self.page_index[old_page] entry[0] page entry[1] 1 self.page_index[page] self.clock_hand break self.clock_hand (self.clock_hand 1) % self.capacity self.clock_hand (self.clock_hand 1) % self.capacity return False这段实现里最核心的变量是clock_hand它记录当前扫描到环形缓冲区的位置。注意一个细节访问命中的页只是把访问位改成 1并不移动它在环里的位置——这是和严格 LRU 最本质的区别。严格 LRU 把节点移到链表头时钟算法只改一个 bit。当一个 access_bit 为 1 的页被指针路过时它不会被淘汰而是被降级成 access_bit 为 0相当于获得第二春。如果这个页被频繁访问它的 bit 持续被硬件置 1就可能永远活在环里这就是时钟算法在局部性好的负载上逼近 LRU 的原因。时钟算法有个必须注意的边界如果你把所有页都访问一遍指针转一圈把所有的 1 改成 0此时正好有缺页它就会强杀第一个 0。这个行为其实等价于 FIFO所以时钟算法在极端扫描负载下并不比 LRU 好它只是比 FIFO 多给热页一次机会。你在代码里怎么定clock_hand的初始位置我一般习惯是每个 CPU 一个独立时钟指针避免多个核扫同一个环造成锁竞争。但如果是单线程模拟一个全局指针就够了不需要为了省几个变量做一个微架构优化。4.3 Redis 为什么用采样 LRU 而不是严格 LRURedis 的缓存淘汰是很多人第一步接触 LRU 的地方网上文章满天飞但很少有人解释清楚一个事实Redis 的 LRU 从来就不是严格 LRU而是采样近似 LRU。你打开 redis.conf 能看到maxmemory-policy allkeys-lru和maxmemory-samples两个参数。maxmemory-samples默认是 5意思是每次淘汰时Redis 从所有 key 里随机抽 5 个 key把这 5 个里最久没访问的淘汰掉。为什么不做全局 LRU因为 Redis 的 key 数量可能上千万要维护一个全量的双向链表每访问一个 key 都要改链表这个开销会让单线程的 Redis 明显变慢。而采样 LRU 的数学基础是只要样本量够大随机采样得到的 max-idle key 和全局 max-idle key 非常接近。Redis 官方文档给过一个公式直观结果是当maxmemory-samples配置成 10 时近似度已经很接近严格 LRU只要不漏掉极端的长尾访问几乎看不出来差别。我在自己的实践里建议你把maxmemory-samples调成 10 而不是默认的 5代价是每次淘汰多扫几个 key但命中率通常能提升几个百分点。如果你的数据访问特别集中在少数 key 上5 就够了因为你本来就不会经常触发淘汰如果数据长尾很长、访问又分散就把样本数调大比如 15但不要调成 100那等于每次淘汰都花大量 CPU 去做全局扫描近似 LRU 的逻辑反而名存实亡。5. LRU 常见问题与避坑从哈希表扩容到扫描型访问5.1 把链表节点从自己身上摘下来再插回去操作顺序错了就丢节点现象我自己写 LRU 的 put 时最初写完的代码在重复 put 同一个 key 时偶尔出现访问不到这个 key 的情况查了十分钟找不到逻辑错误。原因在“删除旧节点并重新插到头部”这一段里我先把 node 从链表里摘下来再把它插入头部这两步顺序反了导致被插的节点 next/prev 指向了自己。解决先_remove_node(node)再_add_to_head(node)顺序不能换。这个坑非常低级但几乎每个手写链表的人都会踩一遍尤其是用两个哨兵节点时摘节点后头尾状态非常容易混乱。我的建议是加一个断言插入前校验 node.next 和 node.prev 都是 None或者在调试模式打印链表长度。5.2 扫描型访问会让 LRU 命中率瞬间归零现象系统里跑一个批量任务不断线性扫描一个大文件结果 LRU 缓存的命中率从常态的 95% 直接掉到接近 0%连带着数据库查询全部变慢。原因扫描型访问sequential read每次访问的都是“新页”这些新页会把缓存里原本的热数据全部挤出。LRU 按照最近访问时间排序扫描产生的大量新页不断占据链表头部把真正的热点全部推到尾部并被淘汰。解决看你的工作负载特征。如果是内核的 page cacheLinux 早已用“识别顺序读并专用预读缓冲”来解决如果这是你自己维护的应用层缓存最常见的对策是把淘汰策略改成 LRU-K 或者 LFU。LRU-K 的思路是每个页被访问了 K 次才进入 LRU 链扫描页只访问一两次永远进不了热度链这就能保护实际热点。如果不想改算法另一个低成本的替代方案是给缓存容量加一个保护头用 10% 的容量专门缓存长连接数据让它们永远不被扫描页挤掉。5.3 脏页必须单独处理LRU 别顺手承担持久化任务现象一个数据库进程把某个页改成脏页且一直没有回写这个页因为老被访问一直站在 LRU 链头部被反复保留结果发生掉电时丢失的数据量远大于预期。原因LRU 只管“冷热”不管“脏净”。一个页是热的不代表它在磁盘上就是最新的如果热页脏的数据一直不落盘它在缓存里待得越久崩溃时的风险就越大。解决任何 LRU 缓存系统里需要把脏页回写调度和 LRU 淘汰解耦。常见的做法是后台线程周期性地把“超过某阈值时间未写”的脏页回写或者使用fdatasync强制落盘。在 Linux 内核里pdflush / writeback 机制就是独立于 LRU 的它不会因为页在 LRU 尾部就给脏页判死刑而是优先刷脏页年龄大的。你在设计自己的缓存写回策略时至少要在 LRU 节点里加一个 dirty 标记并且在淘汰时如果标记为脏必须触发异步写盘后再淘汰否则等比例回收物理内存时选择脏页会让整个文件系统卡在刷盘上。5.4 并发场景误用全局锁吞吐跌到单线程还更慢现象把上文的 LRUCache 原封不动放进多线程服务用一把threading.Lock把 get 和 put 全部锁上结果是压测时吞吐量只有单核下的 30%。原因get 和 put 内部操作的是链表和哈希表全局锁让所有线程串行化而且还引入了频繁的锁切换实际上比单线程慢。解决如果你只需要过一个“学术”的坎用 Python 的functools.lru_cache它内部就是线程安全的。真正做高并发 LRU 时我通常会分段加锁哈希表按 key 的哈希值分成 N 个段每个段独立锁链表不设全局锁对每个节点用无锁的 CAS 更新链表链接。内存开销大一些但伸缩性远好过整锁。另一个更常用的行业方案是牺牲一点精度、换取极大并发让线程在 get 时不更新链表只在后台以固定时间窗口统一刷访问顺序。这种“半 LRU”在很多数据库缓冲池里是标准做法。5.5 用 Python 或 Lua 写原型容量一大就慢到没法用现象原型阶段用 List 作为 LRU 队列每次命中都list.remove(elem)在容量 5 万以下没问题容量 100 万时 benchmark 显示单次命中耗时 50 毫秒。原因list.remove是 O(n) 的老老实实的扫描比对。解决切记Python 里要实现 LRU 别自己造链表除了小容量直接用collections.OrderedDict。它是官方维护的双向链表加哈希表move_to_end 是 O(1)比你自己写的 C 层级实现更可靠。这个不是偷懒是避免低水平重复劳动。你写文章、写方案、做技术预研时OrderedDict足够能证明 LRU 的算法性能不必把手写链表那份纯 C 实现提前搬出来。内核或上层组件里真正手写 LRU 链表的地方基本都在严格的实时路径上不在你用来做 demo 的代码里。6. 给你的 LRU 实现“打分”用三个测试序列验证它在真负载上的行为6.1 手写 LRU 后如何自测三大测试序列写完 LRU 之后别急着说自己完成了先跑这三个序列验证。第一个是纯热区序列一个集合里的页反复访问容量刚好覆盖这个集合缺页率应该降为 0容量小于集合大小时缺页率应该稳定在某个固定值。第二个是循环扫描序列访问顺序是 1,2,3,...,N,1,2,3,...N 远大于容量此时 LRU 的缺页率应该接近 100%这时你要观察时钟算法是不是也一样差。第三个是最坏交替序列比如容量为 2访问序列是 1,2,3,1,2,3,...理论上 LRU 每次都会缺页看你的代码会不会因为哈希表里的旧页残影得到错误结果。这些序列不用很多代码写几十行就够但能暴露绝大多数实现 bug。我当初就是被第三个序列抓到一个列表下标溢出的问题。6.2 从缺页率到工程决策什么情况下你该放弃 LRU当你按上面方法得出缺页率曲线后下一步不是“将就用”而是果断做决策。如果缺页率在容量增大到工作集大小时仍未下降你的数据很可能是随机访问或者扫描型的LRU 根本不是你的菜。这时我会优先考虑 LFU最不常用优先淘汰或者干脆用自适应替换缓存ARC做动态平衡。判断标准就一个热点是否稳定。热点稳定就用 LFU热点漂移快就用 LRU两者都提不上来就换 ARC 并调它的两个自适应参数。这个决策点我建议你在项目一开始就画好别上线后再回头。一次真正让我受益的习惯是先做一个如上文描述的最小模拟器拿真实访问日志跑一遍再决定要不要引入重型 LRU 数据结构。一个干净的模拟器半小时就能回答这个方向值不值得投入它每年都能帮你省下一个月的返工时间。希望这个思路对你有用。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
