主内存

主内存是计算机系统中用于存储正在执行的程序和数据的关键存储介质。在多进程并发执行的环境中，多个进程需要同时访问主内存，每个进程都需要独立的内存空间来存储其指令、数据和运行时状态。 操作系统负责协调这些内存访问，确保每个进程只能访问分配给它的内存区域，防止进程之间相互干扰，同时保证系统内核的内存空间不被用户进程非法访问。这就是主内存管理的核心任务。

在之前的学习中，我们学会了如何让CPU高效地服务多个进程。通过合理的调度策略，我们可以让CPU得到充分利用，让计算机更快地响应用户的需求。 但是要实现这种高效的并发执行，我们就必须让多个进程同时驻留在内存中，也就是说，我们需要共享内存资源。

在本部分，我们将一起探索操作系统管理主内存的各种方法。这些方法从最简单的裸机方案一直发展到复杂的分页技术，每种方法都有自己的优势和局限性。 选择哪种内存管理方案，往往取决于系统的硬件设计特点。我们会发现，大多数现代的内存管理算法都需要硬件的支持，这使得操作系统和硬件紧密地集成在一起。

背景知识

内存在计算机系统中起着至关重要的作用。CPU执行指令和处理数据时，必须从内存中读取指令和数据，处理完成后将结果写回内存。 CPU无法直接访问硬盘等辅助存储设备，所有需要处理的数据和指令都必须先加载到主内存中，CPU才能对其进行操作。

内存提供的是按地址访问的存储空间。每个内存单元都有一个唯一的地址，CPU通过指定地址来访问对应的内存单元。 内存本身并不关心存储在这些地址中的内容是什么，它只是提供存储和检索功能。无论是程序代码、数据还是系统状态信息，都可以存储在内存中。

在学习内存管理时，我们需要理解几个关键问题：首先，计算机的硬件架构是如何组织的？ 其次，程序中的符号名称（变量名、函数名等）是如何转换为物理内存地址的？ 逻辑地址和物理地址有什么区别？最后，我们还需要了解动态链接和共享库的实现机制。

计算机的基本硬件架构

计算机硬件架构中，CPU能够直接访问的存储设备主要有两种：主内存和CPU内部的寄存器。 寄存器是CPU内部的高速存储单元，访问速度极快，但容量很小。主内存是容量更大的存储设备，但访问速度相对较慢。

CPU只能直接访问主内存和寄存器中的数据，无法直接访问硬盘等辅助存储设备。 所有需要处理的数据和指令，都必须先从辅助存储设备加载到主内存或寄存器中，CPU才能对其进行操作。

从访问速度来看，寄存器的访问速度最快，通常在一个时钟周期内就能完成数据访问。 主内存的访问速度虽然比硬盘快得多，但相比寄存器仍然较慢。CPU访问主内存需要通过内存总线进行数据传输，这个过程需要多个时钟周期。 如果CPU需要等待数据从内存传输完成，就会导致CPU空闲，降低系统效率。

为了解决CPU和主内存之间的速度差异问题，现代计算机系统在CPU和主内存之间引入了高速缓存（Cache）。 缓存存储了最近访问的数据和指令的副本，当CPU需要访问数据时，首先检查缓存，如果数据在缓存中（缓存命中），就可以快速获取数据，避免访问较慢的主内存。 缓存的管理完全由硬件自动完成，操作系统无需干预。

除了性能问题，内存访问的安全性也是关键考虑因素。如果进程可以随意访问其他进程或操作系统内核的内存空间，就会导致系统不稳定和安全问题。 操作系统需要确保每个进程只能访问分配给它的内存区域，这种内存保护机制必须由硬件来实现。 如果完全由软件（操作系统）来检查每次内存访问的合法性，会严重影响系统性能，因此硬件必须提供内存保护支持。

内存保护的基本机制

每个进程都需要拥有独立的内存空间，这是保证系统稳定性和安全性的基本要求。 如果进程可以随意访问其他进程或操作系统内核的内存空间，就会导致数据损坏、程序崩溃甚至系统安全问题。 因此，每个进程必须被限制在分配给它的内存区域内，不能越界访问。

实现内存保护的基本机制是使用基址寄存器和界限寄存器。基址寄存器存储进程内存空间的起始地址，界限寄存器存储进程内存空间的大小。 例如，如果基址寄存器值为300040，界限寄存器值为120900，那么该进程只能访问从300040到420939（300040+120900-1）的内存地址范围，超出此范围的访问将被禁止。

每次进程尝试访问内存时，CPU的硬件会检查访问的地址是否在允许的范围内。如果地址超出界限，CPU会触发内存保护异常，操作系统会处理这个异常，可能终止该进程。 通过这种方式，可以防止进程访问操作系统或其他进程的内存空间。

这两个寄存器的值只能由操作系统在内核模式下通过特权指令进行设置。普通用户程序无法修改这些寄存器的值，因为它们只能在用户模式下运行，没有执行特权指令的权限。 只有操作系统在内核模式下才能修改这些寄存器，从而控制每个进程可以访问的内存范围。

