虚拟内存

虚拟内存是现代操作系统中一种重要的内存管理技术，它通过将程序的逻辑地址空间与物理内存的地址空间分离，使得程序能够使用比实际物理内存更大的地址空间。这种技术允许操作系统在有限的物理内存上运行超出内存容量的大型程序，同时提高了系统的多道程序设计能力和资源利用率。

虚拟内存的核心机制是地址转换：程序使用虚拟地址进行内存访问，而内存管理单元（MMU）负责将这些虚拟地址转换为实际的物理地址。当程序访问的页面不在物理内存中时，操作系统会从辅助存储器（通常是磁盘）将所需页面调入内存，这个过程对程序来说是透明的。

为什么需要虚拟内存

在传统的内存管理方法中，程序运行时必须将所有指令和数据都加载到物理内存中。这个要求虽然直观，但带来了一个根本性的限制：程序的大小不能超过物理内存的容量。

然而，通过分析实际程序的执行特征，我们发现了一个重要的现象：程序在执行过程中，并非所有代码和数据都需要同时存在于内存中。例如，程序中处理罕见错误情况的异常处理代码，在实际运行中可能永远不会被执行。程序中声明的数据结构可能比实际使用的大小大得多，一个声明为100×100的数组，实际可能只使用10×10的部分。还有一些程序模块可能很少被调用，比如某些系统工具程序中的特定功能模块。

即使在需要完整程序的情况下，程序的不同部分也往往在不同时间被访问，不需要同时驻留在内存中。这种时间局部性和空间局部性的特征，为虚拟内存技术的应用提供了理论基础。

虚拟内存的优势

通过实现按需加载机制，虚拟内存技术带来了显著的优势：

• 程序不再受物理内存容量的限制。程序员可以为极大的虚拟地址空间编写程序，而无需关心物理内存的实际大小。这使得大型应用程序的开发变得更加灵活。
• 由于每个程序实际占用的物理内存减少，系统可以同时运行更多的进程，提高了多道程序设计的程度。这有助于提高CPU利用率和系统整体吞吐量，同时不会显著增加响应时间或周转时间。
• 通过智能的页面调度策略，可以减少不必要的I/O操作次数，提高程序的执行效率。

虚拟地址空间

每个进程都拥有一个独立的虚拟地址空间，这个地址空间从地址0开始，可以延伸到非常大的地址范围（在64位系统中可达数TB）。从进程的角度看，这个地址空间是连续且完整的，进程可以使用其中的任何地址进行内存访问。

然而，物理内存的实际组织方式与虚拟地址空间的连续视图不同。物理内存被划分为固定大小的页框（page frame），这些页框在物理上可能分散在内存的不同位置。内存管理单元（MMU）负责维护虚拟地址空间中的逻辑页面与物理内存中页框之间的映射关系，实现虚拟地址到物理地址的转换。

虚拟地址空间通常包含几个主要区域：代码段、数据段、堆（heap）和栈（stack）。堆区域用于动态内存分配，向高地址方向增长；栈区域用于函数调用和局部变量存储，向低地址方向增长。堆和栈之间通常存在大片的未使用地址空间，这些空间在虚拟地址空间中存在，但并没有对应的物理内存分配。

这种设计形成了稀疏地址空间（sparse address space）的特征。稀疏地址空间的优势在于灵活性：当堆或栈需要扩展时，操作系统可以动态分配物理页框并建立映射；当需要加载共享库时，可以在虚拟地址空间的空闲区域建立映射。这种机制既节省了物理内存资源，又简化了内存管理。

这张图展示了虚拟地址空间如何映射到物理内存。虽然虚拟地址空间看起来是连续的，但实际的物理页框可能分散在内存的不同位置。

共享内存和库

虚拟内存技术除了实现逻辑地址空间与物理地址空间的分离外，还提供了内存共享机制，允许多个进程共享同一块物理内存或同一个文件。

共享库是内存共享的典型应用。例如，C语言标准库等系统库可以被多个进程共享。每个进程在自己的虚拟地址空间中看到完整的库映射，但实际上所有进程共享同一份物理内存中的库代码。这种机制显著减少了内存占用，因为多个进程不需要各自加载相同的库代码。通常，共享库的代码段被标记为只读，确保共享的代码不会被意外修改。

进程间通信（IPC）也可以通过共享内存实现。两个或多个进程可以将各自的虚拟地址空间映射到同一块物理内存区域，这样它们就可以通过读写这块共享内存进行数据交换。虽然每个进程在自己的虚拟地址空间中看到的是不同的地址，但它们实际上访问的是同一块物理内存。

在进程创建过程中，虚拟内存也发挥了重要作用。当使用fork()系统调用创建子进程时，父进程和子进程最初可以共享相同的物理页面。只有当某个进程试图修改共享页面时，操作系统才会为该进程创建页面的独立副本。这种写时复制（Copy-on-Write）机制大大提高了进程创建的效率。

接下来，我们将详细讨论虚拟内存的核心机制——按需分页，这是实现虚拟内存高效管理的关键技术。

按需分页

按需分页（Demand Paging）是虚拟内存系统的核心机制。与传统的预分页方式不同，按需分页只在进程实际访问某个页面时才将该页面从辅助存储器加载到物理内存中。这种延迟加载策略可以显著减少初始加载时间，提高内存利用率，并允许系统运行超出物理内存容量的程序。

按需分页的基本概念

按需分页的核心思想是在需要时才将页面加载到内存中。在程序执行过程中，有些页面在内存中，有些页面在辅助存储器中。因此，我们需要某种硬件支持来区分这两者。

我们可以利用之前部分中提到的有效-无效位方案来实现这个目的。当页面在内存中时，页面表项中的有效位被设置为“有效”； 当页面不在内存中时，页面表项被标记为“无效”。

如果进程试图访问一个标记为无效的页面，就会发生页面错误。页面错误会触发一个陷阱(trap)，操作系统会处理这个错误。

页面错误的处理过程

当页面错误发生时，操作系统会按照以下步骤进行处理：

这个流程图展示了页面错误处理的完整过程。从发现页面错误到最终重新启动指令，每一步都很重要。

纯按需分页

在极端情况下，我们可以让一个进程在没有任何页面在内存中的情况下开始执行。 当操作系统将指令指针设置为进程的第一条指令时，如果这条指令不在内存驻留页面上，进程会立即为该页面发生错误。

