内存管理

物理内存

物理内存

物理内存（Physical Memory）是计算机系统中实际存在的、用于存储程序指令和数据的硬件介质，通常指主存储器（如 DRAM 内存条）。它在物理上表现为一组连续的字节（Byte）或字（Word）的数组。

• 基本特性：
  • 易失性：物理内存（特指 DRAM）通常是易失的，意味着断电后存储的信息会丢失。
  • 寻址：内存中的每个字节都有一个唯一的物理地址。如果地址总线有 $n$ 位，那么总共可以寻址 $2^n$ 个字节。
  • 访问：CPU 可以通过物理地址直接对内存单元进行读取（Read）或写入（Write）操作。
• 数据传输：
  • 地址总线（Address Bus）：用于 CPU 指定要访问的内存单元的物理地址。
  • 数据总线（Data Bus）：用于在 CPU 和内存之间双向传输数据。
  • 控制总线（Control Bus）：传递控制信号，如读写命令、时钟信号等。

下图展示了一个简化的内存组织结构，其中地址译码器根据地址输入选择相应的存储单元，并通过数据总线进行数据交换。

内存保护

当引入进程这一抽象后，内存便不再仅仅是字节的集合，它获得了更深层次的「语义」——内存区域成为了进程状态的一部分。

• 进程状态：进程在内存中的数据（如变量、堆栈内容）共同构成了其当前状态。
• 状态机规约：进程的执行可以看作一个状态机，其状态的改变必须遵循预设的规约。例如，一个内存分配函数 kalloc(s)，在给定已分配内存集合 $S = [l_0, r_0) \cup [l_1, r_1) \cup \dots$ 的情况下，其返回的新分配区域 $[l, r)$ 必须满足 $[l, r) \cap S = \empty$。
• 未定义行为：如果进程的状态改变违背了规约（例如，非法访问内存），就会导致「未定义状态」，进而可能引发「未定义行为」，如程序崩溃或数据损坏。
• 操作系统职责：作为进程状态机的管理者，操作系统必须提供保护机制，以防止或处理违背规约的行为，确保系统的稳定性和安全性。

非法状态改变操作

哪些对进程「状态」（即内存）的改变操作是非法的，需要操作系统进行保护？

1. 修改其他进程的状态：
   • 必须明确界定每个进程的内存边界，防止一个进程恶意或无意地修改属于其他进程的内存区域。
2. 非法增加自身状态空间：
   • 进程增加自身内存占用（如扩大堆栈）时，只能从「空闲」内存中申请，不能占用已被其他进程或自身其他部分使用的内存。操作系统需要维护哪些内存是「空闲」的。
3. 违反内部状态的读写权限：
   • 内存区域（如代码段、只读数据段）应有相应的访问权限（读、写、执行）。操作系统需要标记内存块的权限，并在访问时进行断言，确保操作符合权限。

早期计算机系统的内存管理

内存保护并非一开始就存在。

单道程序设计年代

在单道程序设计（Uniprogramming）时期：

• 硬件限制：物理内存容量非常小。
• 软件结构：
  • 内存中只有一个用户应用程序和一小部分简单的操作系统代码/数据。
  • 应用程序直接面向物理内存编程。
  • 由于一次只运行一个应用程序，它总是被加载到物理内存的同一固定位置。
  • 此时，保护的需求不迫切，因为没有其他用户程序会干扰当前运行的程序。

原始多道程序设计

多道程序设计（Multiprogramming）允许内存中同时存在多个进程，通过上下文切换实现分时操作系统。

• 地址重定位：编译后的程序地址需要是可重定位的（relocatable）。例如，一个符号的地址不再是绝对地址，而是相对于模块起始的偏移量（如「模块基址 + 14 字节」）。
• 静态重定位：使用加载器（Loader）或链接器（Linker）在程序加载到内存时，将这些可重定位地址转换为绝对物理地址。这是一种静态重定位（Static Relocation），因为一旦加载，地址就固定了。

缺乏保护的风险

早期的多道程序设计通常缺乏有效的保护机制。一个程序的 bug（如野指针）可能导致其他程序甚至操作系统本身崩溃。程序也未被禁止访问其他进程的内存地址。

早期保护尝试：保护键

IBM System/360 系统采用了一种名为保护键（Protection Key）的机制：

• 内存被划分为固定大小（如 $\pu{2KB}$）的内存块（Block）。
• 每个内存块关联一个（如 4-bit 的）key，存储在特殊的硬件寄存器中。
• 每个进程也关联一个 key。
• 当进程访问某个内存块时，CPU 硬件检查进程的 key 是否与内存块的 key 匹配（或满足特定权限关系）。如果不匹配，则产生异常。

保护键的局限

这种方法需要为每个内存块设置一个 key 寄存器，对于大内存系统，这将需要大量的专用寄存器，不具备可扩展性，因此不现实。

基址和界限寄存器保护

一种更通用且实用的保护方法是使用基址寄存器（Base Register）和界限寄存器（Bound Register/Limit Register）。例如，大型机 Cray-1 就采用了这种机制。

• 硬件支持：CPU 中设置两个特殊的寄存器：
  • 基址寄存器：存储当前运行进程在物理内存中的起始地址（基地址）。
  • 界限寄存器：存储当前运行进程占用的内存空间的大小（界限或长度）。
• 软件支持：
  • 每个进程的进程控制块（Process Control Block, PCB）中保存其独立的 base 和 bound 值。
  • 当发生上下文切换时，操作系统负责将新换入进程的 base 和 bound 值加载到 CPU 的这两个寄存器中。

地址转换与保护流程：

1. 程序产生的地址（逻辑地址或相对地址）首先与界限寄存器的值进行比较。
2. 如果逻辑地址 >= 界限值，说明访问越界，CPU 产生异常（如 segmentation fault），阻止非法访问。
3. 如果逻辑地址 < 界限值，说明访问合法，则物理地址 = 基址寄存器的值 + 逻辑地址。
4. CPU 使用计算出的物理地址访问内存。

一个程序的典型内存布局（如代码段、数据段、堆、栈）在加载时，加载器会找到一块合适的连续物理内存空间，计算出 Base 和 Bound，然后将程序加载进去。

这种方式下，每个进程看到的仍然是物理地址空间的一个片段，但其起始点（由 Base 决定）和大小（由 Bound 决定）受到硬件保护。

使用物理地址的缺点

尽管基址和界限寄存器提供了一定的保护，但应用程序仍然间接或直接地与物理地址打交道，这带来了一些问题：

1. 加载器复杂性：当一个应用加载或卸载时，可能会影响其他应用的加载决策（例如，寻找足够大的连续空闲块），增加了加载器的压力和复杂性。
2. 缺乏隔离性：一个应用可以通过自身的内存地址（即使是逻辑地址，结合已知的加载模式）猜测出其他应用的加载位置，可能导致安全风险。
3. 管理困难：随着程序动态申请和释放内存，物理内存空间容易产生碎片，难以高效管理。

核心问题：是否能让应用程序「看不见」真实的物理地址？

• 「看不见」意味着应用程序对物理地址布局不可知。
• 进程无需关心其他进程占用了哪些物理地址，不受其他进程影响。
• 这能带来更强的隔离性和保护能力。

David Wheeler

All problems in computer science can be solved by another level of indirection.
计算机科学中的所有问题都可以通过增加一个间接层来解决。

但要注意引用的完整后半句：「…except for the problem of too many levels of indirection.」（除了间接层太多的问题。）

虚拟内存抽象

为了解决物理地址直接暴露带来的问题，现代操作系统引入了虚拟内存（Virtual Memory）抽象。

• 核心思想：为每个进程提供一个独立的、私有的、连续的虚拟地址空间（Virtual Address Space, VAS）。
• CPU 支持：需要硬件支持虚拟内存功能，通常通过内存管理单元（Memory Management Unit, MMU）实现。MMU 负责将进程使用的虚拟地址动态转换为物理内存地址。
• 操作系统角色：操作系统负责配置和启用 MMU 的虚拟内存机制，管理虚拟地址到物理地址的映射关系。
• 透明性：所有软件（包括应用程序和部分操作系统代码）均使用虚拟地址（Virtual Address）进行内存访问，它们无法直接访问物理地址。

MMU

MMU 通常集成在 CPU 核心中，它在每次内存访问时自动进行地址翻译。

虚拟/逻辑地址

在虚拟内存抽象下，程序使用的地址称为虚拟地址（Virtual Address, VA）或逻辑地址（Logical Address, LA）。

• 自动翻译：虚拟地址会被 MMU（硬件）自动地、透明地翻译成物理地址。
• 独立地址空间：每个应用程序都拥有自己独立的、从 0 开始的虚拟地址空间。
  • 应用程序「认为」自己独占了整个内存系统（至少是其虚拟地址空间所能表示的范围）。
  • 应用程序不再能直接看到或感知到物理地址的布局。
• 加载简化：应用程序加载时，其内部地址（如代码、数据段的起始地址）可以是固定的虚拟地址（例如，代码段总是从虚拟地址 0x400000 开始），无需像静态重定位那样在加载时为地址增加一个偏移量。

Linux 虚拟地址空间示例

在 Linux 系统中，每个进程都有一个 task_struct 结构体来描述，其中包含一个指向 mm_struct 的指针（mm）。