操作系统在内核模式下拥有最高权限，可以执行所有操作，包括内存分配、错误处理、输入输出管理等。 正是通过这种硬件支持的内存保护机制，系统才能安全高效地运行多个进程。

地址绑定的过程

程序从源代码到最终在内存中执行，需要经历多个阶段。最初，程序以二进制可执行文件的形式存储在硬盘等辅助存储设备上。 当程序需要运行时，操作系统会将其加载到主内存中，为它分配内存空间，并创建一个进程来执行该程序。 进程执行完毕后退出，其占用的内存空间会被操作系统回收，可以分配给其他进程使用。

操作系统在内存分配上具有很大的灵活性，可以将进程加载到内存的任意合适位置。 虽然逻辑上进程的地址空间通常从0开始，但进程在物理内存中的实际起始地址并不一定是0。操作系统会根据当前内存的使用情况，将进程安排在合适的位置。 后面我们会详细讨论操作系统如何进行内存分配。

在程序执行之前，地址会经历多次转换。在源代码阶段，我们使用符号名称（如变量名、函数名）来引用数据。 编译器将这些符号名称转换为相对于模块起始位置的偏移地址，生成可重定位的目标代码。 链接器或加载器随后将这些可重定位地址转换为实际的物理内存地址。每一步转换都在不同的抽象层次上进行。

地址绑定可以在不同的阶段完成：

逻辑地址空间与物理地址空间

在程序执行过程中，CPU为每个数据项和每条指令分配地址。这个地址是程序视角中的地址，称为逻辑地址或虚拟地址。 而物理内存中的每个存储单元也有自己的地址，这个地址是实际的物理地址，对应内存硬件中的具体位置。

在某些情况下，逻辑地址和物理地址是相同的，例如在编译时绑定地址的情况下，程序被编译为使用固定的物理地址。 但在大多数现代系统中，程序运行时的逻辑地址和物理地址是不同的。 例如，程序可能认为自己的地址空间从0开始，但操作系统可能将其加载到物理内存的10000地址开始的位置。此时，逻辑地址需要转换为物理地址。

这种地址转换由内存管理单元（MMU）这一硬件组件完成。MMU负责将程序使用的逻辑地址转换为实际的物理地址。 逻辑地址空间是程序看到的地址范围，通常从0开始到某个最大值；物理地址空间是实际物理内存的地址范围，从某个起始地址R开始到R+max。 程序员只需要关心逻辑地址，认为程序从地址0开始，而MMU负责将逻辑地址映射到实际的物理地址。

逻辑地址和物理地址的分离使得操作系统能够灵活地管理内存，让每个程序都拥有独立的逻辑地址空间，而不会相互干扰。 这是现代内存管理的核心思想，为多进程并发执行提供了基础。

动态加载技术

前面讨论的内容默认了一个前提：进程运行时，整个程序和所有数据都需要一次性加载到内存中。 这意味着进程的大小不能超过可用内存容量，否则无法运行。但在实际应用中，我们希望更灵活地使用内存，这时就需要使用动态加载技术。

动态加载是指程序在运行时，只有当某个功能模块（如函数或库）真正需要使用时，才将其从磁盘加载到内存中。 主程序在启动时会被加载到内存，而其他功能模块则保留在磁盘上。当程序执行到需要某个模块时，才会将该模块加载到内存中。

例如，一个大型程序可能包含错误处理模块。在程序正常运行的情况下，错误处理代码可能不会被使用，因此可以保留在磁盘上。 只有当真正发生错误时，才将错误处理模块加载到内存中。这样，虽然整个程序很大，但实际占用内存的部分可能很小，从而提高了内存利用率。

动态加载通常不需要操作系统的特殊支持，程序员可以在应用程序层面实现。 当然，操作系统也可以提供一些工具和库来简化动态加载的实现。

动态链接和共享库

动态链接库（DLL，在Linux系统中称为共享库）是一种允许多个程序共享同一份库代码的机制。 在没有动态链接库的情况下，每个程序都需要包含所需库的完整副本，这会导致大量重复代码占用内存空间。

有了动态链接库后，多个程序可以共享同一份库代码，内存中只需要保存一份库的副本，而不需要每个程序都携带自己的副本。 这就是动态链接库的主要优势：节省内存空间，提高资源利用率。动态链接库在Windows和Linux系统中都很常见。

程序如何使用动态链接库呢？当程序运行时，如果需要使用库中的某个功能，操作系统会定位该库文件（DLL或共享库）。 如果库还没有加载到内存中，操作系统会将其加载进来。然后，操作系统会告诉程序库代码在内存中的位置，程序就可以调用这些功能了。

动态链接库的另一个优势是版本管理。如果库发布了新版本（修复了bug或添加了新功能），只需要更新库文件，所有使用该库的程序在下次运行时都会自动使用新版本。 这样，所有程序都能及时获得最新的库功能。

当然，如果新版本与旧版本不兼容，操作系统会通过版本号来管理。每个程序会记录自己使用的库版本，如果新版本不兼容，旧版本会保留，不同程序可以使用不同版本的库，互不干扰。 只有专门为新版本设计的程序才会使用新版本的库。

