内存管理

文档说明

本文档根据《2025-OS-CH-9-物理内存管理clean.pptx》和《2025-OS-CH-10-虚拟内存管理.pptx》总结而成，旨在帮助学习和复习操作系统中的内存管理相关知识。

第九讲：物理内存管理策略

学习目标

• 讨论内存管理的多种方法
• 理解内存分页和分段的概念
• 了解内存硬件的各种组织方法
• 掌握进程内存分配的各种技术
• 详细讨论现代计算机系统的分页机制
• 理解动态链接与共享

1. 内存管理基础

• 程序必须从磁盘加载到内存并放入进程中才能运行。
• 主存储器和寄存器是 CPU 可以直接访问的唯一存储。
• 寄存器访问速度快（一个 CPU 时钟周期或更少），主内存访问可能导致暂停 (stall)。
• 缓存 (Cache) 位于主内存和 CPU 寄存器之间，用于加速访问。
• 内存管理不仅关心访问速度，还需确保操作正确、保护操作系统。这通常通过硬件实现，操作系统不直接干预 CPU 对内存的访问。

2. 内存保护

• 目的：限制进程只能访问其自身的地址空间。
• 实现：通过一对基址寄存器 (Base Register) 和界限地址寄存器 (Limit Register) 定义进程可访问的地址范围。
• CPU 在用户模式下每次内存访问都会检查地址是否在 [基地址, 基地址 + 界限地址) 范围内。
• 加载基址和界限寄存器的指令是特权指令，只能在内核模式下执行。

3. 地址绑定 (Address Binding)

程序中的地址在生命周期的不同阶段有不同表示：

1. 编译时 (Compile time)：
   • 如果内存位置已知，可以生成绝对代码 (Absolute Code)。例如 MS-DOS 的 .COM 程序。
   • 如果起始位置改变，必须重新编译。
   • 符号地址（源代码中）被绑定到可重定位地址。
2. 加载时 (Load time)：
   • 如果编译时内存位置未知，必须生成可重定位代码 (Relocatable Code)。
   • 链接器或加载程序将可重定位地址绑定到绝对地址（物理地址）。
3. 执行时 (Execution time)：
   • 如果进程在执行期间可以从一个内存段移动到另一个内存段，则绑定延迟到运行时。
   • 需要硬件支持地址映射，如基址寄存器和界限寄存器。

用户程序的处理过程

源代码 -> 编译器/汇编器 -> 目标模块 -> 链接器 -> 加载模块 -> 加载器 -> 内存中的进程

4. 逻辑地址空间 vs. 物理地址空间

• 逻辑地址 (Logical Address)：由 CPU 生成，也称为虚拟地址 (Virtual Address)。
• 物理地址 (Physical Address)：内存单元实际看到的地址。
• 编译时和加载时地址绑定：逻辑地址与物理地址相同。
• 执行时地址绑定：逻辑地址与物理地址不同。
• 逻辑地址空间：程序生成的所有逻辑地址的集合。
• 物理地址空间：对应这些逻辑地址的物理地址的集合。

5. 内存管理单元 (MMU)

• 功能：在运行时将虚拟地址映射到物理地址的硬件设备。
• 简单方案 (重定位寄存器)：
  • 基址寄存器也称为重定位寄存器 (Relocation Register)。
  • 用户进程生成的每个逻辑地址在发送到内存前，都会加上重定位寄存器中的值。
  • 例如：重定位寄存器值为 14000，逻辑地址为 346，则物理地址为 14000 + 346 = 14346。
  • 用户程序处理逻辑地址，看不到真实的物理地址。

6. 动态加载 (Dynamic Loading)

• 目的：提高内存利用率。
• 机制：一个程序（或例程）在被调用之前不会被加载到内存中。
• 优点：
  • 更好的内存空间利用率，不加载未使用的例程。
  • 对于处理不经常发生的情况（如错误处理）的大量代码特别有用。
• 实现：通常由程序设计实现，操作系统可提供库支持。

7. 动态链接与共享库 (Dynamic Linking and Shared Libraries)

