本文为操作系统导论中关于虚拟化部分的读书笔记。其中主要涉及CPU虚拟化，内存虚拟化的策略及相关知识。

CPU虚拟化

操作系统提供的基本的抽象就是进程，进程就是运行中的程序。程序本身只是磁盘上的一些指令，是操作系统让这些字节运行起来，让程序发挥作用。

人们通常希望能同时运行多个程序，因此如何让操作系统提供几乎有无数个CPU可用的假象成为了一个挑战，因为通常只有少量的物理CPU。

操作系统通过 虚拟化CPU 来提供这种假象，通过让一个进程只运行一个时间片，然后切换到其他进程，操作系统提供了存在多个虚拟CPU的假象。这就是 时分共享CPU 技术，允许用户运行多个并发的进程，潜在的开销就是性能的损失，因为如果CPU必须共享，每个进程就会运行的慢一点。

进程为了理解构成进程的是什么，我们必须理解它的机器状态：程序在运行时可以读取或更新的内容，它包括内存，寄存器以及持久存储设备。

进程创建

那么程序是如何转化为进程的呢？即操作系统如何启动并运行一个程序？进程创建实际如何进行？

进程的创建共分为以下几个步骤：

1）将代码和所有的静态数据（如初始化变量）加载到内存中，加载到进程的地址空间中。程序最初以某种可执行格式驻留在磁盘上。因此程序和静态数据加载到内存的过程，需要操作系统从磁盘读取这些字节，并将它们存放在内存的某处，如图1。

2）为程序的运行时栈（run-time stack）分配内存。例如，C程序使用栈存放局部变量、函数参数及返回地址。

3）为程序的堆（heap）分配一些内存。例如如，在C程序中，堆用于显示请求的动态分配数据。

4）执行一些其他的初始化任务，特别是与输入/输出（I/O）相关的任务。例如，Unix系统中默认每个程序都会分配3个文件描述符，用于标准的输入、输出和错误。

5）启动程序。OS将CPU的控制权转移到新创建的进程中，从而程序开始执行。

​ 图1 加载：从程序到进程

进程状态

进程可能在给定的时间处于的不同状态。它一般会处于以下三种状态：

• 运行（running）：在运行状态下，进程正在处理器上运行。这意味着它正在执行指令。
• 就绪（ready）：在就绪状态下，进程已准备好运行，但由于某种原因，操作系统选择不再此运行。
• 阻塞（blocked）：在阻塞状态下，一个进程执行了某种操作，直到发生其他事件时才会准备运行。

如果将这些状态映射到图上，见图2

数据结构

为了跟踪每个进程的状态，操作系统可能会为所有就绪的进程保留某种进程列表，以及跟踪当前正在运行的进程的一些附加信息，有些人称这些存储关于进程的信息的结构体为进程控制块（Process Control Block，PCB）。操作系统还必须以某种方式跟踪被阻塞的进程，当I/O事件完成时，能正确的唤醒对应的进程。

下面的代码展示了OS需要跟踪的xv6内核中每个进程的信息类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// the registers xv6 will save and restore
// to stop and subsequently restart a process
struct context {
    int eip;
    int esp;
    int ebx;
    int ecx;
    int edx;
    int esi;
    int edi;
    int ebp;
};

// the different states a process can be in
enum proc_state { UNUSED, EMBRYO, SLEEPING,
					RUNNABLE, RUNNING, ZOMBIE };

// the information xv6 tracks about each process
// including its register context and state
struct proc {
    char *mem; 						// Start of process memory
    uint sz; 						// Size of process memory
    char *kstack; 					// Bottom of kernel stack
    								// for this process
    enum proc_state state; 			// Process state
    int pid; 						// Process ID
    struct proc *parent; 			// Parent process
    void *chan; 					// If non-zero, sleeping on chan
    int killed; 					// If non-zero, have been killed
    struct file *ofile[NOFILE]; 	// Open files
    struct inode *cwd; 				// Current directory
    struct context context; 		// Switch here to run process
    struct trapframe *tf; 			// Trap frame for the
    								// current interrupt
};

对于停止的进程，寄存器上的上下文会保存其寄存器上的内容。当一个进程停止时，它的寄存器将被保存到这个内存的位置。通过恢复这些寄存器，可以恢复这个进程。这个过程称为上下文切换。

除了运行、阻塞、就绪外，还有其他的一些状态：进程创建的初始（initial）状态，已退出但尚未清理的最终状态（final）。

进程API

UNIX系统调用

• fork()：用于创建新的进程，新创建的进程称为子进程，原来的进程称为父进程。子进程并不是完全拷贝父进程，他从fork返回的值不同。父进程得到的是子进程的pid,子进程得到是0.
• wait()：父进程调用wait()，延迟自己的执行，直到子进程执行完毕。
• exec()：让子进程和父进程执行不同的程序。exec() 会从可执行程序加载代码和静态数据，并用它复写自己的代码段，堆、栈及其他内存空间也会被重新初始化。然后操作系统执行该程序，将参数通过argv传递给该进程。

操作系统控制权