需要注意的是，动态链接和动态加载是不同的概念。动态加载是程序在运行时决定何时加载哪些功能模块，而动态链接和共享库通常需要操作系统的支持。 只有操作系统才能确保多个程序安全地共享同一份库代码，而不会相互干扰。

静态链接 vs 动态链接

静态链接（传统方式）

动态链接（共享方式）

库版本管理

等我们讲到分页的时候，还会详细讨论操作系统是如何实现多个进程安全共享这些共享库的。

连续内存分配

主内存需要同时为操作系统内核和用户程序分配空间。如何高效地分配这些内存空间，确保系统稳定运行并充分利用内存资源，是内存管理的重要问题。 接下来我们讨论最早期、最直接的内存分配方法——连续内存分配。

内存保护机制

防止进程访问不属于自己的内存空间，可以使用重定位寄存器和界限寄存器来实现内存保护。 重定位寄存器存储进程内存空间的起始地址，界限寄存器存储进程内存空间的大小。 例如，如果重定位寄存器值为100040，界限寄存器值为74600，那么该进程只能访问从100040到174639（100040+74600-1）的内存地址范围。

每次进程尝试访问内存时，MMU（内存管理单元）会检查访问的地址是否在允许的范围内。如果地址超出界限，访问会被阻止，并可能触发异常。

当CPU切换到另一个进程时，调度器会更新这两个寄存器的值，设置为新进程的起始地址和大小。 这样，每个进程都被限制在自己的内存区域内，无法越界访问。

这种机制还有一个优势：操作系统可以灵活地管理内存。例如，某些设备驱动如果暂时不需要，可以不加载到内存中，需要时再加载； 不需要时可以释放其占用的内存，分配给其他进程使用。这样，内存利用率更高，系统运行更高效。

内存分配策略

在连续内存分配中，每个进程被分配一块连续的内存区域，不同进程的内存区域大小可以不同，但每个区域只分配给一个进程。 操作系统维护一张表，记录哪些内存区域是空闲的，哪些已经被分配。

初始状态下，整个内存空间是空闲的，形成一个大的连续空闲区域。随着进程的创建和加载，操作系统根据每个进程的内存需求，为其分配合适大小的连续内存区域。 进程获得内存后，就可以在内存中运行，参与CPU调度。当进程终止时，它占用的内存区域会被释放，操作系统可以将这块空间分配给其他需要的进程。

如果新进程到达时，没有足够大的空闲内存区域，有两种处理方式：一种是直接拒绝该进程，让它等待； 另一种是将进程放入等待队列，当有内存释放时，操作系统会检查等待队列，看是否有进程可以分配到新释放的内存。

实际上，内存中的空闲区域（称为“空洞”）会随着进程的分配和释放变得越来越零碎。每当有进程需要内存时，操作系统会在这些空洞中寻找足够大的区域。 如果找到的空洞比进程需要的还大，就将空洞分成两部分，一部分分配给进程，剩余部分继续作为空闲区域。 进程释放内存后，其占用的区域又变成空洞。如果新产生的空洞与相邻的空洞相连，操作系统会将它们合并成一个更大的空洞，以便后续分配。

这种分配方式是动态内存分配的典型例子。如何从大小不一的空洞中选择合适的空间分配给进程？ 有几种常见的策略：首次适应、最佳适应和最差适应。这些方法各有优缺点。

模拟显示，在减少时间和存储利用率方面，首次适应和最佳适应都比最差适应更好。在存储利用率方面，首次适应和最佳适应都没有明显的优势，但首次适应通常更快。

内存分配实验室

内存碎片问题

无论是首次适应还是最佳适应等分配方法，都会遇到外部碎片问题。随着进程的分配和释放，内存中会产生许多小的空闲区域。 虽然这些空闲区域的总和可能很大，但每个区域都太小，无法满足新进程的内存需求。例如，即使所有空闲区域的总和足够大，但由于分散成许多小块，无法分配给需要连续内存的进程。

有时候，外部碎片问题会非常严重。最坏的情况是，每两个已分配的进程之间都有一小块空闲内存。 如果能够将这些小块合并，或许可以满足更多进程的内存需求。我们选择的分配策略会影响碎片的产生程度。 有些系统使用首次适应效果较好，有些使用最佳适应更合适。另外，每次分配时，剩余空间是保留在高地址端还是低地址端，也会影响碎片的分布。

无论使用哪种方法，外部碎片总是难以避免。根据内存总量和进程平均大小，外部碎片有时只是小问题，有时会成为严重问题。 例如，有研究发现，使用首次适应时，如果分配了N块内存，大约会有0.5N块内存因为碎片而浪费。也就是说，大约三分之一的内存可能无法使用。这就是著名的"50%规则"。

除了外部碎片，还有内部碎片。例如，如果有一个18,464字节的空闲区域，下一个进程只需要18,462字节。 如果精确分配，剩下的2字节区域太小，管理它的开销可能比它本身还大。

