2. 虚拟内存管理

  虚拟内存技术允许执行进程不必完全处于内存。这种方案的一个主要优点就是，程序可以大于物理内存。此外，虚拟内存将内存抽象成一个巨大的、统一的存储数组，进而实现了用户看到的逻辑内存与物理内存的分离。这种技术使得程序员不再担忧内存容量的限制。
  虚拟内存还允许进程轻松共享文件和实现共享内存。此外，它为创建进程提供了有效的机制。然而，虚拟内存的实现并不容易，并且使用不当还可能会大大降低性能。

2.1 背景

  内存管理算法是必要的，因为有一个基本要求：执行的指令应处于物理内存。满足这一要求的第一种方法是，将整个逻辑地址空间置于物理内存中。动态加载可以帮助缓解这种限制，但它通常需要特殊的预防措施和程序员的额外工作。
  指令应处于物理内存以便执行的要求，似乎是必要的和合理的；但它也是有缺点的，因为它将程序的大小限制为物理内存的大小。事实上，通过实际程序的研究会发现，在许多情况下并不需要将整个程序置于内存中。
  虚拟内存(virtual memory) 将用户逻辑内存与物理内存分开。这在现有物理内存有限的情况下，为程序员提供了巨大的虚拟内存，如下图所示。虚拟内存使得编程更加容易，因为程序员不再需要担心有限的物理内存空间，只需要关注所要解决的问题。

  进程的虚拟地址空间(virtual address space) 就是进程如何在内存中存放的逻辑(或虚拟)视图。通常，进程从某一逻辑地址(如地址0)开始，连续存放，如下图所示。物理地址可以按帧来组织，并且分配给进程的物理帧也可以不连续，这就需要内存管理单元(MMU) 将逻辑页映射到内存的物理页帧。

2.2 请求调页

  如何从磁盘加载可执行程序到内存。
  一种选择是，在程序执行时将整个程序加载到物理内存。然而，这种方法的一个问题是，最初可能不需要整个程序都处于内存。假设程序开始时带有一组用户可选的选项。加载整个程序会导致所有选项的执行代码都加载到内存中，而不管这些选项是否最终使用。
  另一种策略是，仅在需要时才加载页面。这种技术被称为请求调页(demand paging) ， 常常用于虚拟内存系统。对于请求调页的虚拟内存，页面只有在程序执行期间被请求时才被加载。因此，从未访问的那些页从不加载到物理内存中。

  请求调页系统类似于具有交换的分页系统，如下图所示，这里进程驻留在外存上(通常为磁盘)。当进程需要执行时，它被交换到内存中。不过，不是将整个进程交换到内存中，而是采用惰性交换器(lazy swapper) 。惰性交换器除非需要某个页面，否则从不将它交换到内存中。

  在请求调页的上下文中，使用术语“交换器”在技术上是不正确的。交换器操纵整个进程， 而调页程序(pager) 只涉及进程的页面。因此，在讨论请求调页时，我们使用“调页程序”，而不是“交换器”。

2.3 页面置换

  如果增加了多道程序，那么可能会过度分配内存。
  内存的过度分配会有问题。当用户进程正在执行时，可能发生缺页错误。操作系统确定所需页面的磁盘位置，但是却发现空闲帧列表上没有空闲帧，所有内存都在使用。
  这时，操作系统有多个选项。它可以终止用户进程。然而，请求调页是操作系统试图改善计算机系统的使用率和吞吐量的技术。用户不应该意识到，他们的进程是运行在调页系统上：对用户而言，调页应是透明的。因此，这个选择并不是最佳的。
  此外，操作系统也可以交换出一个进程，以释放它的所有帧并降低多道程度。在某些情况下，这个选项是不错的。这里，我们讨论最常见的解决方案：页面置换(page replacement) 。

2.3.1 基本页面置换

  页面置换采用以下方法。如果没有空闲帧，那么就查找当前不再使用的一个帧，并释放它。可以这样来释放一个帧：将其内容写到交换空间，并修改页表(和所有其他表)，以表示该页不在内存中，如下图所示。

  现在可使用空闲帧，来保存进程出错的页面。修改缺页错误处理程序，以包括页面置换：
   1. 找到所需页面的磁盘位置。
   2. 找到一个空闲帧：
    a. 如果有空闲帧，那么就使用它。
    b. 如果没有空闲帧， 那么就使用页面置换算法来选择一个牺牲帧(victim frame) 。
    c. 将牺牲帧的内容写到磁盘上，修改对应的页表和帧表。
   3. 将所需页面读入(新的)空闲帧，修改页表和帧表。
   4. 从发生缺页错误位置，继续用户进程。
  注意，如果没有空闲帧，那么需要两个页面传输(一个调出，一个调入)。这种情况实际上加倍了缺页错误处理时间，并相应地增加了有效访问时间。
  为实现请求调页， 必须解决两个主要问题：应设计帧分配算法(frame-allocation algorithm)和页面置换算法(page-replacement algorithm) 。也就是说， 如果有多个进程在内存中， 则必须决定要为每个进程分配多少帧；并且当需要页面置换时，必须选择要置换的帧。设计适当的算法来解决这些问题是个重要任务，因为磁盘I/O是如此昂贵。即使请求调页方法的轻微改进也会为系统性能带来显著提高。