在将这个页面调入内存后，进程继续执行，根据需要发生页面错误，直到它需要的所有页面都在内存中为止。 此时，它可以无错误地执行。这种方案被称为纯按需分页：永远不要在需要之前将页面调入内存。

理论上，有些程序可能在每次执行指令时访问几个新的内存页面（一个用于指令，多个用于数据），可能导致每个指令发生多次页面错误。这种情况会严重影响系统性能。

幸运的是，对运行进程的分析表明，这种行为极不可能发生。程序倾向于具有局部性引用，这使得按需分页具有合理的性能。

硬件支持

支持按需分页的硬件与分页和交换的硬件相同：

• 页面表：这个表能够通过有效-无效位或保护位的特殊值来标记条目无效。
• 辅助存储器：这个存储器保存不在主内存中的页面。辅助存储器通常是高速磁盘或NVM设备，被称为交换设备，用于此目的的存储部分称为交换空间。

按需分页的一个关键要求是能够在页面错误后重新启动任何指令。因为我们在页面错误发生时保存了中断进程的状态（寄存器、条件码、指令计数器）， 我们必须能够以完全相同的地方和状态重新启动进程，只是所需的页面现在在内存中并且可以访问。

在大多数情况下，这个要求很容易满足。页面错误可能发生在任何内存引用上。如果页面错误发生在指令获取时，我们可以通过再次获取指令来重新启动。 如果页面错误发生在获取操作数时，我们必须再次获取和解码指令，然后获取操作数。

复杂指令的挑战

以最坏的情况为例，考虑一个三地址指令，比如“将A的内容加到B，并将结果放在C”中。执行这个指令的步骤是：

1. 获取并解码指令（ADD）。
2. 获取A。
3. 获取B。
4. 将A和B相加。
5. 将结果存储在C中。

如果我们在尝试存储到C时发生页面错误（因为C在一个当前不在内存中的页面上），我们将不得不获取所需的页面，将其调入，更正页面表，然后重新启动指令。 重新启动将需要再次获取指令，再次解码，再次获取两个操作数，然后再次相加。 不过，重复的工作并不多（少于一条完整指令），而且只有在页面错误发生时才需要重复。

最复杂的情况是：一条指令可能修改内存中的多个位置。例如，块移动指令可以将一大段数据（如256字节）从一个内存区域复制到另一个区域，且源区域和目标区域可能重叠。

如果源区域和目标区域跨越页面边界，或者在数据移动过程中发生页面错误，就会产生问题。特别是当源区域和目标区域重叠时，源数据可能已被部分修改，无法简单地重新执行指令，因为原始数据已经改变。

操作系统解决这个问题有两种主要方法。第一种方法是预取（prefetching）：在执行数据移动之前，系统预先访问所有涉及的页面。如果某些页面不在内存中，会先触发页面错误并加载这些页面。等所有页面都加载完成后，再执行数据移动操作，避免中途发生页面错误。

第二种方法是使用临时寄存器保存即将被覆盖的数据。如果在数据移动过程中发生页面错误，系统可以将保存的原始数据写回内存，恢复内存到初始状态，然后安全地重新执行指令。

分页系统在设计时面临诸多挑战。分页机制位于CPU和内存之间，理想情况下对程序应该是透明的。但要支持按需分页（即页面错误后能够继续执行），不能简单地将分页机制添加到任何系统架构中。对于将页面错误视为致命错误的老系统，分页可以相对简单地实现；但如果要求页面错误是可恢复的，需要硬件和操作系统的协同支持。

空闲帧列表

当页面错误发生时，操作系统必须将所需的页面从辅助存储器调入主内存。为了解决页面错误，大多数操作系统维护一个空闲帧列表，这是一个用于满足此类请求的空闲帧池。

空闲帧也必须在进程的栈或堆段扩展时分配。操作系统通常使用一种称为按需清零的技术来分配空闲帧。按需清零帧在分配之前被“清零”，从而擦除它们以前的内容。

当系统启动时，所有可用内存都被放在空闲帧列表上。随着空闲帧被请求（例如，通过按需分页），空闲帧列表的大小会缩小。在某个时候，列表要么降到零，要么降到某个阈值以下，此时必须重新填充。我们在后面的页面置换部分讨论这两种情况的策略。

按需分页演示

按需分页的性能分析

按需分页技术使得系统能够在有限的物理内存上运行超出内存容量的大型应用程序，但这种灵活性也带来了性能开销。当进程访问的页面不在物理内存中时，需要从辅助存储器（通常是磁盘）加载页面，这个过程涉及磁盘I/O操作，耗时远大于内存访问。

为了量化这种性能影响，我们需要分析页面错误率对有效访问时间的影响。有效访问时间是正常内存访问时间和页面错误处理时间的加权平均，它反映了系统在按需分页机制下的实际性能表现。

有效访问时间的计算需要考虑两种不同的访问场景：正常的内存访问和页面错误处理。

在正常情况下，当所需页面已在物理内存中时，内存访问可以直接完成，典型的访问时间约为10纳秒。这是理想的访问场景，性能最优。

当进程访问的页面不在物理内存中时，会触发页面错误。操作系统需要从辅助存储器（通常是磁盘）加载页面，这个过程包括：查找页面在磁盘上的位置、执行磁盘I/O操作、将页面加载到物理内存、更新页面表等步骤。典型的页面错误处理时间约为8毫秒，是正常内存访问时间的约80万倍。

有效访问时间通过加权平均计算：有效访问时间 = (1 - p) × 正常访问时间 + p × 页面错误处理时间

其中p表示页面错误率（0 ≤ p ≤ 1）。当p = 0时，系统达到理想的10纳秒访问时间；当p接近1时，几乎每次访问都会触发页面错误，有效访问时间接近8毫秒，系统性能严重下降。

写时复制

写时复制（Copy-on-Write, COW）是一种内存管理优化技术，广泛应用于进程创建和内存共享场景。该技术的核心思想是：多个进程最初共享相同的物理页面，只有当某个进程试图修改共享页面时，操作系统才为该进程创建页面的独立副本。

写时复制技术允许父进程和子进程在创建时共享相同的页面，而不是立即复制所有页面。只有当其中一个进程试图写入共享页面时，才创建该页面的副本。

写时复制的基本概念

