专题进阶 · 操作系统算法推荐总顺序 · 第 146 / 148 课

逐次模拟 FIFO 缺页替换,理解命中不重排,以及增加页框反而缺页更多的例子。

先学会这些,再进入本课 先来先服务 集合
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 操作系统算法

FIFO 页面置换FIFO Page Replacement

淘汰最早进入内存的页,实现简单,但可能出现更多页框反而更多缺页的异常。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

逐次模拟 FIFO 缺页替换,理解命中不重排,以及增加页框反而缺页更多的例子。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

内存只能同时容纳几页,访问新页时淘汰最早装入的页,会发生什么?

02一步步得到方法

页框、命中与缺页

页框是当前驻留页面的位置。访问已驻留页称为命中;访问未驻留页称为缺页,需要把它装入。若容量已满,就按策略挑一个牺牲页。这里仅统计缺页次数,不模拟磁盘读写延迟。

FIFO 维护装入顺序队列。命中不会改变顺序,缺页时新页入队,满容量先弹出最早装入页。用集合辅助判断驻留,避免每次在线性队列里搜索。

一次命中不会获得保护

容量3,装入 [1,2,3] 后再次访问1仍保持队列 [1,2,3],再访问4就会淘汰1。页面刚被访问,不代表它刚被装入。

LRU 则会在访问1后把它移到最近端,因此可能淘汰2。这说明替换策略要先明确记录的时间究竟是装入时间还是最后访问时间。

Belady 异常说明容量与策略要一起分析

序列 1,2,3,4,1,2,5,1,2,3,4,5,在 FIFO 下3个页框缺页9次,4个页框却缺页10次。容量增加改变了淘汰轨迹,结果不一定更好。

具有栈包含性质的策略会让较小容量的驻留集合包含于较大容量的集合,从而排除这类异常。FIFO 一般不具备该性质;不能由直觉断言所有替换策略都随容量增加单调改善。

03把一个小例子完全算清楚

容量3,引用串 [1,2,3,1,4]。

步骤计算与状态为什么这样做
访问1、2、3连续3次缺页,队列[1,2,3]填满空页框
再次访问1命中,队列仍[1,2,3]FIFO 不刷新装入顺序
访问4缺页,淘汰1,队列[2,3,4]总缺页4次

窄屏可左右滑动表格,阅读完整计算与理由。

最终驻留 {2,3,4},缺页4次。

04为什么这个方法成立

  1. 集合与队列始终保存同一批驻留页,队列顺序按最近一次装入时间排列。
  2. 命中不修改顺序;缺页时弹出队首并从集合删除,再插入新页到队尾及集合。
  3. 因此每次替换都选择最早装入的当前驻留页,缺页计数恰在未驻留访问时增加。

05把推导翻译成代码

Python · 可独立运行的教学实现

from collections import deque

def fifo_pages(references,capacity):
    if capacity<1:
        raise ValueError("positive capacity required")
    queue,resident = deque(),set()
    faults,trace = 0,[]
    for page in references:
        hit = page in resident
        if not hit:
            faults += 1
            if len(queue)==capacity:
                resident.remove(queue.popleft())
            queue.append(page)
            resident.add(page)
        trace.append((page,hit,list(queue)))
    return faults,trace

print(fifo_pages([1,2,3,1,4],3))

逐个理解关键决定

hit = page in resident
集合用于平均 O(1) 的命中检测。
resident.remove(queue.popleft())
队列与集合必须同步删除同一个牺牲页。
trace.append
轨迹复制用于教学,实际仅需计数时不必保存每一步驻留状态。

06时间、空间与实现范围

不保存轨迹时,n 次访问平均 O(n),驻留结构 O(capacity)。

本教学版每次复制最多 capacity 个页,最坏时间和轨迹空间 O(n×capacity)。

07改变条件,检查哪里会出错

命中也把页移到队尾

那会改变 FIFO 规则,可能更接近 LRU 行为。

页框越多缺页必然越少

FIFO 存在已知反例,应通过具体轨迹验证。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

容量3时访问 [1,2,3,1,4],为何1被淘汰?

需要一点提示

它仍是最早装入项。

查看解析与答案

命中1没有改变 FIFO 次序。

练习 2 · 边界与辨析

重复访问同一页100次,正容量下缺页几次?

需要一点提示

首次装入后一直驻留。

查看解析与答案

1次。

练习 3 · 变式与迁移

怎样验证 Belady 异常而不是相信结论?

需要一点提示

分别跑容量3和4并比较完整轨迹。

查看解析与答案

对给定12项引用串得到9与10次缺页,逐步检查每次队首淘汰。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Arpaci-Dusseau · Operating Systems: Three Easy Pieces

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。