• 静态链接 (Static Linking)：加载程序将系统库和程序代码组合成单个二进制程序映像。
• 动态链接 (Dynamic Linking)：链接过程延迟到运行时。
  • 使用一小段代码，称为存根 (Stub)，用于定位内存中适当的库例程。
  • 存根将自身替换为库例程的地址并执行。
  • 操作系统检查库例程是否已在进程内存中，若否则加载。
• 优点：
  • 方便库的更新和共享。
  • 多个进程可以共享同一份库代码的物理拷贝。
• 也称为共享库 (Shared Libraries)。
• 可能需要版本控制。

8. 交换 (Swapping)

• 概念：进程可以暂时从内存中交换到备份存储（如磁盘），之后再换回内存继续执行。
• 目的：允许多个进程的总物理地址空间超过真实的物理地址空间，提高多道程序设计的程度。
• 代价：交换操作（磁盘 I/O）非常耗时。
• 触发：通常在内存空闲空间低于某个阈值时启用，常与虚拟内存结合使用。
• 移动系统：通常禁止交换。内存不足时，可能终止进程，或将其状态保存到闪存以便快速恢复。

9. 连续分配 (Contiguous Allocation)

早期内存分配方法，每个进程在内存中占据单个连续区域。

• 内存分区：
  • 操作系统通常位于低地址（包含中断向量表）。
  • 用户进程位于高地址。
• 保护：使用重定位寄存器（基址）和界限寄存器。

9.1 固定分区 (Fixed Partitions)

• 将用户内存空间划分为若干固定大小或不同大小的分区。
• 缺点：
  • 分区数量限制了活动进程数量。
  • 小作业可能无法有效利用大分区空间，产生内部碎片。

9.2 可变分区 (Variable Partitions) / 动态分区

• 分区大小根据进程需求动态调整。
• 内存中会产生多个分散的可用内存块，称为孔 (Hole)。
• 进程到达时，从一个足够大的孔中分配。
• 进程退出时，释放其分区，并可能与相邻空闲分区合并。

• 操作系统维护已分配分区和空闲分区（孔）的信息。

  放置算法 (Placement Algorithms)：

  • 首次适应 (First-fit)：分配第一个足够大的孔。速度快，可能在内存前端产生小碎片。
  • 最佳适应 (Best-fit)：分配最小的、但足够大的孔。需搜索整个列表，易产生许多无法使用的小碎片。
  • 最差适应 (Worst-fit)：分配最大的孔。也需搜索整个列表，试图留下较大的剩余孔。

  放置算法比较

  首次适应通常是最好和最快的。最佳适应性能往往较差。

9.3 碎片 (Fragmentation)

• 外部碎片 (External Fragmentation)：存在足够的总内存空间满足请求，但它们不连续。
  • 例如，有 10KB 和 5KB 的两个孔，但无法满足 12KB 的请求。
  • 50% 规则：首次适应分析表明，给定N个块的分配，大约有0.5N个块由于碎片而丢失（即1/3的内存可能无法使用）。

• 内部碎片 (Internal Fragmentation)：分配给进程的内存块略大于其请求的内存，这部分差值在分区内部但未被使用。

  • 例如，进程请求 10KB，分配了 12KB 的分区，有 2KB 内部碎片。

  解决外部碎片：

  • 压缩 (Compaction)：移动内存内容，将所有空闲内存合并成一个大块。需要动态重定位（执行时地址绑定）。开销大。
  • 非连续分配：允许进程的逻辑地址空间在物理上不连续，如分段和分页。

10. 分段 (Segmentation)

• 概念：程序及其数据被划分为多个段 (Segment)，如代码段、数据段、堆栈段等。
• 段的长度不固定，但有最大长度。
• 逻辑地址：一个二维地址，由 <段号, 段内偏移> 组成。
• 优点：
  • 方便程序员组织程序和数据，支持模块化。
  • 消除了内部碎片（因为段大小可变）。
• 缺点：
  • 会产生外部碎片。
  • 程序需要知道段的最大长度限制。