写时复制技术允许父进程和子进程最初共享相同的页面。这些共享页面被标记为写时复制页面，这意味着如果任一进程写入共享页面，就会创建一个共享页面的副本。

让我们通过一个例子来说明写时复制的工作原理：

假设子进程试图修改一个包含栈部分的页面，且该页面被设置为写时复制。操作系统会从空闲帧列表中获取一个帧，并创建该页面的副本，将其映射到子进程的地址空间。然后，子进程会修改其复制的页面，而不是属于父进程的页面。 显然，当使用写时复制技术时，只有被任一进程修改的页面才会被复制；所有未修改的页面都可以由父进程和子进程共享。

此外，只有可以修改的页面才需要标记为写时复制。不能修改的页面（包含可执行代码的页面）可以由父进程和子进程共享。 写时复制是几个操作系统常用的技术，包括Windows、Linux和macOS。

这个流程图展示了写时复制的工作机制。当进程需要修改共享页面时，系统会自动创建副本，确保每个进程拥有独立的内存空间。

vfork()系统调用

几个版本的UNIX（包括Linux、macOS和BSD UNIX）提供了fork()系统调用的变体——vfork()（虚拟内存fork），其操作方式与带有写时复制的fork()不同。

使用vfork()时，父进程被挂起，子进程使用父进程的地址空间。因为vfork()不使用写时复制，如果子进程更改了父进程地址空间的任何页面，更改的页面在父进程恢复后对父进程可见。

因此，必须谨慎使用vfork()，以确保子进程不会修改父进程的地址空间。vfork()旨在用于子进程在创建后立即调用exec()的情况。因为没有页面复制发生，vfork()是进程创建的一种极其有效的方法，有时用于实现UNIX命令行shell接口。

写时复制技术不仅用于进程创建，还广泛应用于其他需要共享数据但又要保持独立性的场景，比如虚拟机的克隆、容器技术的实现等。

页面置换

当物理内存中的页框都被占用，而进程又需要访问不在内存中的页面时，操作系统必须选择一个当前驻留在内存中的页面，将其替换出去，为新页面腾出空间。这个过程称为页面置换（Page Replacement），被选中的页面称为受害页面（victim page）。

页面置换的必要性

我们之前聊过，按需分页让每个页面在第一次被访问时才会发生页面错误，这样可以节省不少没用到页面的加载时间和空间。 但现实中，进程有时候会突然需要用到更多页面，尤其是多道程序设计程度高的时候，内存就可能不够用了。

比如说，假如我们有6个进程，每个进程理论上能用10页，但平时只用5页，这样看起来内存还绰绰有余。 但万一这些进程突然都要用满10页，内存就会不够，大家都抢帧，系统压力就大了。更别说内存还要分给I/O缓冲区，分配起来就更紧张了。

这时候，操作系统不能随便终止进程，也不能总是把整个进程换出去。 现在主流做法是结合页面置换和页面交换：当内存不够时，挑选部分页面换出去，腾出空间给需要的页面，这样既能提高效率，也让分页对用户来说是“无感”的。

基本页面置换

基本页面置换的核心流程是：当内存中没有空闲帧时，系统需要选择一个当前驻留在内存中的页面进行替换。替换过程包括：如果被替换的页面已被修改（dirty），需要将其内容写回辅助存储器；更新页面表，标记该页框为空闲；将新页面加载到释放的页框中；更新新页面的页面表项。

一旦完成页面替换，进程就可以访问新加载的页面，继续执行。

这个流程图展示了页面置换的核心步骤。当没有空闲帧时，系统会选择一个受害页面进行替换。

页面置换过程的一个重要优化是使用修改位（dirty bit）来标记页面是否被修改。每当页面内容被修改时，硬件会自动设置该页面的修改位。当需要替换页面时，系统首先检查修改位：如果页面未被修改（clean page），可以直接丢弃，因为辅助存储器中已有该页面的原始副本；如果页面已被修改（dirty page），必须先将页面内容写回辅助存储器，然后才能释放该页框。

这个优化对于只读页面特别有效，例如程序的可执行代码段。这些页面永远不会被修改，因此可以安全地直接丢弃，无需写回操作。

通过页面置换机制，按需分页实现了逻辑内存与物理内存的完全分离。程序员可以在巨大的虚拟地址空间中编程，而无需关心物理内存的实际容量限制。

例如，一个需要20页内存的程序可以在只有10页物理内存的系统上运行。当程序访问不在内存中的页面时，如果内存已满，系统会选择一个现有页面进行替换，将新页面调入。如果被替换的页面已被修改，其内容会被保存到辅助存储器；当该页面再次被访问时，可以从辅助存储器重新加载。

页面置换虽然增加了系统复杂性，但提供了显著的灵活性，使得系统能够在有限的物理内存上运行超出内存容量的大型程序，提高了资源利用率。要实现高效的页面置换，需要解决两个关键问题：如何在多个进程间公平分配内存帧，以及如何选择最优的受害页面。

页面置换算法的评估

页面置换算法多种多样，每个操作系统可能都有自己的选择方案。我们的目标很明确：选择页面错误率最低的算法。 为了评估不同算法的优劣，我们需要一个公平的测试标准。

这个标准就是“引用字符串”——一段内存访问序列。我们可以通过两种方式获得引用字符串：人工生成（用随机数模拟）或实际跟踪系统记录的内存访问地址。后一种方法虽然更真实，但会产生海量数据（每秒上百万个地址）。 为了让数据更易处理，我们会做两个简化：首先，只记录页面号而不是完整地址；其次，过滤掉连续的对同一页面的重复访问，因为第一次访问后该页面已经在内存中了。

举个例子，假如我们记录到一个地址序列：0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104... 如果每页100字节， 这个序列就能简化为：1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

在使用引用字符串测试算法时，我们还需要考虑内存帧的数量这个关键因素。 显然，帧越多，页面错误就越少。如果有3个或更多帧，上述引用字符串只会产生3个页面错误（每个页面的首次访问）。 但如果只有1个帧，每次访问都会触发页面替换，导致11个错误。

一般规律是：随着帧数的增加，页面错误率会逐渐下降到一个最小值。当然，增加物理内存就能提供更多帧。 接下来我们将介绍一些经典的页面置换算法，并用这个引用字符串进行演示：

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

测试环境：3个内存帧。

FIFO页面置换

