编辑“︁页面置换算法”︁（章节）

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

=== 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（避免历史积累权重过高）。