• 分段硬件：
• • 段表 (Segment Table)：将二维逻辑地址映射到一维物理地址。
  • 每个段表条目包含：
    • 段基址 (Segment Base)：该段在物理内存中的起始地址。
    • 段界限 (Segment Limit)：该段的长度。
  • 地址转换：
    1. 检查段内偏移是否 < 段界限。若否则地址越界陷阱。
    2. 物理地址 = 段基址 + 段内偏移。

  分段示例

  假设段表如下：

  段号	基址	界限
  0	1400	1000
  1	6300	400
  2	4300	400
  3	3200	1100
  4	4700	1000

  逻辑地址 <2, 53>：段2基址4300，界限400。53 < 400，有效。物理地址 = 4300 + 53 = 4353。

  逻辑地址 <0, 1222>：段0基址1400，界限1000。1222 > 1000，地址越界。

11. 分页 (Paging)

• 概念：允许进程的物理地址空间非连续。
• 基本思想：
  • 将物理内存划分为固定大小的块，称为帧 (Frame)。帧大小是2的幂（如 4KB, 8KB）。
  • 将逻辑内存划分为同样大小的块，称为页 (Page)。
• 运行程序：要运行 N 页的程序，需找到 N 个空闲帧，加载程序页到这些帧中，并设置页表。
• 优点：
  • 避免外部碎片。
  • 避免了紧缩的需要。
• 缺点：
  • 仍然存在内部碎片（最后一页通常不会占满整个帧）。

11.1 地址转换

• CPU 生成的逻辑地址分为两部分：
  • 页号 (Page number, p)：用作页表的索引。
  • 页偏移 (Page offset, d)：在页内的相对地址。
• 如果逻辑地址空间大小为 \(2^m\)，页面大小为 \(2^n\) 字节：
  • 页号占 \(m-n\) 位。
  • 页偏移占 \(n\) 位。
  • 逻辑地址 = | 页号 (p) | 页偏移 (d) |
• 物理地址 = (帧号 \(\times\) 页面大小) + 页偏移。 或者更直接地：物理地址 = | 帧号 (f) | 页偏移 (d) | (帧号和页偏移位数可能不同，但偏移量部分直接复制)

11.2 页表 (Page Table)

• 功能：存储逻辑页到物理帧的映射关系。
• 每个进程都有一个页表。
• 页表基址寄存器 (PTBR, Page Table Base Register)：指向当前进程页表在内存中的起始地址。
• 页表长度寄存器 (PTLR, Page Table Length Register)：指示页表的大小（条目数）。

• 地址转换过程：

  1. 从逻辑地址中提取页号 p。
  2. 访问页表中第 p 个条目，获取对应的帧号 f。
  3. 将帧号 f 与逻辑地址中的页偏移 d 组合成物理地址。

  内存访问开销

  每次数据/指令访问需要两次内存访问：一次访问页表，一次访问实际数据/指令。

11.3 转换检测缓冲区 (TLB, Translation Lookaside Buffer)

• 也称快表 (Associative Memory)，是一种特殊的快速查找硬件缓存。
• 键值存储：存储最近使用过的页号到帧号的映射。
  • 键：页号
  • 值：帧号
• 工作原理：
  1. CPU 生成逻辑地址，提取页号 p。
  2. 并行在 TLB 中查找 p。
  3. TLB 命中 (TLB Hit)：若找到，直接获取帧号，计算物理地址。速度快。
  4. TLB 未命中 (TLB Miss)：若未找到，则访问内存中的页表获取帧号，然后将此映射存入 TLB（可能替换旧条目），再计算物理地址。
• ASID (Address-Space Identifier)：TLB 中可存储 ASID 以区分不同进程的条目，避免上下文切换时刷新整个 TLB。

• 有效访问时间 (EAT, Effective Access Time)：

  设 TLB 查找时间为 \(\epsilon\) (可忽略不计或很小)，内存访问时间为 \(t\)，TLB 命中率为 \(\alpha\)。

  \(EAT = \alpha \times (t) + (1-\alpha) \times (2t)\) (简化模型，TLB查找时间忽略，一次TLB miss导致两次内存访问：查页表+访数据)

  如果考虑TLB访问时间 \(\epsilon\) 和内存访问时间 \(m\):

  \(EAT = \alpha \times (\epsilon + m) + (1-\alpha) \times (\epsilon + m + m)\)

  \(EAT = \epsilon + m + (1-\alpha)m\)

  \(EAT = \text{TLB\_lookup} + \text{Hit\_Rate} \times (\text{Memory\_Access}) + (1-\text{Hit\_Rate}) \times (\text{Page\_Table\_Access} + \text{Memory\_Access})\)

  EAT 计算

  假设 TLB 查找时间为 0 ns (理想情况，实际很小)，内存访问时间为 10 ns。

  命中率 80%： \(EAT = 0.80 \times 10\text{ns} + 0.20 \times (10\text{ns} + 10\text{ns}) = 8\text{ns} + 0.20 \times 20\text{ns} = 8\text{ns} + 4\text{ns} = 12\text{ns}\)

  命中率 99%： \(EAT = 0.99 \times 10\text{ns} + 0.01 \times (10\text{ns} + 10\text{ns}) = 9.9\text{ns} + 0.01 \times 20\text{ns} = 9.9\text{ns} + 0.2\text{ns} = 10.1\text{ns}\)

