18 KiB
18 KiB
14. 分页存储管理
课程: 操作系统 - 存储器管理 核心内容: 碎片问题、分页思想、地址结构、页表、地址变换、TLB快表、多级页表、倒转页表
前置知识
一、碎片问题
在连续分配方式中，内存中会出现无法被利用的空闲区域，称为碎片。
| 碎片类型 | 出现位置 | 产生原因 | 对应分配方式 |
|---|---|---|---|
| 内碎片 (Internal Fragmentation) | 分配区域内部 | 固定分区大小 > 进程实际需要 | 固定分区分配 |
| 外碎片 (External Fragmentation) | 分配区域外部 | 空闲分区太小，无法满足任何请求 | 动态分区分配 |
flowchart LR
subgraph 内碎片示意
direction TB
A1["┌──────────────┐"]
A2["│ 进程实际数据 │"]
A3["│──────────────│"]
A4["│ 未使用空间 │ ← 内碎片"]
A5["└──────────────┘"]
end
subgraph 外碎片示意
direction TB
B1["┌────┐ ┌────┐ ┌────┐ ┌────┐"]
B2["│进程A│ │空闲│ │进程B│ │空闲│"]
B3["└────┘ └────┘ └────┘ └────┘"]
B4[" ↑外碎片 ↑外碎片"]
end
根本原因: 无论是固定分区还是动态分区，都要求进程在内存中连续存放。要彻底解决碎片问题，必须放弃"连续"要求——这就是分页思想的核心出发点。
二、分页的基本思想
分页存储管理将虚拟地址空间和物理内存都划分为大小相等的小块：
- 虚拟地址空间的每一块称为虚拟页 (Virtual Page, VP)
- 物理内存的每一块称为物理页框 (Page Frame, PF)
常见的页面大小为 2^k 字节：512B、1KB、2KB、4KB（最常用）。
flowchart TB
subgraph VA["虚拟地址空间 (进程视角)"]
direction TB
VP0["虚拟页 VP0"]
VP1["虚拟页 VP1"]
VP2["虚拟页 VP2"]
VP3["虚拟页 VP3"]
VP4["..."]
end
subgraph PM["物理内存"]
direction TB
PF0["物理页框 PF0"]
PF1["物理页框 PF1"]
PF2["物理页框 PF2"]
PF3["物理页框 PF3"]
PF4["..."]
end
VP0 -->|"页表映射"| PF2
VP1 -->|"页表映射"| PF0
VP2 -->|"不在内存"| DISK["外存(磁盘)"]
VP3 -->|"页表映射"| PF3
style VA fill:#e3f2fd,stroke:#1976d2
style PM fill:#fff8e1,stroke:#f9a825
style DISK fill:#fce4ec,stroke:#c62828
关键特性:
- 虚拟页在物理内存中不需要连续存放
- 每个虚拟页可以映射到任意一个空闲物理页框
- 消除了外碎片（但每个页内可能有少量内碎片）
三、地址结构
在分页系统中，虚拟地址被划分为两部分：
虚拟地址 VA (v+k 位)
┌─────────────────┬─────────────┐
│ VPN (v位) │ VPO (k位) │
│ 虚拟页号 │ 页内偏移 │
└─────────────────┴─────────────┘
计算公式:
- 页大小 =
2^k字节 - 虚拟页号 VPN = $\lfloor VA / 2^k \rfloor$（即高位部分）
- 页内偏移 VPO = $VA \mod 2^k$（即低
k位）
物理地址同理：
物理地址 PA (p+k 位)
┌─────────────────┬─────────────┐
│ PPN (p位) │ PPO (k位) │
│ 物理页号 │ 页内偏移 │
└─────────────────┴─────────────┘
- 物理页号 PPN 由页表查得
- PPO = VPO（页内偏移不变，直接复制）
地址计算示例
例题: 某系统虚拟地址 16 位，页面大小 4KB (
2^{12})，求虚拟地址 VA = 0x3A6F 对应的 VPN 和 VPO。
- 页大小 $2^k = 2^{12}$，所以 $k = 12$，
v = 16 - 12 = 4 - VPN = $0x3A6F / 0x1000 = 0x3$（高4位：0011）
- VPO = $0x3A6F \mod 0x1000 = 0xA6F$（低12位）
VA = 0x3A6F = 0011 1010 0110 1111
──── ────────────────
VPN VPO
(0x3) (0xA6F)
四、页表
页表是实现虚拟页到物理页框映射的核心数据结构。
页表结构
每个进程拥有独立的页表。页表以 VPN 为索引，每个页表项 (PTE) 包含：
页表 (以VPN为索引)
┌──────┬───────┬──────────────────────────────┐
│ VPN │ PPN │ 控制位 │
├──────┼───────┼──────────────────────────────┤
│ 0 │ 5 │ V=1 D=0 R=1 W=1 U/S=1 │
│ 1 │ 2 │ V=1 D=1 R=1 W=1 U/S=1 │
│ 2 │ --- │ V=0 (不在内存) │
│ 3 │ 8 │ V=1 D=0 R=1 W=0 U/S=1 │
│ ... │ ... │ ... │
└──────┴───────┴──────────────────────────────┘
页表项 (PTE) 各字段
| 字段 | 含义 | 说明 |
|---|---|---|
| 有效位 (Valid/Present) | 页面是否在内存中 | V=1：在内存；V=0：不在内存（缺页） |
| 修改位 (Dirty) | 页面是否被写过 | D=1：被修改过，换出时需写回外存 |
| 引用位 (Reference) | 页面是否被访问过 | 用于页面置换算法（如Clock、LRU近似） |
| 读/写权限 (R/W) | 读写保护 | 只读页被写入时触发保护异常 |
| 用户/内核 (U/S) | 访问权限 | U=0：仅内核可访问；U=1：用户可访问 |
| 物理页号 (PPN) | 对应的物理页框号 | 与VPO拼接得到物理地址 |
五、地址变换过程
基本地址变换流程
flowchart TD
A["CPU发出虚拟地址 VA"] --> B["从VA中提取VPN和VPO"]
B --> C{"TLB查找VPN"}
C -->|"TLB命中"| D["直接取出PPN"]
C -->|"TLB未命中"| E["访问页表<br/>(页表基址寄存器PTBR + VPN × PTE大小)"]
E --> F{"页表项有效位?"}
F -->|"V=1"| G["取出PPN"]
F -->|"V=0"| H["**缺页中断**<br/>操作系统处理"]
H --> I["从外存调入页面"]
I --> J["更新页表"]
J --> G
D --> K["物理地址 PA = PPN × 2^k + PPO"]
G --> K
K --> L["访问物理内存"]
style H fill:#ffcdd2,stroke:#c62828
style C fill:#e8f5e9,stroke:#2e7d32
详细步骤
- 提取地址字段: 从虚拟地址 VA 中分离出 VPN 和 VPO
- 查TLB: 用 VPN 在 TLB 中查找（见第六节）
- 查页表: 若 TLB 未命中，用 PTBR（页表基址寄存器）+ VPN 定位页表项
- 检查有效位:
- V=1：取出 PPN，与 PPO 拼接得到物理地址
- V=0：触发缺页中断，OS 从外存调入页面
- 拼接物理地址: PA = PPN | PPO（将 PPN 放高位，PPO 放低位）
缺页中断处理流程
flowchart TD
A["发生缺页中断"] --> B["保存CPU现场"]
B --> C{"外存中找到该页?"}
C -->|"找到"| D{"内存有空闲页框?"}
C -->|"未找到"| E["终止进程<br/>(非法访问)"]
D -->|"有空闲"| F["从外存读入该页"]
D -->|"无空闲"| G["执行页面置换算法<br/>选择牺牲页"]
G --> H{"牺牲页Dirty=1?"}
H -->|"是"| I["将牺牲页写回外存"]
H -->|"否"| J["直接覆盖"]
I --> F
J --> F
F --> K["修改页表<br/>设置V=1, PPN"]
K --> L["重新执行被中断的指令"]
地址变换计算示例
例题: 某系统页面大小 1KB (
2^{10})，虚拟地址 14 位。页表如下，求虚拟地址 VA=0x1A8F 对应的物理地址。
| VPN | PPN | Valid |
|---|---|---|
| 0 | 3 | 1 |
| 1 | 7 | 1 |
| 2 | --- | 0 |
| 3 | 5 | 1 |
| 4 | 2 | 1 |
| 5 | 8 | 1 |
| 6 | 1 | 1 |
解题过程:
- 页面大小 $2^{10}$，所以 $k=10$，
v=14-10=4 - VA = 0x1A8F = 01 1010 1000 1111 (二进制)
- VPN = 高4位 = 0110 = 6
- VPO = 低10位 = 10 1000 1111 = 0x28F
- 查页表：VPN=6 对应 PPN=1，Valid=1
- PA = PPN | PPO = 1 × 2^{10} + 0x28F = 0x400 + 0x28F = 0x68F
VA = 0x1A8F: 0110 1010001111
VPN=6 VPO=0x28F
查页表: VPN=6 → PPN=1
PA = 0001 1010001111 = 0x068F
PPN=1 PPO=0x28F
六、TLB 快表
TLB 概述
TLB (Translation Lookaside Buffer) 是集成在 MMU 中的高速缓存，存储最近使用的页表项。
flowchart LR
CPU["CPU"] -->|"虚拟地址"| TLB{"TLB<br/>(快表)"}
TLB -->|"命中<br/>取出PPN"| PA["物理地址"]
TLB -->|"未命中"| PT["查页表<br/>(内存)"]
PT -->|"PPN"| PA
PT -->|"更新TLB"| TLB
style TLB fill:#e8f5e9,stroke:#2e7d32
style PT fill:#fff3e0,stroke:#e65100
TLB 组织方式
| 方式 | 说明 | 特点 |
|---|---|---|
| 全相联 | VPN可以放在TLB的任意位置 | 灵活但查找慢，适合小容量TLB |
| 组相联 | VPN映射到固定的组(set)，组内任意放置 | 折中方案，最常用 |
| 直接映射 | VPN映射到固定的TLB位置 | 最快但冲突多 |
TLB 性能分析
设 TLB 查找时间为 $\lambda$，内存访问时间为 $t$，TLB 命中率为 $a$：
无 TLB 时：每次地址变换需要访问一次页表（内存）+ 一次数据访问（内存）
EAT_{无TLB} = t + t = 2t
有 TLB 时：
EAT = a(\lambda + t) + (1-a)(\lambda + t + t) = \lambda + t + (1-a) \cdot t
计算示例: 设 $\lambda = 10$ns, $t = 100$ns, $a = 0.98$（98%命中率）
EAT = 10 + 100 + (1 - 0.98) \times 100 = 10 + 100 + 2 = 112ns相比无TLB的
2t = 200ns，性能提升了约 44%。
七、多级页表
为什么需要多级页表
对于 32 位系统，页面大小 4KB：
- 虚拟地址空间 =
2^{32}= 4GB - 页数 =
2^{32} / 2^{12} = 2^{20}= 1M 个页 - 每个页表项 4 字节 → 页表大小 = 1M × 4B = 4MB
4MB 的页表对于每个进程都太大了！而且页表必须连续存放。
二级页表结构
核心思想: 将页表本身也分页，用"页目录"来索引这些页表页。
32位虚拟地址 (二级页表)
┌──────────────┬──────────────┬──────────────┐
│ 页目录索引(10位)│ 页表索引(10位) │ 页内偏移(12位)│
└──────────────┴──────────────┴──────────────┘
flowchart LR
CR3["CR3<br/>(页目录基址)"] --> PD["页目录<br/>(1024项)"]
PD -->|"页目录项"| PT1["页表1<br/>(1024项)"]
PD -->|"页目录项"| PT2["页表2<br/>(1024项)"]
PD -->|"页目录项"| PT3["页表3<br/>(1024项)"]
PT1 -->|"页表项+偏移"| PF1["物理页框"]
PT2 -->|"页表项+偏移"| PF2["物理页框"]
PT3 -->|"页表项+偏移"| PF3["物理页框"]
style PD fill:#e3f2fd,stroke:#1976d2
style PT1 fill:#fff3e0,stroke:#e65100
style PT2 fill:#fff3e0,stroke:#e65100
style PT3 fill:#fff3e0,stroke:#e65100
多级页表的优势
- 页目录只需常驻内存（4KB），页表页按需创建
- 未使用的虚拟地址区域不需要分配页表页，节省大量内存
- 64 位系统通常使用 3~5 级页表（如 Linux 的 4 级页表：PGD→PUD→PMD→PTE→偏移）
二级页表地址变换
- 用 CR3 找到页目录基址
- 用页目录索引在页目录中找到页表页的物理地址
- 用页表索引在页表页中找到 PPN
- PPN 与页内偏移拼接得到物理地址
注意: 二级页表需要 3 次内存访问（页目录 + 页表 + 数据），比一级页表多一次。因此 TLB 的作用更加重要。
八、倒转页表
基本思想
传统页表以虚拟页号为索引，每个进程一张。倒转页表以物理页框号为索引，整个系统一张。
| 对比项 | 传统页表 | 倒转页表 |
|---|---|---|
| 索引 | 虚拟页号 (VPN) | 物理页框号 (PFN) |
| 表项数 | 虚拟页数（可能很大） | 物理页框数（固定） |
| 进程数 | 每进程一张 | 全系统一张 |
| 查找方式 | 直接索引 | 需要搜索（或用Hash） |
flowchart LR
subgraph 传统页表
direction TB
T1["VPN 0 → PPN x"]
T2["VPN 1 → PPN y"]
T3["VPN 2 → PPN z"]
T4["..."]
end
subgraph 倒转页表
direction TB
I1["PFN 0 ← VPN a, 进程P1"]
I2["PFN 1 ← VPN b, 进程P2"]
I3["PFN 2 ← VPN c, 进程P1"]
I4["..."]
end
优点: 表大小与物理内存成正比，节省空间（尤其在 64 位系统）
缺点: 查找需要搜索整个表（通常用 Hash 加速）
九、内存保护
分页系统中通过以下机制实现内存保护：
1. 越界保护
- 页表项中的有效位 V=0 表示该页不在内存，访问时触发缺页中断
- 非法虚拟地址（超出进程地址空间范围）触发保护异常
2. 标志位保护
| 标志位 | 保护功能 |
|---|---|
| R/W | 读/写权限控制。只读页被写入时触发异常 |
| U/S | 用户/内核权限。用户态访问内核页时触发异常 |
| NX (No Execute) | 禁止执行位。数据页被当作代码执行时触发异常 |
3. 键保护
- 每个物理页框有一个保护键 (Protection Key)
- 每个进程有一个键寄存器
- 只有键匹配时才允许访问
- Intel MPX/MPK 技术支持此机制
十、空闲页面管理
操作系统需要跟踪物理内存中哪些页框是空闲的：
1. 位示图法 (Bitmap)
用一个 bit 表示一个物理页框的状态：0=空闲，1=已分配。
位示图示例 (假设16个物理页框):
位号: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
状态: 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1
↑ ↑ ↑
空闲 空闲 空闲
- 优点: 简单，查找连续空闲块方便
- 缺点: 位示图本身占用内存（物理内存 4GB、页大小 4KB → 位示图 128KB）
2. 链表法
将所有空闲页框用链表串起来：
空闲链表: [PF3] → [PF5] → [PF8] → [PF12] → NULL
- 优点: 实现简单，不额外占用大量空间
- 缺点: 查找连续空闲块需要遍历链表
十一、Nachos 页式存储管理代码
Nachos 教学操作系统中实现了基本的分页存储管理。以下是关键代码片段：
核心数据结构
// 页表项结构 (Machine/translate.h)
typedef struct {
int virtualPage; // 虚拟页号 (VPN)
int physicalPage; // 物理页号 (PPN)
bool valid; // 有效位
bool readOnly; // 只读标志
bool use; // 引用位 (用于LRU等算法)
bool dirty; // 修改位
} TranslationEntry;
地址转换核心代码
// Machine/translate.cc - translate()
// 将虚拟地址转换为物理地址
int Machine::Translate(int virtAddr, int *physAddr, int size, bool writing) {
// 1. 计算VPN和偏移
int vpn = virtAddr / PageSize;
int offset = virtAddr % PageSize;
// 2. 查找页表
TranslationEntry *entry = &pageTable[vpn];
// 3. 检查有效位
if (!entry->valid) {
// 缺页处理
return PageFaultException;
}
// 4. 检查写权限
if (writing && entry->readOnly) {
return ReadOnlyException;
}
// 5. 计算物理地址
*physAddr = entry->physicalPage * PageSize + offset;
// 6. 更新引用位和修改位
entry->use = true;
if (writing) entry->dirty = true;
return NoException;
}
内存分配示例
// AddrSpace/addrspace.cc - 进程地址空间初始化
// 为进程分配物理页框
void AddrSpace::InitRegisters() {
// 初始化页表
pageTable = new TranslationEntry[numPages];
for (int i = 0; i < numPages; i++) {
pageTable[i].virtualPage = i;
pageTable[i].physicalPage = bitMap->Find(); // 位示图分配
pageTable[i].valid = true;
pageTable[i].readOnly = false;
pageTable[i].use = false;
pageTable[i].dirty = false;
}
}
十二、小结
mindmap
root((分页存储管理))
碎片问题
内碎片(固定分区)
外碎片(动态分区)
根因:连续存放
分页思想
虚拟页VP
物理页框PF
等大划分
地址结构
VPN+VPO
PPN+PPO
页内偏移不变
页表
VPN→PPN映射
有效位/Dirty/Ref
每进程独立
地址变换
PTBR+VPN查页表
取PPN拼PPO
缺页中断处理
TLB快表
高速缓存页表项
命中率影响EAT
多级页表
页目录+页表
节省内存
倒转页表
按物理块号索引
全系统一张
思考题
-
概念理解: 为什么分页能消除外碎片但不能消除内碎片？内碎片平均浪费多少？
-
计算题: 某系统页面大小 4KB，虚拟地址 20 位，物理地址 18 位。
- 虚拟地址空间有多少页？
- 物理内存最大多少？
- 页表至少需要多少项？
-
TLB计算: 设 TLB 查找时间 5ns，内存访问时间 80ns，要求有效访问时间不超过 100ns，TLB 命中率至少为多少？
-
多级页表: 对于 64 位系统，为什么至少需要 3 级页表？
关联笔记
- 13_存储管理基础 — 存储器层次结构与地址空间基础
- 15_段式存储管理 — 分段式地址转换，段页式结合
- 16_虚拟存储器 — 基于分页的虚拟存储器实现
- 11_处理机调度 — 进程调度与缺页处理的关系