第9周 星期二 第2大节

• 视频：screen_操作系统与分布式计算_第9周_星期二_第2大节.mp4
• 字幕：transcripts/第9周_星期二_第2大节.srt

时间轴

• [01:11] 虚拟存储回顾与页表项标志位
• [04:00] 缺页中断与页面置换引⼊
• [07:44] 驻留集与置换策略分类（局部/全局）
• [08:25] FIFO置换 + Belady异常
• [15:02] OPT最优置换（理论不可实现、评价标尺）
• [21:13] LRU（最近最少使用、栈式算法、无Belady异常）
• [26:47] Clock时钟算法（第二次机会）
• [31:29] NRU最近未使用（使用位+修改位）
• [35:27] 全局置换引⼊：程序形态（局部性+阶段转换）
• [40:10] WS工作集置换（δ间隔）
• [52:24] SWS采样工作集（时间戳）
• [54:16] 实用OS策略：SWS + 延迟清除（自由列表/修改列表）
• [01:00:36] 多级页表（为什么需要、10+10+12结构）
• [01:08:57] 多级页表计算示例（1K页、2B页表项→128项页目录）
• [01:16:07] 64位系统与哈希页表
• [01:23:53] 最佳页面大小推导（S/P + P/2 → P = sqrt(2S)）
• [01:29:57] 存储管理总结
• [01:32:00] 文件系统开篇

页面置换策略分类

驻留集（resident set）：进程当前在内存中的物理页帧集合。

分类	驻留集大小	置换范围	策略
局部置换	固定	进程内	FIFO、OPT、LRU、Clock、NRU
全局置换	可变	系统内	WS、SWS

局部置换策略（驻留集大小固定）

FIFO（First In First Out）

• 淘汰最早进入内存的页面
• Belady异常：驻留集增大，缺页中断次数反而可能增加
• 实现简单，无需额外硬件支持，但效果差

演算示例（访问串 7,0,1,2,0,3,0,4,2,3,0,3,2...，驻留集=3）： 页面调入顺序导致 7→0→1 依次入内存；访问2时缺页，淘汰最先进入的7；访问0命中；访问3时缺页，淘汰0（当前最早）…

OPT（Optimal，最优置换）

• 淘汰未来最远才被访问的页面（或永不访问的页面）
• 理论上缺页中断次数最少
• 不可实现（未来访问串未知）
• 价值：作为理论下界，为其他策略提供评价标尺

演算同上示例，缺页次数明显少于 FIFO。

LRU（Least Recently Used）

• 淘汰过去最久未被访问的页面（“往后看未知，往前看已知”）
• 栈式算法：驻留集大小为 M 时的页帧集合 ⊆ 驻留集为 M+1 时的页帧集合
• 无 Belady 异常（栈式算法可证明，驻留集增大时缺页次数一定不增）
• 实现需额外硬件支持，如每页帧配计数器：访问时清零，其余加一，淘汰计数值最大的页

Clock（时钟算法，Second Chance）

• 物理页帧组成循环链表（钟面），指针（钟针）在其中旋转
• 淘汰策略：
  • 指针指向页的访问位 = 1 → 置 0，指针下移（给第二次机会）
  • 访问位 = 0 → 淘汰
• 若全部页面访问位均为 1，转一圈后全部变 0，回到原点淘汰
• 与 LRU 思想类似（淘汰足够长时间未被访问的页），但只需访问位，无需额外硬件

NRU（Not Recently Used）

• 结合 FIFO 和 LRU 思想：页表项增加使用位，定时清零
• 淘汰优先级（同时考虑使用位和修改位）：
  1. 使用位=0，修改位=0（最优先，无需回写外存）
  2. 使用位=0，修改位=1（需回写）
  3. 使用位=1，修改位=0
  4. 使用位=1，修改位=1（最后）
• 优先淘汰修改位=0 的页面：避免回写开销

全局置换策略（驻留集大小可变）

程序形态

• 局部性形态：程序在一段时间内工作于某个局部热点（工作集 working set）
• 阶段转换形态：执行热点从工作集 A 跳转到工作集 B

为什么需要全局置换

• 驻留集 < 工作集 → 频繁抖动（thrashing）
• 驻留集 >> 工作集 → 内存浪费
• 动态匹配工作集大小，兼顾抖动避免和内存利用率

WS（Working Set）

• 设置 δ 间隔（delta），每经过 δ 次页面访问，淘汰在该间隔内未被访问的页面
• 驻留集大小随工作集动态变化
• 实现：每页配计数器，访问时清零、其余加一；淘汰计数器值 = δ 的页
• 特点：开销大（每页一个计数器），不太实用

SWS（Sampled Working Set）

• 改进 WS：页表项中记录当前时间戳（访问时写入时钟值）
• 操作系统定时检查：当前时钟值 - 页表项时间戳 > δ → 淘汰
• 无需额外计数器，硬件消耗仍较大

