《操作系统导论》四、内存虚拟化(1)

13-抽象：地址空间

早期系统

早期操作系统是一组函数(实际上是一个库)，在内存中(在本例中，从物理地址0开始)，然后有一个正在运行的程序(进程)，目前在物理内存中(在本例中，从物理地址64KB开始)，并使用剩余的内存。

多道程序和时分共享

由于机器昂贵，人们开始更高效地共享机器(提高效率)。
因此，多道程序系统时代开启，其中多个进程在给定时间准备运行，比如当有一个进程在等待I/O操作的时候，操作系统会切换这些进程，这样增加了CPU的有效利用率。

随着人们开始对机器的要求增多，分时系统的时代诞生。
具体来说，很多人意识到批量计算的局限性，尤其是程序员本身，他们厌倦了长时间(低效率)编程–调试循环。交互型变的很重要，因为许多用户可能同时在使用机器，每个人都在等待（或希望）他们执行的任务及时响应。

一种实现时分共享的方法，是让一个进程单独占用全部内存运行一小段时间，然后停止它，并将它所有的状态信息保存在磁盘上(包含所有的物理内存)，加载其他进程的状态信息，再运行一段时间，这就实现了某种比较粗糙的机器共享。

遗憾的是，这种方法有一个问题：太慢了，特别是当内存增长的时候。虽然保存和恢复寄存器级的状态信息(程序计数器、通用寄存器等)相对较快，但将全部的内存信息保存到磁盘就太慢了。因此，在进程切换时，我们仍然将进程信息放在内存中，这样操作系统可以更有效率地实现时分共享。

随着时分共享变得更流行，人们对操作系统又有了新的要求。特别是多个程序同时驻留在内存中，使保护成为重要问题。人们不希望一个进程可以读取其他进程的内存，更别说修改了。

地址空间

因此操作系统需要提供一个易用(easy to use)的物理内存抽象。这个抽象叫作地址空间(address space)，是运行的程序看到的系统中的内存。理解这个基本的操作系统内存抽象，是了解内存虚拟化的关键。

一个进程的地址空间包含运行的程序的所有内存状态。

接下来，在程序运行时，地址空间有两个区域可能增长(或者收缩)。它们就是堆(在顶部)和栈(在底部)。

关键问题：如何虚拟化内存

操作系统如何在单一的物理内存上为多个运行的进程(所有进程共享内存)构建一个私有的、可能很大的地址空间的抽象？

当操作系统这样做时，我们说操作系统在虚拟化内存，因为运行的程序认为它被加载到特定地址(例如0)的内存中，并且具有非常大的地址空间。现实很不一样。

例如，当图13.2的进程A尝试在地址0(我们将其为虚拟地址，virtual address)执行加载操作时，然而操作系统在硬件的支持下，出于某种原因，必须确保不是加载到物理地址0，而是物理地址320KB(这是A载入内存的地址)。这是内存虚拟化的关键，这是世界上每一个现代计算机系统的基础。

提示：隔离原则

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

目标

虚拟化内存(VM)系统的一个主要目标是透明(transparency)。操作系统实现虚拟内存的方式，应该让运行的程序看不见。因此，程序不应该感知到内存被虚拟化的事实，相反，程序的行为就好像它拥有自己的私有物理内存。

虚拟内存的另一个目标是效率(efficiency)。操作系统应该追求虚拟化尽可能高效，包括时间上(即不会使程序运行得更慢)和空间上(即不需要太多额外得内存来支持虚拟化)。在实现高效率虚拟化时，操作系统将不得不依靠硬件支持，包括TLB这样得硬件功能。

最后，虚拟内存第三个目标是保护(protection).操作系统应确保进程收到保护，不会受到其他进程影响，操作系统本身也不会受进程影响。当一个进程执行加载、存储或指令提取时，它不应该以任何方式访问或影响任何进程或操作系统本身的内存内容(即在它的地址空间之外的任何内容)。因此，保护让我们能够在进程之间提供隔离(isolation)的特性，每个进程都应该在自己的独立环境中运行，避免其他出错或恶意进程的影响。

14-插叙：内存操作API

关键问题：如何分配和管理内存

在UNIX/C程序中，理解如何分配和管理内存是构建健壮和可靠软件的重要基础。通常使用哪些接口？哪些错误需要避免？

内存类型

在运行一个C程序的时候，会分配两种类型的内存。第一种称为内存，它的申请和释放是编译器来隐式管理的，所以有时也称为自动(automatic)内存。(如在函数内部定义一个变量，编译器将确保进入func()函数的时候，在栈上开辟空间)。

