02 Virtualization

计算机中，运行一个程序就是让计算机执行一系列简单的执行指令。处理器从内存中获取一条指令，对其进行解码（弄清楚这是哪条指令），然后执行（例如两个数相加、访问内存、检查条件、跳转到函数等）。完成这条指令后，处理器继续执行下一条指令，依此类推，直到程序最终完成。这就是冯·诺依曼(Von Neumann)计算模型的基本概念。而为了让一个或多个程序的运行变得容易，有一类程序专门负责确保系统既易于使用又正确高效地运行，它能让多个程序同时运行、共享内存、与设备交互。这些软件就称为操作系统(Operating System, OS)。要做到这一点，操作系统主要利用一种通用的技术，我们称之为虚拟化(virtualization)。操作系统将物理资源（如CPU、内存或磁盘）转换为更通用、更强大且更易于使用的虚拟形式。

CPU的虚拟化

在讨论操作系统时，我们把运行中的程序抽象为一个进程(process)。事实表明，人们常常希望同时运行多个程序。比如我们会同时运行浏览器、邮件、游戏、音乐播放器等等。实际上，一个正常的系统可能会有上百个进程同时在运行。而通常一台计算机只有一个（或几个）CPU，所以我们面临的根本问题就是：如何让多个进程同时运行？或者，如何创造出我们拥有许多CPU的假象？

操作系统本身就是一个进程。是一直运行在计算机上的程序（通常称为内核kernel）。当计算机电源打开时，它需要运行一个初始程序(bootstrap program)。这个程序通常是计算机上的一个只读的固件，它初始化CPU、寄存器等等，其中很重要的一部分就是定位操作系统程序（kernel）并把它加载到内存。操作系统开始运行以后，用户就可以与计算机交互，例如直接输入指令或从硬盘读取代码（这些都属于输入与输出，简写为I/O），由此启动其它进程。

受限直接执行

无论是操作系统还是其它一般的进程，每个进程要运行都需要占用内存和CPU（寄存器）。为了使进程安全且高效地运行，操作系统开发人员想出了一种技术，称为“受限直接执行(limited direct execution)”。“直接执行”就是指：直接在CPU上运行程序即可。而受限就是指，这一运行过程是会被操作系统监管的。操作系统对进程的管理包括对进程的创建、终止、暂停等等。这些操作通过操作系统的系统调用(system call)来完成。系统调用提供操作系统服务的接口，通常用C或C++编写。即使简单程序也可能大量使用操作系统，系统每秒通常会执行成千上万的系统调用。通常在实际系统调用中，开发人员会写一组应用编程接口(Application Programming Interface, API)，调用者无需知道如何实现系统调用，只需遵循API就可以使用系统调用，这样能够把大量底层细节隐藏起来，方便应用代码的编写。

当进程发出I/O请求，或者要访问某些地址等等时，这些请求必须得到操作系统的同意。这是操作系统管理进程的基本方式。为了实现这种受限执行的模式，一种方法是设置两种处理器模式，一种称为用户态(user mode)，一种称为内核态(kernel mode)。进程在用户态下运行。在用户态下运行的进程不能I/O，不能访问内存等等，要完成这些操作，首先要发起系统调用陷入(trap)内核态，把控制权交还给操作系统，待操作系统完成这些工作后返回用户态。

以上陷入内核态的调用必须由进程主动发出。但是如果进程出错，或者本来就是恶意的，那么它可能永远无法触发系统调用。人们用时钟中断(timer interrupt)来解决这个问题：我们为硬件增加一些机制，使得每过一段时间（几毫秒）进程就暂停，启动操作系统上的中断处理程序，这样操作系统就可以每个几毫秒就掌握一次主动权。

调度(scheduling)

每一次进程切换时，我们都需要把当前寄存器上的值保存到内存的某个地方，然后才能运行另一个进程。这一过程称为上下文切换。当多个进程同时运行时，我们通常频繁地切换进程，制造出这些进程在同时运行的假象。

每一次时钟中断时，我们都可以选择终止当前进程而运行另一个进程，也可以选择继续运行当前进程。怎么做出决定呢？这就是进程的调度问题。怎么样才能做出一个“好”的决策是和我们想要达到的目标有关的。

周转时间(turnaround time)

一个很重要的衡量调度策略的指标就是一个进程的周转时间，定义为任务到达系统的时间与任务最终被完成的时间之间的时间间隔。下面假设我们唯一的优化目标就是最小化每个进程的平均周转时间。

