操作系统笔记：内存虚拟化
亿网程序自身并不需要关心自己的数据及代码存在哪，并且对程序来说，内存看上去是连续且独占的。当然事实肯定不是如此，而这背后就是操作系统的功劳 —— 内存虚拟化。本篇文章就介绍操作系统是如何实现虚拟内存系统的。
操作系统提供了一个易用的物理内存抽象：地址空间。地址空间是运行的程序看到的系统中的内存。
一个进程的地址空间包含运行的程序的所有内存状态。每次内存引用时，硬件都会进行地址转换，将应用程序的内存引用重定向到内存中实际的位置。
为了完成地址转换，每个 CPU 需要两个硬件寄存器：基址 (base) 寄存器和界限 (bound) 寄存器。程序的起始地址存放在基址寄存器。进程产生的所有内存引用，都会被处理器通过以下方式转换成物理地址：
界限寄存器的作用在于，确保了进程产生的所有地址都在进程的地址 “界限” 中。
操作系统和硬件支持结合，实现了虚拟内存，而为了实现虚拟内存，操作系统所需要做的工作如下：
为了解决连续内存的浪费问题，操作系统引入了分段。
具体来说，在 MMU 中引入不止一个基址和界限寄存器对，而是给地址空间内的每个逻辑段一对。一个段只是地址空间里的一个连续定长的区域，在典型的地址空间里有 3 个逻辑不同的段：代码、栈和堆。
分段机制使得操作系统能够将不同的段放入不同的物理内存区域，从而避免了虚拟地址空间中的未使用部分占用物理内存。如下图所示：
而如何从一个虚拟地址中识别出对应的段是哪一个，主要有两个方法：
分段带来一些新的问题。
第一个是段寄存器的值必须被保存和恢复。每个进程都有自己独立的虚拟地址空间，操作系统必须在进程运行前，确保这些寄存器被正确的赋值。
第二个也是更重要的问题是分段会带来外部碎片。空闲空间被分割成不同大小的小块，成为碎片，后续的请求可能会失败，因为没有一块足够大的连续空闲空间，即使这时总的空闲空间超出了请求的大小。
解决外部碎片的一种方法是紧凑物理内存，重新安排原有的段，但内存紧凑成本很高；另一种简单的方法是使用空闲列表（free-list）管理算法，试图保留大额内存用于分配。目前已经有数百种方法，包括经典算法：
还有一些改进策略：
然而不管算法多么精妙，外部碎片仍然存在，无法完全消除。唯一真正解决的办法就是完全避免这个问题，永远不要分配不同大小的内存块，这也是分页被引入的原因。
分页不是将一个进程的地址空间分割成几个不同长度的逻辑段 (即代码、堆、段)，而是分割成固定大小的单元，每个单元称为一页。相应的，我们把物理内存看成是定长槽块的阵列，叫做页帧。每个页帧包含一个虚拟内存页。
操作系统为每个进程保存一个数据结构，称为页表。主要用来为地址空间的每个虚拟页面保存地址转换，从而让我们知道每个页在物理内存中的位置。
虚拟地址分成两个组件：虚拟页号（VPN）和页内的偏移量（offset）
通过虚拟页号，我们现在可以检索页表，找到虚拟页所在的物理页面。因此，我们可以通过用物理帧号替换虚拟页号来转换此虚拟地址，然后将载入发送给物理内存。偏移量保持不变，因为偏移量只是告诉我们页面中的哪个字节是我们想要的。如下图所示：
简言之，页表就是一种数据结构，用于将虚拟地址 (或者实际上，是虚拟页号) 映射到物理地址 (物理帧号)。因此任何数据结构都可以采用，最简单的形式成为线性页表，就是一个数组。操作系统通过虚拟页号 (VPN) 检索该数组，并在该索引处查找页表项 (PTE) ，以找到期望的物理帧号 (PFN)。
对于每个内存引用，分页都需要我们执行一个额外的内存引用，以便首先从页表中获取地址转换。额外的内存引用开销很大，而且在这种情况下，可能会使进程减慢两倍或更多。
分页虽然看起来是内存虚拟化需求的一个很好的解决方案，但这两个关键问题必须先克服。
为了解决页表内存开销过多的问题，Multics 的创造者提出了分页和分段结合的想法。解决方法是，不是为进程的整个地址空间提供单个页表，而是为每个逻辑分担提供一个页表。
在分段中，有一个基址寄存器用来存放每个段在物理内存中的位置，还有一个界限寄存器用来存放该段的大小。在这里依然使用这些结构，不过，基址不是指向段本身，而是保存该段的页表的物理地址；界限寄存器用来指示页表的结尾（即它有多少有效位）。
这种杂合方案的关键区别在于，每个分段都有界限寄存器，每个界限寄存器保存了段中最大有效页的值。例如，如果代码段使用前3个页，则代码段页表将只有3个项分配给它，并且界限寄存器将被设置为3。与线性页表相比，杂合方法实现了显著的内存节省，栈和堆之间未分配的页不再占用页表中的空间 (仅将其标记为无效)。
而这种方法的弊端在于，一是它仍然要求使用分段，如果有一个大而稀疏的堆，仍然可能导致大量的页表浪费；二是外部碎片再次出现，尽管大部分内存是以页表大小单位管理的，但页表现在可以是任意大小 (PTE 的倍数)。
多级页表也是用来解决页表占用太多内存的问题，去掉页表中的所有无效区域，而不是将它们全部保留在内存中。多级页表将线性页表变成了树。
首先，将页表分成页大小的单元；然后，如果整页的页表项 (PTE) 无效，就完全不分配该页的页表。为了追踪页表的也是否有效 (以及如果有效，它在内存中的位置)，使用了名为页目录的新结构。页目录可以告诉你页表的页在哪里，或者页表的整个页不包含有效页。
下面的图展示了一个例子，左边是经典的线性页表，即使地址空间的大部分中间区域无效 (即页表的中间两页)，我们仍然需要为这些区域分配页表空间；右边是一个多级页表，页目录仅将这些区域分配页表空间 (即第一个和最后一个)，页表的这两页就驻留在内存中。因此，我们可以形象地看到多级页表的工作方式：只是让线性页表的一部分消失 (释放这些帧用作其他用途)，并用页目录记录页表的哪些页也被分配。
在一个简单的两级页表中，页目录为每页页表包含了一项。由多个页目录项 (PDE) 组成，PDE 至少拥有有效位 (valid bit) 和页帧号 (PFN)，类似于 PTE。但这个有效位的含义稍有不同：如果 PDE 项是有效的，则意味着该项指向的页表 (通过 PTE) 中至少有一页是有效的，即在该 PDE 所指向的页中，至少一个 PTE，其有效位被设置为 1。如果 PDE 项无效，则 PDE 的其余部分没有定义。
多级页表分配的页表空间，与你正在使用的地址空间内存量成比例，因此通常很紧凑，并且支持稀疏的地址空间。
如果仔细构建，页表的每个部分都可以整齐的放入一页中，从而更容易管理内存。有了多级页表，我们增加了一个间接层，使用了页目录，指向页表的各个部分，这种间接方式，让我们能够将页表页放在物理内存的任何地方。
多级页表是有成本的，在 TLB 未命中时，需要从内存加载两次，才能从页表中获取正确的地址转换信息 (一次用于页目录，另一次用于 PTE 本身)，而用线性页表只需要一次加载。
另一个明显的缺点是复杂性。无论是硬件还是操作系统来处理页表查找，这样做无疑都比简单的线性页表查找更复杂。
为了解决分页所带来的额外内存访问的问题，操作系统需要一些额外的帮助，因此引入了地址转换旁路缓冲寄存器 (TLB)，就是频繁发生的虚拟到物理地址转换的硬件缓存。
首先从虚拟地址中提取页号 (VPN)，然后检查 TLB 是否有该 VPN 的转换映射；
如果有，我们就有了 TLB 命中，意味着 TLB 有该页的转换映射，就可以从相关的 TLB 项中取出页诊号 (PFN) 与原来虚拟地址中的偏移量组合成期望的物理地址；
如果没有 (TLB 未命中)，在不同的系统中表现不一样：
TLB 中包含的虚拟到物理地址映射只对当前进程有效，对其他进程是没有意义的。所以在上下文切换时，TLB 的管理有两种方法。
如果是软件管理 TLB 的系统，可以在发生上下文切换时，通过一条显式指令来完成；如果是硬件管理 TLB 系统，则可以在页表基址寄存器内容发生变化时清空 TLB。不论哪种情况，情况操作都是把全部有效位置为 0，本质上清空了 TLB。
但该方法有一定开销：每次进程运行，当它访问数据和代码页时，都会触发 TLB 未命中，如果操作系统频繁切换进程，这种开销会很高。
增加硬件支持，实现跨上下文切换的 TLB 共享。比如有的系统在 TLB 中添加一个地址空间标识符 (ASID)，可以把 ASID 看做是进程标识符，但通常比 PID 位数少一位。TLB 因此可以同时缓存不同进程的地址空间映射，没有任何冲突。
为了支持更大的地址空间，操作系统需要把当前没有在用的那部分地址空间找个地方存储起来。硬盘通常能够满足这个需求，在我们的存储层级结构中，大而慢的硬盘位于底层，内存之上。增加交换空间让操作系统为多个并发运行的进程都提供巨大地址空间的假象。
在硬盘上开辟一部分空间用于物理页的移入和移出，在操作系统中这样的空间称为交换空间，因为我们将内存中的页交换到其中，并在需要的时候又交换回去。因此，我们会假设操作系统能够以页为大小为单元读取或者写入交换空间，为了达到这个目的。
硬件通过页表中的存在位，来判断是否在内存中。如果存在位设置为1，则表示该页存在于物理内存中，并且所有内容都正常进行；如果存在位设置为0，则页不在内存中，而在硬盘上。
访问不在物理内存中的页，这种行为通常被称为页错误。这时 “页错误处理程序” 被执行，处理页错误。
处理页错误的流程：
如上图所示，当操作系统接收到页错误时，会先找可用的物理帧，如果找不到，操作系统会执行交换算法，踢出一些页，释放物理帧，并将请求发送到硬盘，将页读取到内存中。
当硬盘 I/O 完成时，操作系统会更新页表，将此页标记为存在，更新页表项的 PFN 字段以记录新获取页的内存位置，并重试指令。下一次重新访问 TLB 还是未命中，然而这次因为页在内存中，因此会将页表中的地址更新到 TLB 中。
最后的重试操作会在 TLB 中找到转换映射，从已转换的内存物理地址，获取所需的数据或指令。
为了保证有少量的空闲内存，大多数操作系统会设置高水位线 (HW) 和低水位线 (LW)。
原理是：当操作系统发现有少于 LW 个页可用时，后台负责释放内存的线程会开始运行，直到有 HW 个可用的物理页。这个后台线程有时称为交换守护进程 (swap daemon) 或页守护进程 (page daemon)，然后会进入休眠状态。
当内存不够时，由于内存压力迫使操作系统换出一些页，为常用的页腾出空间，确定要踢出哪些页封装在操作系统的替换策略中。交换策略有很多，如下：
最优替换策略能达到总体未命中数量最少，即替换内存中在最远将来才会被访问到的页，可以达到缓存未命中率最低。但很难实现。
FIFO 策略，即页在进入系统时，简单地放入一个队列，当发生替换时，队列尾部的页被踢出。
FIFO 有个很大的优势：实现相当简单。但其根本无法确定页的重要性，即使页 0 已被多次访问， FIFO 仍然会将其踢出。且 FIFO 会引起 Belady 异常。
LRU 策略是替换最近最少使用的页。
LRU 目前看来优于 FIFO 策略及随机策略，但随着系统中页的数量的增长，扫描所有页的时间字段只是为了找到最精确最少使用的页，这个代价太大。
Clock 算法是近似 LRU 的一种算法，也是许多现代系统的做法。该算法需要硬件增加一个使用位。
过程：
考虑到内存中的页是否被修改，硬件增加一个修改位。每次写入页时都会设置此位，因此可以将其合并到页面替换算法中。如果页已被修改并因此变脏，则提出就必须将它写回磁盘，这很昂贵；如果没有被修改，踢出就没有成本。因此，一些虚拟系统更倾向于踢出干净页，而不是脏页。
本文就操作系统的内存虚拟化部分做了简单总结，包括分段、分页、TLB 以及交换空间。通过这些，操作系统实现了虚拟内存系统，从而保证内存对程序的透明，程序访问内存的高效，以及进程之间的相互隔离。