重学操作系统：内存虚拟化

内存是操作系统需要管理的另一重要资源。同管理 CPU 类似，操作系统在管理物理内存时想要达到以下目的：

• 共享：多个进程可以同时使用物理内存，每个进程都感觉自己在独占内存空间。
• 安全：共享带来的另一个问题就是安全，操作系统要隔离不同进程的内存访问，确保它们访问的是属于进程本身的物理内存，而不可以随意读写其它进程的内存空间。
• 高效：尽可能减少时间空间资源的占用，以更高效的方式管理内存。

为了达成以上目的，需要在物理内存上提供一层虚拟（或者叫抽象），进程在访问地址空间内某个内存单元时，进程感觉自己在独占地址空间，而感觉不到物理内存上还运行着操作系统和其它进程。这个抽象叫 地址空间，是进程看到的系统中的内存。最简单的地址空间可以分为 4 类：

• 代码区
• 栈
• 堆
• 未分配

进程运行时生成的地址称为 虚拟地址，而物理内存的地址称为 物理地址。显然，想要为进程提供地址空间的抽象，必须在进程运行时将虚拟地址转换为物理地址，以访问真正的物理内存。这一机制称为：地址转换。地址转换一般需要硬件的参与，因此也称为：基于硬件的地址转换。

1. 地址转换

现代 CPU 和操作系统的地址转换机制比较复杂，但是我们从最简单的假设开始，即：进程地址空间固定且小于物理内存。在这种情况下，硬件需要提供以下功能以为进程提供虚拟地址空间：

• CPU 需要有特权模式和用户模式。
• CPU 的内存管理单元需要提供两个寄存器：基址寄存器 和 界限寄存器。
• CPU 提供修改基址/界限寄存器的特权指令。

操作系统同样也需要额外的工作，以为进程提供地址空间的抽象：

• 创建进程时，OS 要为进程的地址空间分配实际的空闲物理内存，并在基址/界限寄存器记录。
• 进程终止时，OS 要回收进程占据的物理内存，加入空闲列表。
• 进程控制块中额外记录进程的基址/界限寄存器值，用于上下文切换。
• OS 提供异常处理程序，处理进程越界访问内存。

有了改基址/界限寄存器后，物理地址可以由以下方式计算出： \[ \text{physical address} = \text{base register} + \text{virtual address} \] 在 进程地址空间固定且小于物理内存 这种最简单的假设下，上述硬件机制和 OS 提供的功能即可为进程提供虚拟的地址空间。但是，由于进程空间大小固定，每次 OS 都要为进程分配固定大小的物理内存空间，会导致 内部碎片（具体来说：堆和栈直接可能存在大量未使用区域）。下面对这种一对基址/界限寄存器的机制进行泛化，得到分段机制，以改善这个问题。

2. 分段

分段就是泛化的基址/界限。这一机制在 CPU 的内存管理单元（MMU）中引入多个基址/寄存器对，表示地址空间内的每个逻辑段（代码段、栈、堆）。

引入分段机制后，对于给定的虚拟地址，我们首先要根据虚拟地址的高若干位，确定属于哪个段，进而去访问对应的基址/界限寄存器。

另外，由于不同段的地址增长方向不一样，MMU 中还需要额外的位来标记地址增长方向。为了 共享代码，还需要额外的位标识每个段的读、写、执行权限。

不过，由于不同段的大小不同，OS 在分配段空间管理物理内存时，很容易导致 外部碎片（内存被划分为很多小的空闲区域，无法满足一次大的内存分配申请）。

3. 空闲空间管理

在堆上管理空闲空间的数据结构通常称为 空闲列表。具体而言，可以通过链表形式的数据结构，链表每个节点记录连续空闲空间的起始位置和大小。

分配内存空间的一个重要问题就是：选择哪个空闲区域进行分配，具体有以下策略：

• 最优匹配
• 最差匹配
• 首次匹配
• 下次匹配：不从列表开始查找，而是从上一次查找结束的位置开始查找

除了上述方式，还有其它的内存分配方式：

• 分离空闲列表：如果程序经常申请一种或几种固定大小的内存空间，就用一个独立的列表只管理这样大小的对象；其它大小的请求都交给更通用的内存分配程序。
• 伙伴系统：Linux 采用。

4. 分页

分页的核心思想是：将物理内存划分为固定大小，称为：页帧（page frame）。进程的虚拟内存空间同样划分为固定大小的页，并将虚拟页放在某个物理页帧中。为了记录地址空间的每个虚拟页放在物理内存中的位置，OS 通常为 每个进程 保存一个数据结构，称为：页表（page table），用于将虚拟地址空间的虚拟页转换为物理内存的页帧。

将虚拟地址转换为物理地址过程如下：

• 将虚拟地址分为两部分：高位的虚拟页面号（Virtual Page Number，VPN）和低位的页内偏移量（offset）；
• 在页表中检索（为了找到页表在物理内存中位置，硬件还需要提供一个 页表基址寄存器），找到虚拟页面号对应的物理页号（Physical Page Number，PPN）；
• 用 PPN 替代 VPN，生成物理地址。