，，，，，，，，，，，，，，

内存的虚拟化

计算机在运行时有多个进程同时进行，为了能创造出它们都在同时运行的假象，我们采用时分共享的方式让它们轮转运行。然而在切换进程的时候，出于效率考虑，我们不可能每次都重新加载进程用到的内存，而只能让进程之间共享内存。因此，操作系统需要做好内存管理的工作。这个工作既要能保证进程切换时效率要足够高，又要能提供保护机制使得一个进程不能非法访问另一个进程的内存。

我们想要创造出一个假象，让程序认为自己能够使用连续且足够大的整块内存。为此，我们设置一个地址转换机制，程序代码中涉及的全都只是虚拟地址，而由硬件来把虚拟地址映射到真正的物理地址上。这样，程序只需在虚拟地址层面操作，所有转换的工作都由硬件来完成。这就是虚拟化内存。

基址/界限

实现地址转换的一个简单的策略是base and bound。假设每个进程在物理内存中占有的空间也是连续的，那么我们可以为每个进程分配一段物理空间，同时设置两个寄存器的值base和bound。对于给定的虚拟地址，加上base(基址)就对应到物理地址，同时我们检查这个值有没有超出bound。这样就保证了不同进程间内存的独立，又能实现进程切换时内存的快速转换。但存在的问题是每个进程分配到的内存大小是固定的，如果这个进程并没有利用到大部分分配给它的内存，那么就造成了浪费，这部分浪费的空间称为“内部碎片”。

分段

为了解决这个问题，我们采取一个称为分段(segmentation)的方法。一个进程所需要的内存分为三部分，一部分是代码（静态的），一部分是栈（局部变量、函数参数等所需要的空间），一部分是堆（用户自主申请并释放的内存空间）。在虚拟内存看来，我们一般把代码部分的内存放在顶部，栈和堆在代码下方，堆空间自顶向下分配，栈空间自底向上分配。在刚才的策略中，它们共同占用了一段连续的内存空间。现在我们允许同一个进程的代码、栈、堆被分配在物理空间的不同位置，称为不同的“段”，每个段依然采取base and bound的地址转换方式。这就是分段（这也是为什么C语言访问非法内存时的报错信息是segmentation fault）。每个段有对应的段寄存器，记录了每个段对应的base和bound，以及偏移是向上还是向下等等。一个问题是，对于一个给定的虚拟地址，怎么知道它属于哪个段呢？一种显式的方法是用虚拟地址中的某几位来标识它属于堆、栈、还是代码；也有隐式的方法，例如用虚拟地址的产生方式来判断。分段解决了内部碎片的问题（而且还更容易支持内存共享），但产生了外部碎片的问题：随着许多进程的开始与结束，整个物理内存在许多连续段上被占用，可能存在剩余总内存足够，但没有一个足够大的连续内存分配给新进程的情况。解决外部碎片的一种方法是定期整理物理内存使之变得紧凑，但每一次整理需要停止所有进程并占用大量CPU时间；另一种思路是涉及高效的分配段空间的算法，至今人们已经提出了许多这样的算法，但算法最终也只能尽可能减少外部碎片而不能消除它，可见分段方法本身存在不足之处。

分页

分段的方法产生外部碎片的原因主要是允许不同大小的内存块。与之相反的是分页(paging)的方法，我们把整个虚拟内存分割成大小相同的块，每个块称为一个页(page)，每个页对应到物理内存中不同的位置。这样，每当需要请求某一大小的内存时，我们只需用free list给出相应数量个页，就再也不会有外部碎片的问题了。为此，我们需要为每个进程维护一个页表(page table)，记录每个虚拟内存页对应的物理地址。然而这样做有两个问题，一是页表可能很大，本身占用很多内存；二是页表的访问和地址转换本身要占用较长的时间，效率低。

TLB

为了解决频繁地页表访问造成的效率低下问题，我们考虑增加一个CPU附近的转换旁路缓冲存储器(translation-lookaside buffer, TLB)，里面存储频繁访问的虚拟地址及其对应的物理地址，实践表明这带来了巨大的性能提升。具体地，每当我们要寻找一个虚拟地址对应的物理地址时，我们首先不到页表中寻找，而是在TLB中寻找。如果TLB中存储了答案，那么称为TLB命中，那么就不需要去页表内存中找了；如果没有存储，称为TLB未命中，这时再到页表中找，找到以后用替换最近最少使用(least-recently-used， LRU)的策略或随机替换等等的策略更新TLB。TLB利用地址访问的空间局部性（同一个页表内的地址也会被频繁访问）和时间局部性（最近访问的还会被频繁访问）大大提高了性能。注意，TLB是对单个进程的，当发生上下文切换时，一个可行的做法是每次清空TLB。但这样的开销较大，另一个常用方法是为TLB中的每个地址增加地址空间标识符(Address Space Identifier, ASID)，它可以看作进程对应的标识符。

