地址转换

在实现 CPU 虚拟化时，我们遵循的一般准则被称为受限直接访问(LDE)。LDE 背后的想法很简单：让程序运行的大部分指令直接访问硬件，只在一些关键点由操作系统介入，以确保“在正确的时间地点，做正确的事情”。为了实现高效的虚拟化，操作系统应该尽量让程序自己运行，同时通过在关键点的及时介入，来保持对硬件的控制。高效和控制是现代操作系统的两个主要目标。

在实现虚拟内存时，我们将追求类似的战略，在实现高效和控制的同时，提供期望的虚拟化。高效决定了我们要利用硬件的支持，这在开始的时候非常初级，但会逐渐变得相当复杂。控制意味着操作系统要确保应用程序只能访问它自己的内存空间。因此，要保护应用程序不会互相影响且不影响操作系统本身，我们还是需要硬件的帮助。最后，我们对虚拟内存还有一点要求，即灵活性。具体来说，我们希望程序能够以任何方式访问它自己的地址空间，从而让操作系统更易编程。所以关键问题在于：

关键问题：如何高效、灵活的虚拟化内存

我们利用了一种通用技术，有时被称为硬件的地址转换，简称地址转换。它可以被看做是受限执行这种一般方法的补充。利用地址转换，硬件对每次的内存访问都进行处理，将指令中的虚拟地址转换为实际存储数据的物理地址。因此，在每次内存引用时，硬件都会进行地址转换，将应用程序的内存引用重定位到内存中实际的位置。

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

同样，所有这些工作都是为了创造一种美丽的假象：每个程序都拥有私有的内存，那里存放着它自己的代码和数据。虚拟现实的背后是丑陋的物理现实：许多程序其实是在同一时间共享着内存，就像 CPU 在不同的程序之间切换运行。通过虚拟化，操作系统将丑陋的机器现实转换为一种有用的、强大的、且易于使用的抽象。

假设

我们先假设用户的地址空间必须连续的存放在物理内存中。同时为了简单，我们假设地址空间不是很大，小于物理内存的大小。最后，假设每个地址空间的大小完全一样。

实例

为了更好的理解地址转换的实现，我们先来看一个例子。设想一个进程的地址空间如下图所示。这里我们需要检查一小段代码，它从内存加载一个值，对其加 3，让后再放回内存。

void func() {
	int x;
	x = x + 3;
}

编译器将这段代码转换为类似如下汇编代码：

128: movl 0x0(%ebx), %eax   ;load 0+ebx into eax
132: addl $0x03, %eax       ;add 3 to eax register
135: movl %eax, 0x0(%ebx)   ;store eax back to mem

这段代码相对简单，它假定 x 的地址已经存入寄存去 ebx，之后通过 movl 指令将该地址的值加载到通用寄存器 eax。下一条指令对 eax 的值加 3。最后一条指令将 eax 中的值写回到内存的同一位置。

提示：介入很强大 介入是一种很常见又很强大的技术，计算机系统中使用介入常常能带来很好的效果。在虚拟内存中，硬件可以介入到每次内存访问中，将进程提供的虚拟地址转换为数据实际存储的物理地址。但是，一般化的介入技术有更加广阔的应用空间，实际上几乎所有良好定义的接口都应该提供介入机制，以便增加功能或在其他方面提升系统。这种方式最基本的特点是透明，介入完成时通常不需要改动接口的客户端，因此客户端不需要任何改动。

在前面的图中，可以看到代码和数据都位于进程的地址空间，3 条指令序列位于地址 128，变量 x 的值位于地址 15KB。如前图所示，x 的初始值为 3000。

如果这 3 条指令执行，从进程的角度来看，发生了以下几次内存访问：

• 从内存 128 获得指令。
• 执行指令(从地址 15KB 加载数据)。
• 从地址 132 获得命令。
• 执行命令(没有内存访问)。
• 从地址 135 获得指令。
• 执行指令(新值存入地址 15KB)。