操作系统必须以高性能的方式虚拟化CPU，同时保持对系统的控制，如何有效的运行进程，同时保留对CPU的控制？为此，需要硬件和操作系统的支持。

受限直接执行

为了使程序尽可能快的运行，操作系统开发人员开发了一种称之为受限的直接执行 (limited direct execution) 的技术。整个受限直接执行的过程一般如下：当OS希望启动程序运行时，它会在进程列表中为其创建一个进程条目，为其分配一些内存，将程序代码加载到内存中，找到入口点 main() 函数，跳转到这里，并开始运行用户代码。

​ 表1 直接运行协议（无限制）

上面的过程存在两个问题：①如何限制进程的操作并高效的运行它；②如何切换进程；

1. 受限的操作

通过引入一种新的处理器模式，称为用户模式（user mode）。在用户模式下运行的代码会受到限制；与之不同的是内核模式（kernel mode），操作系统或者内核以这种方式运行。

为了执行某种特权操作，现在的硬件一般都提供了用户程序执行系统调用的能力，它允许内核向用户程序暴露某些关键的功能，如访问文件系统、创建和销毁进程、与其他进程进行通讯，分配更多的内存等。

要执行系统调用，程序必须执行特殊的陷阱（trap）指令。该指令同时跳入内核并将特权级别提升至内核模式。一旦进入内核，系统就可以执行任何需要的特权操作。完成后，操作系统调用一个特殊的从陷阱返回的指令（return-from-trap）,该指令返回到发起调用的用户程序中，同时将级别降低回到用户模式。

内核通过在启动时设置的陷阱表（trap table）来实现在OS内运行正确的代码。当机器启动时，他在内核模式下运行，因此可以根据需要只有配置机器硬件。操作系统第一件事就是告诉硬件在发生某种异常事件时要运行的代码。操作系统通常会通过某些特殊的指令，通知硬件这些陷阱处理程序的位置，一旦硬件被通知，他就会记住这些处理程序的位置。

在表2中，我们假设每个进程都有一个内核栈，在进入内核和离开内核时，寄存器分别被保存和恢复。

​ 表2 受限直接运行协议

2. 进程间切换

一个进程在CPU上运行，意味着操作系统并没有运行，那么如何让操作系统重新获得CPU的控制权，以便它可以在进程间切换，就是进程切换遇到的关键问题。

协作方式：等待系统调用

在这种方式下，操作系统相信系统的进程会合理运行，运行时间过长的进程被假定会定期放弃CPU，以便于操作系统可以决定其他任务。

非协作方式：操作系统进行控制

事实证明，没有硬件的额外帮助，如果进程拒绝进行系统调用，那么控制权不会被交还到操作系统，操作系统无法做任何事情。

我们可以通过时钟中断（timer interrupt）来解决上面的问题。时钟设备可以编程为几毫秒产生一次中断，产生中断时，当前正在运行的进程停止，操作系统中预先配置的中断处理程序会运行，此时，操作系统重新获得CPU的控制权，进行进程的切换。

保存和恢复上下文

既然操作系统已经重新获得控制权，那么无论是通过系统调用协作还是通过时钟中断更强制执行，都必须决定：是继续运行，还是切换进程。这个决定是由调度程序（scheduler）决定的。

如果进行切换，那么OS会执行一些底层代码，即所谓的上下文切换，即操作系统要做的就是为当前正在执行的进程保存一些寄存器的值，并为即将执行的进程恢复一些寄存器的值。

为了保存正在运行的进程的上下文，操作系统会执行一些底层的汇编代码，来保存通用寄存器、程序计数器，以及当前正在运行的内核栈指针，然后恢复寄存器、程序计数器，并切换内核栈，供即将运行的程序使用。通过切换栈，内核在进入切换代码调用时，是一个进程的上下文，在返回时，是另一个进程的上下文。当操作系统最终执行从陷阱返回的指令时，即执行的进程变成了当前运行的进程，上下文切换完毕。

表3 展示了整个过程。展示进程A切换到进程B的过程。

​ 表3 受限直接执行协议（时钟中断）

进程调度

前面了解了进程底层机制，下面介绍一下操作系统调度程序采用的上层策略。

在了解策略之前，我们先要了解一下与系统中运行的进程有关的工作负载（workload），确定工作负载时构建调度策略的关键部分。除了工作负载外，我们还需要调度指标来比较不同的策略，它包括两种：公平指标和性能指标。、

其中性能指标中一种重要的指标为周转时间（turnaround time），任务的周转时间指的是任务完成时间减去任务到达系统的时间。如果考虑周转周期，下面介绍几种有趣的调度方式。

1. 先进先出（FIFO）：也称为先到先服务（FCFS）。

2. 最短任务优先原则（SJF）：shortest job first，先运行最短的任务，然后次短的任务，如此往复。

3. 最短完成时间优先（STCF）： shortest time-to-completion first，或称为抢占式最短作业优先（preemptive shortest job first, PSJF），当新任务进入系统时，它会确定剩余工作和新工作中，谁的剩余时间最少，然后调度工作。

