第8周星期二第2大节

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

时间轴

[01:00] 回顾分区存储管理→引入页式
[08:00] 页式：逻辑页→物理页帧
[11:00] 页表（Page Table）
[15:00] 地址转换：页号+页内偏移
[22:00] 两次访存→快表TLB（命中率计算）
[31:00] 空闲页帧管理：Bitmap位视图
[35:00] 共享与保护（权限位）
[52:00] 段式存储管理（二维逻辑地址）
[01:03:00] 段页式存储管理
[01:14:00] 内存扩充：Overlay（覆盖）+ Swapping（交换）
[01:22:00] 虚拟存储：局部性原理、虚拟地址空间、缺页中断、swap分区

页式存储管理

背景

分区存储管理要求逻辑地址连续 ⇒ 物理地址也必须连续，导致外部碎片、内存紧致耗时。页式存储管理打破了这一限制——逻辑上连续的空间在物理内存中可以分散存放在不同页帧。

核心概念

页（Page）：逻辑空间划分为大小相等的逻辑页
页帧（Page Frame）：物理空间划分为大小相等的物理页帧（大小与页相同）
页大小定为 2 的 k 次幂：地址转换中的除法/乘法可转化为移位操作，提高效率

页表（Page Table）

数据结构，记录逻辑页 → 物理页帧的映射关系
每个进程有独立页表，PCB 中有指针指向其页表
存储在系统空间
本质是数组：数组下标 = 逻辑页号（自然映射，无需额外存储页号），节省内存
页表项内容：物理页帧号 + 权限位

地址转换过程

从 PCB 获取该进程页表起始地址
线性逻辑地址 → 页号 P（高位）+ 页内偏移 W（低位）
以 P 为下标查页表，得到物理页帧号 F
物理地址 = F（高位拼接）+ W（低位）
拼接后的物理地址直接访存取数据

两次访存问题 → TLB（快表）

两次访存：查页表（1次）→ 取数据（1次），共2次内存访问
TLB（Translation Lookaside Buffer，快表）：一组高速联想寄存器，存放近期访问的页表项
TLB 容量有限（通常 8~12 项），利用程序局部性提高命中率
命中率计算实例：
- 一次访存 750ns，查 TLB 50ns
- TLB 命中率 80%：命中耗时 50+750=800ns，未命中耗时 50+750+750=1550ns
- 平均访问时间 = 80%×800 + 20%×1550 = 950ns
- 无 TLB：2×750 = 1500ns
进程切换时，TLB 需刷新并装入新进程的页表项

空闲页帧管理：Bitmap（位视图）

每个物理页帧对应位图中的一位
- 0 = 空闲，1 = 占用
相比链表，位图极大节约存储空间
计算实例：256MB 内存 / 4KB 页大小 = 65536 页帧 → 65536 bit = 8192 字节

共享与保护

共享：不同进程的页表项指向同一物理页帧（如多进程执行同一程序，共享代码段）
保护：
- 页表长度寄存器：检查逻辑页号是否越界
- 权限位：页表项中增加访问权限字段（只读/读写）
  - 代码段 → 只读
  - 数据段 → 可读写

页式优缺点

优点：无外部碎片、物理内存不要求连续、更灵活
缺点：仍有内部碎片（平均半页）、地址转换变复杂（硬件实现）、页表占用额外内存、需一次性装入全部逻辑页

段式存储管理

核心概念

按程序自然结构（代码段、数据段、栈段等）划分逻辑空间
二维逻辑地址：段号（S）+ 段内偏移（D）
每段独立编址（从 0 开始），段长可变
物理内存采用可变分区管理

段表

记录逻辑段 → 物理段映射，包含：
- 段长度
- 物理起始地址
段号由数组下标自然表示
PCB 中有指针指向段表

地址转换

查段号 S 是否超过段表长度寄存器（越界保护）
查段表获取该段物理起始地址
物理地址 = 起始地址 + 段内偏移 D（加法拼接，区别于页式的位拼接）

优缺点

优点：无内部碎片、按语义分段便于共享和保护
缺点：有外部碎片（需内存紧致）、编程复杂（需在汇编中加段号）

页式 vs 段式对比

维度	页式	段式
划分依据	系统固定大小	程序员按语义
大小	固定（2^k）	可变
地址结构	一维线性	二维（段号+偏移）
表	页表（较长）	段表（较短）
物理地址形成	帧号\|偏移（拼接）	基址+偏移（加法）
碎片	内部碎片	外部碎片
共享	支持，不灵活	支持，更自然
内存扩充	不支持	不支持

