1. 传统存储管理方式的特征#

3.1节讨论的各种内存管理策略，都是为了将多个进程同时保留在内存中，以支持多道程序设计。它们具有以下两个共同特征。

1. 一次性。作业必须一次性全部装入内存后才能开始运行。这会带来两个问题：
   1. 当作业过大而无法全部装入内存时，该作业将无法运行；
   2. 当大量作业请求运行时，由于内存不足以容纳所有作业，只能让少数作业先运行，导致系统并发度下降。
2. 驻留性。作业一旦装入内存，便一直驻留其中，其任何部分都不会被换出，直至作业运行结束。然而，运行中的进程常因等待I/O而被阻塞，可能长时间处于等待状态。

由上述分析可知，许多在程序运行中暂未使用或暂时不用的代码和数据仍占据大量内存空间，而一些急需运行的作业却因内存不足无法装入，显然造成了宝贵内存资源的浪费。

2. 局部性原理#

要真正理解虚拟内存技术的思想，首先必须了解著名的局部性原理。从广义上讲，快表、页高速缓存及虚拟内存技术都属于缓存技术，这个技术所依赖的原理就是局部性原理。局部性原理既适用于程序结构，又适用于数据结构。局部性原理表现在以下两个方面。

1. 时间局部性。程序中的某条指令或某个数据项一旦被访问，不久之后很可能再次被访问。这主要是由于程序中存在大量的循环和重复操作。
2. 空间局部性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很可能被访问。这是因为指令通常按顺序存放并顺序执行，而数据（如向量、数组、表等）也一般以连续或簇聚的方式存储。

时间局部性通过将近期使用的指令和数据保存在高速缓存中，并借助多级缓存层次结构加以利用；空间局部性则通过采用较大容量的缓存，并集成预取机制到缓存控制逻辑中实现。虚拟内存技术正是基于局部性原理，将外存作为内存的透明扩展，有效缓解物理内存不足的问题。

3. 虚拟存储器的定义和特征#

基于局部性原理，在程序装入时，仅需将当前运行所需的少数页面（或段）装入内存，其余部分暂留外存，即可启动程序执行。在程序执行过程中，若所访问的信息不在内存中，则操作系统会自动将其从外存调入内存，然后继续执行程序，这一机制称为请求调页（或请求调段）。当内存空间不足时，操作系统又会将暂时不用的信息换出到外存，以腾出空间存放即将调入的内容，这一机制称为页面置换（或段置换）。正是通过这两种机制的协同工作，系统为用户提供了一个逻辑上远大于物理内存的地址空间，称为虚拟存储器。

之所以称为“虚拟”存储器，是因为该存储器并非真实存在的物理实体，而是操作系统通过部分装入、请求调入和置换功能（均对用户透明）所构造的一种逻辑抽象。用户程序可像使用大容量内存一样运行，而无须关心物理内存的实际大小。虚拟存储器有以下三个主要特征。

1. 多次性。作业无须在运行前一次性全部装入内存，而是可以分多次动态调入。只需将当前需要执行的程序和数据装入内存即可开始运行，后续所需部分在访问时按需调入。
2. 对换性。作业在运行过程中无须常驻内存，操作系统可根据需要，将暂不使用的程序或数据换出至外存对换区，并在后续需要时再换入内存，从而实现内存的高效利用。
3. 虚拟性。从用户视角看，内存容量被逻辑扩充，呈现出远大于实际物理内存的可用空间。虚拟性正是虚拟存储器的本质特征和根本目标，其实现依赖于多次性与对换性。

4. 虚拟内存技术的实现#

虚拟内存技术允许将一个作业分多次调入内存。若采用连续分配方式，则会导致相当一部分内存空间处于暂时甚至“永久”的空闲状态，不仅造成内存资源的严重浪费，也无法从逻辑上扩充内存容量。因此，虚拟内存的实现必须建立在离散分配的内存管理方式基础之上。

目前，虚拟内存主要有以下三种实现方式：

• 请求分页存储管理。
• 请求分段存储管理。
• 请求段页式存储管理。

无论采用哪种方式，均需一定的硬件支持，主要包括以下几个方面：

• 足够容量的内存和外存，用于存放程序的当前部分与后备部分。
• 页表机制（或段表机制），作为地址映射的关键数据结构。
• 中断机构，用于在用户程序访问尚未调入内存的部分时，触发缺页（或缺段）中断。
• 地址变换机构，负责在程序运行过程中动态地将逻辑地址转换为物理地址。

1. 页表机制#

相比于基本分页系统，请求分页系统中的页表需提供更多信息，以支持请求调页和页面置换。具体而言，操作系统必须能够：

1. 判断某页是否已调入内存；
2. 若尚未调入，则还需获知该页在外存中的存放位置；
3. 在页面置换时，依据访问特征选择合适的换出页面；
4. 对于要换出的页面，还需知道其是否被修改过，以决定是否需写回外存。

