3 虚拟化

虚拟化的目标是让每个进程以为自己独占资源。分两条线:

  • CPU 虚拟化 → 进程(见总览章节)
  • 内存虚拟化 → 虚拟地址空间(本章主体)

地址空间

什么是地址空间

**地址空间(Address Space)**是进程看到的内存视图:

0xFFFFFFFF ┌──────────────┐ 高地址
           │     栈       │  向下增长,函数调用、局部变量
           │      ↓       │
           │              │
           │      ↑       │
           │     堆       │  向上增长,malloc/new
           ├──────────────┤
           │   BSS        │  未初始化的全局/静态变量
           ├──────────────┤
           │   Data       │  已初始化的全局/静态变量
           ├──────────────┤
           │   Text       │  代码(只读)
0x00000000 └──────────────┘ 低地址

关键性质:每个进程的地址空间是独立的、从 0 开始的、连续的。

// 两个进程打印同一个指针值,指向的是不同的物理内存
printf("%p\n", &x);   // 都是 0x7ffd4a3b8f2c,但物理地址不同

为什么需要虚拟化内存

  1. 隔离:进程 A 不能读写进程 B 的内存(安全和可靠性的基石)
  2. 便利:每个程序都从地址 0 开始链接,不用考虑别的程序占哪里
  3. 效率:可以超额分配(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(2122^{12}):

  • 低 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 页 →2202^{20} = 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 TLBL2 TLB
条目数64~128512~1536
命中时间~1 周期~10 周期
未命中惩罚几十~几百周期

现代 CPU 还有专门的 iTLB(指令)和 dTLB(数据)。

TLB 的一致性问题

关键问题:页表变了,TLB 里的旧条目怎么办?

场景:

  1. 上下文切换:换进程 = 换页表 = TLB 里的映射全部失效

解法:

  • 简单粗暴:切换时清空 TLB(flush)。代价:切回来后要重新热身
  • 优化:给 TLB 条目加 **ASID(Address Space ID)**标签,切换时不用清,靠标签区分
  1. 页被回收: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,优先换出"既没访问过又没写过"的页(不用写回磁盘,更快)。

AD含义换出代价
00最近没访问,没修改最低,直接丢弃
01最近没访问,改过要写回
10访问过,没改—
11访问过且改过—

Linux 的做法:活跃的 inactive/active 双链表 + LRU 近似,相当复杂(要处理文件页、匿名页、共享页等不同情况)。

工作集模型

局部性:程序在一段时间内只访问一小部分页,这个集合叫工作集(Working Set)。

W(t,τ)=在时间区间 (t−τ,t) 内被访问过的页的集合W(t, \tau) = \text{在时间区间 } (t-\tau, t) \text{ 内被访问过的页的集合}

结论:

  • 分配给进程的物理页 ≥ 工作集大小 → 缺页很少,正常运行
  • 远小于工作集 → 抖动

这就是容量规划的依据:不是"总共用了多少内存",而是"活跃工作集有多大"。

CPU 调度

虚拟化的另一半:多个进程共享 CPU,谁先跑?

评价指标

指标定义期望
周转时间(Turnaround)完成时间 - 到达时间小
响应时间(Response)首次被调度的时间 - 到达时间小
公平性各进程获得的 CPU 份额均衡
吞吐量单位时间完成的作业数大

根本矛盾:周转时间和响应时间不可兼得。

  • 优化周转 → 长作业优先跑完 → 短作业等很久(响应差)
  • 优化响应 → 频繁切换 → 切换开销大,周转变差

调度算法

FIFO / FCFS

先来先服务。简单公平,但有护航效应(convoy effect):一个 100 秒的长任务在前面,后面三个 1 秒的任务要等 100 秒。

SJF(Shortest Job First)

最短作业优先。理论上周转时间最优(可证明),但需要预知运行时长,且长作业可能饿死。

STCF / PSJF(抢占式最短作业优先)

新来的作业如果更短,抢占当前作业。解决 SJF 的问题,但响应性仍可能差。

RR(Round Robin,时间片轮转)

每个进程跑一个时间片,然后轮到下一个。

  • 响应时间好:Tresponse=(N−1)×时间片T_{response} = (N-1) \times \text{时间片}
  • 周转时间差(所有任务都被拉长)
  • 时间片大小是核心权衡:
    • 太小 → 上下文切换开销占比高
    • 太大 → 退化成 FIFO,响应差
  • 典型时间片:1~10 ms

RR 是公平性和响应性最好的简单算法,是分时系统的基石。代价是周转时间。

MLFQ(多级反馈队列)

现实中最广泛使用的思路(BSD、Solaris、Windows NT 的调度器都是它的变体)。

┌─────────────────────────────┐
│ Q0: 最高优先级 (时间片 8ms)  │  ← 新进程进来
├─────────────────────────────┤
│ Q1: (时间片 16ms)            │
├─────────────────────────────┤
│ Q2: (时间片 32ms)            │
├─────────────────────────────┤
│ Q3: 最低优先级 (时间片 ∞)    │  ← 长时间运行的 CPU 密集型
└─────────────────────────────┘

规则:

  1. 优先级高的队列先跑
  2. 同优先级内 RR
  3. 新进程放最高优先级
  4. 用完时间片就降一级(时间片用完 = 这个进程是 CPU 密集的)
  5. 主动让出 CPU(如等 I/O)则保持优先级(交互型进程的特征)
  6. 定期优先级提升(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 排序,取最左节点,O(log⁡n)O(\log n)
  • 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 时才缺页分配物理页
  • 共享内存未同步:多个进程映射同一块内存,仍然需要自己加锁/同步