Virtual Address Space

问题

物理现实中，不同进程和线程共享同一套硬件内存。如果所有程序都直接使用物理地址，一个 bug 就可能写坏别的进程或 OS。操作系统需要在不让每次 load/store 都陷入内核的前提下，同时提供保护、重定位和受控共享。

机制

address space 是程序可读写的地址集合，以及这些地址关联的状态。在 virtual address space 中，CPU 产生 virtual address，物理内存使用 physical address，中间由 MMU 做 translation。

32-bit 地址空间大小是 2^32 bytes，约 4GB；如果一个 32-bit integer 占 4 bytes，则可容纳 2^30 个整数。地址位数题默认按 byte-addressable 理解：k bit 地址能指向 2^k 个 byte，而不是 2^k 个 word。

虚拟地址空间是进程可见的完整地址命名空间，并不表示同等大小的物理内存已经驻留。实际驻留页数由映射和 residency 决定。访问某个地址还可能对应 memory-mapped I/O、segfault/abort，或触发 OS 介入。

三个目标

内存复用需要同时满足三项目标：

OS 对 I/O 可以通过 syscall 介入，对 CPU 可以通过 interrupt/preemption 介入，但不能对每次内存访问都 trap。load/store 太频繁，如果都走内核，普通指令执行会被系统调用级开销拖垮。因此结构必须分成 fast path 和 slow path：常见合法访问由硬件 MMU/TLB 直接翻译并检查权限，缺页、非法访问或权限错误才进入 OS。

Base and Bound

问题

Uniprogramming 中只有一个应用运行，没有 translation/protection，应用可以访问任意物理地址。Primitive multiprogramming 把多个程序同时放入物理内存，用 loader/linker 调整地址，但仍没有真正保护；一个程序的错误写入仍可能破坏其他程序或 OS。

机制

base and bound 是最简单的保护模型：

1
2
3
4
5
6
7

base  = 进程在物理内存中的起始地址
bound = 进程允许访问的范围

若 program_address < bound:
  physical_address = base + program_address
否则:
  fault

它给每个进程一个连续物理区间。context switch 时，OS 只需要切换当前进程对应的 base/bound 寄存器，硬件即可在每次访问时检查。

取舍

base and bound 很简单，但表达力有限。不同进程大小不同，长期运行会产生 external fragmentation；一个进程的 code/data/heap/stack 可能很稀疏，单个连续区间不够灵活；进程间共享 code segment 或 shared memory 也不自然。Segmentation 和 paging 分别从逻辑分段与固定大小映射入手解决这些限制。

Segmentation

机制

segmentation 把一个进程的地址空间分成多个逻辑段，例如 code、data、heap、stack 和 shared segment。每个 segment 都像一个独立的小地址空间，拥有自己的：

地址翻译流程是：

1
2
3
4
5
6
7

Virtual Address = segment number | offset

1. 用 segment number 查 segment table。
2. 检查 valid bit。
3. 检查 offset < limit。
4. 检查访问权限。
5. Physical Address = base + offset。

如果 offset >= limit，或权限不匹配，就触发 fault。每个段都有独立的 base and bound，因此 code/data/stack 可以分别放到物理内存不同位置。

取舍

segmentation 支持稀疏地址空间和共享段，也能自然表达 code 只读、heap 可写、stack 向下增长等语义。但段仍是变长块，长期运行会出现 external fragmentation；必要时可能搬移/compaction，代价很高。swapping 可以看作极端 context switch：为了腾出内存，把某些进程或段换到磁盘，之后再换回。

Paging

问题

segmentation 仍然要把变长段放进物理内存。即使总空闲空间足够，也可能因为没有足够大的连续空洞而放不下某个段。Paging 用固定大小的 page 和 frame 消除这种 external fragmentation。

机制

paging 把虚拟地址空间和物理内存都切成固定大小块：

地址翻译流程是：

1
2
3
4
5
6
7

Virtual Address = VPN | offset

1. CPU 产生 virtual address。
2. MMU 用 VPN 查 page table。
3. PTE 给出 PPN 和权限位。
4. 检查 valid/protection。
5. Physical Address = PPN | offset。

如果 page size 是 4KB，则 offset 需要 log2(4KB) = 12 bits。32-bit 地址下，VPN 有 32 - 12 = 20 bits，因此简单线性页表需要 2^20 个 PTE。

取舍

固定大小 page 让物理内存分配变简单：每个 frame 一样大，可用 bitmap/free list 管理，基本消除 external fragmentation。代价是最后一页可能用不满，产生 internal fragmentation；page size 太大浪费空间，太小则 PTE 数量和管理开销上升。

翻译流程

Segmentation

1
2
3
4
5

VA = seg | offset
查 seg table -> base, limit, valid, permission
valid? offset < limit? permission OK?
PA = base + offset
否则说明 fault 类型

写推导时要明确 fault 的原因：invalid segment、offset 越界，或权限不允许。

Paging

1
2
3
4

VA = VPN | offset
PTE[VPN] -> PPN + flags
valid/protection OK?
PA = PPN | offset

小例子：4-byte page 表示 offset 是 2 bits。虚拟地址 0x06 拆成 VPN=1、offset=2；如果 PTE[1] = PPN 3，物理地址就是 3 * 4 + 2 = 0x0E。

Page Sharing

不同虚拟页可以映射到同一个物理页，这就是 paging 支持受控共享的关键。典型用途包括：

共享不是复制物理页，而是多个 PTE 指向同一个 PPN。权限可以不同，例如同一个物理页在一个进程中只读，在另一个进程中可执行。若 shared memory 中直接存指针，最好把共享页映射到各进程地址空间的同一虚拟位置，否则指针值在另一个进程中可能没有相同含义。

Simple page table 的 PTE 数量由 virtual page 总数决定，稀疏地址空间中会留下大量 invalid/null PTE。Multi-level page table 只为实际使用的地址范围分配下层页表，从而压缩这些空洞。