最简单的页面置换算法是先进先出（FIFO）算法。FIFO替换算法将每个页面与该页面调入内存的时间相关联。当必须替换页面时，选择最旧的页面。

请注意，严格来说，没有必要记录页面调入的时间。我们可以创建一个FIFO队列来保存内存中的所有页面。我们替换队列头部的页面。当页面调入内存时，我们将其插入队列尾部。

对于我们的示例引用字符串，我们的三个帧最初是空的。前三个引用（7, 0, 1）导致页面错误，并被调入这些空帧。下一个引用（2）替换页面7，因为页面7最先被调入。由于0是下一个引用并且0已经在内存中，我们对这个引用没有错误。对3的第一次引用导致替换页面0，因为它现在排在第一位。由于这个替换，下一个引用0将发生错误。然后页面1被页面0替换。这个过程继续进行，总共有15个错误。

FIFO页面置换算法易于理解和编程。但是，其性能并不总是很好。一方面，被替换的页面可能是很久以前使用过的初始化模块，不再需要。另一方面，它可能包含一个重度使用的变量，该变量很早就被初始化并一直在使用。

请注意，即使我们选择替换一个正在使用的页面，一切仍然可以正确工作。在用新页面替换活动页面后，对该页面的后续引用将导致页面错误。此时，该页面将被调回内存，可能替换进程中的其他页面。

最优页面置换

最优页面置换算法是一种理论上的理想算法，它选择在最长时间内不会被访问的页面进行替换。 这种算法需要预知未来的页面引用序列，这在实际系统中是不可能实现的，但它为其他算法提供了性能上限。

算法工作原理

最优算法的核心思想是：选择未来最长时间内不会被访问的页面进行替换。这意味着算法需要"预知未来"，知道每个页面下次被访问的时间点。

使用引用字符串：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1（3个内存帧）

|
步骤1-3: 7, 0, 1 → 内存: [7, 0, 1] (3个页面错误)
步骤4: 访问2 → 内存: [2, 0, 1] (替换7，因为7下次访问最晚)
步骤5: 访问0 → 内存: [2, 0, 1] (已在内存中)
步骤6: 访问3 → 内存: [2, 0, 3] (替换1，因为1下次访问最晚)
步骤7: 访问0 → 内存: [2, 0, 3] (已在内存中)

最终结果：仅产生6个页面错误（理论最小值）

LRU页面置换

最近最少使用（LRU，Least Recently Used）算法是一种在实际操作系统中广泛应用的页面置换策略，其性能表现优异。

LRU算法的核心思想基于程序的局部性原理：程序在执行过程中，最近访问过的页面在不久的将来很可能再次被访问。因此，LRU算法选择替换最久未被访问的页面，期望这些页面在未来也不太可能被访问，从而减少页面错误的发生。

在内存管理中，LRU算法维护每个页面的访问时间戳，记录页面最近一次被访问的时间。当需要替换页面时，系统选择访问时间最早的页面（即最久未使用的页面）作为受害页面。这种策略能够有效利用程序的访问局部性，显著降低页面错误率，提高系统性能。

使用引用字符串：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1（3个内存帧）

|
时间序列跟踪:
步骤1: 访问7 → 内存: [7] (时间: t1)
步骤2: 访问0 → 内存: [7, 0] (时间: t1, t2)
步骤3: 访问1 → 内存: [7, 0, 1] (时间: t1, t2, t3)
步骤4: 访问2 → 内存: [2, 0, 1] (替换7，最久未使用)
步骤5: 访问0 → 内存:

最终结果：产生8个页面错误

LRU实现方式

LRU算法的实现方式大致可以分为硬件和软件两种。硬件实现时，通常会为每个页面设置一个专属的计数器，每当某个页面被访问，这个计数器就会被重置为0，而其他页面的计数器则依次加1。这样一来，计数器数值最大的页面，就是最久没被用过的，系统就会优先把它换出去。这种方式速度快，但需要专门的硬件支持，实际中并不常见。

软件实现则更灵活。我们可以用一个时间戳或者栈来记录每个页面的访问顺序。每次访问页面时，就把它的时间戳更新为最新，或者把它移动到栈顶。这样，栈底的页面就是最久未被访问的，遇到需要替换时，直接从栈底挑选即可。这种方法虽然实现起来简单，但如果页面数量很多，维护数据结构的开销也不小，所以实际操作系统里常常会用一些近似LRU的算法来权衡效率和效果。

页面置换可视化

帧分配策略

在操作系统的虚拟内存管理中，帧分配策略（Frame Allocation Policy）是决定如何将有限的物理内存帧分配给多个并发进程的关键机制。物理内存中的帧数量是有限的，而系统中同时运行的进程数量及其内存需求各不相同。

帧分配策略的核心任务是根据进程的实际内存需求、优先级、历史访问模式等多种因素，科学合理地将有限的物理帧分配给各个进程。合理的帧分配既要保证每个进程的基本运行需求，避免进程因内存不足而频繁发生页面错误，又要提高系统的整体吞吐量和响应速度。

帧分配策略需要在公平性和效率之间取得平衡。如果所有进程平均分配帧，可能导致内存需求小的进程浪费资源，而内存需求大的进程频繁发生页面置换，影响运行效率。如果根据进程的实际内存需求动态分配帧，可以显著降低页面错误率，提高系统稳定性和吞吐量。因此，帧分配策略的设计和实现直接关系到虚拟内存系统的性能表现，是操作系统内存管理的重要组成部分。

基本分配策略

最简单的分配方式是平均分配。如果我们有m个帧和n个进程，每个进程会得到m/n个帧。例如，如果有93个帧和5个进程，每个进程会得到18个帧，剩下的3个帧作为缓冲池。

但是，平均分配并不总是最优的。考虑一个系统，其中一个10KB的小程序和一个127KB的数据库程序同时运行。 如果有62个可用帧，平均分配会给每个进程31个帧。但小进程只需要10个帧，剩下的21个帧就被浪费了。

为了解决这个问题，我们可以使用比例分配策略。按照这种策略，我们根据进程的大小来分配内存。 假设进程pi的大小是si，所有进程大小的总和是S，那么进程pi会得到大约(si/S)×m个帧。

在上面的例子中，两个进程大小总和是137KB：

• 小进程（10KB）得到 (10/137)×62 ≈ 4个帧
• 数据库进程（127KB）得到 (127/137)×62 ≈ 57个帧