为了解决这个问题，可以将内存分成固定大小的块，分配时按块进行。 这样，分配给进程的内存可能会比它实际需要的多一点点，这多出来的部分就是内部碎片——即分配给进程但未使用的空间。

如何解决外部碎片问题？一种方法是内存压缩，即将内存中的内容重新整理，将所有空闲区域合并成一个大块。 这样后续分配就方便多了。不过，压缩不是随时都能进行的。如果内存地址是固定的，压缩就无法实现。 只有在地址可以动态调整的情况下，才能将程序和数据移动到新位置，然后更新基址寄存器，让进程知道新的地址。 最简单的压缩方法是将所有进程移动到内存的一端，所有空闲区域移动到另一端，形成一个大块。但这样做有时会很耗时。

还有一种更彻底的方法，就是不要求进程的内存必须是连续的，允许进程的内存分散在内存的不同位置。这就是分页技术，我们接下来会详细讨论。

实际上，碎片问题不仅存在于内存管理中，在管理任何数据块集合时都会遇到。后面在存储管理章节中，我们还会详细讨论这个话题。

为了更好地理解内存分配的工作原理，让我们用一个简单的图表来展示这个过程：

分页

前面讨论的内存分配方法都要求进程的内存必须是连续的，这会导致外部碎片问题。 随着进程的分配和释放，内存中会产生许多小的空闲区域，虽然总和可能很大，但每个区域都太小，无法满足新进程的需求。

分页技术解决了这个问题。分页将物理内存和进程的地址空间都分成固定大小的块，进程的内存可以分散在物理内存的不同位置。 这样，即使内存中有小的空闲区域，也可以灵活利用，不用担心外部碎片问题，也不需要频繁进行内存压缩。

分页技术非常灵活高效，因此现在几乎所有的操作系统——无论是大型服务器还是移动设备——都采用分页技术。 分页是操作系统和硬件协同实现的，接下来我们详细讨论其工作原理。

分页的基本方法

分页将物理内存和进程的地址空间都分成固定大小的块。物理内存被分成固定大小的块，称为"帧"（frame）； 进程的地址空间也被分成同样大小的块，称为"页"（page）。当进程需要运行时，操作系统将这些页从硬盘或其他存储设备加载到内存中任何可用的帧中。 这样，内存和硬盘上的数据块大小都对齐，便于传输和管理。

分页的一个重要特性是进程看到的虚拟地址空间可以与实际的物理内存完全不同。 即使物理内存容量有限，进程仍然可以拥有一个很大的虚拟地址空间，这个虚拟地址空间可以比物理内存大得多。

每次CPU访问内存时，会将逻辑地址分成两部分：页号（p）和页内偏移（d）。 操作系统根据页号在页表中查找对应的帧号，然后结合页内偏移，就能准确定位到物理内存中的具体位置。

页号用作索引，在进程的页表中查找对应的条目。页表包含每个页对应的物理帧号。 帧号与页内偏移相结合，就构成了物理内存地址。分页的内存模型如下图所示：

MMU翻译CPU生成的逻辑地址为物理地址的步骤如下：

页的大小是由硬件预先规定的。一般来说，页的大小都是2的幂，如4KB、8KB，有些系统还支持1GB的大页。 使用2的幂作为页大小，是为了简化地址转换的计算，使页号和偏移的提取可以通过简单的位操作完成，提高效率。

分页为每个进程分配固定大小的页。每个进程使用的内存空间被分成多个页，这些页可以放在物理内存中的任意可用帧中。 这样做的好处是，任何空闲的帧都可以用来存储进程的页，不会出现外部碎片问题。

不过，分页也有缺点。例如，一个进程的最后一页可能只使用了一半，剩余的一半就浪费了，这种浪费称为"内部碎片"。 如果进程的大小与页的大小没有关系，平均而言，每个进程大约会浪费半页的空间。

页的大小需要权衡：页太小，内部碎片少，但页表会变得很大，因为每一页都需要一个页表条目，管理开销大。 页太大，页表小，管理简单，但内部碎片会增加。另外，页越大，从磁盘传输数据时效率可能更高。 因此，实际系统中会根据内存容量和程序特点选择合适的页大小。现在常见的页大小一般是4KB或8KB，有些系统还支持更大的页。

硬件支持

每个进程都有自己的页表，页表的指针与进程的其他重要信息（如程序计数器、寄存器状态等）一起存储在进程控制块（PCB）中。 当CPU切换到另一个进程时，需要加载新进程的页表指针和相关状态信息。

硬件如何存储和使用页表？有几种方法。最简单的方法是用一组专门的高速寄存器来存储页表，这样查找速度很快。 但问题很明显：每次切换进程时，这些寄存器都需要重新加载，这会降低进程切换的速度。

如果进程的页表很小，例如只有256个条目，使用寄存器存储还可行。但现代系统的进程往往需要上百万个页表条目（例如2的20次方），这时使用寄存器就完全不现实了。 因此，页表通常存储在主内存中，只用一个页表基址寄存器（PTBR）来指向它。 这样，切换进程时只需要更新这个指针，速度更快，也更节省资源。

翻译后备缓冲器