11.4 内存保护

• 通过在页表条目中增加保护位实现。
• 有效-无效位 (Valid-Invalid Bit)：
  • Valid (v)：关联页在进程的逻辑地址空间中，且已调入内存。
  • Invalid (i)：关联页不在进程的逻辑地址空间中，或未调入内存。
  • 访问无效页会产生陷阱 (trap) 给操作系统（缺页异常或段错误）。
• 其他保护位：如只读 (Read-Only)、读写 (Read-Write)、仅执行 (Execute-Only) 等。

11.5 共享页 (Shared Pages)

• 共享代码 (Shared Code)：多个进程可以共享只读（可重入）代码的一个副本（如文本编辑器、编译器）。
• 共享数据 (Shared Data)：如果允许多个进程共享读写页面，可用于进程间通信。
• 私有代码和数据：每个进程保留各自的副本。

11.6 页表结构

对于大地址空间（如32位或64位），简单页表可能非常庞大。

例如：32位逻辑地址，页面大小 4KB (\(2^{12}\) 字节)。 页表条目数 = \(2^{32} / 2^{12} = 2^{20}\) (约100万)。若每条目4字节，则页表大小为 4MB。

解决方案：

1. 分层页表 (Hierarchical Paging / Multi-level Page Tables)

   • 将页表本身进行分页。
   • 二级页表：
     • 逻辑地址分为：| 外层页号 (p1) | 内层页号 (p2) | 页偏移 (d) |
     • p1 用于索引外层页表，找到内层页表的基址。
     • p2 用于索引内层页表，找到数据页对应的帧号。
   • 三级或更多级页表：对于64位系统，二级页表仍可能过大，可扩展到更多级。
     • 缺点：多次内存访问才能获取最终物理地址（每级页表一次）。

2. 散列页表 (Hashed Page Tables)

   • 适用于大于32位的地址空间。
   • 虚拟页码经过哈希函数计算，得到页表中的索引。
   • 页表条目是一个链表头，存储哈希到同一位置的元素。
   • 每个元素包含：<虚拟页码, 映射的帧号, 指向链表下一元素的指针>。
   • 聚簇页表 (Clustered Page Tables)：哈希页表的变体，每个条目引用多个页面（如16个），适用于稀疏地址空间。

3. 倒排页表 (Inverted Page Tables)

   • 不是每个进程一个页表，而是系统中只有一个页表，为每个物理帧建立一个条目。
   • 每个条目包含：<存储在该帧的虚拟页号, 拥有该页的进程ID>。
   • 优点：大大减少了存储页表所需的内存。
   • 缺点：搜索表所需时间增加（因为要根据<进程ID, 虚拟页号>搜索整个表）。通常使用哈希表辅助搜索。
   • 实现共享内存较复杂。

12. 示例体系结构

• Intel IA-32 (32位)
  • 支持分段和分页。CPU生成逻辑地址 -> 分段单元 (使用GDT/LDT) -> 线性地址 -> 分页单元 -> 物理地址。
  • 页面大小可以是 4KB 或 4MB。
  • PAE (Page Address Extension)：允许32位应用访问超过4GB内存。使用3级分页，地址空间扩展到36位（64GB物理内存）。
• Intel x86-64 (64位)
  • 实际实现48位寻址。
  • 页面大小 4KB, 2MB, 1GB。
  • 通常使用4级分页层次结构。