这样分配更加合理，每个进程都能根据其“需求”获得相应的内存。

最小帧数要求

帧分配策略受到多种限制。我们不能分配超过可用帧的总数量（除非有页面共享）。我们还必须为每个进程分配至少最小数量的帧。 这个最小数量是由计算机架构决定的。例如：

• 如果指令只能引用一个内存地址，我们至少需要1个帧存放指令，1个帧存放数据
• 如果允许一级间接寻址，可能需要3个帧
• 如果移动指令跨越两个帧，或者操作数是间接引用，可能需要6个帧

最小帧数由架构定义，而最大帧数由可用物理内存决定。在这个范围内，我们有很大的分配选择空间。

全局替换与局部替换

在多个进程竞争帧的情况下，我们可以将页面置换算法分为两大类：全局替换和局部替换。

全局替换允许进程从所有帧中选择替换帧，即使该帧当前分配给另一个进程。也就是说，一个进程可以从另一个进程那里拿走帧。 局部替换要求每个进程只能从自己的帧集合中选择替换帧。

全局替换的问题在于，进程在内存中的页面集合不仅取决于自己的分页行为，还取决于其他进程的行为。因此，同一个进程可能由于完全外部的原因而在不同的执行中表现不同。 局部替换则不同。进程在内存中的页面集合只受其自身分页行为的影响。局部替换可能阻碍进程使用其他较少使用的内存页面，但全局替换通常能产生更高的系统吞吐量，因此是更常用的方法。

页面错误分类

操作系统通常将页面错误分为两大类：主页面错误和次页面错误。

主页面错误发生在页面被引用但不在内存中时。处理主页面错误需要从后备存储器读取所需页面到空闲帧，并更新页面表。 次页面错误发生在进程没有页面的逻辑映射，但页面已在内存中时。次页面错误可能有两种原因：

1. 进程引用了内存中但没有映射到其页面表的共享库
2. 页面从进程回收并放入空闲帧列表，但尚未清零并分配给另一个进程

处理次页面错误通常比处理主页面错误快得多。 在Linux系统中，我们可以使用ps -eo min_flt,maj_flt,cmd命令来观察主页面错误和次页面错误的次数。通常，次页面错误的次数远高于主页面错误，这表明Linux进程大量利用共享库。

内存回收策略

为了实现全局页面置换策略，我们可以采用一种策略：当空闲帧列表下降到某个阈值以下时，就开始页面替换，而不是等到列表为空。

这个策略的目的是保持空闲内存高于最小阈值。当空闲内存下降到最小阈值以下时，内核会触发一个例程，从系统中所有进程回收页面（通常不包括内核）。这些内核例程被称为“收割者”，它们可能使用前面讨论的任何页面置换算法，但通常使用某种LRU近似算法。 当空闲内存达到最大阈值时，收割者例程会被挂起，直到空闲内存再次下降到最小阈值以下。这个过程会持续进行。

这种策略确保系统始终有足够的空闲内存来满足新请求，而不会等到内存完全耗尽才开始回收。

颠簸现象

颠簸（Thrashing）是虚拟内存系统中的一个严重性能问题，指进程花费大量时间进行页面置换而不是执行实际工作的情况。当进程没有足够的物理帧来容纳其当前工作集（working set）时，就会发生颠簸。

在颠簸状态下，进程频繁发生页面错误，每次页面错误都需要从辅助存储器加载页面，这个过程耗时很长。由于进程的大部分时间都花在等待页面加载上，CPU利用率急剧下降，系统吞吐量显著降低。严重时，进程可能花费90%以上的时间进行页面置换，只有不到10%的时间在执行有用工作。

颠簸的原因

颠簸(thrashing)是指进程花费更多时间进行页面置换而不是执行实际工作的情况。当一个进程没有足够的帧来容纳其当前正在使用的页面时，就会发生颠簸。

考虑这样一个场景：操作系统监控CPU利用率。如果CPU利用率太低，它会通过引入新进程来增加多道程序设计的程度。 使用全局页面置换算法，它会替换页面而不考虑页面属于哪个进程。

现在假设一个进程进入执行的新阶段，需要更多帧。它开始发生页面错误，并从其他进程那里夺取帧。这些进程也需要那些页面，所以它们也发生页面错误，从其他进程那里夺取帧。

这些发生页面错误的进程必须使用分页设备来交换页面进出。随着它们在分页设备队列中排队，就绪队列变空。随着进程等待分页设备，CPU利用率下降。

CPU调度程序看到CPU利用率下降，并因此增加多道程序设计的程度。新进程试图通过从正在运行的进程那里夺取帧来启动，导致更多页面错误和分页设备的更长队列。 结果，CPU利用率进一步下降，CPU调度程序试图进一步增加多道程序设计的程度。颠簸发生了，系统吞吐量急剧下降。

局部性模型

要防止颠簸，我们必须为进程提供它需要的足够帧。但我们如何知道它"需要"多少帧？ 一个策略是从进程实际使用的帧数量开始。这个方法定义了进程执行的局部性模型。

局部性模型指出，随着进程执行，它从一个局部性移动到另一个局部性。局部性是一组一起被积极使用的页面。一个正在运行的程序通常由几个不同的局部性组成，这些局部性可能重叠。 例如，当调用一个函数时，它定义了一个新的局部性。在这个局部性中，内存引用被指向函数调用的指令、其局部变量和全局变量的子集。当我们退出函数时，进程离开这个局部性，因为函数的局部变量和指令不再被积极使用。

如果我们为进程分配足够的帧来容纳其当前局部性，它将为局部性中的页面发生页面错误，直到所有这些页面都在内存中为止；然后，在它改变局部性之前，它不会再次发生页面错误。 如果我们没有分配足够的帧来容纳当前局部性的大小，进程将颠簸，因为它无法将所有正在积极使用的页面保存在内存中。

工作集模型

工作集模型（Working Set Model）用于确定进程当前实际需要的内存页面集合。工作集定义为在最近Δ次内存访问中引用过的页面集合，其中Δ是工作集窗口大小。

如果进程的工作集能够完全装入物理内存，进程可以顺畅运行，页面错误率很低。但如果所有进程的工作集总和超过了可用物理帧数量，进程之间会竞争内存资源，导致频繁的页面置换，系统进入颠簸状态，性能急剧下降。

