操作系统——内存虚拟化

本文是操作系统导论内存虚拟化部分的笔记。

发展历史

早期的计算机更像一个厂房，既昂贵又占地方，还需要配有专门的操作员，很不友好。那时的操作系统还只是一些库，用户进程几乎独占内存。

后来开始有了小型机和个人计算机，人们对计算机要求的也不断提高，需要让计算机变得更易于使用，由此发展出了多道程序和时分共享。在多道程序中，多个进程被分配给计算机进行处理，操作系统会在一个进程休眠时切换到别的进程，这样可以有效利用计算机 CPU。时分共享强调了交互性，进程之间可以迅速切换，即使进程没有执行完毕或者休眠，这样多个用户就可以同时共享一台计算机，可以快速获得计算机的响应。

为了实现时分共享，一种粗糙的方式是让进程独占内存一小会，切换时保存到磁盘上。但这种方式效率太低了。为了更有效率地进行时分共享，需要给每个进程分配一部分内存。由于多个进程同时驻留在内存中，需要保护一个进程的内存不被其他进程读取或修改。

基本概念和虚拟化目标

地址空间是对物理内存的抽象，不同的进程有不同的物理内存进行隔离，但有相同的地址空间。地址空间向进程隐藏了物理细节，好像进程独占了内存空间。进程空间是内存虚拟化的关键，通过地址空间和真实物理内存间的映射关系，用户进程不需要直接访问物理内存。

进程的地址空间包含运行它所需要的所有状态，包括代码、静态区、堆和栈。代码即运行程序的指令。静态区保存初始化变量。栈负责保存函数调用信息，包括局部变量、函数参数和返回值。堆用于管理用户动态分配的内存。

虚拟内存的目标：

透明化。用户进程感知不到这种虚拟化，也无需为这种工作编写额外的代码，负责虚拟化的一切工作由操作系统和硬件在幕后完成。
效率。时空效率，不能太慢以及消耗太多额外的内存。
保护。进程之间相互隔离，不能进程不可以访问别的进程和操作系统的内存。

内存操作接口与空闲空间管理

在介绍时下内存虚拟化的机制之前，先了解一下操作系统提供的内存操作接口。

对于上文中地址空间的栈部分，通常由编译器来隐式管理，进行申请和释放。所以栈内存又被称为自动内存。我们更关注需要显式管理的内存，既堆内存。操作系统提供了 malloc 和 free 两个系统调用，分别用于分配和释放内存。一些语言提供了垃圾回收机制，在自动申请内存，并在不再使用时自动释放。而使用 C 程序而言，需要自己来管理堆内存，因此需要注意以下问题：

没有正确地分配内存，包括不分配内存就使用、分配的内存不够用。
分配内存后使用不当。如没有填写值就去读取，导致读到一些未知的数据。
错误释放。忘记释放、过早释放、反复释放和错误释放了地址

malloc 和 free 是操作系统空闲空间管理模块提供的接口。底层会维护一个空闲列表，分配和释放意味着对这个列表进行分割和合并。分配内存时有一些分配策略：

最优匹配。找出适合的空闲块中最小的一个。性能代价高。
最差匹配。找出最大的一个。导致过量的碎片，性能代价高。
首次匹配。找到第一个足够大的。性能佳，碎片少。
下次匹配。类似于首次匹配，需要维护一个指针，指向上次查找结束的位置。
离空闲列表等。程序经常分配一下固定大小的内存，将这部分单独处理，其他部分使用通用的分配程序。
伙伴系统。以二分地方式进行分配与合并。分配的大小可能超出实际请求的大小，造成内部碎片。

地址转化

地址转化技术将虚拟的地址转化为实际的物理地址。地址转化依赖于硬件支持，以保证高效性。除此之外，操作系统需要在必要的时候介入，以管理整个内存。

我们假设用户的地址空间映射在物理内存上是连续的，地址空间小于物理内存，并且每个地址空间的大小是一样的。下面介绍地址转化首次在时分机器上的实践。

采用的方式是基址加界限机制，又称为动态重定位。CPU 中有一个负责地址转化的内存管理单元（MMU），包含两个寄存器：基址寄存器和限制寄存器。寄存器用来记录地址空间的起始物理地址，使用它可以将虚拟地址转化为物理地址。限制寄存器提供了访问保护，当前进程访问的地址超出这个界限时，CPU 将触发异常。

物理地址 = 基址 + 虚拟地址

动态重定位机制依赖于硬件和软件的支持。对于硬件：

特权模式
基址/界限寄存器
修改基址/界限寄存器的特权指令
虚拟地址转化以及检查是否越界
注册异常程序以及触发异常

对于操作系统：

内存管理：启动时为进程分配内存空间，设置基址/界限寄存器；终止时回收空间；管理空闲列表。
基址/界限管理：上下文切换时，保存和恢复基址/界限寄存器。数据可能放在 PCB 中。PCB 位于内核中。
异常处理：操作系统向硬件提供异常处理程序，当进程越界发生时，CPU 触发异常，运行异常处理程序，操作系统终止进程并回收内存。

这种动态重定位技术存在空间浪费问题。进程的地址空间占有固定的槽块，而进程一开始可能用不了这么大，这会造成内部碎片。为了解决这个问题，引出了分段。

分段

上一节处理的方式中，堆与栈之间有一大块空闲区域，造成了内存的浪费。为了解决这个问题，引入了分段的概念。这时需要多个基址/界限寄存器，用来对应地址空间的每个逻辑段，这里仅分为三部分：代码/堆/栈。分段机制将不同的段分到不同的物理内存区域，避免了未使用部分对空间的浪费。