将页表放在主内存中，虽然切换进程时很方便，只需要更新指针，但每次访问数据都需要先查页表再访问数据，相当于需要两次内存访问，速度会明显下降。 这就像查找一本书的某一页，需要先查目录（页表），再翻到那一页（数据），效率较低。

为了解决这个问题，引入了TLB（翻译后备缓冲器），它是一个高速缓存，存储最近使用的页表条目。 CPU每次访问内存时，首先在TLB中查找，如果找到（TLB命中），就可以直接获得物理地址，速度很快； 如果没有找到（TLB未命中），再去主内存中查找页表。TLB可以存储不同进程的页表条目，通过ASID（地址空间标识符）来区分，避免不同进程的地址混淆。 这样，在大多数情况下都能快速获得物理地址，大大提高了内存访问效率。

内存保护

分页中的内存保护通过在页表中为每一页设置保护位来实现。这些保护位定义了该页的访问权限，如只读、读写、只执行等。 每次访问内存时，系统会检查页表中的保护位，确定该页是否允许当前操作。如果程序试图执行不被允许的操作（如向只读页写入数据），硬件会立即触发异常，通知操作系统处理，从而防止程序非法修改内存。

这种保护机制可以更细致。例如，可以让某些页只能读，某些页只能写，某些页只能执行（如存储程序代码的页）。 通过在页表中设置不同的保护位，硬件可以帮助管理各种访问权限。任何程序试图执行不被允许的操作，系统都会立即检测并阻止。

另外，每个页表条目还有一个有效-无效位。有效位为1表示该页属于当前进程，可以访问； 有效位为0表示该页不属于当前进程或尚未分配，任何访问都会被阻止。这确保了进程只能访问分配给它的页。

共享页

分页的一个重要优势是允许多个进程共享同一份代码。这可以大大节省内存空间，因为多个进程可以使用同一份代码副本，而不需要每个进程都拥有自己的副本。

例如，标准C库（libc）是常用的库，几乎每个Linux进程都需要使用。 如果每个进程都拥有自己的libc副本，假设有40个进程，每份2MB，总共就要占用80MB内存，非常浪费。 通过分页机制，只要代码是可重入的（即代码在执行过程中不会修改自身，多个进程可以安全地同时执行），所有进程就可以共享同一份libc。 每个进程有自己的数据和寄存器，互不干扰，但代码都指向内存中的同一块区域。这样，40个进程总共只需要2MB内存，节省了大量空间。

不仅仅是libc，像编译器、窗口系统、数据库等常用程序，也可以采用这种方式共享。 只要代码是可重入的，操作系统就可以将其设置为只读，防止被修改，多个进程就可以安全地共享使用。

分页演示

页表结构

当页表变得很大时，如何高效地存储和管理页表是一个重要问题。工程师们提出了多种解决方案，如层次化分页、哈希页表、倒排页表等。 这些方法都是为了在节省空间的同时提高查找速度，解决大内存地址空间下的页表管理问题。

层次化分页

现代计算机系统支持非常大的虚拟地址空间，从2的32次方到2的64次方。 地址空间越大，页表也会变得非常大。例如，在一台32位系统中，如果页大小为4KB（2的12次方），那么页表就需要2的20次方（约100万）个条目。 如果每个条目占4字节，一个进程的页表就需要4MB内存。如果每个进程都需要这样大的页表，内存很快就会耗尽。

解决方案是层次化分页：不将页表作为一大块连续的表，而是将其分成多个层次，每个层次只存储需要的部分。这样既节省空间，又提高了灵活性。

最常见的做法是两级分页，即将页表本身也进行分页。例如，在32位地址、4KB页大小的系统中， 原本虚拟地址分成20位的页号和12位的页内偏移。现在将20位的页号拆成两段：前10位是外层页表的索引，后10位是内层页表的索引。 这样，虚拟地址的结构如下：

其中p1是外层页表的索引，p2是内层页表中的页内位移。地址翻译方法如下图所示：

因为地址翻译从外层页表向内工作，这个方案也被称为前向映射页表。

两级分页在32位系统中很好用，但在64位系统中就面临挑战。原因如下：假设页大小仍然是4KB（2的12次方）， 那么整个虚拟地址空间可以分成2的52次方个页。如果使用两级分页，内层页表一页可以存储2的10次方（1024）个4字节的条目，表面上看还可以， 但实际情况如下：

如果直接使用两级分页，外层页表需要2的42次方个条目，仅存储这些条目就需要2的44次方字节，这是不可接受的。 如果每个进程都需要这样大的页表，内存很快就会耗尽。解决方案是将外层页表也进行分页，这样就不需要一次性分配那么大的空间，既节省空间又提高了灵活性。 这种思路在一些32位CPU上也使用过。

例如，可以将外层页表也像普通页表那样分页，这样就变成了三级分页。 假设外层页表的每一块还是2的10次方个条目（4KB），虽然这样已经比原来节省了不少，但64位的虚拟地址空间仍然非常庞大，三级分页也还是面临挑战。