操作系统通过监控每个进程的工作集大小，确保为每个进程分配足够的帧来容纳其工作集。当内存充足时，系统可以支持更多并发进程；当内存不足时，系统需要暂停部分进程（将其换出到辅助存储器），释放内存资源给其他进程，以维持系统整体性能。

页面错误频率

工作集模型虽然有效，但实现复杂度较高。页面错误频率（Page Fault Frequency, PFF）提供了一种更直接、更简单的颠簸检测和预防机制。

页面错误频率反映了进程访问不在内存中的页面的频率。如果一个进程的页面错误率持续较高，说明分配给它的物理帧不足以容纳其工作集，需要增加帧分配。相反，如果进程的页面错误率很低，说明它可能被分配了过多的帧，可以回收部分帧给其他进程使用。

操作系统为页面错误率设定上下限阈值。当进程的页面错误率超过上限时，系统增加分配给该进程的帧数；当页面错误率低于下限时，系统减少分配给该进程的帧数。这种动态调整机制能够使每个进程获得合适的内存分配，避免系统进入颠簸状态。

如果系统整体内存不足，无法通过帧重新分配解决问题，操作系统需要暂停部分进程，将其换出到辅助存储器，释放内存资源给急需内存的进程，以维持系统整体性能。

当前实践

实际上，颠簸和由此产生的交换对性能有着令人不快的巨大影响。实现计算机系统的当前最佳实践是尽可能包含足够的物理内存，以避免颠簸和交换。 从智能手机到大型服务器，提供足够的内存以在极端条件下同时保持所有工作集在内存中，可以提供最佳用户体验。

工作集与页面错误率的关系

工作集和页面错误率之间存在密切的关联关系。当进程的工作集完全驻留在物理内存中时，页面错误率很低，进程可以高效执行。当进程的工作集发生变化，需要访问新的页面时，如果这些页面尚未加载到内存，页面错误率会短暂升高；随着新工作集的页面被加载到内存，页面错误率会逐渐降低并稳定在较低水平。

工作集可以理解为在时间窗口内访问过的页面集合，这个窗口是滑动的，随着进程执行不断向前移动。窗口内的页面被认为是当前工作集的一部分，窗口外的页面则可能不再属于工作集。

在实际操作系统中，工作集的确定通常通过定时器和引用位（reference bit）来实现。系统定期检查哪些页面被访问过，记录这些信息，从而估算当前工作集。虽然这种方法不是完全精确的，但足以支持系统进行合理的内存分配决策，有效避免因频繁页面置换导致的性能下降。

内存压缩

除了传统的分页和页面置换机制外，现代操作系统还采用内存压缩（Memory Compression）技术来管理内存压力。内存压缩将暂时不活跃的页面内容压缩后存储在内存中，而不是立即写入辅助存储器，从而在内存紧张时释放物理内存空间。

当系统检测到内存压力时，会选择一些不常用的页面进行压缩，将压缩后的数据集中存储。当这些页面再次被访问时，系统会将其解压缩并恢复到正常状态。内存压缩特别适用于移动设备等交换空间有限的系统，可以在不进行昂贵的磁盘I/O操作的情况下缓解内存压力。

内存压缩的优势在于能够在不显著增加延迟的情况下管理内存压力，提高系统在内存紧张时的响应性能。Windows、macOS、Android等主流操作系统都采用了内存压缩技术，以改善多任务环境下的系统性能。

内核内存分配

虽然用户进程通过页面置换算法从空闲帧列表中分配页面，但内核通常使用不同的内存池来满足其内存需求。这有两个主要原因：

• 内核请求的内存大小各异，其中一些小于一个页面。由于内核必须谨慎使用内存以尽量减少碎片化，这一点尤其重要。许多操作系统不会将内核代码或数据置于分页系统之下。
• 用户模式进程分配的页面不一定必须在物理内存中连续。但是，某些硬件设备直接与物理内存交互（没有虚拟内存接口的益处），因此可能需要驻留在物理连续页面中的内存。

在接下来的部分中，我们将检查两种用于管理分配给内核进程的空闲内存的策略：伙伴系统和slab分配。

伙伴系统

伙伴系统从固定大小的物理连续页面段中分配内存。它使用2的幂分配器来满足以2的幂为单位大小的请求（4KB、8KB、16KB等）。对于不适合大小的请求，将向上舍入到下一个最高2的幂。

例如，假设内存段的初始大小为256KB，内核请求21KB的内存。该段最初分为两个伙伴——我们称之为AL和AR，每个128KB。然后，其中一个伙伴进一步分为两个64KB伙伴——BL和BR。但是，下一个从21KB开始的2的幂是32KB，因此BL或BR中的一个被再次分为两个32KB伙伴，CL和CR。其中一个伙伴用于满足21KB请求。

伙伴系统的一个优点是相邻伙伴可以快速组合以形成更大的段。在上面的例子中，当内核释放它分配的CL单元时，系统可以将CL和CR合并为64KB段。然后，该段BL可以与其伙伴BR合并，形成128KB段。最终，我们可以回到原来的256KB段。

伙伴系统的明显缺点是将请求向上舍入到下一个最高2的幂很可能会导致分配段内的碎片化。例如，33KB的请求只能用64KB段来满足。实际上，我们无法保证分配单元中少于50%的空间由于内部碎片化而被浪费。

Slab分配

另一种分配内核内存的策略称为slab分配。一个slab由一个或多个物理连续页面组成。一个缓存由一个或多个slab组成。对于每个唯一的内核数据结构都有一个单独的缓存——例如，进程描述符的单独缓存、文件对象的单独缓存、信号量的单独缓存等。

每个缓存填充有代表该缓存表示的内核数据结构的对象的实例。例如，表示信号量的缓存存储信号量对象的实例，表示进程描述符的缓存存储进程描述符对象的实例等。

slab、缓存和对象之间的关系如图所示。该图显示了三个7KB大小的内核对象和三个2KB大小的对象，每个存储在单独的缓存中。

slab分配算法使用缓存来存储内核对象。当创建缓存时，将多个对象（最初标记为空闲）分配给缓存。缓存中的对象数量取决于关联slab的大小。例如，一个由三个连续4KB页面组成的12KB slab可以存储六个2KB对象。最初，缓存中的所有对象都标记为空闲。当需要新的内核数据结构对象时，分配器可以从缓存中分配任何空闲对象来满足请求。从缓存分配的对象被标记为已使用。

