页面置换算法

概述

页面置换算法（Page Replacement Algorithm）是操作系统中虚拟内存管理的核心机制，用于在物理内存不足时决定哪些页面应被换出到磁盘。当进程访问的页面不在内存中（即发生缺页中断）时，系统需选择一个内存页面置换出去，以便装入新页面。算法的选择直接影响系统性能，低效的算法可能导致频繁的磁盘I/O（称为抖动现象）。

核心问题

• 目标：最小化缺页中断次数。
• 约束条件：未来页面访问序列不可预知（除理想算法外），需依赖局部性原理设计启发式策略。

常见算法及实现

以下介绍五种经典算法，按复杂度递增排列。

1. 先进先出（FIFO）

Main article: 先进先出算法

原理：选择最早进入内存的页面置换。

• 优点：实现简单（使用队列数据结构）。
• 缺点：可能置换频繁使用的页面（Belady异常：分配更多物理页框时缺页率反而升高）。

代码示例

from collections import deque

class FIFO:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = deque()
        self.pages = set()

    def access_page(self, page):
        if page not in self.pages:
            if len(self.queue) == self.capacity:
                removed = self.queue.popleft()
                self.pages.remove(removed)
            self.queue.append(page)
            self.pages.add(page)
            print(f"Page {page} loaded. Pages in memory: {list(self.queue)}")
        else:
            print(f"Page {page} already in memory.")

# 示例运行
fifo = FIFO(3)
for p in [1, 2, 3, 4, 1, 5]:
    fifo.access_page(p)

2. 最近最少使用（LRU）

Main article: 最近最少使用算法

原理：选择最长时间未被访问的页面置换。

• 实现方式：时间戳或计数器（硬件支持） / 近似算法（如Clock）。

代码示例

from collections import OrderedDict

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

    def access_page(self, page):
        if page in self.cache:
            self.cache.move_to_end(page)
            print(f"Page {page} accessed. Order: {list(self.cache.keys())}")
        else:
            if len(self.cache) == self.capacity:
                removed = self.cache.popitem(last=False)
                print(f"Page {removed[0]} evicted.")
            self.cache[page] = None
            print(f"Page {page} loaded. Order: {list(self.cache.keys())}")

# 示例运行
lru = LRU(3)
for p in [1, 2, 3, 4, 2, 1, 5]:
    lru.access_page(p)

3. 时钟算法（Clock）

原理：LRU的近似实现，使用环形链表和引用位（又称二次机会算法）。

• 步骤：

 # 遍历页面帧，检查引用位。
 # 若为0则置换，若为1则置0并跳过。

graph LR A[开始扫描] --> B{引用位=1?} B -->|是| C[置0并跳过] B -->|否| D[置换该页] C --> E[继续扫描] D --> F[结束]

4. 最优置换（OPT）

原理：置换未来最长时间不会被访问的页面（理论最优但不可实现，仅用于对比研究）。

• 数学表达：选择满足 $\max (t_i)$ 的页面，其中 $t_i$ 是第i页的下次访问时间。

5. 最不经常使用（LFU）

原理：统计历史访问频率，置换使用次数最少的页面。

• 变体：带老化的LFU（避免历史积累权重过高）。

算法对比

性能与特性对比

算法	实现复杂度	需要硬件支持	是否可避免Belady异常
FIFO	低	否	否
LRU	中	需要引用位	是
Clock	中	需要引用位	是
OPT	高（需预知未来）	不可实现	是
LFU	高	需要计数器	是

实际应用案例

操作系统实践

• Linux内核使用CLOCK改进算法（考虑页面活跃状态）。
• Windows NT采用工作集模型结合局部置换。

练习问题

1. 给定引用串 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 和3个页框，计算FIFO和LRU的缺页次数。
2. 为什么LRU算法需要硬件支持？软件实现可能有什么缺陷？
3. 设计一个混合算法，结合LFU和LRU的优点。

参见

• 虚拟内存
• 缺页中断
• 工作集模型