Base/Bound
段式保护的最简形式，但会带来外部碎片
CS152 · 第 9 课
这一课回答一个基础问题：多个程序如何安全地共享同一块物理内存？答案的历史演进——从裸机、到 base/bound 段式保护、再到分页——本身就是一部压缩版的操作系统内存管理简史，并直接引出 TLB 这一关键的性能优化结构。
在裸机（bare machine）上，程序看到的地址就是硬件的物理地址，没有任何转换；链接器/加载器（linker/loader）负责把位置无关的库模块重定位到实际的物理内存位置。一旦需要多道程序共享内存，就需要动态地址转换：基址寄存器（base register）提供位置无关性，界限寄存器（bound register）提供保护（防止程序互相踩踏），两者都只能在监管模式下访问。物理地址 = 基址 + 逻辑地址，同时逻辑地址要与界限寄存器比较，超出即触发越界异常。程序段和数据段可以使用独立的一对 base/bound 寄存器（这正是 2002 年 X1 之前所有 Cray 向量超级计算机采用的方案）。基址加法可以与（寄存器+立即数）的地址计算合并，用进位保留加法器（carry-save adder）实现，只比普通两数相加多花几个门延迟。
段式分配带来的外部碎片（真实场景推演）：假设内存里依次有 Job1（32K）、Job2（24K）、剩余 72K 空闲；Job3（64K）到来占用部分空闲空间，剩 8K 空闲；随后 Job2（24K）结束，留下一个 24K 的空隙——但因为 Job3 夹在中间，这个 24K 空隙和之前的 8K 空隙已经不连续；这时 Job4（32K）到达，尽管总空闲空间是 24K+8K=32K，却因为不连续而无法运行，必须先做内存压缩（compaction）才能腾出连续空间。这就是外部碎片（external fragmentation）的经典成因。
分页（paging）把程序生成的（虚拟/逻辑）地址拆成"页号 + 页内偏移"，用页表把每个固定大小的虚拟页映射到物理页帧——这样一个连续的虚拟地址空间就可以被打散存放在不连续的物理页中，从根本上解决了外部碎片问题（代价是内部碎片：页内没被实际用满的字节被浪费）。每个用户进程有自己私有的虚拟地址空间和页表；页表本身也存放在物理内存中（现代操作系统常常把页表放进内核自己的虚拟地址空间，使页表本身也能被换出）。
历史上应对"主存不够大"问题的几种早期做法：手动覆盖（manual overlays）——程序员显式地把代码/数据搬进搬出主存，繁琐且容易出错；软件解释编码（Brooker, 1960）——解释器自动检测被换出到磁鼓/磁盘的变量并取回，对程序员友好但效率低下。
1962 年 Atlas 计算机的按需分页：Tom Kilburn 提出的理念——只有当处理器（隐式地）需要某一页时，才把它从辅助存储调入主存，"主存成为辅助存储的一个缓存"。Atlas 的硬件组织：32 个物理页帧（每帧 512 字，字长 48 位），每帧配一个页地址寄存器（Page Address Register, PAR），存储 <有效页号, 状态>；有效页地址会与全部 32 个 PAR 比较，命中则正常访问，全部不中则触发缺页异常（同时保存当前部分执行指令的状态）。除了 32 页主存，还有 16 页 ROM（系统代码，不换出）、2 页辅助页（系统数据，不换出）、192 页磁鼓存储、以及若干磁带机作为更慢一级的存储。
线性页表大小 = 虚拟页数 × 每个页表项（PTE）字节数，其中虚拟页数 = 2^(虚拟地址位数 − 页内偏移位数)。
32 位地址空间例子：4KB 页、4 字节 PTE。页内偏移 = log2(4KB) = 12 位；页号位数 = 32 − 12 = 20 位 → 2^20 = 1,048,576 个 PTE，页表大小 = 2^20 × 4 字节 = 4,194,304 字节 = 4MB；覆盖整个虚拟地址空间需要 4GB 的交换空间——重新验算后与幻灯片给出的数字完全一致。
64 位地址空间例子（发现的数字不一致）：幻灯片给出"即使用 1MB 大页，也需要 2^44 个 8 字节 PTE（35 TB！）"。重新验算：页内偏移 = log2(1MB) = 20 位；页号位数 = 64 − 20 = 44 位 → 2^44 个 PTE，这一步与幻灯片一致。但页表总大小 = 2^44 × 8 字节 = 2^47 字节 ≈ 140.7 TB（十进制）或 128 TiB（二进制），与幻灯片写的"35 TB"相差约 4 倍。这是原始材料本身的一处数字不一致，我按实际输入重新计算后如实标注，而不是直接沿用幻灯片的"35 TB"。
无论具体数字如何，结论是一致的：即使用超大页，64 位地址空间的线性页表也大到不现实——这正是层级页表（hierarchical page table）存在的原因：把虚拟页号拆成多级索引（例如 RISC-V Sv32 用 p1/p2 两级各 10 位），每一级只在真正被使用到的地址区域才需要填充完整的下一级表，从而避免为整个巨大的虚拟地址空间预先分配一张完整的线性表。
TLB（Translation-Lookaside Buffer）是地址转换结果的缓存，用来避免每次访存都要走一遍（可能是多级的）页表：TLB 命中 ⇒ 单周期完成转换；TLB 缺失 ⇒ 需要走页表（page-table walk）来重新填充 TLB。
TLB Reach（TLB 覆盖范围）= TLB 项数 × 页大小（假设映射连续）。例：64 个 TLB 项、每项映射一个 4KB 页 → 64 × 4KB = 256KB（如果连续的话）——重新验算后与幻灯片一致。TLB 缺失的处理可以走软件路径（如 MIPS）或硬件路径（如 x86，硬件页表遍历器自动完成，如 SPARC v8 的三级页表遍历所示）。
问题 1：在课程给出的外部碎片场景中，为什么总共 32K 的空闲空间（24K + 8K）却不能满足 Job4 的 32K 需求？
问题 2：用 64 位虚拟地址、1MB 页大小、8 字节 PTE，重新计算线性页表的大小，结果与幻灯片给出的"35 TB"相比如何？
问题 3：层级页表（如 RISC-V Sv32 的两级页表）相比线性页表，主要解决了什么问题？
段式保护的最简形式，但会带来外部碎片
用固定大小的页解决外部碎片，代价是内部碎片
64 位地址空间下即使用大页也需要上百 TB，催生层级页表
缓存地址转换本身，TLB Reach = 项数 × 页大小
sp23/lecture_slides/L09_Address_Translation.pdf（UC Berkeley CS152/CS252A, Spring 2023, Sophia Shao）