从程序的角度来看，它的地址空间从 0 开始到 16KB 结束。它包含的所有内存引用都应该在该范围呢。然而，对虚拟内存来说，操作系统希望将该进程地址空间放在物理内存的其他位置，并不一定从地址 0 开始。因此我们遇到如下问题：怎样在内存中重定位该进程，同时对该进程透明？怎样提供一种虚拟地址空间从 0 开始的假象，而实际上地址空间位于另外某个物理地址？

上图展示了一个例子，说明该进程的地址空间被放入物理内存后可能的样子。从上图可以看到，操作系统将第一块物理内存留给了自己，并将上述例子中的进程地址空间重定位到从 32KB 开始的物理内存地址。剩下的两块内存空闲。

硬件动态重定位

为了更好的理解基于硬件的地址转换，我们先来讨论他的第一次应用。在 20 世纪 50 年代后期，它首次出现在分时系统中，那时只是一个简单的思想，称为地址加界限机制，有时又称为动态重定位，我们将交叉使用这两个术语。

具体来说，每个 CPU 需要两个硬件寄存器：基址寄存器和界限寄存器，或称为限制寄存器。这两个寄存器能够支持我们将地址空间放在屋里内存的任何位置，同时又能确保进程只能访问自己的地址空间。

采用这种方式，在编写和编译程序时假设地址空间从 0 开始。但是，当程序真正执行时，操作系统会决定其在物理内存中的实际加载地址，并将其实地址记录在基址寄存器中。在上面的例子中，操作系统决定加载在物理地址 32KB 的进程，因此将基址寄存器设置为这个值。

当进程运行时，有趣的事情发生了。现在，该进程产生的所有内存引用，都会被处理器通过以下方式转换为物理地址：

physical address = virtual address + base

补充：基于软件的重定位 在早期，在硬件支持重定位之前，一些系统曾经采用基于软件的重定位方式。基本技术被称为静态重定位，其中一个名为加载程序的软件接收将要运行的可执行程序，将它的地址重写到物理内存中期望的便宜位置。 然而，静态重定位存在很多问题，首先也是最重要的是不提供访问保护，进程中的错误地址可能导致对其他进程或操作系统内存的非法访问，一般来说，需要硬件支持来实现真正的访问保护。静态重定位的另一个缺点是一旦完成，稍后很难将内存空间重定位到其他位置。

进程中使用的内存引用都是虚拟地址，硬件接下来将虚拟地址加上基址寄存器中的内容，得到物理地址，再发给内存系统。

为了更好的理解，我们来追踪一条指令执行的过程。

128: movl 0x0(%ebx), %eax

程序计数器首先被设置为 128.当硬件需要获取该指令时，它先将该值加上基址寄存器中的 32KB(32768)，得到实际的物理地址为 32896，然后硬件从该地址获取指令。接下来，处理器开始执行该指令。这时，进程发起从虚拟地址 15KB 的加载，处理器同样将虚拟地址加上基址寄存器的内容(32KB)，得到最终的物理地址为 47KB，从而获得需要的数据。

将虚拟地址转换为物理地址，这正是所谓的地址转换技术。也就是说，硬件取得进程认为要访问的地址，将它转换成数据实际位于的物理地址。由于这种重定位是在运行时发生的，而且我们甚至可以在进程开始运行后改变其地址空间，这种技术一般被称为动态重定位。

提示：基于硬件的动态重定位 在动态定位的过程中，只有很少的硬件参与，但获得了很好的效果。一个基址寄存器将虚拟地址转换为物理地址，一个界限寄存器将确保这个地址在进程地址空间的范围内。它们一起提供了简单高效的虚拟内存机制。

现在你可能会问，界限寄存器去哪了？不是基址加上界限机制吗？正如你猜测的那样，界限寄存器提供了访问保护。在上面的例子中，界限寄存器被设置为 16KB。如果进程需要访问超过了该界限或者为负数的虚拟地址，CPU 将触发异常，进程可能被终止。界限寄存器的用处在于，它确保了进程产生的所有地址都在进程地址的界限内。

