虚拟化

本章展开虚拟化的学习。所谓虚拟化，与并发一样，是一种技术手段，通过将一个进程划分为不同的部分并按需调入内存，实现每个进程独占内存的假象。

产生背景

连续存储。我们首先学习古老的连续存储技术，以便更好的过渡到后面的页式存储。连续存储顾名思义，就是对于每一个进程，都需要完整的将其装入或移出内存，有以下三种连续存储策略：

连续分区。一个进程占用整个用户内存空间（内存分为 OS 空间和用户空间）。这种策略显然不支持并发，同时也让内存浪费严重；
固定分区。将用户内存空间划分为 \(n\) 个固定大小的分区，其余逻辑与上述连续分区一致。这种策略的缺点依然很明显：1）虽然解决了只能一个进程执行的问题，但是由于一个进程只能占用一个分区，因此仍然限制了并发的进程数量上限为 \(n\) 并且不支持超过最大分区容量的进程执行；2）同样会造成内存浪费；3）不利于进程的内存开销的动态变化；
可变分区。可以理解为拼图，通过移动/紧凑技术将进程移动到地址相连的内存空间从而可以不浪费进程之间的小内存区域。设计者设计了「可分配分区表」和「被占用分区表」。OS 可以每次从可分配分区表的第一个可分配分区开始找，也可以按照上次寻找结束的分区开始找；也可以按照可分配空间大小降序排序开始找；也可以按照可分配空间大小升序排序开始找。这种策略解决了内存浪费的问题但缺点依然明显：1）同样不支持大作业进程；2）上述的移动/紧凑策略对于时间开销很大，不利于进程的高效执行。

页式存储。本章我们会以页式存储为例，展开虚拟化技术的学习（段式、段页式等虚拟化技术此处不予讨论）。但是在开始学习之前不妨问个问题：为什么会有虚拟化技术？从上面介绍的连续存储方法可以看出，如果将一个进程完整的调入调出内存，将会很大程度上约束程序员的编程空间，因为内存造价相对较高，并且现在程序的空间需求越来越大，完整的调入调出进程就变得不合适，再加上程序具有局部性这一天然的优势，我们完全可以将一个进程分割成小部分，然后按需调入内存即可。这不仅提升了编程空间，也可以让程序员不受限于不同主机内存大小不一的问题，而只需要关心每一个程序具体的运行逻辑。

虚拟化技术的局限性。虚拟化技术并不是万能的。对于程序空间要求高，但是计算速度要求不是很严格的应用场景（例如服务器、台式机、笔记本），虚拟化技术可谓是神来之笔，大大提升了程序空间开销的上限。但是虚拟化技术实现的代价就是需要一定的时间开销来完成虚拟地址到物理地址的转换，这对于计算实时性要求高并且计算资源有限的场景式无法容忍的，比如嵌入式，此时 CPU 访问的指令就直接对应了 cache 或内存中的物理地址。

页式存储

页式存储的 Python 模拟：Explorer-Dong/OS_Simulate

下面详细展开页式存储的实现细节。

组织结构

分块方式。对于页式存储，设计者将内存和进程分别划分为等空间大小的子模块。其中内存中的子模块叫做 frame/实页/页框，进程中的子模块叫做 page/虚页/页面。

映射关系。对于页式存储，实页和虚页之间是全相联映射的关系，即进程中任意一个虚页可以对换到内存中任意一个实页中。值得注意的是，这里的对换与内存和 cache 的对换并不是一个意思。在内存和 cache 中，存储的都是实际的物理地址，因此内存和 cache 的对换就是信息的复制与拷贝并通过一个标记位来表示存储是否有效。但是在外存虚页和内存实页的对换中，由于进程的虚页地址和内存的实页地址并不是基于同一个空间，因此我们不能像内存和 cache 一样把所有信息进行对换，于是「页表」应运而生。

如上图所示，我们通过页表建立起了「进程的虚页」与「内存的实页」之间的对应关系。在页表中每一行数据被称为页表项，对应一个虚页的映射信息。例如上图所示一共有 8 个虚页，那么页表就一共有 8 个页表项。每一个进程都有自己的一个页表用来记录其每一个虚页在实页中的映射关系。为了节省空间，每一个进程只会在其 PCB 中存储对应页表的首地址与偏移量。