如果我们知道任务长度，而且任务只使用CPU，而且我们唯一的衡量是周转时间，那么 STCF 将是一个很好的策略。新引入的分时系统改变了这些，为了获得更好的交互性，需要一个新的度量标准，即响应时间。响应时间指的是从任务到达系统到首次运行的时间。下面是一些考虑了新指标的调度方式。

1. 轮转（Round-Robin）：RR在一个时间片内运行工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。反复执行，直到所有任务结束。因此，RR有时被称为时间切片。其时间片的长度必须是时钟中断周期的倍数。

2. 多级反馈队列（MLFQ）：Multi-level Feedback Queue，MLFQ基本规则：

   1. 如果A的优先级 > B的优先级，运行A；
   2. 如果A的优先级 = B的优先级，轮转运行A和B。
   3. 工作进入系统时，放在最高优先级（最上层对垒）；
   4. 一旦工作用完了其在某一层的时间配额（无论主动放弃多少次CPU），就降低其优先级。
   5. 经过一段时间S，就将系统中所有工作重新加入到最高优先级队列。

比例份额调度（proportional-share）：公平份额调度程序，其最终目标是确保每个工作获得一定的CPU时间，而不是优化周转时间和响应时间。比例份额调度中有一种称为彩票调度的方式，其基本思想是：每隔一段时间，都会举行一次彩票抽奖，以确定接下来该运行哪个进程。

彩票调度（lottery scheduling）:这种调度利用了随机性，彩票数代表了进程占有的某个资源份额，一个进程拥有的彩票数占总票数的百分比，就是它占有资源的份额。通过不断的抽取彩票，彩票调度从概率上获得份额比例。随机方法的优势：

1. 避免奇怪的边角情况，例如LRU替换算法，在有重复序列的负载时表现的非常差。

2. 随机方法很轻量，几乎不用记录任何状态。

3. 随机方法很快，只要能很快的生成随机数，做出决策就很快。

内存虚拟化

地址空间

随着时分共享流行，当多个进程驻留在内存中时，大家不希望一个进程可以读取其他进程的信息，因此操作系统需要提供一个易用的物理内存抽象。这个抽象叫做地址空间（address space），是运行程序看到的系统中的内存。理解这个基本的操作系统内存抽象，是了解虚拟内存的关键。一个进程的地址空间包含运行该程序的所有内存状态。如：代码，栈和堆等。

当然，我们描述地址空间时，所描述的是操作系统提供给运行程序的抽象。当操作系统这么做时，我们说操作系统在虚拟化内存（virtualizing memory）。因为运行的程序认为他被加载到特定的地址的内存中，并且具有非常大的地址空间。

虚拟内存的目标：

1. 透明（transparency）：程序不应感知到内存被虚拟化的事实，它的行为就好像它拥有自己的私有物理内存。
2. 效率（efficiency）：操作系统应追求虚拟化的尽可能的高效，包括时间上的（不让程序运行的更慢）和空间上的（不需要太多额外的内存来支持虚拟化）。实现高效需要硬件的支持，包括像TLB这样的硬件功能的支持。
3. 保护（protection）：操作系统应当确保进程收到保护，不会受到其他进程的影响，操作系统本身也不会影响。当一个进程执行加载、存储或指令提取时，它不应该以任何方式访问或者影响其他进程或者操作系统本身的内容。因此保护提供了进程之间隔离（isolation）的特性。

隔离原则：隔离是建立可靠系统的关键原则。操作系统力求让进程彼此隔离，从而防止相互造成伤害。通过内存隔离，操作系统进一步确保运行的程序不会影响底层操作系统的操作。一些现代操作系统通过将某些部分与操作系统其它部分分离，实现进一步的隔离。这样的微内核可以比整体内核提供更大的可靠性。

内存操作API

在运行一个C程序时，会分配两种类型的内存，一种称为栈内存，它的申请和释放操作是由编译器来隐式管理的，有时也称为自动（automatic）内存；另一种称为堆内存，其中所有的申请和释放都是由程序员显式完成的。

malloc() 调用：申请内存空间，传入一个size_t类型的参数，该参数表示你需要申请多少字节。

free() 调用：释放不在使用的堆内存。该函数接收一个参数，即一个由malloc返回的指针。

calloc() 调用：在返回之前将其清零。

relloc() 调用：创建一个新的更大的内存区域i，将旧区域复制到其中，并返回新区域的指针。

常见错误：

• 忘记分配内存，如下代码段：

  1 2 3 4 5 6 7 8 9

  // 错误的方式 char *src = "hello"; char *dst; //未分配内存 strcpy(dstl, src); //会导致段错误，segmentation fault // 正确的方式 char *src = "hello"; char *dst = (char *) malloc(strlen(src) + 1); strcpy(dstl, src);

• 没有分配足够的内存

  1 2 3 4

  // 错误的方式 char *src = "hello"; char *dst = (char *) malloc(strlen(src)); strcpy(dstl, src);

• 忘记初始化分配的内存，会遇到未初始化的读取，读取了一些未知数据。

• 忘记释放内存，会导致内存泄漏（memory leak）。

• 在用完之前释放内存，会导致悬挂指针（dangling pointer）的错误。