2.3.2 FIFO页面置换

  最简单的页面置换算法是FIFO（First In First Out）算法。FIFO页面置换算法为每个页面记录了调到内存的时间。当必须置换页面时，将选择最旧的页面。请注意，并不需要记录调入页面的确切时间。
  可以创建一个FIFO队列， 来管理所有的内存页面，置换的是队列的首个页面。当需要调入页面到内存时，就将它加到队列的尾部。

2.3.3 最优页面置换

  最优页面置换即置换最长时间不会使用的页面。
  这种页面置换算法确保，对于给定数量的帧会产生最低的可能的缺页错误率。

2.3.4 LRU页面置换

  最近最少使用算法（Least-Recent-Used algorithm，LRU算法）。
  LRU置换将每个页面与它的上次使用的时间关联起来。

2.3.5 基于计数的页面置换

  页面置换还有许多其他算法。例如，可以为每个页面的引用次数保存一个计数器，并且开发以下两个方案：
    - 最不经常使用(Least Frequently Used， LFU) 页面置换算法要求置换具有最小计数的页面。这种选择的原因是，积极使用的页面应当具有大的引用计数。然而，当一个页面在进程的初始阶段大量使用但是随后不再使用时，会出现问题。由于被大量使用，它有一个大的计数，即使不再需要却仍保留在内存中。一种解决方案是，定期地将计数右移1位，以形成指数衰减的平均使用计数。
    - 最经常使用(Most Frequently Used， MFU) 页面置换算法是基于如下论点：具有最小计数的页面可能刚刚被引人并且尚未使用。

2.4 帧分配

  在各个进程之间，如何分配固定数量的可用内存？每个进程各分配多少帧？

2.4.1 帧的最小数

  帧分配策略受到多方面的限制。例如，所分配的帧不能超过可用帧的数量，也必须分配至少最小数量的帧。
  分配至少最小数量的帧的一个原因涉及性能。显然，随着分配给每个进程的帧数量的减少，缺页错误率增加，从而减慢进程执行。此外，请记住，若在执行指令完成之前发生缺页错误，应重新启动指令。因此，必须有足够的帧来容纳任何单个指令可以引用的所有不同的页面。

2.4.2 分配算法

  平均分配： 每个进程分配相同数量的帧。
  按比例分配： 进程占用内存越大，分配帧的数量越多。

2.4.3 全局分配与局部分配

  为各个进程分配帧的另一个重要因素是页面置换。由于多个进程竞争帧，可以将页面置换算法分为两大类：全局置换(global replacement) 和局部置换(local replacement) 。
  全局置换允许一个进程从所有帧的集合中选择一个置换帧，而不管该帧是否已分配给其他进程；也就是说，一个进程可以从另一个进程那里获取帧。
  局部置换要求每个进程只从它自己分配的帧中进行选择。

2.5 系统抖动

  如果进程没有需要支持活动使用页面的帧数，那么它会很快产生缺页错误。此时，必须置换某个页面。然而，由于它的所有页面都在使用中，所以必须立即置换需要再次使用的页面。因此，它会再次快速产生缺页错误，再一次置换必须立即返回的页面，如此快速进行。这种高度的页面调度活动称为抖动。如果一个进行的调页时间多于它的执行时间，那么这个进程就在抖动。

2.5.1 系统抖动的原因

  抖动导致严重的性能问题。考虑以下场景，这是基于早期调页系统的实际行为。
  操作系统监视CPU利用率。 如果CPU利用率太低， 那么通过向系统引人新的进程来增加多道程度。采用全局置换算法会置换任何页面，而不管这些页面属于哪个进程。现在假设进程在执行中进入一个新阶段，并且需要更多的帧。它开始出现缺页错误，并从其他进程那里获取帧。然而，这些进程也需要这些页面，因此它们也会出现缺页错误，并且从其他进程中获取帧。这些缺页错误进程必须使用调页设备以将页面换进和换出。当它们为调页设备排队时， 就绪队列清空。随着进程等待调页设备， CPU利用率会降低。
  CPU调度程序看到CPU利用率的降低， 进而会增加多道程度。新进程试图从其他运行进程中获取帧来启动， 从而导致更多的缺页错误和更长的调页设备队列。因此， CPU利用率进一步下降， 并且CPU调度程序试图再次增加多道程度。这样就出现了抖动， 系统吞吐量陡降。缺页错误率显著增加。结果，有效内存访问时间增加。没有工作可以完成，因为进程总在忙于调页。
  如何解决抖动问题？
   1. 通过局部置换算法。
   2. 工作集模型。
   3. 缺页错误频率：设置缺页错误率的上下限。

2.5.2 内存映射文件

  假设采用标准系统调用open() 、read() 和write() 来顺序读取磁盘文件。每个文件访问都需要系统调用和磁盘访问。或者，采用所讨论的虚拟内存技术，以将文件I/O作为常规内存访问。这种方法称为内存映射(memory mapping) 文件， 允许一部分虚拟内存与文件进行逻辑关联。正如我们将会看到的，这可能导致显著的性能提高。