3 虚拟化
虚拟化的目标是让每个进程以为自己独占资源。分两条线:
- CPU 虚拟化 → 进程(见总览章节)
- 内存虚拟化 → 虚拟地址空间(本章主体)
地址空间
什么是地址空间
**地址空间(Address Space)**是进程看到的内存视图:
0xFFFFFFFF ┌──────────────┐ 高地址
│ 栈 │ 向下增长,函数调用、局部变量
│ ↓ │
│ │
│ ↑ │
│ 堆 │ 向上增长,malloc/new
├──────────────┤
│ BSS │ 未初始化的全局/静态变量
├──────────────┤
│ Data │ 已初始化的全局/静态变量
├──────────────┤
│ Text │ 代码(只读)
0x00000000 └──────────────┘ 低地址关键性质:每个进程的地址空间是独立的、从 0 开始的、连续的。
// 两个进程打印同一个指针值,指向的是不同的物理内存
printf("%p\n", &x); // 都是 0x7ffd4a3b8f2c,但物理地址不同为什么需要虚拟化内存
- 隔离:进程 A 不能读写进程 B 的内存(安全和可靠性的基石)
- 便利:每个程序都从地址 0 开始链接,不用考虑别的程序占哪里
- 效率:可以超额分配(overcommit),进程实际用多少物理内存就给多少;可以共享代码(多个进程共享同一份 libc 的物理页)
内存虚拟化的三条原则
OSTEP 总结的三个目标,任何内存管理机制都要在这三者间权衡:
| 原则 | 含义 |
|---|---|
| 透明(Transparency) | 程序感觉不到地址被转换了,它看到的还是完整连续的地址空间 |
| 效率(Efficiency) | 转换不能太慢(时间),页表不能太大(空间) |
| 保护(Protection) | 进程不能访问不属于它的内存 |
效率靠硬件(MMU + TLB),保护靠页表权限位,透明靠地址转换机制。
地址转换
硬件支持:MMU
MMU(Memory Management Unit)在 CPU 里,负责把虚拟地址(VA)实时转换成物理地址(PA)。
CPU 发出虚拟地址 → MMU 查页表 → 物理地址 → 内存**动态重定位(Dynamic Relocation)**是最简单的思路:
物理地址 = 虚拟地址 + 基址寄存器(base)
且检查 虚拟地址 < 界限寄存器(bound)早期系统用过。问题:整个地址空间必须连续放在物理内存里,会产生大量外部碎片。
分段(Segmentation)
把地址空间切成几个逻辑段(代码、堆、栈),每段有独立的 base/bound:
虚拟地址 = [段号][段内偏移]
│ │
│ └─ 加上该段的 base → 物理地址
└─ 查段表得到 base 和 bound优点:段之间可以不连续,缓解外部碎片;不同段可以有不同权限(代码段只读可执行、数据段可读写不可执行)。
问题:段粒度太粗,段内仍要连续 → 段之间产生外部碎片。内存吃紧时还是要紧凑(compaction),代价高。
现代 x86 仍保留段寄存器,但64 位模式下基本被架空(Linux 用的是平坦模式,所有段 base=0)。
分页(Paging)
现代方案:把内存切成固定大小的页(page,通常 4KB)。
- 虚拟内存切成 VP(虚拟页)
- 物理内存切成 PP(物理页 / 页帧 frame)
- 通过**页表(Page Table)**建立 VP → PP 的映射
虚拟地址 = [虚拟页号 VPN][页内偏移 offset]
│ │
│ └── 直接作为物理页内偏移(**不变**)
└── 查页表 → 物理页号 PPN
物理地址 = [PPN][offset]关键:页内偏移不需要转换。因为页大小是 2 的幂,虚拟页和物理页大小相同,页内相对位置一致。
例:32 位地址,页大小 4KB():
- 低 12 位 = offset
- 高 20 位 = VPN
页表项(PTE)
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬─────────────┐
│ P │ W │ U │PWT│PCD│ A │ D │PAT│ G │ PFN(物理页号) │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴─────────────┘
│ │ │ │ │
│ │ │ │ └── Dirty:被写过(换出时要写回磁盘)
│ │ │ └────── Accessed:被访问过(LRU 近似用)
│ │ └────────────────── U/S:用户态能否访问(0=只有内核能访问)
│ └────────────────────── R/W:可写?(0=只读)
└───────────────────────── Present:页在内存里吗(0=缺页)保护就靠这些位:
U/S = 0→ 用户态访问会触发段错误(这就是"用户程序不能碰内核内存"的实现)R/W = 0→ 写代码段会触发异常- 页表里没有的页 → 任何访问都非法
分页解决了什么,带来了什么
| 解决了 | 带来了 |
|---|---|
| ✓ 无外部碎片(页大小固定,任意物理页都能用) | ✗ 内部碎片(最后一页用不满,平均浪费半个页) |
| ✓ 灵活,虚拟页可映射到任意物理页 | ✗ 页表本身占内存 |
| ✓ 支持部分加载(按需分页) | ✗ 每次访存都要多一次内存访问查页表 |
两个代价都要专门解决,见下文。
页表太大怎么办
32 位地址、4KB 页 → = 100 万个页表项,每项 4 字节 → 每个进程 4MB 页表。
64 位地址更是天文数字。解法:
多级页表
只在实际用到的地址区间分配页表。
x86-64 的四级页表(4KB 页,48 位虚拟地址):
虚拟地址 48 位:
┌───────┬───────┬───────┬───────┬────────────┐
│ PML4 │ PDPT │ PD │ PT │ offset │
│ 9 bit │ 9 bit │ 9 bit │ 9 bit │ 12 bit │
└───────┴───────┴───────┴───────┴────────────┘
转换过程(4 次内存访问):
CR3(页表基址寄存器)→ PML4 表 → PDPT 表 → PD 表 → PT 表 → 物理页
│ │
└──────────── 每次都要从内存读一次 ─────────────────────┘为什么省空间:大部分虚拟地址空间是空的(比如 0x0000... 到 0x7fff... 之间的巨大空洞)。多级页表里,中间层某个条目为空时,其下整棵子树都不用分配。典型进程只需要 4 级 × 几张 4KB 页 = 几十 KB。
代价:转换需要 4 次内存访问(而不是 1 次)——慢了 4 倍。这个代价由 TLB 解决。
反向页表(Inverted Page Table)
不为每个进程存页表,而是为每个物理页存一条记录(哪个进程的哪个虚拟页映射到了这里)。
- 空间与物理内存成正比,与进程数无关
- 但查找慢(要遍历或哈希)
- PowerPC、某些大型机用过
大页(Huge Page / Large Page)
用 2MB 甚至 1GB 的页替代 4KB:
- 页表项减少 512 倍 → TLB 覆盖率大幅提升
- 适合数据库、JVM、深度学习等大内存场景
# Linux 大页
cat /proc/meminfo | grep Huge
echo 1024 > /sys/kernel/mm/hugepages/hugepages-2048kB/nr_hugepages**THP(Transparent Huge Pages)**让应用无感使用,但会导致内存碎片和延迟抖动,数据库场景常建议关闭。
TLB:让地址转换变快
问题
多级页表让每次访存变成 5 次访存(4 次查表 + 1 次取数据)。不可接受。
解法:TLB
TLB(Translation Lookaside Buffer)是 MMU 里的地址转换缓存:
虚拟地址 → MMU
├─ 查 TLB(快,1 个周期)→ 命中,直接用 PPN
└─ 未命中 → 走多级页表(慢,4 次内存访问)→ 填进 TLB为什么 TLB 有效:局部性原理。程序在一段时间内只访问少数几个页(循环、顺序扫描、函数调用栈都在少数页内),TLB 命中率通常 > 99%。
TLB 的典型参数
| L1 TLB | L2 TLB | |
|---|---|---|
| 条目数 | 64~128 | 512~1536 |
| 命中时间 | ~1 周期 | ~10 周期 |
| 未命中惩罚 | 几十~几百周期 |
现代 CPU 还有专门的 iTLB(指令)和 dTLB(数据)。
TLB 的一致性问题
关键问题:页表变了,TLB 里的旧条目怎么办?
场景:
- 上下文切换:换进程 = 换页表 = TLB 里的映射全部失效
解法:
- 简单粗暴:切换时清空 TLB(flush)。代价:切回来后要重新热身
- 优化:给 TLB 条目加 **ASID(Address Space ID)**标签,切换时不用清,靠标签区分
- 页被回收:OS 把某页换出,映射变了
- 需要 TLB shootdown:在多核上,通知其他 CPU 也失效对应条目(通过处理器间中断 IPI)。这是多核 OS 里一个不小的开销来源
TLB 性能影响
如果工作集超出 TLB 覆盖范围,每次访存都 TLB miss → 性能可能下降数倍。
这就是为什么:
- 数据库用大页
- 有人追求减少内存随机访问
- benchmark 里常见 "TLB miss" 成为瓶颈
按需分页与交换
按需分页(Demand Paging)
进程启动时不把所有页加载进内存,而是缺页时才加载。
1. 进程访问某虚拟地址
2. MMU 查页表,发现 Present = 0
3. 触发缺页异常(Page Fault)
4. 内核的缺页处理程序:
a. 检查地址合法性(越界?权限不对?→ 杀进程 SIGSEGV)
b. 找一个空闲物理页
c. 从磁盘读入内容
d. 更新页表,Present = 1
e. 重试刚才那条指令
5. 程序继续,**完全不知道发生了什么**(透明性)收益:
- 启动快(不用等全部加载)
- 省内存(只加载真正用到的)
- 支持 overcommit:所有进程的虚拟内存总和可以远超物理内存
缺页的三种情况:
| 类型 | 原因 | 处理 |
|---|---|---|
| Minor fault | 页已在内存,只是没建立映射(如共享库首次访问、写时复制) | 快,无需 I/O |
| Major fault | 页在磁盘上,要读盘 | 慢,毫秒级 |
| Invalid fault | 地址非法 | 发 SIGSEGV |
交换(Swapping)
内存不够时,把不常用的页换到磁盘的交换区(swap space)。
内存满 → 选一个"牺牲页"(victim)→ 若 Dirty 则写回磁盘 → 腾出物理页 → 加载需要的页抖动(Thrashing):内存严重不足时,系统把全部时间花在换页上,几乎不干活。表现是磁盘灯狂闪、系统卡死。
检测:如果缺页率持续很高,且 CPU 利用率反而低 → 抖动。解法:加内存、杀进程、减少并发。
页面置换算法
选哪个页作为"牺牲页"?目标是最小化缺页率。
假设访问序列:7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,物理内存 3 页。
FIFO
换出最早进入的页。简单,但可能换出常用页。
缺页次数:15 次(本例)
Belady 现象:增加物理页框数,缺页率反而上升。FIFO 不是"栈算法",会有这种反直觉行为。
OPT(最优 / MIN)
换出未来最晚才会被访问的页。
理论上最优(缺页 9 次),但无法实现(需要预知未来)。价值在于作为上界,用来评估其他算法。
LRU(Least Recently Used)
换出最久没被访问的页。基于局部性原理:最近没用的,近期大概率也不会用。
缺页次数:12 次(接近 OPT)
实现困难:要精确维护访问顺序,每次访存都要更新,代价太高。
实践中的近似:
时钟算法(Clock / Second Chance)
用 PTE 的 Access bit 做近似 LRU:
所有页排成一个环,指针顺时针走
要换页时:
if (当前页的 A bit == 1) { // 最近被访问过
A bit = 0; // 给第二次机会
指针前进;
} else { // A bit == 0,最近没访问
换出这一页;
}硬件支持:每次访存 MMU 自动把 A bit 置 1,软件只需清零。开销极低。
改进:考虑 D bit,优先换出"既没访问过又没写过"的页(不用写回磁盘,更快)。
| A | D | 含义 | 换出代价 |
|---|---|---|---|
| 0 | 0 | 最近没访问,没修改 | 最低,直接丢弃 |
| 0 | 1 | 最近没访问,改过 | 要写回 |
| 1 | 0 | 访问过,没改 | — |
| 1 | 1 | 访问过且改过 | — |
Linux 的做法:活跃的 inactive/active 双链表 + LRU 近似,相当复杂(要处理文件页、匿名页、共享页等不同情况)。
工作集模型
局部性:程序在一段时间内只访问一小部分页,这个集合叫工作集(Working Set)。
结论:
- 分配给进程的物理页 ≥ 工作集大小 → 缺页很少,正常运行
- 远小于工作集 → 抖动
这就是容量规划的依据:不是"总共用了多少内存",而是"活跃工作集有多大"。
CPU 调度
虚拟化的另一半:多个进程共享 CPU,谁先跑?
评价指标
| 指标 | 定义 | 期望 |
|---|---|---|
| 周转时间(Turnaround) | 完成时间 - 到达时间 | 小 |
| 响应时间(Response) | 首次被调度的时间 - 到达时间 | 小 |
| 公平性 | 各进程获得的 CPU 份额 | 均衡 |
| 吞吐量 | 单位时间完成的作业数 | 大 |
根本矛盾:周转时间和响应时间不可兼得。
- 优化周转 → 长作业优先跑完 → 短作业等很久(响应差)
- 优化响应 → 频繁切换 → 切换开销大,周转变差
调度算法
FIFO / FCFS
先来先服务。简单公平,但有护航效应(convoy effect):一个 100 秒的长任务在前面,后面三个 1 秒的任务要等 100 秒。
SJF(Shortest Job First)
最短作业优先。理论上周转时间最优(可证明),但需要预知运行时长,且长作业可能饿死。
STCF / PSJF(抢占式最短作业优先)
新来的作业如果更短,抢占当前作业。解决 SJF 的问题,但响应性仍可能差。
RR(Round Robin,时间片轮转)
每个进程跑一个时间片,然后轮到下一个。
- 响应时间好:
- 周转时间差(所有任务都被拉长)
- 时间片大小是核心权衡:
- 太小 → 上下文切换开销占比高
- 太大 → 退化成 FIFO,响应差
- 典型时间片:1~10 ms
RR 是公平性和响应性最好的简单算法,是分时系统的基石。代价是周转时间。
MLFQ(多级反馈队列)
现实中最广泛使用的思路(BSD、Solaris、Windows NT 的调度器都是它的变体)。
┌─────────────────────────────┐
│ Q0: 最高优先级 (时间片 8ms) │ ← 新进程进来
├─────────────────────────────┤
│ Q1: (时间片 16ms) │
├─────────────────────────────┤
│ Q2: (时间片 32ms) │
├─────────────────────────────┤
│ Q3: 最低优先级 (时间片 ∞) │ ← 长时间运行的 CPU 密集型
└─────────────────────────────┘规则:
- 优先级高的队列先跑
- 同优先级内 RR
- 新进程放最高优先级
- 用完时间片就降一级(时间片用完 = 这个进程是 CPU 密集的)
- 主动让出 CPU(如等 I/O)则保持优先级(交互型进程的特征)
- 定期优先级提升(boost),防止低优先级进程饿死
MLFQ 的精妙之处:不用预知任务类型,靠观察行为自动分类。
- 交互式进程(频繁 I/O,主动让出)→ 保持高优先级 → 响应快 ✓(正是我们想要的)
- CPU 密集型(跑满时间片)→ 降级 → 不影响交互响应 ✓
问题:可能被"欺骗"——进程在时间片快用完时故意做一个无用的 I/O,就能保持高优先级。解法是更精细的记账(记录进程在一个 boost 周期内累计用的 CPU 时间,而不只看单次)。
彩票调度(Lottery Scheduling)
概率公平:每个进程持有若干"彩票",每次随机抽一张决定谁跑。
- 天然支持按比例分配(给进程 2 倍彩票 = 2 倍 CPU)
- 实现简单(随机数生成)
- 缺点:随机性导致短期不公平,需要较长周期才收敛
Stride Scheduling
彩票调度的确定性版本:每个进程有一个 stride,每次调度后 pass += stride,选 pass 最小的。保证严格按比例。
公平分享调度(Fair-Share)
按用户而非进程分配 CPU。用户 A 有 10 个进程、用户 B 有 1 个,各得 50%。防止开一堆进程抢占资源。
CFS(Completely Fair Scheduler,Linux 默认)
思路:给每个进程记录"虚拟运行时间" vruntime,每次调度 vruntime 最小的。
vruntime += 实际运行时间 × (nice 权重倒数)- 用红黑树按 vruntime 排序,取最左节点,
nice值调整权重(不是直接调优先级)- 目标:每个进程获得完全均等的 CPU 时间
特点:没有固定时间片,而是追求"理想多任务处理器"的公平性。调度粒度由 sched_latency 动态决定。
多处理器调度
单队列 vs 多队列:
| 单队列(SQMS) | 多队列(MQMS) | |
|---|---|---|
| 结构 | 所有 CPU 共享一个就绪队列 | 每个 CPU 一个队列 |
| 优点 | 天然负载均衡 | 无锁竞争,缓存亲和性好 |
| 缺点 | 需要加锁,缓存亲和性差 | 可能负载不均,需要迁移 |
| 代表 | 早期 Linux O(1) | 现代 Linux、Windows |
缓存亲和性(Cache Affinity):进程最好固定在某个 CPU 上跑,因为它的缓存数据还在那儿。频繁迁移会不断 cache miss。
负载均衡:定期把任务从忙的 CPU 迁到闲的。代价是破坏亲和性——又是权衡。
常见坑
- 以为虚拟地址连续则物理地址也连续:不连续,虚拟地址空间是"假象"
- 忽略 TLB 的影响:热点数据结构超过 TLB 覆盖会显著变慢,benchmark 时容易出现"内存用多了反而慢"
- overcommit 导致 OOM:Linux 默认允许过量分配,多个进程同时真正用满时会被 OOM Killer 杀掉(通常杀掉占用最大的进程,未必是你希望的)
- swap 不是"备用内存":开始用 swap 说明内存已经不够了,性能断崖式下降
- 以为
malloc成功就有物理内存:只是分配了虚拟地址,真正 touch 时才缺页分配物理页 - 共享内存未同步:多个进程映射同一块内存,仍然需要自己加锁/同步