算法)
试题 1
试题正文
已知某系统采用页式存储管理，某进程的地址访问序列如下表，设每页大小为 100 Bytes，请写出相应的虚页访问序列，并试用 FIFO LRU OPT 3种算法实现页面置换，写出相应的淘汰过程并给出各自依次淘汰的页（设允许进程在内存中最多占3个页面），空白处不得分。
✅一、FIFO（先进先出页面置换算法）
核心思想
按照“最早进入内存的页面最先被淘汰”的原则。
把内存当作一个队列，队头是最先进入的页面，队尾是最新进入。
当发生缺页且内存已满时，直接淘汰队头的页面。
特点
实现简单、开销低。
不考虑页面的使用频率和时间，仅按进入顺序决定淘汰。
可能有“Belady 异常”：分配更多物理块反而使缺页次数变多。
✅二、LRU（Least Recently Used，近期最少使用算法）
核心思想
淘汰“最近最长时间没有被使用过”的页面。
根据页面的“最近访问时间”来决定淘汰对象。
模拟“人的直觉”：未来最可能不用的就是过去很久没用过的。
实现方式（常见）
每次访问页面时更新它的使用记录。
可用：
时间戳法：每次访问记录时间戳，淘汰最小的。
栈（双向链表）法：最新访问的移到栈顶，淘汰栈底。
特点
缺页率通常比 FIFO 低。
属于“栈式算法” →不会发生 Belady 异常。
实现比 FIFO 复杂，需要维护使用记录。
✅三、OPT（Optimal，最佳置换算法）
核心思想
淘汰未来最长时间不会被访问的页面。
完全根据未来访问序列做出最优选择。
是理想化的算法，因为实际操作系统不可能提前知道未来访问情况。
算法特性
理论上缺页次数最少，是所有置换算法的下界。
常用于衡量其他算法的性能上限。
虽然不能真正使用，但在教学和分析中很重要。
🔍三者的比较总结
| 算法 | 原理 | 是否考虑访问时间 | 是否可能 Belady 异常 | 实际可实现性 |
|---|---|---|---|---|
| FIFO | 按进入先后淘汰 | ❌ 不考虑 | ✔ 会发生 | ✔ 简单，使用 |
| LRU | 淘汰最近最少使用 | ✔ 考虑过去的访问 | ❌ 不会发生 | ✔ 可实现 |
| OPT | 淘汰未来最长时间不用 | ✔ 未来访问（理想） | ❌ 不会发生 | ❌ 不可实际实现 |
⭐一句话记忆
FIFO：先来的先走。
LRU：很久没用的先走。
OPT：未来最长时间不用的先走（最完美但做不到）。
