内存分页替换模拟 - FIFO/LRU/OPT动画

页面置换算法是操作系统内存管理中的核心机制。当进程请求的页面不在物理内存中（发生缺页中断），且内存已满时，操作系统需要选择一个已有的页面将其换出到磁盘，以便腾出空间加载新页面。这个选择策略就是页面置换算法。常见算法包括FIFO（先进先出）、LRU（最近最少使用）、OPT（最佳置换）、Clock（时钟算法）等。好的置换算法能显著降低缺页率，提升系统性能。

FIFO按页面进入内存的时间顺序进行置换，最早进入的页面最先被换出。实现简单，只需维护一个队列。
优点：实现开销极低，只需要一个循环指针。
缺点：可能发生Belady异常——增加物理块数反而导致缺页率上升。因为FIFO不考虑页面的使用频率，可能将频繁访问的页面换出。
适用场景：对实现复杂度要求极低的嵌入式系统或简单场景。

LRU基于"局部性原理"——最近被访问过的页面在未来更可能被再次访问。当需要置换时，选择最长时间未被访问的页面。
优点：性能接近OPT，能较好地利用时间局部性，不会发生Belady异常。
缺点：纯硬件实现成本高（需要记录访问时间戳或维护访问栈），软件模拟开销也较大。
实现方式：计数器法（每个页面维护时间戳）、栈法（维护访问顺序栈）、近似LRU（如Clock算法）。

OPT（Optimal Page Replacement）是一种理论上的最优算法。当需要置换页面时，它选择在未来最长时间内不会被访问的页面进行换出。如果某个页面永远不会再被访问，则优先选择它。
为什么最优：因为它拥有"预知未来"的能力，能做出理论上缺页次数最少的选择。
局限性：实际系统中无法预知未来的页面访问序列，因此OPT无法实现。它的主要价值是作为理论基准，用于衡量其他算法的性能差距。

Belady异常是指在使用FIFO页面置换算法时，增加物理块数（帧数）反而导致缺页次数增加的异常现象。这违背了"更多内存应该带来更好性能"的直觉。
例如，对于序列 1,2,3,4,1,2,5,1,2,3,4,5：3帧时缺页9次，而4帧时缺页10次。
LRU和OPT算法不会发生Belady异常，因为它们属于栈算法（Stack Algorithm），具有包含性——n帧时的内存内容总是n+1帧时内存内容的子集。

缺页率 = 缺页次数 ÷ 总访问次数 × 100%
缺页率越低，表示页面置换算法性能越好。通常：
• 缺页率 < 5%：性能优秀
• 缺页率 5%-15%：可接受
• 缺页率 > 15%：可能需要优化（增加内存、改进算法）
实际系统中，缺页率受工作集大小、访问模式、物理内存容量和置换算法共同影响。

算法	实现难度	性能	Belady异常	实际应用
FIFO	极低	较差	❌ 可能发生	简单嵌入式系统
LRU	中等	良好	✅ 不会发生	数据库缓存、Web缓存
OPT	无法实现	最优（理论）	✅ 不会发生	性能评估基准
Clock	较低	较好	✅ 不会发生	现代OS（Linux、Windows）

现代操作系统多采用Clock算法（近似LRU）或其变体，在性能和实现成本之间取得平衡。

缺页中断是当CPU访问一个虚拟页面时，发现该页面不在物理内存中而触发的一种异常。处理流程：
1. CPU发出虚拟地址访问请求
2. MMU查找页表，发现页面不在内存中（有效位为0）
3. 触发缺页中断，CPU转入内核态
4. 操作系统在磁盘上找到该页面
5. 若内存已满，使用置换算法选择牺牲页面
6. 将所需页面加载到内存，更新页表
7. 重新执行被中断的指令

帧数的选择需要在内存利用率和缺页率之间权衡：
• 帧数过少 → 缺页频繁，系统性能急剧下降（颠簸/Thrashing）
• 帧数过多 → 内存浪费，其他进程可用内存减少
• 建议：帧数应覆盖进程的工作集（Working Set）——进程在某个时间段内频繁访问的页面集合
通常通过监控缺页率动态调整（如Linux的LRU链表+水位线机制）。