简介：一份针对LRU（Least 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 API：get/put 背后的两个动作
LRU 落到工程上，通常不是你直接操作页面帧，而是封装成一个 cache 对象，对外只暴露 get 和 put 两个接口。你从“页面替换”的角度去看这两个接口，会发现它们是对内存操作的抽象：get(key) 相当于 CPU 访问了某个虚拟页，带来了这一次访问；put(key, value) 相当于把一个页装入内存，如果内存已经满了，put 的内部就必须先完成一次页面替换。
所以判断一个 LRU 实现好不好的标准也很简单：get 命中一个已有页，这个页要被标记成“最近使用”；get 没命中，这是缺页；put 一个新页，如果容量已满，就把最久没用的那个页淘汰掉。这三个动作看着简单，但有一个硬性指标：每个动作平均复杂度最好是 O(1)。为什么必须是 O(1)？因为缓存是访问热路径，每多一次 O(n) 遍历，缺页没等到，性能就先崩了。下面这段代码就是按这个指标来的标准实现。
2.2 用双向链表加哈希表实现 LRU：O(1) 的 get 与 put
class DLinkedNode: __slots__ = ('key', 'value', 'prev', 'next') def __init__(self, key=0, value=0): 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 而不是严格 LRU
Redis 的缓存淘汰是很多人第一步接触 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 cache，Linux 早已用“识别顺序读并专用预读缓冲”来解决；如果这是你自己维护的应用层缓存，最常见的对策是把淘汰策略改成 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 数据结构。一个干净的模拟器，半小时就能回答这个方向值不值得投入，它每年都能帮你省下一个月的返工时间。希望这个思路对你有用。
本文还有配套的精品资源，点击获取