页表的最简单存储方式就是利用一个连续的数组，每个数组的下标 idx 就表示虚拟页面号 VPN，数组存储的内容就是物理页号 PPN。以典型的 32 位虚拟地址空间，页面大小为 4 KB，每个页表项（Page Table Entry，PTE）假设为 4 字节，则存储每个进程的页表需要占用 \(2^{20}\times 4 \text{ Byte} = 4 \text{ MB}\)。如果系统内运行着 100 个进程，则仅仅存储这些进程的页表就需要 400 MB，导致占用大量的物理内存。当采用此种连续数组方式存储页表时，进程访问内存实际过程如下伪码描述：

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE))
PTE = AccessMemory(PTEAddr)
offset = VirtualAddress & OFFSET_MASK
PhyAddr = (PTE.PPN << PPN_SHIFT) | offset
Register = AccessMemory(PhyAddr)

可见，由于引入了进程地址空间这一虚拟层，进程执行时如果要访问一个内存位置，必须经过两次物理内存访问，这会导致进程执行速度变慢。为了解决这一问题，引入地址转换旁路缓存存储器（Translation Lookaside Buffer，TLB）。

5. 快速地址转换：TLB

TLB 类似于 CPU 中的缓存，只不过 CPU 缓存的是指令或数据，而 TLB 缓存的是页表项，以减少虚拟地址转换为物理地址的开销。我们希望通过 TLB，让绝大多数的地址转换都能够命中 TLB 缓存，在极快的时间内获得虚拟地址对应的物理地址，从而提升进程运行效率；而不是通过访问页表获取物理地址，导致多了一次内存访问开销。

由于是缓存，自然就引出了一个问题：如何处理 TLB 未命中的情况？可以由硬件自动处理或者操作系统通过异常处理程序进行处理。处理的具体操作自然就是从页表中读取虚拟地址对应的物理地址，并插入 TLB 中，然后重试导致 TLB 未命中的指令。

TLB 存储的每项记录形式如下： \[ \text{VPN } | \text{ PFN } | \text{ 其他位} \] 其他位中通常包括有效位，用于表示该项是否为有效的地址映射。

引入 TLB 后，在进行进程的上下文切换时，必须对 TLB 内容标记无效，也就是进行清空 TLB 操作。当然，也可以在 TLB 中记录进程标识符 pid，即可在不同进程间共享 TLB。

6. 减小页表空间

前文提到，分页的引入带来了两个问题：

• 页表过大，占用过多物理内存。
• 导致两次访问内存，降低执行效率。

第二个问题通过 TLB 可以极大改善，现在我们着手解决第一个问题。

这里，我们就忽略比较简单的增大页面大小、分段分页结合的方法，它们虽然都能改善页表过大的问题，但是也会引入内部碎片、外部碎片等问题。我们直接来看多级页表这一解决方案。

多级页表的核心思想是：将页表也按照页大小进行划分，如果整页的页表项（PTE）无效，就完全不分配该页的页表。为了追踪页表的页是否有效（以及如果有效，它在内存中的位置），需要使用名为页目录（page directory）的新结构，这一新结构可以看作二级页表。在二级页表中，页目录为每页页表包含了一项。它由多个页目录项（Page Directory Entry，PDE）组成。PDE 至少拥有有效位和页帧号。PDE 中的有效位指的是该项指向的页表中是否至少有一个页是有效的。

和二级页表思想类似，可以引入三级页表等。多级页表形成了一个树结构。

7. 物理内存与硬盘的交换

当物理内存不够时，OS 可以利用硬盘上的一部分空间（交换空间），用于物理页的移入和移出（very similar to buffer pool in DBMS）。为了进行正确的移入移出操作，OS 必须能够记录给定页在硬盘中存放的地址。

为了能够将页换入硬盘，必须在页表项中添加一个位，用于判断页是否在物理内存中，称为 存在位。如果进程指向时发现某个页存在位为 0，说明该页在硬盘中，产生一个页错误，需要操作系统接管处理。操作系统需要知道这一页面存储在硬盘的哪里？这一信息通常记录在页表中。OS 通过页表项获取页面在磁盘的位置，进行 IO 操作。IO 操作完成后，OS 将存在位更改为 1，并在更新页表项的 PFN 字段以记录新获取页在物理内存中的位置，并重试指令。

当物理内存满了时，需要选取页面交换到硬盘内，这叫做页面替换策略。可能的页面替换策略有以下几种：

• 最优替换策略：需要事先知道页面访问序列，由于很难实现，实际很少采用，仅作为最佳策略和其他方法对比。
• FIFO（先入先出策略）
• 随机
• LRU（最近最少使用，Least Recently Used）：替换最近使用最少的页。
• LFU（最不经常使用，Least Frequently Used）：替换最不经常使用的页。
• 时钟算法：系统中所有页放在一个循环列表中，时钟指针初始指向某个页。当必须进行页替换时，OS 检查当前时钟指针指向的页的使用位是 1 还是 0。如果是 1，则说明当前页面最近被使用过，因此不适合被替换。因此将当前页使用位设置为 0，指针后移。直到找到第一个使用位为 0 的页，进行换出。