第二种类型的内存，即所谓的堆(heap)内存，其中所有的申请和释放操作都由程序员显式地完成。

###补充：为什么在你的进程退出时没有内存泄漏
当你编写一个短时间运行的程序时，可能会使用malloc()分配一些空间。程序运行并即将完成：是否需要在退出前调用几次free()?虽然不释放似乎不对，但在真正的意义上，没有任何内存会“丢失”。原因很简单：系统中实际存在两级内存管理。
第一级是由操作系统执行的内存管理，操作系统在进程运行时将内存交给进程，并在进程退出(或以其他方式结束)时将其回收。第二级管理在每个进程中，例如在调用malloc()和free()时，在堆内管理。即使你没有调用free()(并因此泄露了堆中的内存)，操作系统也会在程序结束运行时，收回进程的所有内存(包括用于代码、栈，以及相关堆的内存页)。无论地址空间中堆的状态如何，操作系统都会在进程终止时收回所有这些页面，从而确保即使没有释放内存，也不会丢失内存。
因此，对于短时间运行的程序，泄露内存通常不会导致任何操作问题(尽管它可能被认为是不好的形式)。如果你编写一个长期运行的服务器，泄露内存就是很大的问题，最终会导致应用程序在内存不足时崩溃。

内存工具：purify valgrind

15-机制：地址转换

在实现CPU虚拟化时，我们遵循的一般准则被称为受限直接访问(Limited Direct Execution, LDE).LDE背后的想法很简单：让程序运行的大部分指令直接访问硬件，只在一些关键点(如进程发起系统调用或发生始终中断)由操作系统接入来确保“在正确时间，正确的地点，做正确的事”。为了实现高效的虚拟化，操作系统应该尽量让程序自己运行，同时通过关键点的及时介入(interposing)，来保持对硬件的控制。高效和控制是现代操作系统的两个主要目标。
高效决定了我们要利用硬件的支持，这在开始的时候非常初级(如使用一些寄存器)，但会变得相当复杂(比如我们会讲到的TLB、页表等)。控制意味着操作系统要确保应用程序只能访问自己的内存空间。
最后，我们对虚拟内存还有一点要求，即灵活性。具体来说，我们希望程序能以任何方式访问它自己的地址空间，从而让系统更容易编程。

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

如何实现高效的内存虚拟化？如何提供应用程序所需的灵活性？如何保持控制应用程序可访问的内存位置，从而确保应用程序的内存访问受到合理的限制？如何高效地实现这一切？

基于硬件的地址转化(hardware-based address translation),简称为地址转换(address translation)。利用地址转换，硬件对每次内存访问进行处理(即指令获取、数据读取或写入)，将指令中的虚拟(virtual)地址转换为数据实际存储的物理(physical)地址。因此，在每次内存引用时，硬件都会进行地址转换，将应用程序的内存引用重定位到内存中实际的位置。

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

基址加界限机制(base and bound),有时又称为动态重定位(dynamic relocation).
每个CPU需要两个硬件寄存器：基址(base)寄存器和界限(bound)寄存器，有时称为限制(limit)寄存器。这组基址和界限寄存器，让我们能够将地址空间放在物理内存的任何位置，同时又能确保进程只能访问自己的地址空间。

采用这种方式，在编写和编译程序时假设地址空间从零开始。但是当程序真正执行时，操作系统会决定其在物理内存中的实际加载地址，并将起始地址记录在基址寄存器中。

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

补充：基于软件的重定位

在早期，在硬件支持重定位之前，一些系统曾经采用纯软件的重定位方式。基本技术被称为静态重定位(static relocation)，其中一个名为加载程序(loader)的软件接收将要运行程序，将它的地址重写到物理内存中期望的偏移位置。
例如，程序中有一条指令时从地址1000加载到寄存器(即movl 1000, %eax)，当整个程序的地址空间被加载到从3000(不是程序认为的0)开始的物理地址中，加载程序会重写指令中的地址(即movl 4000，%eax),从而完成简单的静态重定位。
然而，静态重定位有很多问题，首先也是最重要的是不提供访问保护，进程中的错误地址可能导致对其他进程或操作系统内存的非法访问，一般来说，需要硬件支持来实现真正的访问保护。静态重定位的另一个缺点是一旦完成，稍后很难将内存空间重定位到其他位置。(why？)

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

界限(限制)寄存器提供了访问保护。如果进程需要访问超过了界限或者为负数的虚拟地址，CPU将触发异常，进程最终可能被停止。

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

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