多级页表

如何尽可能地减小页表所占用的内存大小呢？在页表中，很多虚拟地址可能是未被分配的，我们想要尽量不要在内存中记录这些地址转换对应的页表项。一个简单的方法是，把页表本身划分成多个页，用一个页目录在记录每个页的信息：如果一个页中的页表项全都是未使用的，那么在页目录中把这个页标记为未使用；如果一个页中至少有一个页表项被使用，那么在页目录中标记为使用，并分配内存记录页表中的内容。我们看到，这样页表的利用率就被大大提高了，正比于真正用到的内存。同时，这样页表的每个页的内容可以被分配到物理内存中的任何地方，只要在页目录中记录好对应的物理地址就好了。这实际上是把原来的一层的线性页表变成了两层的树形结构，可以称为两级页表。

如果用以上方法构建出的页目录本身也太大了，那么可以再把页目录分页，用一个页目录的页目录指向它。这样就得到了一个三级页表。同样地，也可以构建四级、五级的页表，称为多级页表。多级页表是一个多层的树结构。同样地，为了提高效率，在使用多级页表的同时我们也用一个TLB来缓存经常访问的地址。应该指出，和线性页表相比，在TLB未命中时，多级页表需要从内存加载多次，才能从页表中获取正确的地址转换信息（访问内存中多级的页目录），而用线性页表只需要一次加载。

超越物理内存

如果进程所需要的内存空间比物理内存还要大，为了创造内存很大的假象，我们可以借用一部分硬盘的空间来满足这个需求。我们要做的就是允许一部分页存入硬盘中的这部分空间，在需要时在内存与硬盘间交换。因此这部分空间被称为交换空间(swap space)。为了实现这一点，页表项里需要增加一个存在位用来标记这一页在物理内存中还是在硬盘中。如果访问一个不在物理内存中的页，就触发页错误(page fault)，此时陷入操作系统，操作系统发送请求读取硬盘中对应的页，然后找到内存中空闲的地址写入这个页。（注意，访问硬盘的过程属于I/O，这个过程耗时很长，进程将被阻塞，切换到别的进程运行）

当硬盘中的页被交换回内存时，可能内存已满，这时应该交换那一个内存中的页到硬盘中呢？这就是页交换策略问题，是早期的虚拟内存系统要做的最重要的决定之一。

很多时候，操作系统回主动预留一小部分空闲内存。为了保证有少量的空闲内存，大多数操作系统会设置高水位线(HW)和低水位线(LW)。当系统发现有少于LW个页可用时，后台负责释放内存的线程会开始运行，直到有HW个可用的物理页。这个后台线程有时称为交换守护进程(swap daemon)。

另外，我们也可以进行一些性能优化。例如把多个要写入的页聚集起来写入或分组写入，提高硬盘读写的效率。

内存可以看作全部虚拟内存页的缓存(Cache)。因为在虚拟内存系统的角度，内存相对于磁盘就好像高速缓存相对于内存。因此，在为这个缓存选择替换策略时，我们的目标就是让(cache miss)最少。因此，这里的策略和cache的策略本质是相同的。一个OPT的算法显然是上帝视角预知最晚被访问的是那个页，踢出那个页即可。然而如果要求强制在线，采取LRU策略依然可以实践发现是非常优秀的。

在实现LRU时，有时不必找精确的最少使用的页，那样需要非常大的开销。一种效果非常好的方法称为“近似LRU”，在硬件上为每个页增加一个使用位。我们循环访问所有的页，每个当前页如果被标记为1就把它修改为0并访问下一页，直到找到第一个标记为0的页，把这一页当作最近最少使用的页。（循环访问是一种方式，其它的策略诸如随机等等也是可行的近似LRU方案）

最后应该指出，很多时候硬盘访问和内存访问的时间差实际上是巨大的，因此无论怎么优化，最好的方法其实是购买更多的内存（doge）。