为此，请求分页的页表项在基本结构基础上增加了四个字段，如图3.19所示。

| 页号 | 物理块号 | 状态位P | 访问字段A | 修改位M | 外存地址 |

图3.19 请求分页系统中的页表项

各新增字段的说明如下：

• 状态位P(存在位)。标记该页是否已调入内存，供地址变换时判断是否触发缺页中断。
• 访问字段A。记录本页在一段时间内的访问次数，或记录自上次访问以来的时间间隔，供页面置换算法选择换出页面时参考。
• 修改位M(脏位)。标记该页调入内存后是否被修改过，以决定换出时是否需写回外存。
• 外存地址。指示该页在外存中的存放位置（通常为物理块号），供调页时将其读入内存。

2. 缺页中断机构#

在请求分页系统中，当进程访问的页面尚未调入内存时，硬件会自动触发缺页中断，由操作系统的缺页中断处理程序处理：将所需页面从外存调入内存（必要时先换出一页）。具体而言，若内存中有空闲页框，则分配一个页框，将所缺页面从外存装入，并更新页表中相应的表项；若无空闲页框，则需先由页面置换算法选择一个页面淘汰，若该页在内存中被修改过，则必须将其写回外存，否则可直接丢弃。由于页面调入通常涉及较长时间的磁盘I/O操作，系统在此期间可能会调度其他进程运行；待所需页面调入完成后，重新执行引发缺页的那条指令。

缺页中断作为一种内中断，其处理过程与其他中断类似，也需经历保护CPU现场、分析中断原因、转入中断处理程序、恢复CPU现场等步骤。然而，它具有以下两个显著特点：

• 在指令执行期间触发，由当前指令的地址访问直接引发，而非在指令执行完毕之后。
• 一条指令在执行过程中可能引发多次缺页中断。例如，在执行指令 copy A to B 时，若该指令本身及其两个操作数各自跨越两个页面，则最多可能引发6次缺页中断。

3. 地址变换机构#

在基本分页系统地址变换机构的基础上，请求分页系统为支持虚拟存储器，增加了缺页中断触发机制。

请求分页系统的地址变换过程如下。

1. 首先检索快表，若命中，则从相应表项中取出该页的物理块号，并置访问位为1，以供置换算法换出页面时参考。对于写操作，还需置修改位为1。
2. 若快表未命中，则需访问页表。若该页已在内存中（状态位=1），则从相应表项中取出物理块号，并将该页表项装入快表；若快表已满，则按置换算法淘汰一项。
3. 若页面不在内存，则触发缺页中断。操作系统接管后，将所需页面从外存调入内存(必要时先换出一页)，并更新页表和快表。随后，重新执行地址变换以获取物理块号。
4. 将获得的物理块号与页内地址拼接，形成物理地址，用于访存。

1. 最小页框数与驻留集#

2. 内存分配策略#

在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局和局部置换。于是可组合出以下三种适用的策略。

3. 页框调入算法#

在采用固定分配策略时，系统需将空闲页框分配给各进程，常见的分配算法如下。

1. 平均分配算法，将系统中所有可供分配的页框平均分配给各个进程。
2. 按比例分配算法，根据进程的逻辑地址空间大小按比例分配页框。
3. 优先权分配算法，为重要或紧迫的进程分配更多页框。通常的做法是将所有可分配页框分为两部分：一部分按比例分配给各进程，另一部分则依据进程的优先权动态分配。

4. 调入页面的时机#

为确定系统将进程运行时所缺页面调入内存的时机，可采用以下两种调页策略。

1. 预调页策略。根据局部性原理，一次调入若干相邻页面通常比逐页调入更高效。然而，若预调入的页面大多未被访问，则会造成内存浪费。因此，系统可尝试预测进程近期可能访问的页面并预先调入，但目前预测成功率仅约50%。鉴于预测效果有限，该策略主要用于进程首次调入时，由程序员显式指定应优先加载的页面。
2. 请求调页策略。当进程在运行中访问的页面不在内存时，便会触发缺页中断，由系统将其所需页面调入内存。这种策略调入的页面必然会被访问，且实现相对简单，因此当前的虚拟存储器大多采用此策略。其缺点是每次仅调入一页，导致磁盘I/O开销较大。

预调页本质上是在进程运行前完成页面加载，而请求调页则是在运行期间动态调入。

5. 从何处调入页面#

请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放换出页面的对换区，也称交换区。对换区采用连续分配方式，而文件区采用离散分配方式，因此对换区的磁盘I/O速度通常快于文件区。这样，系统在发生缺页时，调入页面的来源可分为以下三种情况。