遗憾的是，这个简单的动态重定位技术有效率低下的问题。另外，在我们当前的方式中，及时有足够的物理内存容纳更多进程，但我们目前要求将地址空间放在固定大小的槽块中，因此会出现碎片(指的是已经分配的内存单元内部有未使用的空间，造成了浪费)。所以我们需要更复杂的基址，以便更好地利用物理内存，避免内部碎片。

16-分段

从图16.1中可知，如果我们将整个地址空间放入物理内存，那么栈和堆之间的空间并没有被进程使用，却依然占用了实际的物理内存。因此，简单的通过基址寄存器和界限寄存器实现的虚拟内存很浪费。另外，如果剩余物理内存无法提供连续区域来放置完整的地址空间，进程便无法运行。这种基址加界限的方式看来并不像我们期望的那样灵活。因此：

关键问题：怎样支持大地址空间

怎样支持大地址空间，同时栈和堆之间(可能)有大量空闲空间？在之前的例子里，地址空间非常小，所以这种浪费并不明显。但设想一个32位(4GB)的地址空间，通常的程序只会使用几兆的内存，但需要真个地址空间都放在内存中

分段：泛化的基址/界限

分段并不是一个新概念，它甚至可以追溯到20世纪60年代初期。这个想法很简单，在MMU中引入不止一个基址和界限寄存器对，而是给地址空间内的每个逻辑段(segment)一对。一个段只是地址空间里的一个连续定长的区域，在典型的地址空间里有3个逻辑不同的段：代码、栈和堆。分段的机制使得操作系统能够将不通的段放到不同的物理内存区域，从而避免了地址空间中未使用部分占用物理内存。

如图16.2，64KB的物理内存中设置了3个段；只有已用的内存才在物理内存中分配空间，因此可以容纳巨大的地址空间，其中包含大量未使用的地址空间(有时又称为稀疏地址空间，sparse address spaces)。

因此，需要MMU中的硬件结构来支持分段：需要一组3对基址和界限寄存器。表16.1展示了上面的例子中的寄存器值，每个界限寄存器记录了一个段的大小。

补充：段错误

段错误指的是在支持分段的机器上发生了非法的内存访问。有趣的是，即使在不支持分段的机器上这个术语依然保留。

引用哪个段？

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

一种常见的方式，有时称为显式(explicit)方式，就是用虚拟地址的开头几位标识不同的段。

使用两位来区分段，但实际只有3个段(代码、堆、栈)，因此有一个段的地址空间被浪费(WHY?)。因此有些系统中会将堆和栈当作同一个段，因此只需要一位来标识。

硬件还有其他方法来决定特定地址在哪个段。在隐式(implicit)方式中，硬件通过地址产生的方式确定段。例如，如果地址由程序计数器产生(即它时指令获取)，那么地址在代码段。如果基于栈或基址指针，它一定在栈段。其他地址则在堆段(怎么区分是栈或基址指针？)。

支持共享

随着分段机制的不断改进，系统设计人员很快意识到，通过再多一点的硬件支持，就能实现新的效率提升。具体来说，要节省内存，有时候在地址空间之间共享(share)某些内存段是有用的。尤其是，代码共享很常见，今天的系统仍然在使用。

为了支持共享，需要一些额外的硬件支持，这就是保护位(protection bit).基本为每个段增加了几个位，标识程序是否能否读写该段，或执行其中的代码。通过将代码段标记为只读，同样的代码段可以被多个进程共享，而不用担心破坏隔离。虽然每个进程都认为自己独占这块内存，但操作系统秘密地共享了内存，进程不能修改这些内容，所以假象得以保持。

细粒度与粗粒度的分段

到目前为止，我们的例子大多针对只有很少的几个段的系统(即代码、栈、堆).我们可以认为这种分段是粗粒度的(coarse-grained)，因为它将地址空间分成较大的、粗粒度的块。但是，一些早期系统(如Multics)更灵活，允许将地址空间划分位大量较小的段，这被称为细粒度(fine-grained)分段。

支持许多段需要进一步的硬件支持，并在内存中保存某种段表(segment table).这种段表通常支持创建非常多的段，因此系统使用段的方式，可以比之前讨论的方式更灵活。

操作系统支持

第一个老问题：操作系统在上下文切换时应该做什么？
各个段寄存器中内容必须保存和恢复。显然，每个进程都有自己独立的虚拟地址空间，操作系统必须在进程运行前，确保这些寄存器被正确地赋值。

第二个问题，即管理物理内存的空闲空间。
新的地址空间被创建时，操作系统需要在物理内存中为它的段找到空间。之前，我们假设所有的地址空间大小相同，物理内存可以被认为是一些槽块，进程可以放进去。现在，每个进程都有一些段，每个段的大小也可能不同。