基本功能

地址转换。在虚拟化技术下，CPU 从进程加载到的地址都是虚拟地址，需要将其转化为物理地址才能正确访问到存储在内存中的信息，这一般交给存储器管理单元 (Memory Management Unit, MMU) 来完成。

如上图所示。MMU 首先会根据页表基址寄存器中的地址找到内存中当前进程对应的页表，接着根据虚拟地址中的高位字段得到虚页号，然后根据虚页号定位到页表中的一个页表项：

如果当前页表项的「装入位」字段为 \(0\)。说明发生了缺页异常，此时进程会发出缺页中断请求，操作系统会采用对应的页面替换算法将缺失的页面装入内存同时维护页表等信息，然后重新开始最初的指令执行过程；
如果当前页表项的「装入位」字段为 \(1\)。则表明对应的虚页已经被加载到内存中了，实页号就存放在当前页表项的「存放位置」字段中。由于虚页和实页的大小是一样的，因此地址在虚页的偏移量和在实页的偏移量也是一样的，故直接将此时「实页号」和「虚页对应的偏移量」进行拼接即可得到实际地址。

页面替换。页面替换算法和缓存的替换算法完全一致，这里不再赘述。

写回机制。也就是读写的一致性策略，页表中有一项叫做修改位，如果在读写或被替换时发现修改位为 \(1\)，则表明对应实页的数据被修改了，此时一般采用 write back 策略来保持一致性，也就是撤回到外存时更新外存信息。

优化改进

快表机制。由于每一个进程的页表都会被加载到内存中，这就意味着每次做地址转换访问页表时都需要访问内存，那为什么不能访问 cache 呢？设计者将经常访问到的页表项拿出来放到 cache 中组成了新的页表叫做后备转换缓冲器 (Translation Lookaside Buffer, TLB)，通常称其为快表（在快表的概念下内存的页表就被称为慢表）。这样一来在地址转换时就会首先查询 cache 中 TLB 的页表项，如果没找到就再去访问内存中的页表。


快表机制下的一次访存（逻辑图）	快表机制下的一次访存（结构图）

如上两图所示，分别展示了逻辑框架和结构框架下，使用了快表机制虚拟化技术的地址转换逻辑。一共有以下 3 种访问情况：

快表命中：快表（物理地址）\(\to\) 内存（存储的信息）；
内存命中：快表 \(\to\) 内存（物理地址）\(\to\) 内存（存储的信息）；
均未命中：快表 \(\to\) 内存 \(\to\) 缺页中断 \(\to\) 快表（物理地址）\(\to\) 内存（存储的信息）。

多级页表。在现代程序的需求下，虚拟空间越来越大，对应的页表项也会越来越多。由于页表（慢表）是连续存储在内存中的，而一个内存实页的存储容量有限，如果一个页表的物理空间超过了一个实页的物理空间怎么办呢？我们引入多级页表这个概念。很容易理解，就是将一个大页表拆分成更多的小页表，然后用页表的索引将所有的小页表连接起来即可。

如上图所示，展示了一个二级页表下的地址转换流程。具体的：

首先根据虚拟地址的高 \(p_1\) 位访问一次内存找到一级页表对应的项，从而得到二级页表所在的内存块号；
然后再访问一次内存并偏移 \(p_2\) 位得到物理地址所在的内存块号；
最后将内存块号和页内偏移 \(d\) 拼接就得到了最终的物理地址。

反置页表。也可以不用每个进程都有一个页表，而是一个内存对应一个页表，这个内存页表中记录了所有活动中进程的页表项。每次根据逻辑地址寻找物理地址时，只需要根据进程 \(pid\) 和虚页号 \(p\) 在内存页表中查找即可，查找到后在内存页表中的偏移量 \(i\) 就是实页号，将其与页内偏移 \(d\) 拼接即可得到最终的物理地址。由于 \(pid\) 是唯一的，那么 \(pid\) 和 \(p\) 的联合就一定是可哈希的，可以利用哈希表加速上述的查找匹配过程。