• mm_struct：描述了进程的整个虚拟地址空间。它包含了如代码段起始（start_code）、栈起始（start_stack）、堆顶（start_brk）等信息，以及一个指向虚拟内存区域（Virtual Memory Area, VMA）链表的指针。
• vm_area_struct：每个 VMA 描述了虚拟地址空间中的一个连续区域（段），例如代码段、数据段、堆、栈、内存映射文件等。它包含了该区域的起止虚拟地址（vm_start, vm_end）、访问权限（vm_flags）、映射的文件（*vm_file）及其在文件中的偏移（vm_pgoff）等。

graph LR
    Process["Process (task_struct)"] -- mm --> AddressSpace["Address Space (mm_struct)"]
    AddressSpace -- 包含多个 --> VMA1["VMA 1 (vm_area_struct)"]
    AddressSpace -- 包含多个 --> VMA2["VMA 2 (vm_area_struct)"]
    AddressSpace -- 包含多个 --> VMA_etc["..."]

    VMA1 -.-> VAS_Segment1[虚拟地址段 1（如代码）]
    VMA2 -.-> VAS_Segment2[虚拟地址段 2（如堆）]

    subgraph VAS [进程虚拟地址空间（0x00...00 - 0xFF...FF）]
        direction TB
        VAS_Segment1
        VAS_Segment2
        VAS_Etc[...]
    end

    style Process fill:#cde, stroke:#333
    style AddressSpace fill:#ced, stroke:#333
    style VMA1 fill:#dec, stroke:#333
    style VMA2 fill:#dec, stroke:#333

• 可以通过查看 /proc/[PID]/maps 文件（其中 [PID] 是进程 ID，self 代表当前进程）来观察一个进程的虚拟地址空间布局及其 VMA 信息。
• 系统调用如 brk（调整堆大小）、mmap（创建新的内存映射）、munmap（解除内存映射）可以用来改变进程虚拟空间的映射和分配。

地址翻译

地址翻译（Address Translation）是将进程的虚拟地址转换为物理内存中对应物理地址的过程。

• 可以看作一个函数 $f: \langle \text{pid}, \text{virtual\_address} \rangle \mapsto \text{physical\_address}$。
  • pid (Process ID) 用于区分不同进程的虚拟地址空间，因为不同进程的相同虚拟地址通常会映射到不同的物理地址。
  • 如果翻译失败（如权限不足、虚拟地址未映射），MMU 会产生一个异常（如 Page Fault），交由操作系统处理。

虚拟内存和地址翻译机制可以很自然地提供以下关键功能：

1. 保护：
   • 通过为不同进程的虚拟地址映射到物理内存中不相交的区域，实现进程间的内存隔离。即，进程 $P_1$ 的映射函数 $f_1$ 的值域与进程 $P_2$ 的映射函数 $f_2$ 的值域不重叠。
   • 
2. 重定位：
   • 进程在物理内存中的位置可以动态改变，而其使用的虚拟地址保持不变。MMU 负责更新映射关系。这是动态重定位（Dynamic Relocation），因为它发生在运行时，而不是编译或加载时。
   • 例如，操作系统可以将一个进程从物理内存的一处移动到另一处（如为了内存整理），只需修改其地址映射，进程本身无需感知。
   • 
3. 数据共享：
   • 可以将不同进程的不同虚拟地址（或相同虚拟地址）映射到同一个物理内存区域。
   • 常用于共享库（如 libc.so），多个进程可以共享同一份库代码的物理内存副本，节省内存。也用于进程间通信（共享内存段）。
   • 
4. 连续空间假象：
   • 进程的虚拟地址空间是连续的，这使得编程模型更简单（例如，数组、栈可以方便地认为是连续分配的）。
   • 实际上，这些连续的虚拟地址可以被映射到物理内存中不连续的、分散的物理块上。这有助于更有效地利用碎片化的物理内存。
   • 

连续内存分配

在引入复杂的虚拟内存机制之前，或在某些特定场景下（如操作系统内核自身的部分内存管理），可能会使用连续内存分配。

• 基本思想：为每个进程（或内存请求）分配一个连续的物理内存块。
• 保护：仍然可以使用基址和界限寄存器来隔离不同进程的地址空间，以及保护操作系统内核不受用户进程干扰。
  • 虚拟地址（此时可以认为是进程内的逻辑地址）首先检查是否小于界限寄存器值。
  • 若是，则物理地址 = 基址寄存器值 + 虚拟地址。
  • 若否，则产生异常。

分区策略

当多个进程需要加载到内存时，物理内存需要被分割成多个分区。

1. 固定分区：

   • 物理内存预先被划分为若干个大小固定的区域（分区）。
   • 分区大小可以相同，也可以不同。
   • 当一个进程请求内存时，系统从空闲分区中选择一个足够大的分配给它。
   • 优点：实现简单，分配和回收效率高。
   • 缺点:
     • 内部碎片：如果分配给进程的分区大于进程实际需要的内存，分区内多余的部分就无法被其他进程使用，造成浪费。
     • 进程大小限制：如果进程所需空间大于任何可用分区的最大值，则无法加载。
     • 并发进程数限制：可同时放入内存的进程数受限于分区数量。
   • 

2. 可变分区：

   • 不预先划分分区，而是根据进程的实际需求动态地从一大块空闲内存中分配相应大小的连续空间。
   • 操作系统需要维护一个空闲内存块的列表（或集合）。初始时，整个可用内存是一个大的空闲块。
   • 分配：当进程请求内存时，操作系统查找一个足够大的空闲块。如果找到的空闲块大于请求大小，则将其分割成两部分：一部分分配给进程，另一部分变回一个较小的空闲块。
   • 回收：当进程终止释放内存时，其占用的分区变为空闲块。如果这个新的空闲块与一个或多个相邻的空闲块接壤，它们会被合并成一个更大的空闲块，以减少碎片。
   • 
   • 进程增长：由于多数进程在运行时内存需求可能增长（如堆扩展），加载时通常会预分配一些额外内存作为「增长空间」。
   • 空间耗尽处理：如果进程分配的区域用完：
     • 可能被移动（重定位）到一个更大的空闲区域。
     • 可能被交换到磁盘，腾出物理内存，直到有足够大的空洞形成后再换回。
     • 可能被操作系统直接终止（如 Linux 的 OOM Killer - Out Of Memory Killer）。
   • 

碎片问题

碎片（Fragmentation）是指内存中存在未被利用的空间，但这些空间因为太小或不连续而无法满足新的分配请求。

• 内部碎片：
  • 发生在已分配给进程的内存区域内部。
  • 原因是分配的内存块大于进程实际请求或使用的量（例如，固定分区分配，或为了对齐、管理方便而分配稍大的块）。
  • 这部分多余空间属于该进程，但未被其使用，也不能分配给其他进程。
• 外部碎片：
  • 发生在已分配内存区域之间。
  • 表现为总的空闲内存足够满足某个请求，但这些空闲内存是不连续的小块（空洞），没有一个单独的空闲块足够大。
  • 通常是由于进程的不断加载、释放和动态分配造成的。

碎片图示

物理内存: [ OS | P1 (10M) | Free(2M) | P2 (5M) | Free(3M) | P3 (8M) ]

• 假设 P1 实际只用了 8M，则 P1 内部有 2M 内部碎片。
• Free(2M) 和 Free(3M) 是外部碎片。如果此时有个请求需要 4M，虽然总空闲有 5M，但无法满足。

处理外部碎片——紧缩（Compaction）：

• 移动内存中的进程，将所有已分配的区域挪到一端，从而将所有小的空闲块合并成一个大的连续空闲块。
• 代价高昂：需要暂停进程，复制大量内存内容，并更新进程的基址寄存器（如果是动态重定位）。
• 通常只在系统内存严重不足，且其他方法无效时作为最后手段（属于内存分配的慢路径 slow path）。

空闲内存管理

为了实现动态可变分区分配，操作系统需要跟踪哪些内存区域是已分配的，哪些是空闲的（空洞）。

1. 位图（Bitmap/Bit Vector）：
   • 将物理内存划分为固定大小的分配单元（如几字节到几千字节）。
   • 用一个位图，其中每一位对应一个分配单元。
   • 例如，位为 0 表示单元空闲，位为 1 表示单元已占用（或反之）。
   • 分配 $k$ 个单元的进程时，需要搜索位图中 $k$ 个连续的 0 位。
   • 优点：简单。
   • 缺点：搜索连续位可能较慢；选择合适的分配单元大小是个权衡。
   • 
2. 空闲内存链表（Free List）：
   • 将所有空闲的内存块链接成一个链表。每个节点记录空闲块的起始地址和长度。
   • 分配：遍历链表，找到一个足够大的空闲块。如果该块大于请求大小，则将其分割，一部分分配，剩余部分更新大小后仍留在链表中（或重新插入）。
   • 回收：进程释放内存时，将其变成一个空闲块。检查其前后是否也是空闲块（需要链表按地址有序或有额外信息），如果是则进行合并（coalescing）以形成更大的空闲块，然后将新块（或合并后的块）插入/更新到空闲链表中。
   • 
   • 元数据：为了能正确 free(ptr)，需要知道 ptr 指向的已分配区域的大小。这通常通过在每次 malloc 时多分配一点空间来存储元信息（如大小、magic number 用于校验）来实现，ptr 指向用户可用空间，元信息在其之前。
   • 

基本分配策略（针对空闲链表）

当空闲链表中有多个空闲块都能满足请求时，选择哪一个？