一般会遇到的问题是，物理内存很快充满了许多空闲的小洞，因而很难分配给新的段，或扩大已有的段。这种问题被称为外部碎片(external fragmentation).

在这个例子中，一个进程需要分配一个20KB的段。当前有24KB空闲，但并不连续(是3个不相邻的块)。因此，操作系统无法满足这个20KB的请求。

该问题的一种解决方案是紧凑(compact)物理内存，重新安排原有的段。例如，操作系统先终止运行的进程，将它们的数据复制到连续的内存区域中去，改变他们的段寄存器中的值，指向新的物理地址，从而得到了足够大的连续空闲空间。这样做，操作系统能让新的内存分配请求成功。但是，内存紧凑成本很高，因为拷贝段是内存密集型的，一般会占用大量的处理器时间。

一种更简单的做法是利用空闲列表管理算法，试图保留大的内存块用于分配。相关的算法可能有成百上千种，包括传统的最优分配(best-bit，从空闲链表种找最接近需要分配空间的空闲块返回)、最坏匹配(worst-fit)、首次匹配(first-fit)、以及像伙伴算法(buddy algorithm)这样更复杂的算法。

小结

分段解决了一些问题，帮助我们实现了更高效的虚拟内存。不只是动态重定位，通过避免地址空间的逻辑段之间的大量潜在的内存浪费，分段能更好地支持稀疏地址空间。它还很快，因为分段要求的算法很容易，很适合硬件完成，地址转换的开销极小。分段还有一个附加的好处：代码共享。如果代码放在独立的段中，这样的段就可能被多个运行的程序共享。

但我们已经知道，在内存中分配不同大小的段会导致一些问题，我们希望克服。首先，是我们上面讨论的外部碎片。由于段的大小不同，空闲内存被割裂成各种奇怪的大小，因此满足内存分配请求会很难。用户可以尝试采用聪明的算法，或定期紧凑内存，但问题很根本，难以避免。

第二个问题也许更重要，分段还是不足以支持更一般化的稀疏地址空间。例如，如果有一个很大但是稀疏的堆，都在一个逻辑段中，整个堆仍然必须完整地加载到内存中。换而言之秒如果使用地址空间的方式不能很好地匹配底层分段的涉及目标，分段就不能很好地工作。

17-空闲空间管理

如果需要管理的空间被划分为固定大小的单元，就很容易。在这种情况下，只需要维护这些大小固定的单元的列表，如果有请求，就返回列表中的第一项。

如果要管理的空闲空间由大小不同的单元构成，管理就变得困难。这汇总情况出现在用户级的内存分配库(如malloc()和free())，或者操作系统用分段(segmentation)的方式实现虚拟内存。在这两种情况下，出现了外部碎片的问题：空闲空间被分割成不同大小的小块，称为碎片，后续的请求可能失败，因为没有一块足够大的连续空闲空间。

关键问题：如何管理空闲空间

要满足变长的分配请求，应该如何管理空闲空间？什么策略可以让碎片最小化？不同方法的时间和空间开销如何？

底层机制

free(void *ptr)接口没有块大小的参数，大多数分配程序都会在头块(header)中保存一点额外的信息，它在内存中，通常就在返回的内存块之前。(其中magic用来提供完整性检查，以及其他信息)

实际释放的是头块大小加上分配给用户的空间的大小。

基本策略

理想的分配程序可以同时保证快速和碎片的最小化。遗憾的是，由于分配及释放的请求序列是任意的(毕竟，它们由用户程序决定)，任何特定的策略在某组不匹配的输入下都会变得非常差。所以我们不会描述"最好""的策略，而是介绍一些基本的选择，并讨论它们的优缺点。

• 最优匹配
  最优匹配（best fit）策略非常简单：首先遍历整个空闲列表，找到和请求大小一样或更大的空闲块，然后返回这组候选者中最小的一块。这就是所谓的最优匹配（也可以称为最小匹配）。只需要遍历一次空闲列表，就足以找到正确的块并返回。
  最优匹配背后的想法很简单：选择最接近用户请求大小的块，从而尽量避免空间浪费。然而，这有代价。简单的实现在遍历查找正确的空闲块时，要付出较高的性能代价。