这种基址寄存器配合界限寄存器的硬件结构位于芯片内，每个 CPU 一对。有时我们将 CPU 的这个负责地址转换的部分统称为内存管理单元(MMU)。随着我们开发更加复杂的内存管理技术，MMU 也将拥有更为复杂的电路和功能。

关于界限寄存器再补充一点，它通常有两种使用方式。像上面这种方式中，它记录地址空间的大小，硬件在将虚拟地址与基址寄存器内容求和前，就检查这个界限。另一种方式是界限寄存器中记录地址空间结束的物理地址，硬件在转化虚拟地址到物理地址之后采取检查该界限。这两种方式在逻辑上是等价的。简单起见，我们这里假设采用第一种方式。

转换示例

为了更好的理解基址加界限的地址转换机制，我们来看一个例子。设想一个进程拥有 4KB 大小的地址空间，它被加载到从 16KB 开始的物理内存中。一些转换过程如下：

从例子可以看出，通过基址加虚拟地址(可以看做是地址空间的偏移量)的方式，很容易得到物理地址。虚拟地址过大或为负数，均会导致异常。

补充：数据结构——空闲列表 操心系统必须记录哪些空闲内存没有被使用，以便能够为进程分配内存。很多不同的数据结构可以用于这项任务，其中最简单的是空闲列表。它实际上是一个列表，记录了当前没有被使用的物理内存的范围。

硬件支持总结

首先，正如在 CPU 虚拟化中提到的，我们需要两种 CPU 模式。操作系统在特权模式运行，可以访问整个机器资源。应用程序在用户模式，只能执行有限的操作。只要一个位，也许保存在处理器状态字中，就能说明当前 CPU 的运行模式。在一些特殊的时刻，CPU 会切换状态，如系统调用、中断、异常。下图则是动态重定位的硬件要求：

硬件还必须提供基址和界限寄存器，因此每个 CPU 的内存管理单元都需要这两个额外的寄存器。用户程序运行时，硬件会转换每个地址，即将用户程序产生的虚拟地址加上基址寄存器的内容。硬件也必须能够检查地址是否有效，通过界限寄存器和 CPU 内的一些电路来实现。

硬件应该提供一些特殊指令，用于修改基址寄存器和界限寄存器，允许操作系统在切换进程时改变它们。这些指令是特权指令，只有在内核模式下才能修改这些寄存器。

最后，在用户程序尝试非法访问内存时，CPU 必须能够产生异常。在这种情况下，CPU 应该阻止用户程序的执行，并安排操作系统的越界异常处理程序来处理。操作系统的处理程序会做出正确的响应，比如在这种情况下终止进程。类似的，如果用户程序尝试修改基址或者界限寄存器，CPU 也应该产生异常，并调用“用户模式尝试执行特权指令”的异常处理程序。CPU 还必须提供一种方法，来通知它这些处理程序的位置，因此又需要一些特权指令。

操作系统的问题

为了支持动态重定位，硬件添加了新的功能，使得操作系统有了一些必须处理的新问题。硬件支持和操作系统管理结合在了一起，实现了一个简单的虚拟内存。具体来说，在一些关键时刻需要操作系统的接入，以实现基址和界限方式的虚拟内存。如下表。

第一，在进程创建时，操作系统必须采取行动，为进程的地址空间找到内存空间。由于我们假设每个进程的地址空间小于物理内存的大小，并且大小相同，这对操作系统来说很容易实现。它可以把整个物理内存看做一组槽块，并标记为空闲或已用。当新进程创建时，操作系统加锁这个数据结构，为新的地址空间找到位置，并将其标记与已用。如果地址空间可变，那么就会变得复杂，我们将在后续章节中讨论。

我们来看一个例子，在前一节的图中，操作系统将物理内存的第一个槽块分配给自己，然后将例子中的进程重定位到物理内存地址 32KB。另两个槽块空闲，因此空闲列表中就包含了这两个空闲槽块。