• ARM
  • 主流移动平台。
  • 支持多种页面大小（如 4KB, 16KB, 1MB, 16MB）。
  • 一级或两级分页。
  • 两级TLB（微TLB + 主TLB）。

13. 伙伴系统 (Buddy System)

一种内存分配方案，试图融合固定分区和动态分区的优点。

• 原理：
  • 内存块大小为 \(2^K\) 字，其中 \(2^L\) 是最小分配块， \(2^U\) 是最大分配块（通常是整个可分配内存）。
  • 当请求大小为 \(S\) 的内存时：
    • 分配大小为 \(2^k\) 的块，其中 \(2^{k-1} < S \le 2^k\)。
    • 如果找不到 \(2^k\) 大小的块，则从更大的块 \(2^{k+1}\)分裂成两个 \(2^k\) 的“伙伴”块。
    • 重复分裂，直到得到合适大小的块。
  • 释放内存：
    • 当一个块被释放时，检查其伙伴块是否也空闲。
    • 如果伙伴也空闲，则合并它们形成一个更大的块，并递归向上检查合并。
• 优点：快速合并空闲块。
• 缺点：仍可能存在内部碎片（因为分配的是2的幂次方大小）。

---

第十讲：虚拟内存管理

学习目标

• 定义虚拟内存及其优点
• 解释请求调页、页面置换算法和页帧分配
• 讨论工作集模型原理
• 讨论共享内存和内存映射文件的关系
• 讨论如何管理内核内存

1. 虚拟内存背景

• 核心思想：允许执行未完全加载入内存的程序。
• 优点：
  • 程序不再受物理内存大小限制。
  • 每个程序占用更少物理内存，可同时运行更多程序，提高 CPU 利用率和吞吐量。
  • 加载或交换程序所需的 I/O 更少，程序运行更快。

• 实现：MMU 将逻辑地址（虚拟地址）转换为物理地址。

  CPU -> (Virtual Address) -> MMU -> (Physical Address) -> Memory
  

• 虚拟内存：将用户逻辑内存与物理内存分离。

  • 逻辑地址空间可以远大于物理地址空间。
  • 允许进程共享地址空间，高效创建进程。
• 实现方式：
  • 请求分页 (Demand Paging)
  • 请求分段 (Demand Segmentation)

2. 虚拟地址空间

• 进程看到的内存是逻辑上连续的地址空间，通常从0开始。
• 典型布局：代码区、数据区、堆（向上增长）、栈（向下增长）。
• 堆栈之间的空洞允许动态增长。
• 系统库、共享内存等通过映射到虚拟地址空间实现共享。

3. 请求分页 (Demand Paging)

• 概念：只在需要时才将页面调入内存（惰性交换 Lazy Swapper）。
• 机制：
  • 页表条目中增加有效-无效位 (Valid-Invalid Bit)：
    • v (valid): 页在内存中。
    • i (invalid): 页不在内存中（或无效引用）。
  • 访问标记为 i 的页，MMU 产生缺页错误 (Page Fault)。

3.1 处理缺页错误

1. CPU 访问某页，MMU 发现该页在页表中标记为无效 (invalid)。
2. MMU 产生一个缺页陷阱 (Page Fault Trap)给操作系统。

3. 操作系统响应：

   a. 检查进程内部表（如 PCB 中）确定引用是否合法（例如，地址是否在进程逻辑地址空间内）。 b. 若非法引用，则终止进程。 c. 若合法但页不在内存： i. 找到一个空闲物理帧 (Free Frame)。(若无空闲帧，则需执行页面置换) ii. 调度磁盘操作，将所需页面从磁盘读入该空闲帧。 iii.磁盘读取完成后，修改进程页表和内部表，将该页标记为有效 (valid)，并记录其物理帧号。 5. 重新启动导致缺页的指令。

纯请求分页

进程启动时，没有任何页在内存中。第一条指令就会导致缺页。

• 硬件支持：
  • 带有效-无效位的页表。
  • 辅助存储（如磁盘上的交换空间 Swap Space）。
  • 指令重启能力。

3.2 请求分页的性能