考虑这样一个场景：内核从slab分配器请求内存以表示进程描述符。在Linux系统中，进程描述符的类型是struct task_struct，需要大约1.7KB的内存。当Linux内核创建一个新任务时，它从其缓存请求struct task_struct对象的必要内存。缓存将使用已经在slab中分配并标记为空闲的struct task_struct对象来满足请求。

在Linux中，一个slab可能处于三种可能状态之一：

• 满。slab中的所有对象都标记为已使用。
• 空。slab中的所有对象都标记为已使用。
• 部分。slab由已使用和空闲对象组成。

slab分配器首先尝试使用部分slab中的空闲对象来满足请求。如果不存在，则从空闲slab分配空闲对象。如果没有空闲slab可用，则从连续物理页面分配一个新的slab并将其分配给缓存；从这个slab分配对象的内存。

slab分配器提供了两个主要好处：

1. 由于碎片化，不会浪费内存。碎片化不是问题，因为每个唯一的内核数据结构都有一个关联的缓存，每个缓存由一个或多个slab组成，这些slab被分成正在表示的对象大小的块。因此，当内核请求对象的内存时，slab分配器返回表示该对象所需的确切内存量。
2. 内存请求可以快速满足。slab分配方案对于管理内存特别有效，当对象经常被分配和释放时（内核请求通常就是这种情况）。分配（和释放）内存的行为可能是一个耗时的过程。但是，对象是预先创建的，因此可以快速从缓存中分配。此外，当内核完成对象并释放它时，它被标记为空闲并返回到其缓存，从而使其立即可用于内核的后续请求。

slab分配器最早用在Solaris 2.4内核，后来也被用在Solaris的一些用户程序里。Linux一开始用的是伙伴系统，到了2.2版本才引入slab分配器，叫做SLAB。现在Linux还多了SLOB和SLUB两种分配器。

SLOB分配器很简单，专门给内存特别紧张的嵌入式设备用。它把小于256字节、中等（小于1024字节）和大（小于一页）的对象分成三类，按需分配，谁合适就用谁。

后来，Linux 2.6.24版本起，SLUB分配器成了默认选择。SLUB比SLAB更省事，很多原本分散在slab里的元数据都集中到每个页面的结构里了，也不再为每个CPU单独维护队列。这样一来，处理器越多，SLUB的效率提升就越明显。

分页系统的其他考虑

分页系统的核心是页面置换算法和内存分配策略，这些内容我们已经在前面详细讨论过。除此之外，分页系统还涉及其他重要的设计考虑，这些因素同样影响系统性能。

预调页

按需分页的一个缺点是进程启动初期会频繁发生页面错误，因为需要逐页将代码和数据加载到内存。为了减少这种启动延迟，系统可以采用预调页（Prepaging）技术，提前将可能被访问的页面加载到内存中。

预调页的有效性取决于预测准确性。如果预先加载的页面大部分会被实际使用，预调页可以显著减少页面错误，提高性能。但如果预测不准确，预加载了大量不会被使用的页面，则会浪费内存和I/O带宽。

预调页对于顺序访问模式特别有效，例如Linux的readahead()系统调用可以提前读取文件的后续内容。但对于程序代码的访问模式，预测哪些页面会被使用往往比较困难，预调页的效果可能有限。

页面大小

页面大小的选择需要在多个因素之间权衡，没有绝对的最优值。较小的页面可以减少内部碎片，提高内存利用率，但会导致页面表增大，增加管理开销。较大的页面可以减小页面表大小，提高I/O效率，但可能增加内部碎片。

如果使用很小的页面（如512字节），内存利用率高，碎片少，但页面数量大幅增加，页面表变得庞大，频繁的页面切换也可能影响性能。如果使用较大的页面（如4KB或更大），虽然可能存在内部碎片，但页面表小，I/O效率高，系统整体性能更好。

页面大小的选择是多种因素的平衡结果。历史上，4KB页面是常见选择，现在许多系统支持更大的页面（如2MB甚至更大）。具体选择需要根据应用特征、硬件支持和系统需求来确定。

程序结构

按需分页机制对程序员是透明的，大多数情况下程序员无需关心内存如何被分页。然而，理解分页机制并优化程序的数据访问模式，可以显著提高程序性能。

考虑一个例子：假设页面大小为128字节，需要将128×128的二维数组初始化为0。C语言中多维数组按行主序存储，即data[0][0]到data[0][127]存储在第一行，data[1][0]到data[1][127]存储在第二行，以此类推。如果每行恰好占用一个页面，那么每行数据分布在不同的页面上。

如果按列遍历数组：

|
int i, j;
int[128][128] data;
for (j = 0; j < 128; j++)
  for (i = 0; i < 128; i++)
    data[i][j] = 0;

这种访问模式每次访问不同行的同一列元素，导致频繁跨页面访问。如果系统只有128个物理帧，每次访问新行都会触发页面错误。整个过程会产生128×128=16384次页面错误。

如果改为按行遍历：

|
int i, j;
int[128][128] data;
for (i = 0; i < 128; i++)
  for (j = 0; j < 128; j++)
    data[i][j] = 0;

这种访问模式在同一页面内完成所有访问后再移动到下一个页面，页面错误次数降至128次，性能提升显著。

程序的数据结构和访问模式会影响局部性（locality）。良好的局部性意味着程序倾向于访问相邻的内存位置，这有利于分页系统的工作。例如，栈数据结构具有很好的时间局部性和空间局部性，因为访问集中在栈顶附近。而哈希表等数据结构可能导致数据分散，局部性较差。不过，局部性只是评估数据结构的一个方面，还需要考虑查找效率、内存占用等因素。

编译器和加载器也可以优化程序的分页性能。例如，将代码和数据分离，生成可重入代码，使得代码页面可以标记为只读。只读页面在不需要时可以直接丢弃，无需写回辅助存储器。加载器可以优化代码布局，尽量将相关函数放在同一页面，避免函数跨越页面边界，减少页面切换开销。这种代码布局优化类似于装箱问题：在固定大小的页面中合理安排代码段，以最小化页面数量和页面切换次数。

I/O互锁和页面锁定

在按需分页系统中，某些情况下需要将页面锁定（pin）在物理内存中，防止被页面置换算法换出。这种情况在I/O操作中特别重要。