第二，在进程终止时，操作系统也必须做一些工作，回收进程的所有内存，以便给其他进程或操作系统使用。在进程终止时，操作系统会将这些内存放回到空闲列表，并根据需要清除相关的数据结构。

第三，在上下文切换时，操作系统也必须执行一些操作。每个 CPU 毕竟只有一个基址寄存器和一个界限寄存器，但对于每个运行的程序，它们的值都不同，因为每个程序被加载到内存中不同的物理地址。因此，在切换进程时，操作系统必须保存和恢复基址和界限寄存器。具体来说，当操作系统决定中止当前进程时，它必须将当前基址寄存器和界限寄存器中的内存保存在内存中，放在每个进程都拥有的结果中，如进程结构或进程控制块中。类似的，当操作系统恢复执行某个进程时，也必须给基址寄存器和界限寄存器恢复正确的值。

需要注意，当进程停止时，操作系统可以改变其地址空间的物理位置，这很容易。要移动进程的地址空间，操作系统首先让进程停止运行，然后将地址空间拷贝到新的位置，最后更新保存的基址寄存器，指向新的位置。当进程恢复执行时，它的新基址寄存器会被恢复，它再次开始运行，显然它的指令和数据都在新的内存位置了。

第四，操作系统必须提供异常处理程序，或需要一些调用的函数。操作系统在启动时加载这些处理程序。比如，当一个进程视图越界访问内存时，CPU 会触发异常。在这种异常产生时，操作系统必须准备采取行动。通常操作系统会做出充满敌意的反应：终止错误进程。操作系统应该尽力保护它运行的机器，因此它不会对那些企图访问非法地址或执行非法指令的进程客气。

下表展按时间线展示了大多数硬件与操作系统的交互。可以看出，操作系统在启动时做了什么，为我们准备好机器，然后在进程开始运行时发生了什么。请注意，地址转换过程完全由硬件处理，没有操作系统的介入。在这个时候，发生时钟中断，操作系统切换到进程 B 运行，它执行了“错误的加载”，这时操作系统必须介入，终止该进程，清理并释放进程 B 占用的内存，将它从进程表中移除。从表中可以看出，我们仍然遵循受限直接访问的基本方法，大多数情况下，操作系统正确设置硬件后，就任凭进程直接运行在 CPU 上，只有进程行为不端时才介入。

小结

本章通过虚拟内存使用的一种特殊机制，即地址转换，扩展了受限直接访问的概念。利用地址转换，操作系统可以控制进程的所有内存访问，确保访问在地址空间的界限内。该技术高效的关键在于硬件支持，硬件快速的将所有内存访问操作中的虚拟地址转换为物理地址。所有的这一切对进程来说是透明的，进程并不知道自己使用的内存引用已经被重定位。

我们还看到了一种特殊的虚拟化方式，称为基址界限的动态重定位。基址界限的虚拟化方式非常高效，因为只需要非常少的硬件逻辑，就可以将虚拟地址和寄存器地址相加，并检查进程产生的地址是否越界。基址界限也提供了保护，操作系统和硬件的协作，确保没有进程能够访问到其他地址空间的内容。保护肯定是操作系统最重要的目标之一。没有保护，操作系统也就无法控制机器。

遗憾的是，这个简单动态重定位技术有效率低下的问题。比如前面的例子中，重定位的进程使用了从 32KB 到 48KB 的物理内存，但由于该进程的栈区和堆区并不是很大，导致这块内存区域中大量的空间被浪费。这种浪费通常称为内部碎片，指的是已经分配的内存单元内部未有使用的空间，造成了浪费。在我们当前的方式中，即使有足够的内存容纳更多进程，但我们目前要求将地址空间放在固定的槽块中，因此会出现内存碎片。所以我们还需要一些复杂的机制，以便更好的利用物理内存，避免内部碎片。第一次尝试是将基址界限的概念稍微泛化，得到分段(segmentation)的概念。