可以看到，即使将外层页表拆成小块，仍然需要2的34次方字节，也就是16GB。仅存储页表就需要16GB，这是不可接受的。

如果还不够用，可以继续增加分页层级，将外层页表再分页，变成四级、五级，甚至更多级。 例如，64位的UltraSPARC处理器需要七级分页才能将一个虚拟地址翻译成物理地址。 每次访问内存都需要查找七层表，效率很低。因此，在64位系统中，单纯依靠多级页表来管理内存往往变得非常低效，通常不采用这种方法。

哈希页表

32位地址空间使用多级页表还能应对，但64位地址空间的页表会变得非常大。有没有更高效的方法？哈希页表就是其中一种。

哈希页表使用哈希表来存储页表条目。要查找一个虚拟页号对应的物理帧号，首先使用哈希函数将虚拟页号转换为哈希值，然后在哈希表中查找。 哈希表的每个槽位可能对应多个虚拟页号（哈希冲突），这时使用链表将冲突的条目链接起来。每个链表节点存储虚拟页号、对应的物理帧号以及指向下一个节点的指针。

查找时，先计算哈希值，定位到哈希表的某个槽位，然后沿着链表逐个比较虚拟页号。如果找到匹配的虚拟页号，就可以获得对应的物理帧号，从而构成物理地址。 如果没找到，说明该页还没有映射到物理内存，需要触发缺页处理。

哈希页表还有一个改进版本，称为聚簇页表。它的思路是：每个哈希表槽位不只存储一个页的映射，而是一次性存储一组（例如16个）页的映射。 这样，查找时可以一次比较多个页，效率更高。聚簇页表特别适合内存使用分散、虚拟地址不连续的场景，能大大减少内存浪费。

总之，哈希页表和聚簇页表通过哈希查找和分组存储的方法，将庞大的页表变得既快速又节省空间，特别适合64位这种超大地址空间。

倒排页表

传统的页表是每个进程都有一张表，按虚拟页号索引，存储对应的物理帧号。因为页表是按虚拟地址组织的，查找时可以直接通过虚拟页号索引，速度很快。

但这种做法有一个问题：如果进程的虚拟地址空间很大，页表就会变得非常庞大，可能有上百万个条目，仅存储这些页表就要占用大量内存。 在内存紧张的情况下，还要为页表分配大量空间，这是很大的浪费。

倒排页表采用不同的思路：它不是按虚拟页来组织，而是反过来——每个物理内存页（物理帧）在表中占一个条目。 每个条目记录该物理页当前被哪个进程、哪个虚拟页占用。这样，整个系统只需要一张页表，条目数等于物理内存页的数量，大大节省了空间。

由于一张表中混合了多个进程的信息，每个条目还需要包含地址空间标识符（进程ID），这样才能区分不同进程的虚拟页。

64位的UltraSPARC、PowerPC等处理器使用了倒排页表。 例如，IBM RT系统就使用倒排页表。它的每个虚拟地址格式如下：

|
<进程ID, 页号, 偏移>

倒排页表可以看作是一份物理内存的使用登记表。每个条目代表一块物理内存页，记录当前是哪个进程（进程ID）的哪个虚拟页在使用这块物理内存。

当要访问内存时，操作系统使用进程ID和虚拟页号这两个信息，在倒排页表中查找匹配的条目。 如果找到了，例如在第i个条目，那么物理地址就是第i个物理页加上偏移量。如果找不到，说明该虚拟页还没有分配物理内存，系统会报告非法地址访问错误。

倒排页表的优势是节省空间，因为只需要为物理内存中的每一页登记一次，无论有多少进程、多少虚拟页，页表的大小都等于物理内存页数。 但缺点是查找效率低，每次查找都需要遍历整个表，尤其是内存很大时，查找会更慢。

为了提高查找速度，通常使用哈希表作为辅助索引。哈希表可以帮助快速定位可能的条目，减少查找次数。 不过，这样每次访问虚拟内存，至少需要两次内存访问：一次查哈希表，一次查倒排页表。如果加上TLB，先查TLB，未命中时再查哈希表和倒排页表，速度会快很多。

倒排页表还有一个问题，就是处理共享内存时。传统页表中，每个进程有自己的页表，可以将不同的虚拟地址指向同一块物理内存，实现真正的共享。 但在倒排页表中，每块物理内存只能登记一个进程和虚拟页的映射，只能有一个虚拟页与之对应。 如果其他进程也想使用这块内存，会触发缺页异常，系统需要更新登记信息。这样，真正的多对一共享就难以实现，只能轮流使用。

交换

进程要运行，其指令和数据必须加载到内存中。但内存空间有限，当进程数量较多时，可能无法将所有进程都加载到内存中。 此时，操作系统会将暂时不用的进程或其部分内容转移到硬盘等后备存储设备中，当需要时再将其加载回内存。 这样，虽然物理内存容量有限，但系统可以同时管理更多进程，提高了多任务处理能力，使系统看起来拥有比实际物理内存更大的内存空间。

标准交换