• 反复释放内存

• 错误的调用free()

地址转换

我们在实现虚拟内存的时候，和CPU虚拟化的追求一样，在实现高效控制的同时，提供期望的虚拟化。控制意味着操作系统要确保应用程序只能访问它自己的内存空间。因此，要保护应用程序不会相互影响，也不会影响操作系统，我们需要硬件的帮助。虚拟内存也要具有一定的灵活性，即我们希望程序能以任何方式访问它自己的地址空间，从而让系统更容易编程。所以关键问题是：如何高效、灵活地虚拟化内存？

这里，利用了一种通用技术，有时称为基于硬件的地址转换（hardware-based address translation），简称为地址转换。利用地址转换，硬件对每次内存的访问进行处理（即指令获取、数据读写），将指令中的虚拟地址转换为数据实际存储的物理地址。

仅仅依靠硬件不足以实现虚拟内存，因为它只是提供了底层机制来提高效率。操作系统必须在关键位置介入，设置好硬件，以便完成正确的地址转换。因此它必须管理物理内存，记录被占用和空闲的内存位置，谨慎介入，保持对内存的管理和控制。

所有这些工作，都是为了创造一种假象：每个程序都有自己的私有内存，那里存放着他们的代码和数据。

动态重定位

动态重定位（dynamic relocation）：又称基址加界限机制（base and bound），具体来说，就是每个CPU需要两个硬件寄存器：基址（base）寄存器和界限（bound）寄存器，有时称为限制（limit）寄存器。

当运行程序的时候，该进程产生的所有内存引用，都会被处理器通过以下方式转为物理内存： physical address = virtual address + base

进程中使用的内存引用都是虚拟地址，硬件将虚拟地址加上基址寄存器中的内容，得到物理地址，再发给内存系统。将虚拟地址转化为物理地址，这正是所谓的地址转换技术。由于这种定位是发生在运行时的，我们可以在进程开始运行后改变其地址空间，这种技术一般称为动态重定位。

其中界限寄存器提供了访问保护，如果进程要访问超过这个界限或者负值的虚拟地址，CPU将触发异常，进程可能被终止。我们将负责地址转换的部分统称为内存管理单元（Memory Management Unit）。

下面三个表格介绍了动态重定位需要的硬件要求和操作系统的职责：

​ 表3 动态重定位：硬件要求

​ 表4 动态重定位：操作系统职责

下表展示了大多数硬件与操作系统的交互。

​ 表5 受限直接执行（动态重定位）

分段

由于栈和堆之间的空间并没有被使用，确依然占用了实际的物理内存。因此简单的动态重定位会造成虚拟空间的浪费，那么现在的关键问题是：怎样支持大地址空间，同时栈和堆之间有大量空闲空间？为了解决这个问题，产生了分段（segmentation）的概念。

分段的概念很简单，就是在MMU中引入不止一个基址和界限寄存器对，而是给地址空间内的每个逻辑段（segment）一对。一个段只是地址空间里的一个连续定长的区域，在典型的地址空间里有三个逻辑不同的段：代码、栈和堆。分段的机制使得操作系统能够将不同的段放到不同的物理区域，从而避免了虚拟空间中的未使用部分占用物理内存。

硬件在地址转换时使用段寄存器。如何知道段内偏移量以及地址引用了哪个段？

1. 显式方式（explicit）：就是用虚拟地址开头几位来标识不同的段。如一个14位的虚拟地址，前两位来标识，后面12位为偏移量
2. 隐式方式（implicit）：硬件通过地址产生的方式来确定段。如地址如果是由程序计数器产生的，那么地址在代码段，如果是基于栈或者基址指针，它在栈段，其他地址则在堆段。

栈在物理内存中反向增长的，它和代码段或者堆段地址转换是有所不同的。这里需要一点硬件的支持，除了基址和界限外，硬件还需要知道段的增长方向。

通过硬件的支持，我们可以在地址空间之间共享某些内存段，这样可以用来节省内存。为了支持共享，需要的硬件就是保护位（protection bit）。就是为每个段增加了几个位，标识程序是否能够读写该段，或者执行其中的代码。通过将代码段标记为只读，同样的代码可以被多个进程共享，而不用担心破坏隔离。

粗粒度分段就是将地址空间分成较大的、粗粒度的块。细粒度分段就是更加灵活地将地址空间划分为大量较小的段。支持细粒度分段需要硬件进一步支持，并在内存中保存某种段表。

内存地址空间分段带来了一些新的问题。操作系统在切换上下文时应该做什么？如何管理物理内存的空闲空间？

第一个问题的是：各个段寄存器中的内容必须保存和恢复。

第二个问题：一种解决方案是紧凑物理内存重新安排原有的段，但紧凑成本很高。另一种解决方案是利用空闲列表管理算法，试图保留大的内存块用于分配，从空闲链表中找最接近需要分配空间的算法有：最优匹配，最坏匹配、首次匹配，以及伙伴算法。

空闲空间管理