实用 OS 策略（SWS + 延迟清除）

现代操作系统（Windows/Linux）实际采用： SWS + 淘汰页数据延迟清除（Deferred Clearing）

延迟清除策略（自由列表 + 修改列表）：

1. 定时按 SWS 策略淘汰页面
2. 根据修改位放入不同队列：
   • 自由列表（free list）：修改位=0，页面内容无需回写
   • 修改列表（modified list）：修改位=1，待回写
3. 修改链过长或自由链过短时，将修改链页面回写外存后移至自由链
4. 缺页中断时，从自由链直接分配物理页帧（数据可覆盖）
5. 关键优化：若自由链/修改链中的页面被再次访问，只需将合法位置 1，无需从外存重新加载

好处：延迟清除，避免不必要的回写，提高访问效率。

多级页表

为什么需要多级页表

32 位系统，页大小 4K（2¹²），页表项 4B → 页表需 2²² = 4MB 连续物理空间。页表本身也可分页存储，避免大块连续分配。

二级页表结构（10+10+12）

• 页内偏移：12 位
• 二级页号（内层页表）：10 位
• 页目录号（一级页表）：10 位
• 地址转换：先查页目录 → 获二级页表地址 → 查二级页表 → 获物理帧号 → 拼接偏移

计算示例

条件：逻辑地址空间 2¹⁶ 个页（即 2²⁶ B = 64MB），页大小 1K（10 位偏移），页表项 2B：

• 总地址位数：26 位
• 页内偏移：10 位
• 每页可存放页表项数：1K / 2B = 2⁹ = 512 项（需 9 位索引）
• 页目录号位数：26 - 10 - 9 = 7 位 → 128 项

页表层数与效率

层数越多，转换开销越大。64 位系统（4K 页）单页目录需 2⁴² 连续空间，多级页表也难应付 → 使用哈希页表（逻辑页号作哈希值，链表解决冲突，包含逻辑页号、物理帧号、next 指针三个字段）。

最佳页面大小推导

假设进程平均大小 S 字节，页面大小 P 字节，页表项 1B：

• 页表开销：S/P（页表项数 × 1B）
• 内部碎片：P/2（每页平均浪费半页）
• 总开销：C(P) = S/P + P/2
• 求导：dC/dP = -S/P² + 1/2 = 0 → P = sqrt(2S)

实际系统据此理论指导选择页大小（如 4K）。

存储管理总结

维度	方案
连续分配	单一连续区 → 固定分区 → 可变分区
非连续分配	页式 / 段式 / 段页式
是否一次性分配	非虚拟（一次全部分配） vs 虚拟（按需调入）
虚拟 + 页式	现代通用 OS（Windows/Linux）

文件系统（开篇）

文件定义

文件是记录在外存上、具有符号名的、在逻辑上有完整意义的一组相关信息项的集合。

用户角度：文件是逻辑外存上的最小分配单元（以文件为单位访问外存）。

文件组成

• 文件体：文件内容数据
• 文件说明信息：即文件的属性/管理信息，存储在文件目录中
  • 文件名、类型、存储位置、大小、访问权限、创建时间、创建用户等
  • 操作系统管理文件的 FCB（File Control Block，文件控制块）即存放这些信息

文件类型

分类依据	例子
后缀/格式	.exe, .c, .com 等
性质和用途	系统文件、库文件、用户文件
存储期限	临时文件、档案文件、永久文件
保护方式	只读文件、读写文件、可执行文件
UNIX 分类	普通文件、目录文件、特殊文件（设备抽象为文件）

操作系统只关心文件体作为整体的存储分配，不解释文件体内部格式（由上層应用处理）。

存取方式

• 顺序存取：按信息顺序依次读写
• 随机/直接存取：直接定位任意记录（定长记录可通过偏移计算）
• 按键存取：通过键值（哈希）映射到物理块

物理设备特性决定存取限制：磁带只能顺序；磁盘支持顺序+随机。

文件物理结构

结构	特点	优点	缺点
连续存储	逻辑连续 → 物理连续	方式简单、批量存取效率高（无需频繁寻道）、支持定长直接存取	外部碎片、不便动态扩充
链接结构	逻辑连续 → 物理离散，指针链接	磁盘利用率高、无外部碎片、便于动态扩充	不支持随机查找、寻道时间长、指针可靠性问题
索引结构	逻辑连续 → 物理离散，索引表映射	顺序/随机均可、支持动态增长、利用率高	寻道时间长、索引表需额外空间

索引表过大时，可用链接方式或多重索引（类似多级页表）组织。UNIX/Linux 采用混合索引（i-node 节点）：直接寻址 + 一级索引 + 二级索引 + 三级索引，最大支持文件达 40GB。