标准交换涉及在主内存和后备存储之间移动整个进程。后备存储通常是快速的辅助存储。 它必须足够大，以容纳需要存储和检索的进程的任何部分，并且必须提供对这些内存镜像的直接访问。 当一个进程或部分被交换到后备存储时，与进程关联的数据结构必须被写入后备存储。 对于多线程进程，所有每线程数据结构也必须被交换。操作系统还必须维护已被交换出的进程的元数据，以便在它们被交换回内存时能够恢复它们。

标准交换的优势在于它允许物理内存被超额订阅，这样系统可以容纳比实际物理内存所能存储的更多的进程。 空闲或大部分空闲的进程是交换的良好候选；分配给这些非活动进程的任何内存都可以专门用于活动进程。 如果一个被交换出的非活动进程再次变得活跃，它必须被交换回来。这在下图中得到了说明：

带分页的交换

早期的UNIX系统使用标准交换，即将整个进程从内存转移到硬盘，或从硬盘加载回内存。 这种方法效率较低，特别是当进程很大时，传输整个进程需要很长时间。 因此，现代操作系统如Linux和Windows基本不再使用这种方法。只有像Solaris这样的系统，在内存严重不足时才会偶尔使用。

现在主流的做法是带分页的交换。即不再交换整个进程，而是只交换进程中使用不到的页。 这样，需要传输的数据量大大减少，速度自然快得多。这种方法让物理内存看起来更大，可以同时容纳更多进程，而且不会因为交换整个进程太慢而导致系统卡顿。

现在通常所说的“交换”，一般指的就是这种带分页的交换。将一页从内存转移到硬盘称为“页出”（page out），从硬盘加载到内存称为“页入”（page in）。 下面的图展示了进程A和B的部分页面被页出和页入的过程。

这样的交换方式比标准交换高效得多，因为只移动需要的页面而不是整个进程。

移动系统上的交换

大多数PC和服务器的操作系统都支持交换页。相比之下，移动系统通常不支持任何形式的交换。移动设备通常使用闪存而不是更宽敞的硬盘作为非易失性存储。 由此产生的空间限制是移动操作系统设计者避免交换的一个原因。其他原因包括闪存能够容忍的写入次数有限，在这些设备中主内存和闪存之间的吞吐量较差。

虽然只交换部分页面比交换整个进程要高效得多，但如果系统开始频繁交换页面，通常说明内存不足，进程数量过多。 遇到这种情况，常见的解决方案有两种：要么终止一些进程以释放内存空间，要么增加物理内存容量，以满足所有进程的需求。

Intel 32位和64位架构实例

在个人电脑CPU领域，Intel占据主导地位。从上世纪70年代末的16位8086，到IBM PC使用的8088，再到32位奔腾（Pentium）系列， Intel一直在不断升级其处理器架构。后来，Intel推出了基于x86-64架构的64位处理器。 现在，主流的操作系统如Windows、macOS和Linux都能在Intel处理器上运行（当然Linux也支持其他架构）。 不过，在手机和平板等移动设备领域，Intel的影响力较小，那里主要是ARM架构的天下。

接下来，我们讨论Intel的IA-32（32位）和x86-64（64位）架构中的地址翻译机制。 需要说明的是，Intel的处理器型号和版本非常多，我们无法详细讨论每一款的内存管理细节，这里我们只讨论最核心、最有代表性的内存管理机制。

IA-32架构

在IA-32系统中，内存管理采用分段和分页两级机制。 CPU首先生成逻辑地址，这个地址先由分段单元处理，分段单元将其转换为线性地址。 接着，线性地址被送到分页单元，分页单元将其翻译成物理内存地址。 分段和分页这两个步骤共同构成了内存管理单元（MMU）的核心功能，将程序中的逻辑地址逐步转换为实际的物理内存地址。

IA-32分段

IA-32架构允许一个段最大为4GB，每个进程的最大段数是16K。一个进程的逻辑地址空间被分成两个分区。 第一个分区由最多8K个私有的进程段组成。第二个分区由最多8K个在所有进程之间共享的段组成。 关于第一个分区的信存储在本地描述符表（LDT）中；关于第二个分区的信存储在全局描述符表（GDT）中。 LDT和GDT中的每个条目由一个8字节的段描述符组成，其中包含关于特定段的详细信息，包括段的基址位置和限制。

逻辑地址是一个对（选择器，偏移），其中选择器是一个16位数字：

这里，s指定段号，g指示段是在GDT还是LDT中，p处理保护。偏移是一个32位数字，指定段内字节的位置。 机器有六个段寄存器，允许一个进程同时寻址六个段。它还有六个8字节的微程序寄存器来保存来自LDT或GDT的相应描述符。 这个缓存让Pentium避免为每次内存引用读取内存中的描述符。

IA-32上的线性地址是32位长的，由以下方式形成：段寄存器指向LDT或GDT中的适当条目。 关于相关段的基址和限制信息被用来生成线性地址。 首先，使用限制来检查地址有效性。如果地址无效，则生成内存故障，导致陷阱到操作系统。如果有效，则偏移的值被加到基址的值上，从而产生32位线性地址。

IA-32分页