当使用用户级的内存分配库或者操作系统用的分段，都会出现空闲空间被分割为不同大小的块，成为碎片，后续请求失败的情况。因为物理内存很快充满了许多空闲空间的小洞，因而很难分配给新的段，或扩大已有的段，这种问题被称为外部碎片（external fragmentation）。那么关键问题是：如何管理空闲空间，什么策略可以让碎片最小化？不同方法的时间和空间开销如何？

底层机制

1. 在释放一块内存时，合并可用空间。
2. 追踪已分配空间的大小。
3. 嵌入空闲列表。
4. 向操作系统申请更大的堆。

策略

• 最优匹配（best fit）：遍历整个空闲列表，找到和请求大小一样或者更大的空闲块，然后返回这组候选者中最小的一块。需要付出较高的性能代价。
• 最差匹配（worst fit）：尝试找到最大的空闲块，分割并满足用户的需求后，将剩余的块加入空闲列表。性能差，表现也差，导致过量的碎片。
• 首次匹配（first fit）：找到第一个足够大的块，将请求的空间返回给用户。有速度优势，如何管理空闲列表的顺序变的十分重要，如基于地址的排序。
• 下次匹配（next fit）：多维护一个指针，指向上次查找的结果，其思想是将对空闲空间的查找操作扩散到整个列表，避免对列表开头频繁的分割，性能类似首次匹配，同时避免了遍历查找。
• 分离空闲列表（segregated list）：如果摸个应用程序经常申请一种大小的内存空间，那么就用一个独立的列表，只管理这样大小的对象，其他大小的请求都交给更通用的内存分配程序。减少了碎片，但引入了复杂性。如厚块分配程序（slab allocator）。
• 伙伴系统（binary buddy allocator）：二分伙伴分配程序，当一个内存分配请求是，空闲的空间被递归地一分为二，直到刚好满足请求的大小，这时请求返回给用户。在其中某块内存被归还时，它会递归合并空闲的伙伴，直到合并整个内存区域。优点是很容易找到伙伴合并内存，缺点是内部碎片问题。
• 其他：上面的这些方法缺乏可扩展性，查找单列表可能很慢，因此还有包括平衡二叉树，伸展树，偏序树等复杂的数据结构。

分页

操作系统主要有两种方法解决空间管理问题，一种是将空间分割成不同长度的分片，就像虚拟内存管理中的分段，但这个方法的主要问题是，将空间切为不同长度的分片后，空间本身会碎片化，随着时间的推移，分配空间将会更加的困难。第二种方法是，将空间分割成固定的长度分片，在虚拟内存中称为分页。

分页不是将一个进程的地址空间分割成几个不同长度的逻辑段，而是分割成固定大小的单元，每个单元称为一页。我们把物理内存看成定长槽块的阵列，叫做叶帧（page frame），每个这样的叶帧包含一个虚拟内存页。这里的问题是：如何通过页来实现虚拟内存，从而避免分段的问题？如何在运行良好的基础上尽可能的减少空间和时间开销？

为了记录地址空间的每个虚拟页放在物理虚拟页放在物理内存中的位置，操作系统通常为每个进程保存一个数据结构，称为页表（page table）。页表的主要作用是为地址空间每个虚拟页面保存地址转换（address translation），从而让我们知道每个页在物理内存中的位置。为了转换虚拟地址，我们需要虚拟页号（virtual page number，VPN）和页内偏移量（offset）。如 movl 21, %eax 指令指的是将虚拟地址为21的内容加载到 eax 寄存器中。将21转变为二进制位 ‘010101’，那么他的虚拟页号和偏移量如下图所示：

虚拟页号通过检索页表找到对应的映射的物理帧号（PFN），有时也称物理页号（PPN），然后找到对应偏移的位置。

页表就是一种用于虚拟地址映射到物理地址的数据结构，因此任何结构都可以采用，最简单的是线性页表（linear page table），它就是一个数组。操作系统通过虚拟页号（VPN）检索该数组，并在该索引处查找到页表项（PTE），以便找到期望的物理帧号（PEN）。

每个页表项（PTE）中有许多不同的位，代表着不同的含义。

1. 有效位（valid bit）：指示特定地址转换是否有效。对于支持稀疏地址空间直观重要。将所有地址空间中未使用的页面标记无效，不在需要为这些页面分配物理帧，能够节省大量的内存。
2. 保护位（protection bit）：表明页是否可以读取、写入或者执行。
3. 存在位（present bit）：表示该页是在物理存储器还是在磁盘上（被换出，swapped out）。交换允许操作系统将很少使用的页面移到磁盘，从而释放物理内存。
4. 脏位（dirty bit）：表明页表被带入内存后是否被修改过。
5. 参考位（reference bit）：也称为访问位（access bit），有时用于追踪页是否被访问，也用于确定哪些页很受欢迎，因此该保留在内存中。

下图显示了来自x86 架构的示例页表项。它包含一个存在位（P），确定是否允许写入该页面的读/写位（R/W）确定用户模式进程是否可以访问该页面的用户/超级用户位（U/S），有几位（PWT、PCD、PAT 和G）确定硬件缓存如何为这些页面工作，一个访问位（A）和一个脏位（D），最后是页帧号（PFN）本身。

