题目
FIFO页面置换算法计算缺页中断次数
信息
- 类型：问答
- 难度：⭐
考点
页面置换算法,缺页中断,FIFO算法
快速回答
FIFO（先进先出）页面置换算法的核心要点：
- 总是淘汰最先进入内存的页面
- 缺页中断发生在访问的页面不在内存且需要置换时
- 计算时需注意初始页面装入也算缺页中断
题目示例中缺页中断次数为：9次
解析
原理说明
FIFO（First-In-First-Out）是最简单的页面置换算法，核心规则是：当发生缺页中断需要置换页面时，选择在内存中驻留时间最长的页面进行淘汰（类似队列的先进先出特性）。操作系统通过维护页面进入内存的顺序队列实现该算法。
题目计算过程
给定条件：物理块数=3，页面访问序列：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
| 访问页面 | 物理块1 | 物理块2 | 物理块3 | 是否缺页 | 淘汰页面 |
|---|---|---|---|---|---|
| 1 | 1 | - | - | 是（初始装入） | - |
| 2 | 1 | 2 | - | 是（初始装入） | - |
| 3 | 1 | 2 | 3 | 是（初始装入） | - |
| 4 | 4 | 2 | 3 | 是 | 1（最早进入） |
| 1 | 4 | 1 | 3 | 是 | 2（最早进入） |
| 2 | 4 | 1 | 2 | 是 | 3（最早进入） |
| 5 | 5 | 1 | 2 | 是 | 4（最早进入） |
| 1 | 5 | 1 | 2 | 否 | - |
| 2 | 5 | 1 | 2 | 否 | - |
| 3 | 5 | 3 | 2 | 是 | 1（最早进入） |
| 4 | 5 | 3 | 4 | 是 | 2（最早进入） |
| 5 | 5 | 3 | 4 | 否 | - |
缺页中断总次数：9次（表格中标记"是"的行）
代码示例（Python模拟）
def fifo(page_references, frames):
memory = [] # 当前内存中的页面
page_faults = 0
for page in page_references:
if page not in memory:
page_faults += 1
if len(memory) == frames: # 内存已满需置换
memory.pop(0) # 移除最先进入的页面
memory.append(page) # 新页面加入尾部
return page_faults
# 测试示例
pages = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print(fifo(pages, 3)) # 输出: 9最佳实践
- 适用场景：FIFO实现简单，适合对性能要求不高的嵌入式系统
- 实现要点：使用队列数据结构维护页面进入顺序
- 优化考虑：可结合访问频率二次筛选，避免频繁置换常用页面
常见错误
- 忘记计算初始页面装入导致的缺页中断
- 错误更新页面顺序（新页面应加入队列尾部，置换时从头部移除）
- 未考虑Belady异常：增加物理块数反而导致更多缺页（FIFO特有现象）
扩展知识
- 对比其他算法：LRU（最近最少使用）更符合程序局部性原理，性能通常优于FIFO
- Belady异常：FIFO算法中，物理块增加时缺页率可能不降反升
- 实际应用：现代操作系统常使用Clock算法（FIFO改进版）平衡性能和开销