• 有效访问时间 (EAT)：

  设 \(p\) 为缺页率 (\(0 \le p \le 1\))，内存访问时间为 \(t_{mem}\)，缺页处理时间为 \(t_{fault}\)。

  \(EAT = (1-p) \times t_{mem} + p \times t_{fault}\)

  其中 \(t_{fault}\) 包括：陷阱处理、磁盘读页、进程重启等开销，远大于 \(t_{mem}\)。

  EAT 计算

  \(t_{mem} = 200 \text{ ns}\)

  \(t_{fault} = 8 \text{ ms} = 8,000,000 \text{ ns}\)

  \(EAT = (1-p) \times 200 + p \times 8,000,000 = 200 + 7,999,800 \times p\)

  如果 \(p = 0.001\) (千分之一的访问缺页):

  \(EAT = 200 + 7,999,800 \times 0.001 = 200 + 7999.8 \approx 8.2 \text{ μs}\) (性能下降约40倍)

  要使性能下降 < 10% (\(EAT < 220 \text{ ns}\)):

  \(220 > 200 + 7,999,800 \times p \implies 20 > 7,999,800 \times p \implies p < 0.0000025\)

  (即每40万次访问少于1次缺页)

• 优化：

  • 使用快速交换空间。
  • 从程序二进制文件按需调页，丢弃只读页而不是换出。
  • 匿名内存（堆栈）需写入交换空间。

3.3 写时复制 (Copy-on-Write, COW)

• fork() 系统调用创建子进程时，父子进程最初共享相同的物理页面。
• 只有当任一进程试图写入共享页面时，才复制该页面，为写入方创建一个私有副本。
• 优点：提高 fork() 效率，因为只复制被修改的页面。
• 空闲页面通常从“按需零填充”池中分配（分配前清零，保证安全性）。

4. 页面置换 (Page Replacement)

当发生缺页但没有空闲帧时，需要选择一个内存中的页（牺牲页, victim page）将其换出到磁盘，以腾出帧给新调入的页。

• 目标：选择一个未来最长时间内不会被访问的页，以最小化缺页率。
• 修改位/脏位 (Modify Bit / Dirty Bit)：
  • 页表条目中增加一位。
  • 当页被写入（修改）时，硬件设置此位为1。
  • 如果牺牲页的脏位为0（未修改），则无需写回磁盘，直接覆盖。
  • 如果脏位为1，则必须先将其内容写回磁盘，再覆盖。

4.1 基本页面置换流程

1. 在磁盘上找到所需页面的位置。
2. 找到一个空闲帧： a. 如果有空闲帧，使用它。 b. 如果没有空闲帧，使用页面置换算法选择一个牺牲帧 (Victim Frame)。 c. 如果牺牲帧对应的页面是“脏”的（被修改过），则将其写回磁盘。
3. 将所需页面读入（刚被释放或原为空闲的）帧中；更新页表和帧表。
4. 重新启动导致陷阱的指令。

开销增加

若无空闲帧且牺牲页是脏的，一次缺页可能导致两次页面传输（一次写出牺牲页，一次读入新页）。

4.2 页面置换算法

评估标准：在给定的内存引用字符串 (Reference String) 和可用帧数下，产生的缺页次数。

