页面置换算法

请求分页系统发生缺页故障后，如果主存中还有空闲页框，直接把缺失页面调入即可；如果没有空闲页框，就必须从某个驻留集中选一页换出。页面置换算法解决的就是“换出哪一页”。

页面换入、换出都需要外存 I/O，代价远大于普通访存。因此，好的置换算法应尽量减少缺页次数，尤其要避免把很快又会访问的页面换出。

Note

FIFO、LRU、Random 的基本思想在 另一处 中已经出现过。这里重点看它们在页框、缺页故障、访问位、修改位中的执行过程。

# 基本指标

设页面访问序列长度为 $N$。

指标 含义
缺页次数 访问页面不在主存的次数
置换次数 缺页且没有空闲页框，需要换出旧页的次数
缺页率 $\text{缺页次数}/N$

缺页不一定发生置换。开始时页框可能为空，此时缺页只是调入页面；只有页框已满后再缺页，才需要置换。

Example

3 个页框初始为空，访问 7, 0, 1 会连续缺页 3 次，但没有发生页面置换，因为每次都有空闲页框。

OPT

最佳置换算法 OPT 每次淘汰以后最长时间内不会再被访问的页面；若某页以后不再访问，则优先淘汰它。

OPT 可以得到最低缺页率。但实际系统无法提前知道未来页面访问序列，所以它不是真实算法实现，只是作为比较其他算法优劣的理论基准。

Example

访问串 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1，分配 3 个页框，OPT 缺页 9 次，置换 6 次，缺页率为：

$$
\frac{9}{20}=45%
$$

# FIFO

FIFO 每次淘汰最早进入主存的页面。页面命中时，不改变进入队列顺序。

FIFO 实现简单，但它完全不关心页面最近是否被访问过。一个很早调入、但现在仍然频繁使用的页面，也可能因为“最早进入”而被淘汰。

Belady 异常

通常直觉会认为：给进程分配的页框数越多，缺页次数不应增加。但 FIFO 可能出现反例：页框数增大，缺页次数反而增加，这称为 Belady 异常。

Example

访问串 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4，采用 FIFO：

页框数 缺页次数
3 9
4 10

增加页框后缺页次数反而从 9 增加到 10，这就是 Belady 异常。

Belady 异常与 FIFO 算法关系
  • 该异常只在 FIFO 情况下发生。
  • 采用 FIFO 算法时，给进程分配的页框数越多，缺页次数可能会增加，但不是一定会增加
# LRU

LRU 每次淘汰最近最长时间未被访问的页面。它比 FIFO 更符合时间局部性：最近访问过的页面，短期内更可能再次访问。

LRU 的问题是实现代价高。系统需要知道各页面最近访问次序，常见方式包括：

  • 用访问字段记录页面自上次访问以来经过的时间。
  • 用栈或链表维护最近访问顺序。
  • 用硬件支持的访问位近似实现。

精确 LRU 通常需要较高硬件或软件开销，因此真实系统中常用 CLOCK 这类近似算法。

CLOCK

CLOCK 又称最近未用算法 NRU，是 LRU 的低成本近似。

基本做法：

  1. 给每个页框设置访问位 R。
  2. 页面被访问时，硬件把 R 置为 1。
  3. 所有页框按环形队列组织，设置一个扫描指针。
  4. 需要置换时，从指针位置开始检查。
  5. 若 R=0，选择该页换出。
  6. 若 R=1，把 R 置为 0，指针后移，继续扫描。

CLOCK 的含义是：访问位为 1 的页面刚被访问过，先给它一次“第二次机会”；如果之后没有再被访问，下一轮扫描时它的访问位仍为 0，就可能被换出。

改进型 CLOCK

简单 CLOCK 只考虑访问位，没有考虑页面是否被修改。若换出修改过的页面，需要写回外存；未修改页面可直接丢弃，因为外存已有正确副本。

改进型 CLOCK 同时考虑：

位 含义
访问位 R 最近是否被访问
修改位 M 调入主存后是否被写过

淘汰优先级：

优先级 状态 含义
1 (0, 0) 最近未访问，且未修改，最好淘汰
2 (0, 1) 最近未访问，但修改过，淘汰前要写回
3 (1, 0) 最近访问过，未修改
4 (1, 1) 最近访问过，且修改过，最不适合淘汰

也就是$RM$表示的二进制数由小到大。

常见扫描过程：

  1. 第一轮寻找 (0, 0)，不修改访问位。
  2. 第二轮寻找 (0, 1)，并把扫描过页面的访问位置为 0。
  3. 第三轮寻找 (0, 0)。
  4. 第四轮寻找 (0, 1)。

经过第二轮后，扫描过的页面访问位都被清 0，因此第三、第四轮一定能选出可淘汰页面。

总览

算法 淘汰依据 特点
OPT 未来最长时间不再访问 理论最优，无法实现
FIFO 最早进入主存 实现简单，可能出现 Belady 异常
LRU 最近最长时间未访问 性能较好，但精确实现代价高
CLOCK 访问位为 0 的页面 近似 LRU，开销较低
改进型 CLOCK 访问位 + 修改位 优先减少写回 I/O