页面置换算法

📚 这是操作系统中 虚拟内存管理 的核心内容之一，用于页面置换时选择“淘汰哪一页”。

---

✅ 为什么需要页面置换算法？

• 操作系统给每个进程分配的物理内存页（Frame）是有限的
• 当一个进程访问了不在内存的虚拟页（Page Fault）
• 系统要将某个已在内存的页“换出去”，把新页加载进来
• 换出去哪个页？→ 页面置换算法决定

---

📌 常见页面置换算法一览表

算法名称	全称	核心思想	特点
FIFO	先进先出	最早进入内存的页被淘汰	简单但容易犯傻（Belady异常）
LRU	最近最少使用	淘汰最长时间没被访问的页	比较优秀，符合人类逻辑
OPT	最佳置换算法	淘汰未来最长时间不访问的页	理论最优，只能模拟，不可实现
CLOCK	时钟算法	模拟 LRU，带引用位	实际系统中常用
LFU	最不经常使用	淘汰被使用次数最少的页	受冷启动影响，复杂度高
Random	随机	随机淘汰一页	实现简单，性能不一定差

---

🔍 逐个讲解（附示意）

---

1️⃣ FIFO（First-In-First-Out）

谁最早进内存，谁最早出

• 用队列实现，入队时加入末尾，换出时从队头出队
• 优点：实现简单
• 缺点：可能淘汰刚刚还在频繁用的页（Belady 异常）

---

2️⃣ LRU（Least Recently Used）

淘汰“最近最少使用”的页面

• 假设“过去很久没用”的页面“将来也不太会用”
• 实现方式：
  • 用链表或栈保存访问顺序
  • 或用访问时间戳
• 优点：性能较好，符合程序访问局部性
• 缺点：实现复杂（需要记录时间）

---

3️⃣ OPT（Optimal Algorithm）

淘汰“未来最长时间不访问”的页

• 理论最优算法，但实际无法预知未来
• 只能用于分析、比较其他算法的效果

---

4️⃣ CLOCK（时钟算法）🕒

模拟 LRU，但成本更低，适合实现

• 每个页有一个引用位（R）
• 页表构成一个“时钟”环形结构
• 每次淘汰：
  • 看当前页的 R 位
    • 若为 0 → 淘汰
    • 若为 1 → 清 0，指针转到下一个
• 优点：效率好、实现简单、效果接近 LRU
• 是现实系统（Linux）最常用的页面置换算法之一

---

5️⃣ LFU（Least Frequently Used）

淘汰使用频率最低的页面

• 每个页维护访问计数器
• 问题：某些曾经很活跃但现在不用的页，也不容易被淘汰（不灵活）

---

6️⃣ Random（随机淘汰）

随机选一个页换出去

• 实现极其简单，居然在某些场景下还挺有效 😂
• 常用于嵌入式或硬件缓存页替换

---

📈 举个例子：3页内存，页面访问顺序如下：

访问顺序：7, 0, 1, 2, 0, 3, 0, 4

你可以用不同算法模拟：

• FIFO 会换出 7, 0, 1…
• LRU 会根据最近使用情况做选择
• OPT 会“看到”后面谁最久不被访问…

📌 可以写个表格或者画个图来清晰展示！

---

✅ 总结对比（重点面试问）

算法	性能	实用性	复杂度
FIFO	中下	✅ 简单，入门常考	低
LRU	高	❌ 难实现硬件支持	中高
OPT	最优	❌ 不可实现，仅分析用	高
CLOCK	接近 LRU	✅ 常用于实际系统	中
LFU	受限	❌ 不常用	高
Random	视场景	✅ 非常轻量	极低

---

🧠 面试金句总结：

页面置换算法用于决定内存不够时淘汰哪一页。常见算法包括 FIFO、LRU、CLOCK、OPT 等。其中 CLOCK 是实际系统中常用的，因为它在效率和实现复杂度之间取得了良好平衡。

---

✅ 要不要我画一张图，展示 CLOCK 算法如何转圈扫描、标记引用位，或者一个 LRU/FIFO 对比图例？可视化真的一看就懂 📊