[!info] related notes 操作系统 MOC 页面置换算法（OPT/FIFO/LRU/Clock） 内存管理

页面置换：LRU（最近最久未使用）

一句话

缺页且页框已满时，淘汰”过去最长时间没有被访问”的那一页。

手算规则

• 命中：把该页标记为”最新访问”
• 缺页且未满：装入，并标记为”最新访问”
• 缺页且已满：
  • 在当前页框里找”最久未被访问”的页淘汰
  • 装入新页并标记为”最新访问”

手算时建议你给每页维护一个”上次访问时刻”。

实现方式

1. 链表 + 哈希表（精确 LRU）

• 双向链表维护访问顺序，最近访问的在头部。
• 哈希表存储 page -> 链表节点 的映射，实现 $O(1)$ 查找。
• 访问时：将节点移到头部 $O(1)$。
• 淘汰时：删除尾部节点 $O(1)$。

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # 标记为最近使用
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # 淘汰最久未用

2. 计数器（Counter）

每次访问递增全局计数器，记录每页上次访问的时刻。淘汰时找计数最小的页。

• 查找最久未用：$O(n)$ 扫描所有页框。
• 适合手算和考试，不适合实际实现。

3. 栈

每次访问将该页移到栈顶。栈底即为最久未用页。

• 移动操作需要 $O(n)$（找到元素并移动）。
• 概念清晰，常用于考试说明。

4. 近似实现（实际系统常用）

精确 LRU 每次内存访问都要更新元数据，开销过大。实际系统使用近似方案：

• Clock / Second Chance：维护环形链表 + 引用位。扫描时引用位为 1 则清零并跳过，为 0 则淘汰。近似 LRU，开销 $O(1)$ 摊销。
• NFU（Not Frequently Used）：为每个页维护访问计数器，定期衰减。

Belady 异常

增加页框数反而导致缺页率上升的现象。

• FIFO：会出现 Belady 异常。例：引用串 1,2,3,4,1,2,5,1,2,3,4,5，3 个页框缺 9 次，4 个页框缺 10 次。
• LRU / OPT：不会出现 Belady 异常（已证明具有栈性质）。

LRU vs FIFO vs OPT 对比

算法	策略	最优性	实现成本	Belady 异常
OPT	淘汰将来最久不用的页	理论最优	不可实现（需预知未来）	无
FIFO	淘汰最早进入的页	一般	低（队列）	有
LRU	淘汰最久未访问的页	接近 OPT	高（需维护访问顺序）	无

工作集模型（Working Set Model）

工作集 $W(t, \Delta)$ = 在时刻 $t$ 前的 $\Delta$ 次内存引用中访问过的页面集合。

• $\Delta$ 是窗口大小，反映程序的局部性。
• 若进程的工作集全部在内存中，不会缺页。
• OS 可以跟踪每个进程的工作集大小，决定是否给该进程分配更多页框或将其挂起（swap out）。

相关笔记

• 页面置换算法（OPT/FIFO/LRU/Clock）
• 内存管理
• 操作系统 MOC