当进程执行I/O操作时，I/O控制器可能直接访问内存中的缓冲区。如果这些页面在I/O进行过程中被换出，I/O操作可能访问到错误的内存位置，导致数据损坏或系统崩溃。

解决I/O互锁问题有两种主要方法：一种是将I/O操作限制在系统内存和设备之间，用户数据需要先复制到系统内存，这种方法安全但效率较低；另一种是在I/O期间锁定相关页面，防止它们被换出，I/O完成后解锁。大多数操作系统支持页面锁定机制，通常需要特殊权限以防止滥用。

页面锁定还可以用于优化页面替换策略。例如，新调入的页面可以被临时锁定，确保至少被访问一次后再允许被替换，避免刚调入就被立即换出的情况。需要注意的是，如果锁定位未及时清除，会导致内存被长期占用，影响系统性能，因此操作系统在实现时需要适当的保护机制。

操作系统示例

Linux

Linux采用按需分页机制，只有当进程实际访问内存时才分配物理页框。页面分配从空闲帧列表中选择可用帧，页面置换采用时钟算法（Clock Algorithm），这是一种LRU的近似实现。

Linux将内存页面分为活动（active）和非活动（inactive）两个列表。活动列表包含最近被访问的页面，非活动列表包含长时间未被访问、可以被回收的页面。每个页面维护访问标记，当页面被访问时，标记被设置，页面被移动到活动列表末尾。随着时间推移，未被访问的页面会逐渐移动到非活动列表，等待回收。

Linux内核的kswapd守护进程定期检查系统内存状态。当空闲内存低于阈值时，kswapd会从非活动列表中回收页面，释放内存空间供新页面使用。

Windows

Windows的虚拟内存管理支持32位和64位系统，64位系统下每个进程可以使用高达128TB的虚拟地址空间，远超过实际物理内存容量。

Windows为每个进程维护一个工作集（working set），表示进程当前可用的物理页面数量。系统根据内存压力动态调整各进程的工作集大小，确保内存资源的合理分配。

当进程访问不在内存中的页面时，Windows采用聚类（clustering）策略，将出错的页面及其邻近页面一起加载到内存，利用空间局部性减少后续页面错误。当系统内存不足时，Windows使用类似时钟算法的页面置换策略，将不常用的页面换出，并自动修剪各进程的工作集，优先缩减大进程的工作集，以维持系统整体性能。

Solaris

Solaris内核维护一个空闲页面列表，确保有足够的内存可用。当线程访问的页面不在内存时，内核从空闲列表分配新页面。当空闲页面数量低于lotsfree阈值时，系统启动pageout进程进行内存回收。

pageout进程采用双指针时钟算法（two-handed clock algorithm）。前指针负责清除页面的引用位，后指针检查页面是否仍未被引用。如果页面在前后指针扫描期间一直未被访问，则被回收到空闲列表；如果页面已被修改，需要先将内容写回辅助存储器。

页面扫描速度根据内存压力动态调整，内存越紧张，扫描速度越快。系统通过handspread参数控制前后指针之间的距离，以平衡内存回收速度和系统性能。

Solaris优先保护被多个进程共享的库页面，避免频繁回收。对于不同类型的数据页面，系统采用差异化的回收策略，在保证重要数据安全的同时提高内存利用效率。

小结

虚拟内存技术是现代操作系统中最重要和最复杂的组件之一，它通过将逻辑地址空间与物理地址空间分离，解决了物理内存有限与程序需求无限之间的矛盾。这种分离机制实现了程序运行时的透明内存管理，使得程序员可以在巨大的虚拟地址空间中编程，而无需关心物理内存的实际限制。

本部分我们详细探讨了虚拟内存的核心机制，包括按需分页、页面置换算法、写时复制等关键技术，以及帧分配策略、颠簸现象防治、内存压缩等高级特性。然而，虚拟内存的实际实现远比我们在这里介绍的复杂。在实际操作系统中，还需要考虑内存碎片、内存泄漏检测与防治、多级页表优化、TLB管理、NUMA架构适配等诸多因素。

此外，虚拟内存的实现与操作系统的其他组件密切相关，包括进程管理、文件系统、设备管理等。虚拟内存系统需要与这些组件协同工作，才能实现高效、可靠的内存管理。因此，虚拟内存的实现是一个复杂而庞大的系统工程，需要持续的研究和优化。

小练习

1. 有效访问时间计算

假设一个系统的正常内存访问时间为10纳秒，页面错误处理时间为8毫秒。请计算：

1. 当页面错误率为0.1%时，有效访问时间是多少？
2. 当页面错误率为1%时，有效访问时间是多少？
3. 当页面错误率为10%时，有效访问时间是多少？

2. FIFO页面置换算法

给定引用字符串：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

假设系统有3个内存帧，使用FIFO页面置换算法。请：

1. 跟踪每个页面访问时的内存状态
2. 计算总页面错误次数
3. 说明FIFO算法的特点

3. LRU页面置换算法

给定引用字符串：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

假设系统有3个内存帧，使用LRU页面置换算法。请：

1. 跟踪每个页面访问时的内存状态和访问时间
2. 计算总页面错误次数
3. 与FIFO算法比较性能

4. 帧分配策略计算

假设系统有100个可用帧，有3个进程：

• 进程A：大小为50KB
• 进程B：大小为100KB
• 进程C：大小为150KB

假设每页大小为4KB。请计算：

1. 使用平均分配策略，每个进程分配多少帧？
2. 使用比例分配策略，每个进程分配多少帧？
3. 比较两种分配策略的合理性

4. 页面替换执行：
   • 将选中的页面写出到辅助存储器
   • 将新页面调入内存
   • 更新页面表

4. 页面替换执行：
   • 将选中的页面写出到辅助存储器
   • 将新页面调入内存
   • 设置新页面的访问时间为当前时间
   • 更新页面表

与FIFO算法比较：

• FIFO算法：15次页面错误（75%错误率）
• LRU算法：12次页面错误（60%错误率）
• 性能提升：LRU比FIFO减少了3次页面错误，错误率降低了15%

LRU算法优势：

1. 利用局部性原理：LRU算法基于程序访问的局部性，认为最近访问的页面在未来更可能被访问
2. 性能优异：在实际系统中，LRU算法的性能通常接近最优算法
3. 实现开销：虽然实现比FIFO复杂，但性能提升明显，是实际系统中应用最广泛的页面置换算法之一