但是在程序加载内存的过程中，对于每个内存的引用，分页都需要我们执行一个额外的内存引用，以便首先从页表中获取地址转换，这会导致系统运行变慢，并且占用过多内存。

快速地址转换（TLB）

上面的内容表明使用分页作为核心机制实现虚拟内存，可能带来较高的性能开销。因此我们面临下一个问题：即如何加速虚拟地址转换？如何避免额外的内存访问？

我们这里的需要硬件的协助，添加地址转换旁路缓冲存储器（translation-lookaside buffer, TLB），它就是频繁发生虚拟到物理地址转换的硬件缓存，即地址转换缓存（address-translation cache)。对于每次内存访问，硬件先检查TLB，看看其中是否有期望的转换映射，有就可以很快进行转换，不用访问页表。

基本算法：

1. 首先从虚拟地址中提取页号（VPN）
2. 检查TLB是否有该VPN的转换映射
   1. 如果TLB命中，则意味着TLB有该页的映射。接下来从相关的TLB项中取出页帧号（PFN），与原来的虚拟地址中的偏移量合成期望的物理地址PA，并访问内存。
   2. 如果TLB未命中，则硬件访问页表寻找转换映射，并用该转换映射更新TLB，当TLB更新成功后，重新尝试该指令。

硬件缓存背后的思想是利用指令和数据引用的局部性，包括时间局部性（temporal locality）和空间局部性（spatial locality）。时间局部性是指，最近访问过的指令或者数据项可能很快会再次访问。空间局部性是指，当程序访问内存地址x时，可能会很快访问邻近x的内存。

处理未命中

复杂指令集（Complex-Instruction Set Computer，CISC）的计算机，由硬件处理TLB未命中，硬件必须知道页表在内存中的确切位置（通过页表基址寄存器，page-table base register，），以及页表的确切格式。发生未命中时，硬件会“遍历”页表，找到正确的页表项，取出想要的转换映射，用它更新TLB，并重试该指令。

精简指令集（Reduced-Instruction Set Computer， RISC）的计算机用软件管理TLB，当TLB未命中时，硬件系统会抛出一个异常，这会暂停当前的指令流，将特权提升至内核模式，跳转到陷阱处理程序，这个陷阱处理程序是一段专门处理TLB未命中的代码这段代码在运行时，会查找页表中的转换映射，然后用特别的“特权”指令更新TLB，并从陷阱返回。此时，硬件会重试该指令（导致TLB 命中）。

TLB的内容

典型的TLB有32箱，64项或128项，并且是全相联的（fully associative）。基本上意味着一条地址映射可能存在于TLB中的任意位置，硬件会并行的查找TLB，找到期望的转换映射，一条TLB项的内容可能如下：

1

VPN	|  PFN	|  其他位

其中其他位中通常有一位有效位，用来标识该项是否是有效地址映射，通常还有一些保护位，用来标识该页是否有访问权限，还可能包括地址空间标识符（address-space identifier）、脏位（dirty bit）等。

上下文切换时对TLB的处理

当有了TLB，当进程切换时，由于TLB中包含的虚拟到物理地址映射只对当前进程有效，所以硬件或者操作系统必须注意确保即将运行的进程不要误读了之前进程的地址映射。

为了解决这个问题，有以下可能的解决方案：

1. 在上下文切换时，清空TLB，但是这回导致每次进程运行，都会触发TLB未命中，如果频繁切换进程，这种开销会很高。
2. 增加硬件支持，实现跨上下文切换的TLB共享，比如在系统TLB中添加地址空间标识符（ASID），可以看做进程标识符。

替换策略

当向TLB中插入新项时，会替换一个旧项，那么该替换哪个旧项？

下面列出一些典型的替换策略：

1. 替换最近最少使用的项（least-recently-used，LRU）。
2. 随机策略，即随机替换一项。

较小的页表

上面TLB解决了虚拟地址到物理地址转换较慢的问题，现在用新的方式解决引入分页导致的第二个问题，页表太大，因此消耗的内存太多。通常系统中每个进程都会有一个页表，但基于数组的线性页表会导致页表占用内存过多，那么关键问题是：如何让页表变小？

更大的页

一种解决方案去减小页表的大小：使用更大的页。比如一个32位的地址空间，使用16KB 的页，那么线性表中共会有2^18个页表项，如果每个页表项大小相同，那么页表会缩小到4KB页的四分之一，只有1MB。

但是问题是大内存的页会导致每页内的浪费，这些被称为内部碎片问题（internal fragmentation）。因此结果是应用程序会分配页，但只能用页的一小部分，而内存很快就会充满这些过大的页。因此一般操作系统使用4KB或者8KB的页。

分页和分段

不是为整个地址空间提供单个页表，而是为每个逻辑分段提供一个。在这里，我们基址不是指向段本身，而是保存该段的页表的物理地址，界限寄存器用于指示页表的结尾。