• 最差匹配
  最差匹配（worst fit）方法与最优匹配相反，它尝试找最大的空闲块，分割并满足用户需求后，将剩余的块（很大）加入空闲列表。最差匹配尝试在空闲列表中保留较大的块，而不是向最优匹配那样可能剩下很多难以利用的小块。但是，最差匹配同样需要遍历整个空闲列表。更糟糕的是，大多数研究表明它的表现非常差，导致过量的碎片，同时还有很高的开销。
• 首次匹配
  首次匹配（first fit）策略就是找到第一个足够大的块，将请求的空间返回给用户。同样，剩余的空闲空间留给后续请求。
  首次匹配有速度优势（不需要遍历所有空闲块），但有时会让空闲列表开头的部分有很多小块。因此，分配程序如何管理空闲列表的顺序就变得很重要。一种方式是基于地址排序（address-based ordering）。通过保持空闲块按内存地址有序，合并操作会很容易，从而减少了内存碎片
• 下次匹配
  不同于首次匹配每次都从列表的开始查找，下次匹配（nextfit）算法多维护一个指针，指向上一次查找结束的位置。其想法是将对空闲空间的查找操作扩散到整个列表中去，避免对列表开头频繁的分割。这种策略的性能与首次匹配很接近，同样避免了遍历查找。

其他方式

• 分离空闲列表
  如果某个应用程序经常申请一种(或几种)大小的内存空间，那就用要给独立的列表，只管理这样大小的对象，其他大小的请求都交给更通用的内存分配程序。
  这种方法的好处显而易见。通过拿出一部分内存专门满足某种大小的请求，碎片就不再是问题了。而且，由于没有复杂的列表查找过程，这种特定大小的内存分配和释放都很快。
  就像所有好主意一样，这种方式也为系统引入了新的复杂性。例如，应该拿出多少内存来专门为某种大小的请求服务，而将剩余的用来满足一般请求？超级工程师Jeff Bonwick为Solaris系统内核设计的厚块分配程序（slab allocator），很优雅地处理了这个问题[B94]。
  具体来说，在内核启动时，它为可能频繁请求的内核对象创建一些对象缓存（object cache），如锁和文件系统inode等。这些的对象缓存每个分离了特定大小的空闲列表，因此能够很快地响应内存请求和释放。如果某个缓存中的空闲空间快耗尽时，它就向通用内存分配程序申请一些内存厚块（slab）（总量是页大小和对象大小的公倍数）。相反，如果给定厚块中对象的引用计数变为0，通用的内存分配程序可以从专门的分配程序中回收这些空间，这通常发生在虚拟内存系统需要更多的空间的时候。
  厚块分配程序比大多数分离空闲列表做得更多，它将列表中的空闲对象保持在预初始化的状态。Bonwick指出，数据结构的初始化和销毁的开销很大[B94]。通过将空闲对象保持在初始化状态，厚块分配程序避免了频繁的初始化和销毁，从而显著降低了开销。
• 伙伴系统
  因为合并对分配程序很关键，所以人们设计了一些方法，让合并变得简单，一个好例子就是二分伙伴分配程序（binarybuddy allocator）[K65]。
  在这种系统中，空闲空间首先从概念上被看成大小为2N的大空间。当有一个内存分配请求时，空闲空间被递归地一分为二，直到刚好可以满足请求的大小（再一分为二就无法满足）。这时，请求的块被返回给用户。在下面的例子中，一个64KB大小的空闲空间被切分，以便提供7KB的块：

在这个例子中，最左边的8KB块被分配给用户（如上图中深灰色部分所示）。请注意，这种分配策略只允许分配2的整数次幂大小的空闲块，因此会有内部碎片（internal fragment）的麻烦。
伙伴系统的漂亮之处在于块被释放时。如果将这个8KB的块归还给空闲列表，分配程序会检查“伙伴”8KB是否空闲。如果是，就合二为一，变成16KB的块。然后会检查这个16KB块的伙伴是否空闲，如果是，就合并这两块。这个递归合并过程继续上溯，直到合并整个内存区域，或者某一个块的伙伴还没有被释放。
伴系统运转良好的原因，在于很容易确定某个块的伙伴。怎么找？仔细想想上面例子中的各个块的地址。如果你想得够仔细，就会发现每对互为伙伴的块只有一位不同，正是这一位决定了它们在整个伙伴树中的层次。

大多数传统的分配程序会从很小的堆开始，当空间耗尽时，再向操作系统申请更大的空间。通常，这意味着它们进行了某种系统调用(例如，大多数UNIX系统中的sbrk)，让堆增长。操作系统在执行sbrk系统调用时，会找到空闲的物理内存页，将它们映射到请求进程的地址空间中去，并返回新的堆的末尾地址。这时，就有了更大的堆，请求就可以成功满足。