物理地址 = 段的基址 + 虚拟地址 - 段在地址空间内的偏移 = 段的基址 + 段内偏移

给定一个虚拟地址，如何知道它处于哪个段，以及段内偏移量是多少呢？

显式方法：因为有三个段，可以用虚拟地址的前两位表示段区域，其余位表示段内偏移。
隐式方法：硬件通过地址的产生方式来判断属于哪个段。

段寄存器除了记录基址和段大小外，还需要记录：

是否反向增长：栈和代码、堆不同，虚拟地址会反向增长，因此计算方式会有不同
保护：例如对于代码段，由于是可读的和可执行的，不同的进程会共享这个段。因此会有物理内存中的一个段被多个进程使用的情况。

上述所讲的段都是粗粒度的，也有一些早期系统使用更细粒度的段，来更高效地利用内存。更细粒度的段也需要硬件进一步地支持。

分段带来的问题：

每个段的数据都需要保存和恢复
每个段的大小可能不同，物理空间会存在许多空闲的小洞，因为不够大而无法非配给段，既出现外部碎片

如何应对分段造成的外部碎片呢？有以下方式：

紧凑物理内存。重排原来的段，同时要改变寄存器中的值，指向新的地址。但这种方式成本很高，需要占用大量 CPU 时间。
更好的空闲列表管理算法。有多种算法，可以试图降低外部碎片。

分页

分段将地址空间划分成不同长度的切片，这会造成外部碎片。另一种考虑是将地址空间划分为固定长度的分片，称之为分页。物理内存被划分为定长槽块，称之为页帧，每个页帧包含一个虚拟的内存页。

每个进程拥有一个名为页面的数据结构，记录地址空间中的虚拟页放在物理内存中的位置。虚拟地址分为页面号（VPN）和偏移量（offset）两部分。通过 VPN 可以找到页表中的页表项（PTE），PTE 中记录着物理帧号（PFN）。

物理地址 = PFN & offset

PTE 中包含 PFN 和一些位标示。这些位标示包括：有效位、保护位、存在位和访问位等。

这种线性页表的分页方式带来两个问题：

太大了。页表存储在操作系统内存区，32位系统 4kb 的页，每个页表的大小为 4M。
太慢了。需要在也表中提取 PTE，开销较大。

因此需要优化目前的分页。

为了优化性能，使用了用于缓存的地址旁路缓冲存储器（TLB），先从 TLB 中根据 VPN 查找 PFN，查不到时再去查页表。一个 TLB 项包含：VPN ｜ PFN ｜其他位｜ ASID。其中 ASID 是地址空间标示符，可以看作是进程标示符。使用 ASID 可以让 TLB 缓存不同进程的地址空间映射。缓存都会有缓存替换策略问题要考虑。TLB 常使用两种策略：LRU 和随机。

为了优化空间问题：

使用更大的页。更大的页意味着页表项会减少，从而降低页表大小。但大的页会带来内部碎片问题。
分段和分页的混合：地址空间分为多个段，每个段有一对基址/界限寄存器，每个段都有一个叶表。这样只会为使用的页分配页表空间。
多级页表：增加了页目录。页表按照页划分单元，通过页目录可以找到页表项或者页表项所在的页全部无效，未分配空间。
页表交换到磁盘。前面一直认为页表放在内核的物理内存中，而有的系统允许将页表放在内核的虚拟内存中，在内存紧张时可以交换到磁盘中。

超越物理内存

前面假设地址空间小于物理内存，所有进程的页都放在物理内存中。但我们想提高系统的易用性，在编写程序时不必担心空间不够的问题，这时需要支持更大的地址空间，而不受物理内存的限制。实现方式是将目前没有在用的那部分地址空间在硬盘中存起来。这时，内存中的页是磁盘中页的缓存。

在磁盘上开辟一段空间，用于物理页的移入和移出，既交换空间。在通过虚拟地址查找真实页时，若 TLB 未命中，则去页表中查询，通过 PTE 中的存在位判断该页是在内存中还是在磁盘中。若是后者，则会触发页错误。操作系统负责处理页错误，根据 PTE 中的存储的磁盘地址，读取磁盘中的页加载到物理内存，并更新 PTE 和 TLB。若内存不够用，则使用页替换策略，将某些页交换出去来腾出空间。交换策略的选择会影响到性能。并非内存满了才会执行交换，操作系统会设置高（HW）低（LW）水位线，当低于 LW 个页可用时，负责内存释放的线程（内核级线程）会执行。

下面介绍页替换策略：

FIFO，先入的页进行交换，实现起来简单。可能剔除重要的页。
随机，随机找一个页进行进行替换：有运气的成分。可能剔除重要的页。
LRU，最不经常使用的进行替换。考虑了时间的局部性。相比前两者有更好地表现，不会剔除重要的页。
近似 LRU：时钟算法等，解决了性能问题：查到最不重要的页比较困难，但查到接近最不重要的页也可接受。

还有一个内存过载问题，进程使用的内存超出了物理内存，系统将不断进行换页，这时系统可能会杀死这个进程。

总结

最早，进程对于内存集合没有抽象，一个进程独占内存。但为了易用性，多个进程间需要共享内存。引入了地址空间的概念，进程通过地址空间查找物理内存。然后有一系列的机制：

基址/界限：有内部碎片问题。
分段：解决了内部碎片问题，外部碎片问题。
分页：解决了碎片问题，但存在性能以及线性页表占空间问题。
优化后的分页：性能通过 TLB 缓存解决；空间通过多级页表等方式解决。
交换策略：地址空间的大小可以超出物理空间，通过交换来解决。