• Best-fit（最佳适应）：选择大小最接近且不小于请求大小的空闲块。
  • 目标：尽可能物尽其用，减少分割后产生过大的剩余空闲块。
  • 缺点：需要遍历整个列表（除非特殊组织），容易产生大量微小且难以利用的外部碎片。
• Worst-fit（最差适应）：选择最大的空闲块。
  • 目标：分割后剩余的空闲块也尽可能大，希望能满足后续的大请求。
  • 缺点：同样需要遍历整个列表，可能过早消耗掉大空闲块，导致后续大请求无法满足。
• First-fit（首次适应）：从链表头开始搜索，选择第一个找到的足够大的空闲块。
  • 优点：搜索开销相对较小。
  • 缺点：可能在链表前端留下较多小碎片。
• Next-fit（下次适应）：从上次查找结束的位置开始搜索（维护一个「上次适配位置」的指针），找到第一个足够大的空闲块。
  • 目标：使搜索更均匀地分布在整个链表中，避免 First-fit 总是从头开始。
  • 性能通常介于 First-fit 和 Best-fit 之间。

实际 Workload

不同策略在不同 workload 下性能各异。例如，Mimalloc: free list sharding in action (APLAS'19) 等研究探讨了现实中的分配器行为。First-fit 和 Best-fit 在速度和碎片化方面通常表现较好。

性能问题与改进：

• 简单链表搜索复杂度为 $O(n)$。
• 可以使用更高级的数据结构（如红黑树，按空闲块大小排序）来加速查找（如 $O(\log n)$），但合并操作可能更复杂。
• 合并效率：为了高效合并，空闲链表通常按地址排序。释放内存时，需要扫描链表找到正确位置进行插入和合并。

伙伴系统

伙伴系统（Buddy System）是一种用于分配和回收物理上连续的、固定大小（通常是页面倍数）内存块的算法，常用于管理较大粒度的内存。

• 核心思想：内存从一个大的、2 的幂次大小的块开始。所有可分配的块的大小都是 2 的幂（例如，$\pu{4KB}, \pu{8KB}, \dots, \pu{256KB}$）。
• 分配：
  1. 当请求大小为 $s$ 时，向上舍入到最接近的 2 的幂 $2^k$ (即 $2^{k-1} < s \le 2^k$)。
  2. 系统查找大小为 $2^k$ 的空闲块。
  3. 如果没有 $2^k$ 的空闲块，则查找更大的空闲块 $2^{k+m}$。
  4. 将 $2^{k+m}$ 的块递归地对半分割，直到得到一个 $2^k$ 的块。每次分割产生两个大小相等的「伙伴」（buddy）块。一个伙伴用于下一轮分割或分配，另一个伙伴加入对应大小的空闲链表。
• 回收：
  1. 当一个大小为 $2^k$ 的块被释放时，系统检查其「伙伴」块是否也空闲。
  2. 伙伴地址计算：伙伴块的地址很容易计算。如果一个块的地址是 addr，大小是 size，则其伙伴的地址是 addr XOR size。这是因为伙伴在地址空间中是对齐的，并且它们在伙伴树的同一层，地址仅在决定其左右位置的那一位上不同。
     • 例如，大小为 $2^k$ 的块，其地址的低 $k$ 位为 0。一个 $2^5$ 大小的块地址如 xxx...xx00000。分割成两个 $2^4$ 的伙伴，地址分别为 xxx...xx00000 和 xxx...xx10000。
  3. 如果伙伴也空闲，则将两者合并成一个 $2^{k+1}$ 的块。这个合并过程递归向上进行，直到伙伴不空闲或已合并到最大块。

伙伴系统分配

假设初始有 $\pu{256KB}$ 空闲块，请求 $\pu{21KB}$：

1. $\pu{21KB}$ 向上取整为 $\pu{32KB}$。
2. $\pu{256KB}$ 分割为两个 $\pu{128KB}$ 的伙伴（$A_L, A_R$）。$A_R$ 加入 $\pu{128KB}$ 空闲链表。
3. $A_L$（$\pu{128KB}$）分割为两个 $\pu{64KB}$ 的伙伴（$B_L, B_R$）。$B_R$ 加入 $\pu{64KB}$ 空闲链表。
4. $B_L$（$\pu{64KB}$）分割为两个 $\pu{32KB}$ 的伙伴（$C_L, C_R$）。$C_R$ 加入 $\pu{32KB}$ 空闲链表。
5. $C_L$（$\pu{32KB}$）分配给请求。

• 优点：合并效率高，因为伙伴地址易于计算。
• 缺点：
  • 内部碎片：由于只能分配 2 的幂大小的块，如果请求不是 2 的幂，会产生内部碎片。例如，请求 $\pu{21KB}$ 分配了 $\pu{32KB}$，则有 $\pu{11KB}$ 内部碎片（这部分内存属于该分配，但未被使用，也不能给别人）。
  • Linux 内核使用伙伴系统分配「大」粒度的连续物理页面（通常最小单位是 $\pu{4KB}$ 物理页）。

Slab 分配器

操作系统内核中经常需要频繁分配和回收许多大小固定且较小（几十到几百字节）的数据结构对象（如 task_struct, inode 等）。

• 如果用伙伴系统分配这些小对象，会产生大量内部碎片。
• 观察：系统频繁分配的对象大小相对较小且固定。小对象分配/回收的可伸缩性是系统内存分配的主要瓶颈。

Slab 分配器是一种针对这类小对象的快速分配策略。

• 目标：快速分配小内存对象，减少内部碎片，利用对象初始化缓存。
• 历史：Jeff Bonwick 在 Solaris 2.4 中首创 SLAB。Christoph Lameter 在 Linux 中优化为 SLUB（Linux 2.6.23+ 默认）。
• 机制：
  1. Slab 分配器从伙伴系统获取大块连续内存（称为一个 slab）。
  2. 每个 slab 被进一步细分成多个大小固定的小块内存对象（slots）。一个 slab 只包含相同大小的对象。
  3. 块大小通常是 $2^n$ 字节（如 $3 \le n \le 12$），也可以支持一些频繁使用的特定大小（如 $\pu{198B}$）以减少内部碎片。
  4. 为每种固定大小的对象维护一个或多个 cache（资源池）。分配请求时，采用 best-fit 策略找到最合适的 cache。
  5. 每个 cache 内部维护三类 slab 链表：
     • full：所有对象都已分配的 slab。
     • partial：部分对象已分配，部分空闲的 slab。
     • empty（或 current）：所有对象都空闲的 slab（或当前优先分配的 slab）。
  6. 分配：
     • Fast path（通常 per-CPU）：尝试从当前 CPU 的 current slab（或 partial slab）中获取一个空闲对象。这非常快，且无锁竞争。
     • Slow path：如果 per-CPU cache 中没有，则从全局的 partial 链表中获取一个 slab 作为当前 slab。如果全局 partial 也空，则从 empty 链表获取，或向伙伴系统申请新的 slab 填充 empty 链表，然后分割成对象。
  7. 回收：释放对象时，将其归还到其所属的 slab。
     • 如果 slab 从 full 变为 partial，则移到 partial 链表。
     • 如果 slab 从 partial 变为 empty，则移到 empty 链表。
     • 如果 empty 链表中的 slab 过多，可以将其归还给伙伴系统。

Linux Slab 信息

Linux 中所有 Slab（或 Slub）信息记录在 /proc/slabinfo 文件中。kmalloc 是内核运行时申请通用内存的主要接口，它背后就是一系列不同大小的 kmalloc slab cache（例如，从 $\pu{8B}$ 到 $\pu{8KB}$）。

连续内存分配的问题总结

如果直接将连续内存块分配给整个进程（包含其所有逻辑段如栈、堆、代码等）：

1. 内部碎片：进程的虚拟地址空间中，栈和堆之间的巨大空隙如果也包含在分配的连续物理块内，则这部分物理内存会被浪费。
2. 无法共享：难以实现内存共享（如共享库代码 glibc），因为每个进程的整个映像是独立分配的。
3. 保护粗糙：保护机制通常是针对整个分配块的（如基址/界限），难以对进程内部的不同逻辑部分（如只读代码段、可写数据段）实施精细化的保护。

这些问题促使了更高级的内存管理方案，如分段和分页。

分段

分段（Segmentation）是一种内存管理方案，它从用户（或编译器）的视角出发，将程序视为一组具有逻辑意义的段（segments）。

• 逻辑单元：每个段是一个逻辑上独立的、连续的虚拟内存区域，对应程序的一个部分，如：
  • 代码段
  • 数据段
  • 堆段
  • 栈段
  • 符号表等
• 分配单位：内存以这些逻辑段为单位进行分配和管理。
• 独立映射：每个段独立地映射到物理内存中的一块连续地址空间。
  • 这些物理块在内存中可以不相邻，顺序也可以任意。
  • 虚拟地址空间中未使用的部分（如堆和栈之间的空隙）不需要映射，从而可以消除这类内部碎片。
  • 不同的段可以独立增长或缩减。

分段底层机制

• 虚拟地址结构：虚拟地址被分为两部分：⟨segment_number, offset⟩
  • segment_number：段号，用于索引段表。
  • offset：段内偏移，指示在段内的具体位置。
• 段表：每个进程都有一个段表。MMU 使用段表进行地址翻译。段表的每一项描述一个段，包含：
  • 段基址：该段在物理内存中的起始地址。
  • 段界限：该段的大小（长度）。
  • 保护位：如读/写/执行权限。
  • 其他控制位。
• 段表基址寄存器（Segment Table Base Register, STBR）：CPU 中的一个寄存器，指向当前进程段表的起始物理地址。
• 地址翻译流程：
  1. 从虚拟地址中提取 segment_number 和 offset。
  2. 使用 segment_number 作为索引，访问段表（地址为 STBR + segment_number * entry_size）获取对应段的描述符。
  3. 检查 offset 是否小于段描述符中的 Segment Bound。
     • 如果 offset >= Segment Bound，则发生段错误（越界访问），产生异常。
     • 如果 offset < Segment Bound，则访问合法。
  4. 物理地址 = Segment Base + offset。

分段的特性

• 共享：
  • 多个进程的段表项可以指向同一个物理段（相同的基址和界限），从而实现段的共享（如共享代码库）。
  • 段表中的保护位可以控制共享段的访问权限。
  • 每个进程仍然认为它在访问自己的私有内存（虚拟地址不同或段号不同），具有透明性。
• OS 支持：
  • 上下文切换时，需要保存和恢复 STBR（或整个段表内容，取决于实现）。
  • 段增长或缩小时，操作系统需要更新对应段表项的界限，并可能需要重新分配/回收物理内存。
  • 创建新地址空间时，操作系统为其段在物理内存中寻找空间，并建立段表。
  • 由于段的长度各不相同，物理内存的分配和回收是一个动态内存分配问题，需要处理分割和合并，类似于可变分区分配。

分段机制的问题

1. 外部碎片：虽然段内是连续的，消除了因固定大小分配单元导致的内部碎片，但由于段大小可变且动态分配，物理内存中段与段之间仍会产生外部碎片。随着时间推移，内存可能变得高度碎片化。
2. 大而稀疏的段：如果一个段很大（如一个巨大的堆），但实际只使用了其中一小部分且分布稀疏，那么整个大段仍需分配连续的物理内存，造成浪费。
3. 不匹配的使用模型：如果应用程序的内存使用模式与预设的段（如单一堆段）不完全匹配（例如，程序内部有多个独立的逻辑数据区），分段机制可能不够灵活。

分页

分页（Paging）是另一种主流的内存管理方案，它将物理内存和虚拟内存都划分为大小固定的、较小的块。

• 物理页帧（Physical Page Frame/Frame）：物理内存被划分为一系列连续的、等长的块，称为页帧。
• 虚拟页（Virtual Page/Page）：进程的虚拟地址空间也被划分为与物理页帧大小相同的块，称为虚拟页。
• 大小：页/页帧的大小通常是 2 的幂，例如 $\pu{4KB}$（即 $2^{12}$ 字节）是常见的大小。
• 映射：任意一个虚拟页可以映射到任意一个物理页帧。
  • 这种映射非常灵活，虚拟上连续的页可以映射到物理上不连续的页帧。
  • 由于分配和映射都以页为单位，不存在外部碎片。

分页机制

• 虚拟地址结构：虚拟地址被分为两部分：⟨Virtual Page Number (VPN), Page Offset⟩
  • VPN：虚拟页号，用于索引页表。
  • Page Offset：页内偏移，指示在页内的具体位置。其位数决定了页的大小（例如，12 位偏移对应 $2^{12} = \pu{4KB}$ 的页）。
  • 
• 页表（Page Table, PT）：每个进程都有一个页表。MMU 使用页表进行地址翻译。
  • 页表是一个数组，其索引是 VPN。
  • 每个页表项（Page Table Entry, PTE）存储一个虚拟页到物理页帧的映射信息。
• PTE 内容：
  • 物理页帧号（Physical Page Frame Number, PFN/Physical Page Number, PPN）：指示该虚拟页映射到的物理页帧的基地址（通常是 PFN，物理地址 = PFN << PageSizeBits）。
  • 控制位（Control Bits）：
    • 有效位（Valid bit/Present bit）：
      • Valid bit：指示该 PTE 是否有效（即该虚拟页是否被分配和映射）。用于支持稀疏地址空间（虚拟地址空间中大段未使用的区域无需为其分配 PTE 或物理页帧）。
      • Present bit：指示该页当前是否在物理内存中。如果不在（例如，已被交换到磁盘），访问会触发缺页异常。
    • 保护位（Protection bits）：定义对该页的允许操作，如读（R）、写（W）、执行（X）。
    • 引用位（Reference bit/Accessed bit, A）：由硬件设置，当页被访问（读或写）时置位。用于页替换算法（如 LRU 近似）。
    • 脏位（Dirty bit/Modified bit, D）：由硬件设置，当页被写入时置位。表示页内容自载入内存后已被修改，如果需要换出，必须先写回磁盘。
• 页表基址寄存器（Page Table Base Register, PTBR/CR3 in x86）：CPU 中的一个寄存器，指向当前进程页表的起始物理地址。
• 地址翻译流程（单级页表）：
  1. 从虚拟地址中提取 VPN 和 Offset。
  2. 计算 PTE 在页表中的地址：PTE_address = PTBR + VPN * size_of_PTE。
  3. 从内存中读取该 PTE。
  4. 检查 PTE 中的控制位（如 Valid, Present, Protection）。若无效或权限不足，产生异常。
  5. 从 PTE 中提取 PFN。
  6. 物理地址 = (PFN << PageSizeBits) + Offset。

页表使能（Enabling Paging）：

• CPU 启动时通常默认进入物理寻址模式。
• 系统软件（如操作系统内核）在初始化阶段会设置好页表结构，并通过配置特定的控制寄存器（如 x86-64 架构中的 CR0 寄存器的 PG 位置 1）来使能分页机制，此后 CPU 进入虚拟寻址模式。

x86 PTE 示例（简化）：

• P (Present): 页是否在内存中。
• R/W (Read/Write): 读写权限。
• U/S (User/Supervisor): 用户模式/内核模式访问权限。
• A (Accessed): 引用位。
• D (Dirty): 脏位。
• PWT (Page Write-Through), PCD (Page Cache Disable), PAT (Page Attribute Table), G (Global): 缓存相关控制位。

分页的特性

• 共享：
  • 不同进程的页表中的不同 PTE 可以指向同一个物理页帧（PFN 相同）。
  • 每个 PTE 中可以有独立的保护位，实现灵活的共享权限控制。
  • 
• 写时复制（Copy-on-Write, COW）：
  • 一种优化技术，常用于 fork() 系统调用创建子进程。
  • fork() 时，父子进程初始共享所有物理页面，但其对应的 PTE 都被标记为只读。
  • 当父进程或子进程尝试写入某个共享页面时，会触发一个保护性页错误。
  • 操作系统捕获此错误，为尝试写入的进程复制该页面的一个私有副本，修改其 PTE 指向新副本，并将新副本的权限设为可写。原先的共享页面（对另一个进程而言）可能仍保持只读或根据需要调整。
  • 这样，只有在实际发生写入时才进行复制，避免了 fork() 时不必要的全内存复制。
  • 

单级页表的问题

如果使用简单的线性页表（一个大数组）：

• 页表大小：页表本身可能非常巨大，占用大量物理内存。
  • 32 位地址空间：页大小 $\pu{4KB}$ ($2^{12}$ B)，PTE 大小 $\pu{4B}$。
    • 虚拟地址空间 $2^{32}$ B。
    • VPN 位数 = $32 - 12 = 20$ 位。
    • 页表项数量 = $2^{20}$。
    • 页表大小 = $2^{20} \times \pu{4B} = 2^{22}\text{B} = \pu{4MB}$。
    • 这仅仅是一个进程的页表大小！
  • 64 位地址空间：页大小 $\pu{4KB}$ ($2^{12}$ B)，PTE 大小 $\pu{8B}$。
    • VPN 位数 = $64 - 12 = 52$ 位。
    • 页表项数量 = $2^{52}$。
    • 页表大小 = $2^{52} \times \pu{8B} = 2^{55}\text{B} = \pu{32PB}$。这显然不现实。

多级页表

为了解决单级页表过大的问题，引入了多级页表（Multi-level Page Table）。

• 思想：将页表本身也进行分页。外层页表（称为页目录）的条目指向内层页表（页表页）的物理地址，而不是直接指向数据页帧。
• 空间节省：如果虚拟地址空间中有一大段连续区域未被使用，则外层页目录中对应的条目可以为空（或标记为无效），那么相应的内层页表页就不需要分配物理内存。实际应用的虚拟地址空间通常是稀疏的。
• 结构（以二级页表为例）：
  • 虚拟地址分为三部分：⟨Page Directory Index (PDI), Page Table Index (PTI), Offset⟩。
  • PTBR 指向页目录。
  • PDI 索引页目录，找到页目录项（Page Directory Entry, PDE）。PDE 指向一个页表页的物理地址。
  • PTI 索引该页表页，找到 PTE。PTE 指向目标数据页帧的物理地址。
  • Offset 是数据页帧内的偏移。
• 页表页：每级页表（页目录、页表页）本身也占用一个物理页帧。例如，$\pu{4KB}$ 页大小，$\pu{8B}$ PTE，则一个页表页可以存放 $4096/8 = 512$ 个 PTE。
• 级数：可以有二级、三级、四级（如 x86-64）甚至更多级的页表。级数越多，潜在的空间节省越大，但地址翻译时的内存访问次数也越多。

倒排页表

倒排页表（Inverted Page Table, IPT）是另一种页表组织方式。

• 动机：虚拟页的数量可能远大于物理页帧的数量，尤其是在 64 位系统中。为每个虚拟页维护 PTE 可能仍然浪费。
• 结构：
  • 全局只有一个倒排页表。
  • 表中的每一项对应一个物理页帧，而不是虚拟页。
  • 每项存储：
    • 占用该物理页帧的进程 ID (Pid)。
    • 该进程的哪个虚拟页（VPN）映射到此物理页帧。
    • 其他控制信息。
• 地址翻译：
  1. 当进程访问虚拟地址 ⟨VPN, Offset⟩ 时，系统需要在 IPT 中搜索 ⟨Pid, VPN⟩ 组合。
  2. 如果找到匹配项，其在 IPT 中的索引 $i$ 即为 PFN（或与 PFN 相关）。物理地址 = (i << PageSizeBits) + Offset。
  3. 如果未找到，则表示该虚拟页未在内存中（缺页）。
• 查找加速：线性搜索 IPT 会非常慢。通常使用哈希表来加速查找，以 ⟨Pid, VPN⟩ 作为键。
• 优点：页表大小与物理内存大小成正比，而不是与虚拟地址空间总大小成正比，显著节省内存。
• 缺点：
  • 查找可能仍比直接索引慢（哈希冲突）。
  • 实现共享较为困难，因为一个物理页帧在 IPT 中只有一个条目，难以表示它被多个 ⟨Pid, VPN⟩ 对共享。
  • 页表通常不具备良好的缓存局部性。

段页式管理

某些系统（如早期 Intel x86 保护模式）结合了分段和分页机制。

• 地址翻译：虚拟地址首先经过分段单元处理，得到一个线性地址（Linear Address）。然后，这个线性地址再经过分页单元处理，得到最终的物理地址。
  • Virtual Address -> [Segmentation Unit] -> Linear Address -> [Paging Unit] -> Physical Address
• Segment Map(Segment Table)：将 ⟨Seg #, Seg_Offset⟩ 映射为线性地址。段描述符包含段基址（线性空间中的）、界限、权限。
• Page Table：将线性地址（看作 ⟨VPN_linear, Offset_linear⟩）映射为物理地址。
• 优点：结合了分段的逻辑划分和分页的物理内存管理灵活性。
• 缺点：地址翻译更复杂，开销更大。现代通用操作系统（如 Linux, Windows）主要采用纯分页模型（可能用段来实现非常粗粒度的隔离，如内核/用户空间，但主要地址管理靠分页）。

地址翻译方案比较

方法	优点	缺点
分段	快速上下文切换（段映射信息可部分由 CPU 维护），符合逻辑结构	外部碎片
单级页表	无外部碎片，分配快速且易于管理	页表规模可能非常巨大；仍有少量内部碎片（页内最后部分若未使用）
多级页表	页表大小与实际使用的虚拟页面数量相关，分配灵活	每次地址翻译涉及多次内存访问（性能开销）；仍有少量内部碎片
倒排页表	页表大小与物理内存页面数量相关，节省空间	需要复杂的哈希函数查找，页表缓存局部性差，共享实现复杂

（多级）页表并非完美

• 多级页表是典型的用时间换空间的设计：
  • 优点：显著减小了页表本身所占用的物理内存空间。
  • 缺点：增加了地址翻译时的内存访问次数。即使是单级页表，一次逻辑内存访问也需要两次物理内存访问（一次读 PTE，一次读数据）。多级页表则需要更多次（每级一次）。
• 权衡（tradeoff）是计算机科学中经典而永恒的话题。

如何降低地址翻译的开销？使用缓存。

地址转换旁路缓冲（TLB）

地址转换旁路缓冲（Translation Lookaside Buffer, TLB），也称「快表」，是一种特殊的、小型的、快速的硬件缓存，用于加速虚拟地址到物理地址的翻译过程。

• 动机：利用局部性原理。
  • 时间局部性：如果一个内存位置（或其 PTE）最近被访问过，那么它在不久的将来很可能再次被访问。
  • 空间局部性：如果一个内存位置被访问过，那么其附近的内存位置（可能在同一页或相邻页）在不久的将来也很可能被访问。
• 功能：TLB 缓存最近使用过的 ⟨VPN, PFN⟩ 及相关控制位的映射关系。它通常位于 MMU 内部。
• 结构：TLB 是一个全相联缓存或组相联缓存。
  • 全相联意味着硬件可以并行搜索所有 TLB 条目，以查看请求的 VPN 是否存在匹配。
• TLB 条目内容（典型）：
  • VPN (Virtual Page Number)
  • PFN (Physical Frame Number)
  • Valid bit：TLB 条目是否有效，不同于 PTE 的 Valid/Present
  • Protection bits (R/W/X)
  • Dirty bit (D)
  • ASID (Address Space Identifier)：可选，用于多进程环境下的 TLB 一致性。
  • 

地址翻译流程（带 TLB）：

1. CPU 产生虚拟地址，提取 VPN。
2. TLB 查找：硬件并行查找 TLB 中是否有匹配 VPN 的条目。
   • TLB Hit（命中）：如果找到匹配且有效的条目，直接从中获取 PFN 和权限位。进行权限检查。若通过，则计算物理地址 (PFN << PageSizeBits) + Offset，访问内存。无需访问页表。
   • TLB Miss（未命中）：如果 TLB 中没有匹配条目。
3. 页表查找：
   • 硬件（或软件，取决于架构）遍历内存中的页表（可能多级），找到对应的 PTE。
   • 如果 PTE 有效且权限通过，则将 ⟨VPN, PFN, ...⟩ 信息加载到 TLB 的一个条目中（可能需要替换现有条目）。然后回到 TLB Hit 的流程。
   • 如果 PTE 无效或权限不足，则产生页错误或保护错误异常。

TLB 大小：TLB 通常很小，包含几十到几千个条目（如 64 到 1024 个）。必须高效利用，存储最可能被访问的地址翻译。某些条目可以被「固定」（pinned/wired down），永久保留在 TLB 中，用于频繁访问的关键映射（如操作系统内核代码）。

有效访问时间（EAT）

设：

• $\alpha$：TLB 命中率（Hit Ratio）
• $\varepsilon$：TLB 查找时间
• $t$：单次物理内存访问时间
• 假设单级页表，TLB Miss 时需要一次额外内存访问读 PTE。

$$\begin{aligned} \text{EAT} &= \text{TLB 命中开销} \times \alpha + \text{TLB 未命中开销} \times (1 - \alpha)\\ &= (\varepsilon + t) \alpha + (\varepsilon + t_{\text{PTE\_lookup}} + t)(1 - \alpha) \end{aligned}$$

如果 $t_{\text{PTE\_lookup}} = t$（即读 PTE 也是一次内存访问）：

$$\begin{aligned} \text{EAT} &= (\varepsilon + t) \alpha + (\varepsilon + 2t)(1 - \alpha)\\ &= \varepsilon + t + t (1 - \alpha) \end{aligned}$$

EAT 计算

假设 $\varepsilon = \pu{20ns}$（TLB 查找），$t = \pu{100ns}$（内存访问）。

• 如果 $\alpha = 80\% = 0.8$：
  • $\text{EAT} = \pu{140ns}$
  • 相比无 TLB 时的 $\pu{200ns}$（1 次 PTE + 1 次数据），性能提升显著
• 如果 $\alpha = 99\% = 0.99$：
  • $\text{EAT} = \pu{121ns}$。

处理 TLB Miss

• 替换策略：如果 TLB 已满，需要加载新条目时，必须替换一个现有条目。常用策略：
  • 最近最少使用（Least Recently Used, LRU）：替换最长时间未被访问的条目。
  • 随机（Random）：随机选择一个条目替换。
  • 先进先出（FIFO）。
• 谁来处理 TLB Miss？
  • 硬件处理（Hardware-managed TLB，如 x86 等 CISC 架构）：
    • 当 TLB Miss 时，硬件自动执行页表遍历，获取 PTE，并将其插入 TLB。
    • 硬件必须知道页表的内存位置（通过 PTBR）和其确切格式。
    • 优点：速度快，对系统软件透明。
  • 软件处理（Software-managed TLB，如 MIPS 等 RISC 架构）：
    • 当 TLB Miss 时，硬件引发一个特定类型的异常（TLB Miss Fault/TLB Exception）。
    • 操作系统内核中的异常处理程序负责遍历页表，找到 PTE，并使用特殊指令将 PTE 更新到 TLB 中，然后返回到原指令。
    • 优点：更灵活（如可以自定义页表结构、替换策略），硬件设计更简单。
    • 缺点：处理开销比硬件处理大。

TLB 一致性

• 问题：当上下文切换时，旧进程的虚拟地址到物理地址的映射（缓存在 TLB 中的）对新进程是无效的。如果新进程使用了与旧进程相同的虚拟地址，而 TLB 中仍有旧进程的条目，可能导致访问到错误的物理地址。
• 解决方案：
  1. 清空 TLB（Flush TLB）：
     • 在每次上下文切换时，简单地将 TLB 中所有（或非全局）条目的有效位清零。
     • 缺点：简单粗暴，导致新进程开始运行时 TLB Miss 率很高，直到 TLB 重新「预热」。
  2. 带标记的 TLB（Tagged TLB）：
     • 在每个 TLB 条目中增加一个地址空间标识符（Address Space Identifier, ASID）字段。
     • 每个进程被赋予一个唯一的 ASID。CPU 当前运行进程的 ASID 存储在一个特殊寄存器中。
     • TLB 查找时，不仅要匹配 VPN，还要匹配 ASID。
     • 这样，不同进程的 TLB 条目可以共存于 TLB 中，上下文切换时无需清空 TLB（只需更新 CPU 的当前 ASID 寄存器）。
     • ASID 位数有限，可能需要管理和回收。

     • VPN	PFN	Valid	Protection	ASID
       100	205	1	rwx	10
       100	310	1	r-x	17
       …	…	…	…	…

交换

当物理内存不足以容纳所有希望运行的进程时，操作系统需要一种机制来管理内存的分配。交换（Swapping）就是一种这样的技术，它允许操作系统将整个进程暂时从主存（RAM）移到辅助存储（如磁盘），然后在需要时再将其移回主存。

交换

交换是一种内存管理技术，其中一个进程可以被暂时从主内存换出到后备存储（通常是磁盘），然后在需要继续执行时再换回内存。这使得所有进程的总大小可以超过实际物理内存的大小。

工作原理与影响

• 后备存储（Backing Store）：通常是磁盘上的一块足够大、足够快的区域，用于存放被换出的进程的内存映像。
• 就绪队列：系统维护一个就绪队列，其中包含了准备运行的进程。这些进程有些可能在内存中，有些可能在后备存储中。
• 上下文切换成本：如果下一个要调度的进程不在内存中，操作系统就需要：
  1. 选择一个内存中的进程将其换出到后备存储（如果内存已满）。
  2. 将目标进程从后备存储换入内存。
     这个过程涉及大量的磁盘 I/O，因此上下文切换时间会显著增加。例如，一个 $\pu{100MB}$ 的进程，在磁盘传输速率为 $\pu{50MB/s}$ 的情况下，换入或换出就需要 $\pu{2s}$。
• I/O 操作的挑战：如果一个进程正在进行 I/O 操作，其 I/O 缓冲区通常位于其自身的地址空间内。
  • 若此时该进程被换出，其 I/O 操作可能会失败或导致数据丢失。
  • 因此，涉及活动的 I/O 操作的页面（或整个进程，取决于交换的粒度）通常需要被锁定（pinned）在内存中，防止在 I/O 完成前被换出。

现代操作系统中的交换

• 标准交换的式微：将整个进程完整换入换出的「标准交换」在现代通用操作系统（如 Linux、Windows）中已不常用，因为其效率较低。
• 变种形式：更常见的是基于「页」的交换（即按需分页中的页面换出），这更为灵活高效。
• 启用时机：交换功能通常默认是禁用的，或者只在物理内存极度不足（例如，可用内存低于某个阈值）时才启动。一旦内存压力缓解，交换可能会再次被禁用。

移动操作系统中的交换

移动操作系统（如 iOS、Android）通常不支持传统意义上的交换：

• 存储介质限制：它们主要使用闪存（Flash Memory）。
  • 闪存空间相对磁盘较小。
  • 闪存有写入寿命限制，频繁交换会缩短其寿命。
• 替代策略：
  • iOS：要求应用程序在收到内存警告时自愿释放其分配的内存。只读数据（如代码段）可以被丢弃，并在需要时从闪存重新加载。如果应用程序未能充分释放内存，操作系统可能会终止它。
  • Android：在内存不足时，会根据进程的优先级和状态终止应用程序。在终止前，可能会将其状态保存到闪存，以便快速重启。

单个进程超过物理内存的问题

传统的交换技术主要解决多个进程总大小超过物理内存的问题。但如果单个进程本身就比物理内存还要大，交换整个进程是行不通的。

这引出了一个核心思想：并非一个程序的所有部分都需要同时加载到内存中才能运行。例如：

• 错误处理代码段只在出错时执行。
• 为应对最坏情况而分配的超大数组，在通常情况下可能只使用了一小部分。
• 程序可以更快地启动，如果不需要在运行前加载整个程序。

这种「部分内存驻留」的需求，是虚拟内存技术的核心动机之一。

虚拟内存

虚拟内存是一种内存管理技术，它为每个进程提供了一个巨大的、连续的、私有的地址空间，称为虚拟地址空间（Virtual Address Space）。这个虚拟地址空间可以远大于实际的物理内存。

虚拟内存

虚拟内存（Virtual Memory）通过将进程的地址空间划分为多个页面，并仅将当前需要的页面加载到物理内存的页帧中，从而实现了对物理内存的抽象。物理内存此时可以看作是所有进程页面在磁盘上的一个缓存。

核心机制与优势

• 大地址空间幻觉：每个进程都认为自己拥有一个独立的、从 0 开始的大量内存。
• 部分加载：程序不必完全加载到内存中即可运行。只有活动的部分（代码、数据）才需要驻留在物理内存中。
  • 程序不再受物理内存限制：可以运行比物理内存更大的程序。
  • 提高多道程序度：每个程序在运行时占用更少的物理内存，允许更多程序并发执行。
  • 减少 I/O：加载或交换程序到内存中所需的 I/O 更少，程序启动更快。
• 透明的间接层：通过页表实现虚拟地址到物理地址的转换。
  • 灵活的数据放置：程序的页面可以存储在物理内存、磁盘，甚至网络位置。
  • 对用户程序透明：数据位置的变化对用户程序是不可见的。

近乎无限的内存

在现代分布式系统中，进程所需的运行部分甚至可以动态地从网络（如云存储、远程服务器）加载，进一步扩展了「可用内存」的概念。

缺页异常

虚拟内存的关键在于如何处理对不在物理内存中的页面的访问。

• 存在/不存在位（Present/Valid Bit）：页表项（PTE）中有一个位，用于指示对应的页面当前是否在物理内存中。
• 访问流程：
  1. 程序引用一个虚拟地址。
  2. MMU 查找页表。
  3. 如果页面在物理内存中（存在位为 1）：MMU 完成地址转换，访问物理内存。
  4. 如果页面不在物理内存中（存在位为 0）：MMU 触发一个缺页异常。

缺页异常

缺页异常（Page Fault）是一种当程序试图访问其地址空间中一个当前并未被加载到物理内存的页面时，由硬件（MMU）产生并通知操作系统的异常。

操作系统处理缺页异常：

1. 陷入内核：CPU 控制权从用户态转移到内核态。
2. 操作系统定位到发生异常的虚拟地址（例如，在 x86_64 架构中，CR2 寄存器会保存导致缺页的地址，异常号为 #PF (13)）。
3. 检查访问的合法性（例如，权限是否匹配）。
4. 从后备存储（如磁盘）找到该页面。
5. 在物理内存中找到一个空闲的页帧。
   • 如果没有空闲页帧，则需要运行页面置换算法选择一个「牺牲者」页帧，将其内容写回磁盘（如果被修改过），然后使用该页帧。
6. 将所需的页面从磁盘读入选定的空闲页帧。
7. 更新页表项，设置存在位为 1，并填入物理页帧号。
8. 重新执行导致异常的指令。此时，由于页面已在内存中，指令可以成功执行。

下图展示了处理缺页异常的流程：

sequenceDiagram
    participant P as 程序（Load M）
    participant MMU as MMU
    participant OS as 操作系统
    participant Disk as 磁盘
    participant PM as 物理内存
    participant PT as 页表

    P ->> MMU: 1. 引用地址 M
    MMU ->> PT: 查找 M 对应页表项
    PT -->> MMU: 页面不在内存（存在位=0）
    MMU ->> OS: 2. Trap (缺页异常)
    OS ->> Disk: 3. 确认页面在后备存储上
    OS ->> PM: 寻找空闲页帧（或置换）
    OS ->> Disk: 4. 将缺失页面调入内存
    Disk -->> PM: 页面数据传输
    OS ->> PT: 5. 更新页表（设置存在位, 页帧号）
    OS -->> P: 6. 恢复上下文, 重启指令
    P ->> MMU: 再次引用地址 M
    MMU ->> PT: 查找 M 对应页表项
    PT -->> MMU: 页面在内存, 物理地址 P_M
    MMU ->> PM: 访问物理地址 P_M

缺页异常的性能

处理缺页异常涉及多个步骤，其中磁盘 I/O 是最耗时的。

• 主要活动耗时：
  • 服务中断：较快（几百条指令）。
  • 读取页面：非常慢（毫秒级），因为涉及磁盘访问。
  • 恢复进程：较快。
• 缺页错误率（$p$）：进程在内存访问中发生缺页异常的概率（$0 \le p \le 1$）。
• 有效访问时间（Effective Access Time, EAT）：

  $$\text{EAT} = (1-p) \times t_{\text{mem}} + p \times t_{\text{page fault service}}$$

  其中：
  • $t_{\text{mem}}$：内存访问时间（例如 $\pu{200 ns}$）。
  • $t_{\text{page fault service}}$：处理缺页异常的平均时间（例如 $\pu{8 ms} = \pu{8 000 000 ns}$）。

性能关键

即使很小的缺页率也会导致显著的性能下降。因此，保持较低的缺页率是虚拟内存系统高效运行的关键。

缺页异常的其他巧妙用法

除了作为虚拟内存的核心机制外，缺页异常还可以用于实现其他一些高级功能：

1. 写时复制（Copy-On-Write, COW）：
   • 当进程（如通过 fork()）创建副本时，父子进程最初共享相同的物理页面，但这些页面被标记为只读。
   • 当任何一个进程尝试写入共享页面时，会触发一个缺页（保护性）异常。
   • 操作系统捕获此异常，为写入方进程创建一个该页面的私有副本，并修改其页表指向新副本（可写）。父进程（或其他共享者）继续指向原始的只读页面（如果它们也需要写，则重复此过程）。
   • 显著提高了进程创建（尤其是 fork()）的效率，因为避免了不必要的页面复制。
2. 按需零填充（Zero-Filled-on-Demand, ZFOD）：
   • 当进程请求新的内存页（如 bss 段、新的堆/栈页）时，这些页在逻辑上应初始化为零。
   • 操作系统可以将这些虚拟页面都映射到一个全局的、预先清零的物理只读页面（zero page）。
   • 当进程首次读取这些页面时，直接从该共享的 zero page 读取，无需额外开销。
   • 当进程首次写入这些页面时，会触发一个缺页（保护性）异常。
   • 操作系统捕获异常，分配一个新的物理页帧，将其清零，然后将进程的相应虚拟页面映射到这个新的、可写的、私有的清零页帧。
   • 避免了在分配时就立即为大量可能不会被立即使用的页面清零的开销。
3. 内存映射文件（Memory-Mapped Files, MMF）：
   • 通过系统调用（如 POSIX mmap()）可以将一个文件或文件的一部分直接映射到进程的虚拟地址空间。
   • 进程可以像访问内存一样访问文件内容，而无需显式的 read() 或 write() 调用。
   • 读取：当访问映射区域中尚未在内存中的部分时，发生缺页异常。操作系统从磁盘读取相应的文件内容到物理页帧，并更新页表。
   • 写入：对映射区域的写入会使对应页面变为「脏页」。操作系统会在适当时（如页面被换出、文件关闭、显式 msync() 调用）将脏页内容写回磁盘文件。
   • 共享：如果多个进程以共享模式映射同一个文件，它们将共享相同的物理页面，从而实现高效的进程间数据共享。

页面置换

当发生缺页异常且物理内存中没有空闲页帧时，操作系统必须选择一个当前在内存中的页面（牺牲者页面，victim page）将其换出到磁盘，以便为新调入的页面腾出空间。这个过程称为页面置换（Page Replacement）。

何时将页面调入内存？

1. 按需分页（Demand Paging）：
   • 最常见的方法：只在发生缺页异常时才将相应的页面调入内存。
   • 优点：简单，只加载实际需要的页面。
   • 为了提高效率，页面调入通常是异步进行的：缺页异常处理程序启动磁盘 I/O 读取页面，然后阻塞当前进程，并调度其他进程运行。当磁盘 I/O 完成后，通过中断通知操作系统，再唤醒等待的进程。
2. 预取（Prefetching）：
   • 操作系统尝试预测进程将来可能很快会访问哪些页面，并提前将它们调入内存。
   • 预测通常基于历史访问模式或程序的结构。
   • 目标：在进程实际需要这些页面之前就使其可用，从而避免缺页异常。
   • 挑战：预测不准确可能导致调入无用页面，浪费 I/O 带宽和内存。

页面置换的步骤

当一个页面必须被换出时：

1. 选择牺牲者页面：根据页面置换算法选择一个物理页帧。
2. 处理牺牲者页面：
   • 如果该页面是「脏」的（即自上次从磁盘调入后被修改过，通常页表项中有脏位标记），则必须将其内容写回磁盘的相应位置。
   • 如果页面是「干净」的（未被修改），则其内容与磁盘上的副本一致，无需写回。
3. 更新页表：
   • 修改牺牲者页面对应的所有页表项（因为物理页帧可能被多个进程共享，或在同一进程内被多次映射），将其存在位设置为 0（表示不在内存中）。
   • 如果页表项中存储了磁盘地址，确保其正确。
4. 使 TLB 条目无效：从 TLB 中移除与牺牲者页面相关的任何缓存条目。
   • TLB 一致性：在多处理器系统中，必须确保所有处理器的 TLB 中相关的条目都被移除（称为 TLB shootdown）。
5. 调入新页面：将请求的页面从磁盘读入到刚被腾出的（现在是空闲的）页帧中。
6. 更新新页面的页表项：设置其存在位为 1，并记录新的物理页帧号。
7. 重启指令：重新执行导致缺页异常的指令。

锁定页面

某些页面不能被换出，必须始终保留在物理内存中。这些页面被称为锁定的或固定的（locked/pinned）页面。

• 内核代码和关键数据结构：操作系统自身的核心部分通常被锁定在内存中。
• I/O 缓冲区：正在进行 DMA（直接内存访问）操作的 I/O 缓冲区必须被锁定，以防止在传输过程中被换出。
• 优先级问题：需要小心处理，例如，一个低优先级进程换入一个页面，然后一个高优先级进程抢占并需要一个新的页帧，如果低优先级进程的页面被不当换出，可能影响系统。

锁定页面会减少可用于页面置换的页帧数量，因此需要谨慎使用。

页面缓冲

操作系统通常不会等到内存完全耗尽才开始进行页面置换。

• 空闲帧池：维护一个小的空闲物理页帧池（buffer）。当发生缺页异常时，可以立即使用池中的空闲帧，而将牺牲者页面的写回（如果需要）和新页面的调入并行进行。
• 页面守护进程（Page Daemon/Paging Daemon）：
  • 一个后台进程（如 Linux 中的 kswapd）定期运行（通常在系统空闲时或内存压力达到一定程度时）。
  • 低水位标记：如果空闲页帧数量低于此标记，守护进程开始扫描并换出一些页面（通常是根据某种置换算法选择的「不常用」页面）。
  • 高水位标记：守护进程持续换出页面，直到空闲页帧数量达到此标记。
  • 批量传输：一次性换出多个脏页通常比逐个写回更有效，因为可以利用磁盘的批量传输特性。
  • 守护进程通常以较低优先级运行，利用 CPU 空闲时间为未来的内存请求做准备。

页面置换策略/算法

页面置换算法的目标是选择一个牺牲者页面，使得未来的缺页异常率最低。理想情况下，我们希望换出将来最长时间内不会被访问的页面。

First-In-First-Out (FIFO)

• 策略：替换在内存中驻留时间最长的页面（即最早进入内存的页面）。
• 实现：维护一个队列，记录页面进入内存的顺序。
• 优点：简单易实现。
• 缺点：可能换出仍然被频繁使用的「老」页面。
• Belady 异常（Belady's Anomaly）：对于某些页面访问序列，增加分配给进程的物理页帧数反而可能导致缺页次数增加。FIFO 是受此异常影响的算法之一。

Belady 异常

Belady 异常指对于某些页面置换算法和某些页面引用序列，当分配的物理页帧数增加时，缺页故障次数反而可能增加的现象。

如果一个算法具有栈属性（Stack Algorithm Property），则不会发生 Belady 异常。

栈属性意味着：对于任意页面引用序列，具有 $k$ 个页帧时内存中的页面集合总是具有 $k+1$ 个页帧时内存中页面集合的子集。FIFO 不具备栈属性。

Optimal (OPT/MIN)

• 策略：替换将来最长时间内不会被使用的页面。
• 优点：能达到最低的缺页率，是衡量其他算法性能的基准。
• 缺点：无法实现，因为它需要预知未来的页面访问序列。
• 用途：主要用于理论分析和算法评估。

Least Recently Used (LRU)

• 策略：替换过去最长时间内没有被使用过的页面。
• 依据：基于局部性原理，认为最近未被使用的页面在将来短期内也不太可能被使用。
• 性能：通常是 OPT 算法的一个良好近似，且不会有 Belady 异常（具有栈属性）。
• 实现挑战：
  • 计数器：为每个页表项关联一个时间戳计数器。每次内存引用时，硬件将当前时钟值复制到该页面的计数器。替换时，选择计数器值最小的页面。开销极大，因为每次内存访问都需要更新计数器并可能涉及写内存。
  • 栈：维护一个按最近使用顺序排列的页面栈。每次引用页面时，将其移到栈顶。替换时，选择栈底页面。同样，每次内存访问都可能需要更新栈，开销也很大。

近似 LRU 算法（Approximating LRU）

由于精确 LRU 实现开销过高，实际系统中通常采用近似算法。这些算法依赖硬件提供的引用位（Reference Bit, R-bit）和修改位（Modify Bit/Dirty Bit, M-bit）。

1. 附加引用位算法/二次机会算法/时钟算法（Additional Reference Bits Algorithm/Second Chance/Clock Algorithm）

   • 机制：
     • 每个页表项有一个引用位（R），由硬件在页面被访问（读或写）时自动设置为 1。
     • 所有物理页帧被组织成一个循环列表（像钟面），一个指针（「时钟指针」）指向当前检查的候选页面。
   • 替换过程（发生缺页且需要选择牺牲者时）：
     1. 从时钟指针指向的页面开始检查。
     2. 如果其 R 位为 1：将其 R 位清零（给它「第二次机会」），然后将时钟指针前进到下一个页面。
     3. 如果其 R 位为 0：该页面即为牺牲者，将其替换。时钟指针前进。
   • 特性：
     • 如果所有页面的 R 位都为 1，则时钟算法会完整扫描一圈，将所有 R 位置零，最终退化为 FIFO。
     • 比 LRU 实现简单，开销小。
   • 

2. 最近未使用算法（Not Recently Used, NRU）/增强型二次机会

   • 机制：同时使用引用位（R）和修改位（M）。操作系统定期将所有 R 位清零。
   • 页面分类：根据 (R, M) 位的组合将页面分为四类：
     1. (0, 0) 最近未引用，未修改（干净）—— 最佳替换选择
     2. (0, 1) 最近未引用，但已修改（脏）—— 次佳，替换前需写回磁盘
     3. (1, 0) 最近已引用，未修改（干净）—— 可能很快再次使用
     4. (1, 1) 最近已引用，且已修改（脏）—— 最不希望替换
   • 替换过程：随机选择一个属于编号最低的非空类别的页面进行替换。
   • 优点：优先替换未被修改的页面，可以减少磁盘写操作。

抖动

如果一个进程没有获得足够的物理页帧来容纳其当前活跃使用的页面集合（即其工作集），它会频繁地发生缺页异常。

抖动

抖动（Thrashing，也称颠簸）是指一个系统或进程花费过多的时间在页面调入调出（即处理缺页异常），而几乎没有时间执行实际有用的计算工作的状态。此时，CPU 利用率急剧下降，系统吞吐量极低。

• 原因：
  • 进程分配到的页帧数过少，无法容纳其工作集。
  • 例如，一个进程循环访问 4 个页面（0,1,2,3,0,1,2,3,…），但只分配到 3 个页帧。使用 FIFO 或 LRU 算法，每次访问都会导致缺页。
• 调度器的恶化作用：
  1. 进程因频繁缺页而阻塞，等待磁盘 I/O。
  2. CPU 利用率下降。
  3. 操作系统调度器可能认为需要提高多道程序度，于是引入更多进程到内存。
  4. 这使得分配给每个进程的平均页帧数进一步减少。
  5. 缺页率进一步上升，CPU 利用率更低，形成恶性循环。

局部性原理

程序在执行过程中，对内存的访问往往不是完全随机的，而是呈现出局部性特征：

• 时间局部性（Temporal Locality）：如果一个内存位置被访问，那么它在不久的将来很可能被再次访问（例如，循环中的指令、变量）。
• 空间局部性（Spatial Locality）：如果一个内存位置被访问，那么它附近的内存位置在不久的将来也很可能被访问（例如，顺序执行的指令、数组元素）。

一个进程在执行时，会从一个局部性区域（locality）迁移到另一个局部性区域。

工作集模型（Working Set Model）

由 Peter Denning 提出，用于防止抖动。

• 工作集 $\text{WS}(t, \Delta)$：一个进程在时间 $t$ 的工作集是指在过去一段时间窗口 $\Delta$ 内（即时间区间 $[t-\Delta, t]$）该进程所引用到的页面集合。
• 核心思想：
  • 如果一个进程的整个工作集都在物理内存中，那么它在接下来的 $\Delta$ 时间内运行时，发生缺页的概率会很低，直到它迁移到新的执行阶段（新的工作集）。
  • 如果分配给进程的物理内存太小，无法容纳其当前工作集，就会发生抖动。
• All-or-Nothing 策略：
  • 操作系统需要跟踪每个进程的工作集大小。
  • 在调度一个进程运行时，必须确保其整个工作集都能被加载到内存中。如果内存不足，则该进程应被挂起（或部分页面换出），而不是在页帧不足的情况下运行。
  • 这能显著降低缺页率，避免抖动。
• 跟踪工作集 $w(t, \Delta)$：
  • 使用一个定时器中断（工作集时钟），以固定的间隔 $\Delta$（或更小间隔）发生。
  • 中断处理程序扫描所有活动进程的页面：
    • 检查引用位（R）：
      • 如果 R=1（在当前 tick 中被访问）：记录当前时间为「上次使用时间」，并将 R 位清零。该页面属于当前工作集。
      • 如果 R=0（在当前 tick 中未访问）：计算 Age = 当前时间 - 上次使用时间。
        • 如果 Age > $\Delta$，则该页面不再属于当前工作集，可以考虑换出。
  • 注意：访问位（R-bit）的硬件支持是必要的。

帧分配

当采用全局页面置换策略时，操作系统需要决定为每个进程分配多少物理页帧。

本地与全局置换策略

• 本地页面置换：
  • 每个进程从其自身已分配到的页帧集合中选择牺牲者。
  • 优点：一个进程的缺页行为不会直接影响其他进程的页帧。每个进程的性能相对隔离和一致。
  • 缺点：可能导致内存利用不足。某个进程可能拥有多余的页帧却不使用，而其他进程急需页帧却无法获得。
• 全局页面置换：
  • 从所有可换出的物理页帧中（无论属于哪个进程）选择牺牲者。
  • 优点：动态调整各进程的页帧数，系统整体吞吐量通常更高。更灵活，更常用。
  • 缺点：一个行为不佳的进程（例如，工作集巨大或访问模式差）可能会「窃取」其他进程的页帧，影响它们的性能。

帧分配方案

对于全局置换，有多种静态分配页帧的初始思路：

• 平均分配：为每个进程分配相同数量的页帧（$M/N$，其中 $M$ 是总可用页帧数，$N$ 是进程数）。
• 比例分配：根据进程的大小（虚拟内存大小）按比例分配页帧。较大的进程获得更多页帧。
• 优先级分配：高优先级的进程获得更多页帧。

这些静态分配方案难以适应进程不断变化的动态内存需求。

缺页错误频率算法

缺页错误频率算法（Page Fault Frequency, PFF）是一种动态的帧分配策略，它试图将每个进程的缺页率控制在一个预设的合理范围内。

• 监控缺页率：操作系统监控每个进程的缺页率（例如，每秒平均缺页次数）。
• 调整帧分配：
  • 设置一个上限阈值和一个下限阈值。
  • 如果一个进程的缺页率超过上限阈值：说明它分配到的页帧太少，操作系统会为其增加分配的页帧数（如果还有可用页帧，或者从缺页率低于下限的进程那里获取）。
  • 如果一个进程的缺页率低于下限阈值：说明它分配到的页帧可能过多，操作系统可以减少其页帧数，将回收的页帧分配给其他更需要的进程或加入空闲池。

操作系统对分页的支持总结

操作系统在支持分页和虚拟内存方面扮演着多重角色：

1. 进程创建时：
   • 确定程序和数据的大小，创建初始的页表结构。
   • 为页表本身分配内存并初始化。
   • 在磁盘上为该进程分配交换空间（swap area）并初始化。
   • 在进程控制块（PCB）中记录页表和交换空间的相关信息。
2. 进程执行时：
   • 当调度一个新进程运行时，重置 MMU 的状态（如加载该进程的页表基址寄存器）。
   • 上下文切换时，通常需要清除 TLB（除非 TLB 支持标记，如 ASID，可以区分不同进程的条目）。
   • 可选地，在进程开始执行前，预先调入其部分或全部页面（预取）。
   • 页面守护进程（Page Daemon）在后台运行，定期检查内存状态，主动准备待驱逐的页面，维持空闲页帧池。
3. 缺页异常处理时：
   • 确定所需页面的虚拟地址，并在磁盘上定位该页面。
   • 找到一个可用的物理页帧（如果内存已满，则运行页面置换算法选择一个牺牲者页帧并将其换出）。
   • 将所需的页面从磁盘读入选定的物理页帧。
   • 更新页表。
   • 备份并重新执行导致异常的指令。
4. 进程终止时：
   • 释放该进程占用的所有资源：页表、它所使用的物理页帧（除非是共享页面且仍有其他进程在使用）、其在磁盘上的交换空间。
   • 共享的页帧只有在最后一个使用它的进程终止时才能被真正释放。

程序优化与分页

分页和虚拟内存不仅仅是操作系统的问题，程序员的行为和程序的特性也会显著影响其性能。

• 减少工作集大小：程序员可以通过优化算法和数据结构来减小程序的活动工作集。
• 数据结构与局部性：
  • 选择合适的数据结构可以改善局部性。例如，数组通常比链表具有更好的空间局部性，因为其元素在内存中是连续存储的。
  • 访问模式：顺序访问数组元素（如在循环中）通常比随机访问具有更好的局部性，可以更有效地利用缓存和预取机制，减少缺页。
• 编译器和链接器的作用：
  • 编译器可以进行代码优化，例如，将经常一起执行的代码块放置在相近的内存位置，以提高空间局部性。
  • 链接器可以安排代码和数据段在虚拟地址空间中的布局，例如，避免将一个频繁调用的函数或关键数据结构分散到多个页面上。

这些优化措施可以显著减少缺页率，从而提高程序的运行性能。

总结

内存管理是操作系统的核心功能之一，其目标是为进程提供一个易用、高效且安全的内存环境。

• 内存抽象：通过虚拟内存技术，屏蔽了物理内存的局限性（如大小限制、非连续性），为进程提供了「无限」、连续、独享的地址空间。
• 实现机制：核心是地址翻译，这需要硬件（MMU, TLB）和操作系统（页表管理、缺页处理、页面置换）的紧密配合。
• 底层物理内存管理：包括连续分配（早期）、分段、分页等策略。TLB 作为页表项的高速缓存，对性能至关重要。
• 虚拟内存的工程挑战：
  • 页面置换：选择合适的算法在内存不足时换出页面。
  • 工作集管理：理解和管理进程的内存访问模式以避免抖动。
  • 帧分配：合理地为并发进程分配物理内存资源。

通过这些复杂的机制，操作系统能够在有限的物理内存上支持多个大型进程的并发执行，并提供内存保护和共享等高级功能。