段页式存储管理

融合段式和页式：
- 逻辑上分段（用户视角）
- 物理上分页（内存管理视角）
逻辑地址：段号 + 段内页号 + 页内偏移
转换过程：查段表（得页表始址）→ 查页表（得页帧号）→ 拼接偏移
三次访存：段表访存 + 页表访存 + 取数据
可配合 TLB 降低等效访问时间

内存扩充技术

背景

当作业地址空间大于物理内存时，进程无法运行。需要借助外存在逻辑上扩充内存。

Overlay（覆盖）

把用户空间划分为固定区和多个可覆盖区
互斥执行的程序段共享同一覆盖区
需要程序员显式安排哪些代码可覆盖（编程复杂度高）
以时间换空间：运行效率降低，但可装载更多进程并发
仍是作业内部覆盖

Swapping（交换）

将处于等待/就绪的进程从内存换出到外存（挂起），需要时换入
操作系统管理，对程序员透明
优点：增加并发数、实现优先级调度；缺点：换入换出 I/O 开销大、需重定位机制支持
是作业之间的交换

Overlay vs Swapping

维度	Overlay	Swapping
范围	作业内部	作业之间
管理方	程序员	操作系统
编程影响	增加复杂度	透明

虚拟存储技术

理论基础：局部性原理（Locality Principle）

程序在执行时有热点区域（如循环、子程序调用），一段时间内仅访问少数页
并非所有指令都会被执行（如错误处理、初始化）
基于此，无需一次性装入全部程序

核心思想

系统为进程提供比物理内存大得多的虚拟地址空间
虚拟空间大小由地址宽度决定（32位→4GB，64位→16EB）
程序装入时只加载当前需要的部分页面
访问时若页面不在内存 → 缺页中断（Page Fault） → OS 从外存调入

Swap 分区（交换区）

硬盘上专门划分的交换区空间
代码页：从程序文件读入（只读，无需回写）
数据页：运行中可能修改，需回写到 swap 区
零页（未初始化数据）：在内存中直接清零，不从外存读

虚拟页式存储的页表结构

较普通页表更复杂，页表项包含：

字段	说明
合法位（Valid）	1=在内存，0=在外存
修改位（Modified）	是否被修改（决定淘汰时是否回写）
页类型	零页/swap区（决定缺页处理方式）
保护码	读写执行权限
外存块号	页在外存的位置
物理页帧号	在内存时的页帧号

缺页中断处理流程

硬件访存发现合法位=0，产生缺页中断
进入缺页中断处理子程序
申请空闲页帧
- 有空闲 → 直接分配
- 无空闲 → 按置换策略淘汰一页
检查页类型：
- 零页 → 物理页帧清零
- 非零页 → 从外存读入数据到页帧
填写页表项（页帧号、合法位置1）
恢复执行访存指令

页淘汰流程

检查淘汰页的修改位
- 未修改 → 合法位清零，页帧回收（无需 I/O）
- 已修改 → 需回写到外存
  - 检查页类型：零页/swap区 → 分配 swap 空间
  - 调用 I/O 子系统将页帧数据写回外存
  - 更新页表项（外存块号、合法位清零）
页帧回收

页面置换策略

在内存已满需要调入新页时，选择淘汰哪个页
评价标准：缺页率越低越好（避免抖动/颠簸）
理想：淘汰后不再被访问的页（或短期内不被访问）
抖动（Thrashing）：页面频繁在内存和外存间调入调出，系统效率急剧下降
原因：置换算法不合理/驻留集太小

驻留集（Working Set）

进程当前在内存中的合法页数
局部置换：驻留集固定（每个进程分固定页帧数）
全局置换：驻留集可变（根据程序运行需要动态调整）

常见置换算法

FIFO（先进先出）
OPT（最佳置换，理论最优）
LRU（最近最少使用）
Clock（时钟置换，改进的 FIFO）

下一讲详细展开置换算法。

作业/复习重点

页式地址转换（页号+偏移→帧号+偏移，注意页式拼接 vs 段式加法）
TLB 命中率计算（公式：h×t_TLB + (1-h)×(t_TLB + 2×t_mem)）
Bitmap 容量计算
段式 vs 页式对比（划分依据、地址结构、碎片、拼接方式）
覆盖 vs 交换的区别
虚拟存储三要素：局部性原理、缺页中断、swap 交换区
页表项各字段含义（合法位、修改位、页类型、外存块号）
缺页中断处理流程