操作系统页面置换： 最近最少使用算法（LRU）
操作系统页面置换算法
概念
最近最少使用（LRU，Least Recently Used）算法是一种页面置换算法，用于管理操作系统中的虚拟内存。它的核心思想是当需要进行页面置换时，选择最长时间未被访问的页面进行替换。这种策略基于“局部性原理”，即最近被访问的页面在未来被访问的概率较高。
工作原理
LRU算法通过维护一个记录页面访问历史的列表来实现，最近被访问的页面放在列表的前端，而最久未被访问的页面放在列表的末尾。当发生页面缺失且需要加载新页面时，算法将列表末尾的页面（即最久未被访问的页面）从内存中移除，并将新页面加载到内存中，同时更新该页面在列表中的位置。
实现方式
-
链表：一个常见的实现方式是使用双向链表。链表的头部表示最近被访问的页面，尾部表示最久未被访问的页面。每次页面被访问时，如果该页面已在链表中，则将其移动到链表头部；如果页面不在链表中，则将其添加到链表头部，如果内存已满，则从链表尾部移除一个页面。
-
哈希表+双向链表：为了优化查找效率，可以使用哈希表存储每个页面在链表中的位置，这样可以在O(1)时间内判断一个页面是否在内存中，并能快速访问链表中的任何一个页面。
示例
假设内存可以容纳3个页面，页面请求序列为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。
- 请求页面1，内存空，加载页面1到内存。内存状态：[1]
- 请求页面2，内存未满，加载页面2到内存。内存状态：[2, 1]
- 请求页面3，内存未满，加载页面3到内存。内存状态：[3, 2, 1]
- 请求页面4，内存已满，按LRU置换页面1，加载页面4到内存。内存状态：[4, 3, 2]
- 请求页面1，内存已满，按LRU置换页面2，加载页面1到内存。内存状态：[1, 4, 3]
- 请求页面2，内存已满，按LRU置换页面3，加载页面2到内存。内存状态：[2, 1, 4]
- 以此类推…
优点
- 性能较好：LRU算法能较好地利用局部性原理，减少页面缺失率。
- 实现直观：算法的策略直观易懂，符合常理。
缺点
- 实现复杂度：相比FIFO等算法，LRU的实现复杂度较高，尤其是在不使用额外数据结构的情况下。
- 运行开销：在没有优化的情况下，每次页面访问都可能需要更新链表，导致额外的运行开销。
LRU算法是一种广泛使用的页面置换算法，特别适用于访问模式具有明显局部性的应用场景。
图示
最近最少使用（LRU）算法的实现通常是通过维护一个记录页面访问顺序的数据结构，如链表。在这个链表中，最近被访问的页面会被放到链表的头部，而最久未被访问的页面会被放到链表的尾部。当需要进行页面置换时，链表尾部的页面（即最久未被访问的页面）会被替换。
为了更清晰地展示LRU算法的过程，我们将通过一个具体的例子，页面请求序列为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。假设内存可以容纳3个页面。
初始状态（所有页面帧为空）
链表状态：空
页面请求序列开始
- 请求页面1，内存空，加载页面1到内存，页面1移动到链表头部。
链表状态：1
- 请求页面2，内存未满，加载页面2到内存，页面2移动到链表头部。
链表状态：2 -> 1
- 请求页面3，内存未满，加载页面3到内存，页面3移动到链表头部。
链表状态：3 -> 2 -> 1
- 请求页面4，内存已满，按LRU置换页面1（链表尾部的页面），加载页面4到内存，页面4移动到链表头部。
链表状态：4 -> 3 -> 2
- 请求页面1，内存已满，按LRU置换页面2（现在链表尾部的页面），加载页面1到内存，页面1移动到链表头部。
链表状态：1 -> 4 -> 3
- 请求页面2，内存已满，按LRU置换页面3（现在链表尾部的页面），加载页面2到内存，页面2移动到链表头部。
链表状态：2 -> 1 -> 4
- 请求页面5，内存已满，按LRU置换页面4（现在链表尾部的页面），加载页面5到内存，页面5移动到链表头部。
链表状态：5 -> 2 -> 1
- 请求页面1，页面1已在内存中，根据LRU，将页面1移动到链表头部。
链表状态：1 -> 5 -> 2
- 请求页面2，页面2已在内存中，根据LRU，将页面2移动到链表头部。
链表状态：2 -> 1 -> 5
- 请求页面3，内存已满，按LRU置换页面5（现在链表尾部的页面），加载页面3到内存，页面3移动到链表头部。
链表状态：3 -> 2 -> 1
通过这个过程，我们可以看到LRU算法如何通过维护一个链表来记录页面的访问顺序，确保最久未被访问的页面被首先替换。这种方法更好地利用了局部性原理，通常能减少页面缺失率，但实现相对复杂，需要额外的数据结构来记录访问历史。