IA-32架构允许页大小为4KB或4MB。对于4KB页，IA-32使用两级分页方案，其中32位线性地址的划分如下：

在IA-32架构下，地址翻译采用两级查找。32位线性地址被分成三部分：前10位用于在页目录中查找，中间10位在页表中继续查找，最后12位是页内偏移。 通过这种层次化查找，最终可以定位到内存中的实际数据。如果使用大页模式，页目录可以直接指向4MB的大页，省去中间的页表查找步骤。

后来大家发现32位系统最多只能用4GB内存，实在不够用，于是Intel推出了PAE（物理地址扩展）。 有了PAE，分页结构从两级变成三级，地址空间也扩展到了36位，最多能支持64GB物理内存。 不过要注意，操作系统也得支持PAE才行，比如Linux和macOS都支持，但32位Windows桌面系统即使开了PAE，还是只能用4GB内存。

x86-64架构

64位处理器的发展历史很有意思。最初Intel推出了IA-64（后来称为Itanium）新架构，但市场反响不佳，采用者很少。 反而是AMD另辟蹊径，在原有32位x86架构基础上进行扩展，推出了x86-64架构。 这个新架构既能兼容旧的32位程序，又能支持更大的内存空间，因此大受欢迎。后来，Intel也不得不采用x86-64架构。

64位地址空间理论上非常大。理论上，64位可以表示2的64次方个地址，即超过16EB（艾字节），这比现在的硬盘容量大得多。 但实际上，并没有使用全部64位。现在的x86-64处理器只使用48位来表示虚拟地址，物理地址最多支持52位，即4096TB。 分页结构也变得更复杂，采用四级分页，可以支持4KB、2MB或1GB的大页。这样既能兼容旧程序，又能支持更大的内存，一举两得。

ARMv8架构实例

在手机、平板等移动设备领域，几乎都使用ARM处理器。 ARM和Intel的商业模式不同。Intel自己设计并生产芯片，而ARM只负责设计处理器架构，然后将设计授权给全球的芯片厂商。 例如，苹果的iPhone、iPad使用的芯片就是基于ARM设计，许多Android手机也是如此。除了手机和平板，智能手表、路由器、汽车智能系统等也广泛使用ARM架构。

ARM架构设备的数量非常庞大，全球出货量已超过1000亿颗，堪称世界上最常见的处理器架构。 接下来，我们讨论ARM家族中非常重要的64位ARMv8架构，看看它是如何管理内存的。

ARMv8有三种不同的翻译粒度：4KB、16KB和64KB。每种翻译粒度提供不同的页大小，以及更大的连续内存部分，称为区域。不同翻译粒度的页和区域大小如下表所示：

在ARMv8架构中，如果选择4KB或16KB作为最小页大小，系统最多可以使用四级分页结构；如果使用64KB的大页，最多可以使用三级分页。 分页采用层次化结构，每一级都将地址范围缩小，最终精确定位到内存中的具体位置。

以4KB粒度为例，ARMv8虽然是64位处理器，但实际上只使用48位来表示虚拟地址。 地址被分成四段，每一段用于查找不同级别的页表。最低的12位是页内偏移，表示在4KB页内的具体位置。 上面三段分别对应不同级别的页表，逐级查找，直到找到目标。

分页表并不总是需要查到底层。有时，一级页表的某个条目可以直接指向一个1GB的大区域，此时后面的30位直接作为这个大区域内的偏移。 类似地，二级页表也可以直接指向2MB的区域，此时使用低21位作为偏移。这样做的好处是，如果有一大块连续的内存，就不需要再细分成很多小页，查找速度更快。

小结

主内存管理作为操作系统的重要组成部分，展现了计算机系统高效运行的底层机制。从地址绑定的灵活性到分页技术的内存虚拟化，再到各种架构的具体实现，每一个概念都是现代计算系统的重要组成部分，共同构成了高效的内存管理体系。

当你在编程或系统设计中遇到内存相关的问题时，理解这些底层机制的原理，有助于找到最优雅的解决方案。 理解底层原理，往往是解决复杂问题的最佳途径。

小练习

1. 地址转换计算

假设一个系统使用分页技术，页大小为4KB（4096字节）。逻辑地址为0x3A7F，请：

1. 将逻辑地址转换为二进制
2. 计算页号和页内偏移
3. 如果页表显示该页对应的帧号为5，计算物理地址

2. 内存分配策略比较

假设内存中有以下空闲区域（按地址顺序）：

• 空洞1：起始地址1000，大小200KB
• 空洞2：起始地址5000，大小100KB
• 空洞3：起始地址8000，大小150KB
• 空洞4：起始地址12000，大小300KB

现在有一个进程需要120KB的内存。请分别使用首次适应、最佳适应和最差适应策略，说明会选择哪个空洞，并计算分配后剩余的空洞大小。

3. 页表大小计算

假设一个32位系统，页大小为4KB，每个页表条目占4字节。请计算：

1. 虚拟地址空间可以分成多少个页？
2. 每个进程的页表需要多少字节？
3. 如果有100个进程，所有页表总共需要多少内存？