假设32位虚拟地址空间，页的大小是4KB，地址空间分为3个段，使用地址空间前两位确定地址引用了哪个段，现在每个进程都有3个与其关联的页表。在TLB未命中时，硬件使用分段位来确定使用的基址/界限对。然后硬件将其中的物理地址和VPN结合起来，形成页表项（PTE）地址。这种方式，实现了显著的内存节省，栈和堆之间未分配的页不再占用页表中的空间。

多级页表

将线性页表变为类似树的结构，这种方法称为多级页表（multi-level page table）。

其基本思想为：首先，将页表分成页大小的单元，然后如果整页的页表项无效，就完全不分配该页的页表。为了追踪页表是否有效，使用了名为页目录（page directory）的新结构。页目录可以因此告诉你页表的页在哪里，或者整个页表不包含有效页。

在一个简单的两级页表中，页目录为每页页表包含了一项。它由多个页目录项（Page Directory Entires，PDE）组成。PDE拥有有效位（valid bit）和页帧号（page frame number，PFN），类似于PTE。这个有效位和之前的稍有不同，如果PDE项是有效的，则意味着该项指向的页表中至少有一页是有效的，即该PDE所指向的页中，至少一个PTE，其有效位被设置为1，如果PDE项无效，则PDE的其余部分没有意义。下图为线性表和堆积页表的示例：

多级页表的优势：

1. 多级页表分配的页表空间与你正在使用的地址空间成比例，因此它通常很紧凑，并且支持稀疏的地址空间。
2. 如果仔细构建，页表的每个部分都可以整齐的放入一页中，从而更容易管理内存。操作系统也可以在需要时更简单的获取下一个空闲页。

多级页表劣势：

1. 多级页表有成本，在TLB未命中，需要从内存加载两次，才能正确的获取地址转换信息。
2. 多级页表引入了复杂性。

反向页表

保留一个页表，其中的项代表系统的每个物理页，而不是有许多页表。页表项告诉我们哪个进程正在使用此页，以及该进程的哪个虚拟页映射到此物理页。

更一般的说，反向页表说明了我们从一开始就说过的内容：页表只是数据结构，用什么方式实现这些数据结构是由自己决定的。

交换到磁盘

到现在假设页一直位于内核拥有的物理内存中，即使我们用很多技巧来减小页表的大小，但它仍有可能无法一次装入内存。因此，一些系统将这样的页表放入内核虚拟内存，从而允许系统在内存压力较大时，将这些页表的一部分交换到磁盘。

超越物理内存：机制

到目前为止，我们一直假定地址空间非常小，能放入物理内存中。事实上，我们假设每个正在运行的进程的地址空间都能放入内存。为了支持更大的地址空间，操作系统需要把当前没有在用的那部分地址空间找个地方存储起来。因此我们可以利用大而慢的硬盘来存储他们。那么关键问题是：操作系统如何利用大而慢的设备，透明的提供巨大虚拟地址空间的假象？

交换空间

我们可以在硬盘上开辟出一部分空间用于物理页的移入和移出，在操作系统中，一般这样的空间被称为交换空间（swap space）。因为我们将内存中的页交换到其中，并在需要的时候又交换回去。因此我们会假设操作系统能够以页大小为单元读取或者写入交换空间。为了达到这个目的，操作系统需要记住给定页的硬盘地址（disk address）。

存在位

我们需要在系统中增加一些更高级的机制，来支持从硬盘交换页。假设有个硬件管理的TLB的系统。那么整个获取指令或者访问数据的流程可能如下：

1. 硬件从虚拟地址中获得VPN，检查TLB是否命中，若果命中，则获得最终的物理地址并从内存中返回；
2. 如果在TLB中找不到VPN，则硬件在内存中查找页表，并使用VPN查找页表项PTE作为索引，如果页有效且存在物理内存中，则硬件从PTE中获得PFN，将其插入TLB，并重试该指令。
3. 当硬件在PTE中查找时，可能发现页不再物理内存中，硬件判断是否在内存中的方法，是通过页表项中的一条信息，即存在位（present bit）。如果存在位设为1，则表示该页存在于物理内存上，并且所有内容都如上述进行；如果存在位为0，则页不再内存中，而在硬盘上，访问不再物理内存中的页，这种行为通常称为页错误（page fault）。在页错误时，操作系统被唤起来处理页错误，将页读取到内存中，更新页表项，并重试指令。

页错误

不论在哪种系统中，如果页不存在，都由操作系统来负责处理页错误。操作系统可以用PTE中某些位来存储硬盘地址，这些位通常来存储像页的PFN这样的数据，当操作系统接收到页错误时，它会在PTE中查找地址，将请求发送到硬盘，将页读取到内存中。

当硬盘I/O完成时，操作系统会更新页表，将此页标记为存在，更新页表项（PTE）的PFN字段以记录新获取的页的内存位置，并重试指令。下次重新访问TLB还是未命中，而这次因为页在内存中，因此会将页表中的地址更新到TLB小红，最后重试指令。当I/O在运行时，进程将处于阻塞装态，因此操作系统可以执行其他可执行的进程。

内存占满

当内存已经占满或结晶占满，则操作系统可能希望先交换出一个或多个页，以便为操作系统即将交换入的新页留出空间。选择哪些页被交换出或者被替换的过程，被称为页交换策略（page-repalcement policy）。

