企业官网建设流程全解析

试题 1

试题正文

已知某系统采用页式存储管理，某进程的地址访问序列如下表，设每页大小为 100 Bytes，请写出相应的虚页访问序列，并试用 FIFO LRU OPT 3种算法实现页面置换，写出相应的淘汰过程并给出各自依次淘汰的页（设允许进程在内存中最多占3个页面），空白处不得分。

✅一、FIFO（先进先出页面置换算法）

核心思想

• 按照“最早进入内存的页面最先被淘汰”的原则。

• 把内存当作一个队列，队头是最先进入的页面，队尾是最新进入。

• 当发生缺页且内存已满时，直接淘汰队头的页面。

特点

• 实现简单、开销低。

• 不考虑页面的使用频率和时间，仅按进入顺序决定淘汰。

• 可能有“Belady 异常”：分配更多物理块反而使缺页次数变多。

✅二、LRU（Least Recently Used，近期最少使用算法）

核心思想

• 淘汰“最近最长时间没有被使用过”的页面。

• 根据页面的“最近访问时间”来决定淘汰对象。

• 模拟“人的直觉”：未来最可能不用的就是过去很久没用过的。

实现方式（常见）

• 每次访问页面时更新它的使用记录。

• 可用：

  • 时间戳法：每次访问记录时间戳，淘汰最小的。

  • 栈（双向链表）法：最新访问的移到栈顶，淘汰栈底。

特点

• 缺页率通常比 FIFO 低。

• 属于“栈式算法” →不会发生 Belady 异常。

• 实现比 FIFO 复杂，需要维护使用记录。

✅三、OPT（Optimal，最佳置换算法）

核心思想

• 淘汰未来最长时间不会被访问的页面。

• 完全根据未来访问序列做出最优选择。

• 是理想化的算法，因为实际操作系统不可能提前知道未来访问情况。

算法特性

• 理论上缺页次数最少，是所有置换算法的下界。

• 常用于衡量其他算法的性能上限。

• 虽然不能真正使用，但在教学和分析中很重要。

🔍三者的比较总结

⭐一句话记忆

• FIFO：先来的先走。

• LRU：很久没用的先走。

• OPT：未来最长时间不用的先走（最完美但做不到）。