1. 先进先出 (FIFO, First-In First-Out)

   • 替换最早进入内存的页面。
   • 实现简单（使用队列）。
   • Belady 异常 (Belady's Anomaly)：对于某些引用串，增加分配的帧数反而可能导致缺页率上升。

2. 最优算法 (OPT / MIN, Optimal)

   • 替换未来最长时间内不会被使用的页面。
   • 理论上缺页率最低，但无法实现（因为无法预测未来）。
   • 作为衡量其他算法性能的基准。

3. 最近最少使用 (LRU, Least Recently Used)

   • 替换过去最长时间内未被使用的页面。基于局部性原理，认为最近未用的将来也不太可能用。
   • 性能较好，不会有 Belady 异常。
   • 实现方式：
     • 计数器 (Counter)：每页一个时间戳，记录最后访问时间。替换时找时间戳最小的。开销大。
     • 栈 (Stack)：维护一个按访问时间排序的页号栈。页被访问则移到栈顶。替换栈底页。更新开销大。

4. 近似 LRU 算法 硬件支持有限，LRU 实现复杂，故采用近似算法。

   • 引用位 (Reference Bit)：
     • 页表条目中增加一位，由硬件设置。
     • 页被访问时，引用位置1。
     • 操作系统定期清零引用位。
   • 附加引用位算法 / 老化算法 (Aging)：
     • 为每页维护一个多位寄存器（如8位）。
     • 定时将引用位移入寄存器的高位，寄存器右移，丢弃低位。
     • 寄存器值越小，表示越久未被访问。
   • 第二次机会算法 (Second-Chance / Clock Algorithm)：
     • FIFO 的改进，结合引用位。
     • 页面组织成循环队列，有一个指针指向下一个可能的牺牲者。
     • 选择牺牲页时：
       • 若引用位为0：替换该页。
       • 若引用位为1：给它“第二次机会”，将其引用位置0，指针后移，继续查找。
   • 增强型第二次机会算法 (Enhanced Second-Chance Algorithm)：
     • 同时考虑引用位和修改位 (dirty bit)。将页分为4类：
       1. (0,0)：最近未引用，未修改 (最佳牺牲者)
       2. (0,1)：最近未引用，但已修改 (次佳，需写回)
       3. (1,0)：最近引用，未修改
       4. (1,1)：最近引用，已修改
     • 按类别顺序查找牺牲者，替换类别编号最小的非空集合中的第一个页。可能需要多次扫描。

5. 计数算法 (Counting Algorithms)

   • 最不经常使用 (LFU, Least Frequently Used)：替换引用次数最少的页。可能将刚调入还未使用的页换出。
   • 最常使用 (MFU, Most Frequently Used)：替换引用次数最多的页。理由是引用少的页可能刚调入。

6. 页面缓冲算法 (Page Buffering Algorithms)

   • 维护一个空闲帧池。
   • 发生缺页时，从空闲池取帧，并将牺牲页加入“待写出列表”或“待重用列表”。
   • 磁盘空闲时，将脏页写回。
   • 如果被“牺牲”但仍在缓冲区的页再次被访问，可快速恢复。

5. 帧分配 (Frame Allocation)

如何为多个进程分配有限的物理帧？

• 最少帧数：每个进程需要一个最小帧数以保证运行（如指令跨多页，间接寻址等）。

• 分配策略：

  • 固定分配 (Fixed Allocation)：
    • 平均分配：每个进程分得相同数量的帧。
    • 比例分配：根据进程大小或优先级按比例分配帧。 \(a_i = \frac{s_i}{S} \times m\), \(a_i\) 为进程 \(i\) 分配的帧数, \(s_i\) 为进程 \(i\) 大小, \(S = \sum s_j\), \(m\) 为总可用帧数。
  • 优先级分配 (Priority Allocation)：根据进程优先级分配帧，高优先级进程可能从低优先级进程处获取帧。

• 全局置换 vs. 局布置换 (Global vs. Local Replacement)

  • 全局置换：进程可以从所有帧（包括属于其他进程的帧）中选择牺牲帧。
    • 优点：系统吞吐量可能更高，灵活。
    • 缺点：一个进程的缺页行为受其他进程影响，缺页率不可控。
  • 局布置换：每个进程只能从分配给它自己的帧中选择牺牲帧。
    • 优点：进程缺页行为更可预测和控制。
    • 缺点：可能造成内存浪费（某进程帧多不用，另一进程帧少急需）。

6. 系统抖动 (Thrashing)

• 现象：如果一个进程没有足够的帧来容纳其当前工作所需的“活动”页面集合，它会频繁发生缺页。CPU 大部分时间都在等待磁盘 I/O（调页），而不是执行用户代码，导致 CPU 利用率极低。
• 原因：进程的“局部性 (Locality)”所需页面总数大于分配给它的帧数。
• 操作系统可能错误地认为 CPU 利用率低是由于多道程序数量不够，从而引入更多进程，加剧抖动。
• 局部性模型 (Locality Model)：进程在执行时，倾向于访问一组相对集中的页面，这个集合称为“局部”。局部性会随时间变化。

6.1 工作集模型 (Working-Set Model)

• 基于局部性假设。
• \(\Delta\): 工作集窗口，一个固定的页面引用次数（如最近10000次内存引用）。
• \(WSS_i\) (进程 \(P_i\) 的工作集)：在最近 \(\Delta\) 次引用中实际访问到的不同页面的集合。\(|WSS_i|\) 是工作集大小。
• 如果 \(\Delta\) 太小，不能包含整个局部；太大，则包含多个局部。
• \(D = \sum |WSS_i|\): 系统总需求帧数。
• 如果 \(D > m\) (总可用帧数)，则可能发生抖动。
• 策略：为进程分配其工作集大小的帧。若内存不足，则挂起某些进程。

6.2 缺页错误率 (PFF, Page-Fault Frequency)

• 更直接的方法控制抖动。
• 设定可接受的缺页率上限和下限。
  • 如果某进程缺页率 > 上限：说明帧不足，分配更多帧。
  • 如果某进程缺页率 < 下限：说明帧有富余，可回收一些帧。
• 若所有进程缺页率都较高但无空闲帧可分配，则需挂起某些进程。

7. 内核内存分配

• 内核内存需求与用户内存不同，通常从单独的内存池中分配。
• 某些内核数据结构需要物理上连续的内存（如 I/O 操作的缓冲区）。
• 常见分配器：
  • 伙伴系统 (Buddy System)：(已在物理内存部分介绍) 将内存按 \(2^k\) 大小管理，分裂和合并。
  • Slab 分配器 (Slab Allocator)：
    • Slab: 一个或多个物理连续的页。
    • Cache: 由一个或多个 Slab 组成，专用于一种特定类型的内核数据结构（对象）。
    • Cache 创建时，Slab 中填充了该类型的对象实例，标记为空闲。
    • 分配对象：从 Cache 中取一个空闲对象。
    • 释放对象：将其标记为空闲，放回 Cache。
    • 优点:
      • 消除内部碎片（对象大小固定）。
      • 分配和释放速度快（对象已预先初始化）。
    • Slab 状态：Full (全满), Empty (全空), Partial (部分使用)。优先从 Partial Slab 分配。
    • Linux 中的 SLOB (Simple List of Blocks, 适用于内存受限系统) 和 SLUB (性能优化的 Slab) 也是类似机制。

8. 其他注意事项

• 预调页 (Prepaging)：
  • 在进程启动或缺页时，除了调入所需页，还“预先”调入一些猜测可能很快会用到的页。
  • 目标是减少初始阶段的大量缺页。
  • 如果预调入的页未使用，则浪费了 I/O 和内存。
• 页面大小 (Page Size)：
  • 影响因素：内部碎片大小、页表大小、I/O 开销、TLB 覆盖率、局部性。
  • 通常是 \(2^k\) (如 4KB, 8KB, ... 4MB)。
  • 趋势是页面大小逐渐增大。
• TLB 覆盖范围 (TLB Reach)：
  • \(TLB\_Reach = (\text{TLB 条目数}) \times (\text{页面大小})\)
  • 理想情况下，进程工作集应能放入 TLB。
  • 增大页面大小或提供多种页面大小可以增加 TLB Reach。
• 程序结构：
  • 数据存储方式和访问模式会显著影响缺页率。
  • 例如，按行存储的二维数组，如果按列访问，且每行一页，会导致大量换页。

    // 假设 int data[128][128]; 每行一页
    // 差的访问 (128*128 次缺页)
    for (j = 0; j < 128; j++)
        for (i = 0; i < 128; i++)
            data[i][j] = 0;
    // 好的访问 (128 次缺页)
    for (i = 0; i < 128; i++)
        for (j = 0; j < 128; j++)
            data[i][j] = 0;
    

• I/O 互锁与页面锁定 (I/O Interlock and Page Locking)：
  • 进行 I/O 操作的页面（如 DMA 缓冲区）必须锁定 (Pinning) 在内存中，不能被置换出去，直到 I/O 完成。

9. 操作系统示例

• Windows：
  • 使用请求调页，带有集群 (Clustering)（一次调入故障页及其周围页）。
  • 为进程分配工作集最小值和最大值。
  • 内存不足时进行工作集修整 (Working Set Trimming)。
• Solaris / (类 Unix 系统)：
  • 维护空闲页列表。通过 lotsfree, desfree, minfree 等阈值控制调页和交换。
  • pageout 进程使用时钟算法扫描页面。
  • scanrate (扫描速率) 从 slowscan 到 fastscan 变化。
  • 优先级调页（如优先保留代码页）。

评论