编辑“︁页面置换算法”︁

{{Note|本条目讲解操作系统中'''页面置换算法'''的核心原理、实现方式及实际应用场景，适合从初学者到高级开发者的学习需求。}}

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

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

== 常见算法及实现 ==
以下介绍五种经典算法，按复杂度递增排列。

=== 1. 先进先出（FIFO） ===
{{Main|先进先出算法}}
'''原理'''：选择最早进入内存的页面置换。
* '''优点'''：实现简单（使用队列数据结构）。
* '''缺点'''：可能置换频繁使用的页面（'''Belady异常'''：分配更多物理页框时缺页率反而升高）。

==== 代码示例 ====
<syntaxhighlight lang="python">
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)
</syntaxhighlight>
{{Output|
Page 1 loaded. Pages in memory: [1]
Page 2 loaded. Pages in memory: [1, 2]
Page 3 loaded. Pages in memory: [1, 2, 3]
Page 4 loaded. Pages in memory: [2, 3, 4]
Page 1 loaded. Pages in memory: [3, 4, 1]
Page 5 loaded. Pages in memory: [4, 1, 5]
}}

=== 2. 最近最少使用（LRU） ===
{{Main|最近最少使用算法}}
'''原理'''：选择最长时间未被访问的页面置换。
* '''实现方式'''：时间戳或计数器（硬件支持） / 近似算法（如Clock）。

==== 代码示例 ====
<syntaxhighlight lang="python">
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)
</syntaxhighlight>
{{Output|
Page 1 loaded. Order: [1]
Page 2 loaded. Order: [1, 2]
Page 3 loaded. Order: [1, 2, 3]
Page 4 loaded. Order: [2, 3, 4]
Page 2 accessed. Order: [3, 4, 2]
Page 1 loaded. Order: [4, 2, 1]
Page 5 loaded. Order: [2, 1, 5]
}}

=== 3. 时钟算法（Clock） ===
'''原理'''：LRU的近似实现，使用环形链表和引用位（又称'''二次机会算法'''）。
* '''步骤'''：
  # 遍历页面帧，检查引用位。
  # 若为0则置换，若为1则置0并跳过。

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

=== 4. 最优置换（OPT） ===
'''原理'''：置换未来最长时间不会被访问的页面（理论最优但不可实现，仅用于对比研究）。
* '''数学表达'''：选择满足 <math>\max(t_i)</math> 的页面，其中 <math>t_i</math> 是第i页的下次访问时间。

=== 5. 最不经常使用（LFU） ===
'''原理'''：统计历史访问频率，置换使用次数最少的页面。
* '''变体'''：带老化的LFU（避免历史积累权重过高）。

== 算法对比 ==
{| class="wikitable"
|+ 性能与特性对比
! 算法 !! 实现复杂度 !! 需要硬件支持 !! 是否可避免Belady异常
|-
| FIFO || 低 || 否 || 否
|-
| LRU || 中 || 需要引用位 || 是
|-
| Clock || 中 || 需要引用位 || 是
|-
| OPT || 高（需预知未来） || 不可实现 || 是
|-
| LFU || 高 || 需要计数器 || 是
|}

== 实际应用案例 ==
=== 数据库缓冲池 ===
{{Example|MySQL的InnoDB引擎使用改进的LRU算法管理缓冲池：
* 将LRU链表分为'''young'''和'''old'''两个子列表
* 新页面先插入old区域，只有被二次访问才移至young区域
* 目的：避免全表扫描污染缓冲池
}}

=== 操作系统实践 ===
* Linux内核使用'''CLOCK改进算法'''（考虑页面活跃状态）。
* Windows NT采用'''工作集模型'''结合局部置换。

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

== 参见 ==
* [[虚拟内存]]
* [[缺页中断]]
* [[工作集模型]]

{{Stub|algorithm}}

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:操作系统]]