1. 系统拥有足够的对换区空间。此时可将所有页面从对换区调入，以提高调页速度。为此，需在进程运行前，将与该进程相关的文件从文件区复制到对换区。
2. 系统对换区空间不足。对于不会被修改的页面，直接从文件区调入；当换出此类页面时，因其内容未变，无须写回磁盘。而对于可能被修改的页面，换出时必须保存到对换区，后续调入时也需从对换区读取，从而兼顾效率与正确性。
3. UNIX方式。与进程相关的文件始终保留在文件区。因此，未运行过的页面从文件区调入；曾经运行过但已被换出的页面则存放在对换区，后续调入时从对换区读取。若多个进程共享同一页面，则只要该页面已在内存中，其他进程便可直接复用，无须重复调入。

6. 如何调入页面#

当进程访问的页面不在内存中时（页表项的存在位为0），CPU会触发缺页中断。中断响应后，系统转入缺页中断处理程序。该程序首先通过页表项获取该页在外存中的地址，然后判断内存是否已满：若内存未满，则分配一个空闲页框，发起磁盘I/O将所缺页面调入，并更新页表项：填写物理块号，置存在位为1；若内存已满，则先按某种置换算法选出一页准备换出。若该页的修改位为0，则直接丢弃；若修改位为1，则需先将其写回对换区，再释放该页框。随后，将所缺页面调入该页框，并更新页表项，置存在位为1。调入完成后，进程即可通过更新后的页表生成正确的物理地址。整个页面调入过程对用户完全透明，由操作系统自动完成。

1. 最佳(OPT)算法#

最佳页面置换算法在发生缺页时，选择淘汰以后永不使用或在最长时间内不再被访问的页面，从而在理论上获得最低的缺页率。然而，由于操作系统无法预知未来的页面访问序列，该算法在实际系统中无法实现。尽管如此，OPT算法仍具有重要的理论意义，常用于评价其他算法。

假定系统为某进程分配了三个物理块，并给定如下页面访问序列：

进程运行时，首先将页面7,0,1依次装入内存。当访问页面2时，发生缺页中断。根据OPT算法，选择未来最久才被再次访问的页面（页面7的下一次访问在第18次，远晚于其他页面）淘汰。随后访问页面0时，因其已在内存中，不产生缺页。访问页面3时再次缺页，此时页面1的下次访问（第14次）最晚，故将其淘汰。。。。。。以此类推，具体过程如图3.21所示。

图3.21 利用最佳置换算法时的置换图

可见，整个过程中共发生9次缺页中断，其中6次触发页面置换（不算初始装入）。

2. 先进先出(FIFO)算法#

先进先出页面置换算法选择淘汰最早进入内存的页面。该算法实现简单，将内存中的页面按调入时间组织成一个队列，需要换出时直接移除队首页面。然而，FIFO算法未利用局部性原理，与进程实际运行规律不符，最早装入的页面仍可能被频繁访问，因此性能通常较差。

仍用上面的例子，采用FIFO算法进行置换。当访问页面2时发生缺页，淘汰最早进入的页面7。随后访问页面3时再次缺页，此时将2,0,1中最先进入的页面0换出。。。。。。以此类推，具体过程如图3.22所示。可见，共发生15次缺页中断，其中12次触发页面置换。

图3.22 FIFO算法的置换图

值得注意的是，FIFO算法存在一种反直觉现象：当为进程分配的物理块数增加时，缺页次数反而可能上升，这一现象称为 Belady 异常。其根本原因在于FIFO仅依据调入时间决策，而忽略了页面的实际使用情况。例如，页面访问需列为3,2,1,0,3,2,4,3,2,1,0,4, 当分配3个物理块时，缺页次数为9次；当分配4个物理块时，缺页次数反而增至10次，如图3.23所示。

图3.23 Belady异常

只有FIFO 算法可能出现Belady异常，而OPT算法和LRU算法永远不会出现此类异常。

3. 最近最久未使用(LRU)算法#

LRU算法选择淘汰最近最长时间未使用的页面，其基本思想是：若某页面在过去一段时间内未被使用，则在近期未来很可能也不会被访问。为实现这一策略，系统需为每个页面维护一个访问字段，记录其自上次被访问以来所经历的时间，淘汰页面时选择该值最大的页面。

仍用上面的例子采用LRU算法进行置换，如图3.24所示。首次访问页面2时发生缺页，将最近最久未使用的页面7换出；随后访问页面3时再次缺页，将最近最久未使用的页面1换出。

图3.24 LRU页面置换算法时的置换图

由图可见，前5次缺页处理的结果与OPT算法相同，但这仅是巧合，并无必然联系。实际上，LRU算法根据页面过去的使用情况来判断，是“向前看”的；而OPT算法则根据页面未来的使用情况来判断，是“向后看”的。而页面过去与未来的走向之间并无必然联系。

OPT 算法的性能最好，但无法实现。FIFO 算法实现简单，但忽略局部性，性能较差。LRU算法性能接近OPT算法，具有良好的实际效果，但其实现通常需要硬件支持，开销较大。

4. 时钟(CLOCK)算法#

LRU算法的性能接近OPT算法，但其实现开销较大。因此，操作系统的设计者尝试了许多算法，试图以较小的开销接近LRU算法的性能，这类算法统称为CLOCK算法的变体。