页错误处理流程

当程序从内存中共读取数据会发生什么？可以注意到当TLB 未命中发生的时候有3 种重要情景。

1. 第一种情况，该页存在（present）且有效（valid）。在这种情况下，TLB 未命中处理程序可以简单地从PTE 中获取PFN，然后重试指令（这次TLB 会命中），并因此继续前面描述的流程。
2. 第二种情况，页错误处理程序需要运行。虽然这是进程可以访问的合法页（毕竟是有效的），但它并不在物理内存中。
3. 第三种情况，访问的是一个无效页，可能由于程序中的错误。在这种情况下，PTE 中的其他位都不重要了。硬件捕获这个非法访问，操作系统陷阱处理程序运行，可能会杀死非法进程。

为了处理页错误，会进行如下操作：

1. 首先，操作系统必须为将要换入的页找到一个物理帧，如果没有这样的物理帧，我们将不得不等待交换算法运行，并从内存中踢出一些页，释放帧供这里使用。
2. 在获得物理帧后，处理程序发出I/O 请求从交换空间读取页。
3. 最后，当这个慢操作完成时，操作系统更新页表并重试指令。重试将导致TLB 未命中，然后再一次重试时，TLB 命中，此时硬件将能够访问所需的值。

何时发生交换

为了保证有少量空闲内存，大多数操作系统会设置高水位线（High Watermark，HW）和低水位线（Low Watermark，LW），来帮助决定何时从内存中清除页。其原理是：当操作系统发现有少于LW个页可用时，后台负责释放内存的线程开始运行，直到有HW个可用的物理页。这个后台线程有时称为交换守护进程（swap daemon）或页守护进程（page daemon）。然后它会进入休眠状态。

为了配合后台的分页线程，交换算法需要先简单检查是否有空闲页，而不是直接交换。如果没有空闲页，会通知后天分页线程按需要释放页。当线程释放一定数目的页时，它会重新唤醒原来的线程，然后就可以吧需要的页交换进内存，继续它的工作。

超越物理内存：策略

当内存不够时，由于内存压力（memory pressure）迫使操作系统换出一些页，为常用的页腾出空间。确定要踢出（evict）哪个页或者哪些页是封装在操作系统中替换策略（replacement policy）中。那么关键问题是：如何决定踢出哪几页？

缓存管理

由于内存中包含系统中所有页的子集，因此可以将其视为系统中虚拟内存页的缓存（cache）。因此，在为这个缓存选取替换策略时，我们的目标是让缓存未命中最少，从而使从 磁盘获取页的次数最少。

在现代系统中，访问磁盘的成本非常高，即使很小概率的未命中也会拉低正在运行的程序的总体平均内存访问时间（Average Memory Access Time，AMAT）。其计算公式为：
$$
AMAT=(P_{hit} * T_M) +(P_{miss} * T_D)
$$
其中$ P_{hit} $表示在缓存中找到数据的概率（命中），$ T_M $表示访问内存的成本，$ P_{miss} $表示在缓存中找不到数据的概率（未命中），$ T_D $表示访问磁盘的成本。

最优替换策略

最优替换策略（原名MIN）是不切实际的，它的目的是达到总体未命中最少，即替换内存中在最远的将来才会被访问到的页，可以达到缓存未命中率最低，但是，未来的访问是未知的，我们无法通过通用操作系统实现最优策略。我们的目的是知道最优策略，进行对比，改进你的策略。

缓存未命中一般分为三个类型：

1. 强制性未命中（compulsory miss）：又称冷启动未命中（cold-start miss），是因为缓存开始是空的，而这是对项目的第一次引用。
2. 容量未命中（capacity miss）：由于缓存空间不足而不得不踢出一个项目以将新项目引入缓存导致的未命中。
3. 冲突未命中（conflict miss）：出现在硬件中，因为硬件缓存中对项的放置位置有限制，这是由于所谓的集合关联性。

策略：FIFO

许多操作系统早期避免尝试达到最优的复杂性，采用了类似于FIFO的替换策略。页在进入系统时，简单放入一个队列，当发生替换时，队列尾部的页被踢出。

它的优点是实现相当的简单。缺点是FIFO无法确定页的重要性，即使页已经被多次访问，它还是会被踢出。

策略：随机

随机策略是指，在内存满的时候随机选择一个页进行替换。优点是实现简单，但是和FIFO一样挑选替换哪个页时不够智能。随机的表现完全取决于幸运。

策略：LRU

页的替换策略可以使用一个历史信息是频率，如果一个页被访问了很多次，也许它不应该被替换，因为它显然更有价值。页更常用的属性是访问的近期性，越近被访问的页，也许再次访问的可能性越大。

这一系列的策略是基于人们所说的局部性原则（principle of locality）。这个原理简单说就是程序倾向于频繁访问某些代码和数据结构。因此基于上面的原理诞生了一系列的算法，如最不经常用（Least-Frequently-Used，LFU）策略会替换最不经常使用的页，最少最近使用（Least-Recently-Used，LRU）策略替换最近最少使用的页面。