15｜LRU：在虚拟内存中页面是如何置换的？
黄清昊
该思维导图由 AI 生成，仅供参考
你好，我是微扰君。
今天我们继续讲解操作系统中另一个常用的算法， LRU 算法（Least recently used），也就是最近最少使用页面置换算法。这是操作系统中常用的内存置换策略之一，在内存有限的情况下，需要有一种策略帮助我们把此刻要用到的外存中的数据置换到内存里。该算法也同样适用于许多类似的缓存淘汰场景，比如数据库缓存页置换、Redis 缓存置换等。
在开始讲解 LRU 算法本身之前，我们先来了解一下这个算法在操作系统中到底解决了什么问题。
操作系统的缓存淘汰
我们知道，计算机是建立在物理世界上的，底层的存储计算需要依赖许多复杂的硬件：比如内存、磁盘、纷繁的逻辑电路等。所以操作系统的一大作用就是，通过虚拟和抽象为应用开发者提供了一套操作硬件的统一接口，而分页机制的发明，就是为了不需要让用户过度操心物理内存的管理和容量。
通过虚拟内存和分页机制，用户可以在一个大而连续的逻辑地址和非连续的物理地址之间，建立起映射。其中，物理地址既可以真的指向物理内存，也可以指向硬盘或者其他可以被寻址的外部存储介质。
用户的程序可以使用比物理内存容量大得多的连续地址空间；而计算机在运行程序的时候，也不再需要把进程所有信息都加载到内存里，只加载几个当前需要的页就可以了。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
LRU算法（Least Recently Used）是操作系统中常用的内存置换策略之一，也适用于缓存淘汰场景。该算法通过置换最久未被访问的数据页，充分利用数据的时间局部性，以提高缓存命中率。相比于其他置换算法，LRU在内存管理上表现更为出色。文章还介绍了最优页面置换算法，但指出其只是理论上的存在，无法实际应用。通过对不同页面置换算法的比较，强调了LRU算法的优越性。文章通过具体例子和图示，生动地展示了不同页面置换算法的效果，帮助读者更好地理解各种策略的优劣。此外，文章还提供了LRU算法的实现思路和代码示例，深入浅出地解释了LRU算法的原理和实现方式。总之，本文通过深入浅出的方式介绍了LRU算法的概念、原理和实现，适合读者快速了解页面置换算法的核心内容。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《业务开发算法 50 讲》，新⼈⾸单¥59
《业务开发算法 50 讲》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(4)
- 最新
- 精选
- Paul ShanLRU需要把中间的节点移动到头部，并且要删除尾部节点，单链表对这两个操作都需要O(n),双链表可以用O(1)完成。LRU组合了哈希表和双向链表各自的强项，因而提供了快速的查询和灵活的资源管理两项功能。
作者回复: 说的很对～
2022-01-133 
liuchao90h其实严格来讲，因为用到了双向链表，所以最差时间复杂度应该是O(n)才对吧？虽然示例代码用了语言自带的包装，但不能忽视本身内部的损耗吧？再有就是作者无无语界确实博才，但对读者却走着更高的理解要求，虽然能猜出各语言大概含义，但阅读起来还是吃力些2022-05-1111
拓山维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。 1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。 2. 如果此数据没有在缓存链表中，又可以分为两种情况：如果此时缓存未满，则将此结点直接插入到链表的头部；如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。2023-08-10归属地：浙江
西门吹牛双向链表，插入删除更灵活，单向链表需要在遍历的过程中记录当前节点的前驱节点，然后前驱节点指直接next后继节点执行删除，双向链表直接找到删除的节点 node，直接 node.pre.next = node.next，node.next.pre = node.pre2022-01-22
收起评论
