[中文] Operating Systems Notes: 06 - 虚拟内存技术

1. 虚拟内存基础概念#

1.1 虚拟地址空间 (Virtual Address Space)#

• 定义: 操作系统为每个进程提供的、看起来连续的、私有的内存空间。它是对物理内存和磁盘空间的抽象。

• 作用:

  • 隔离进程，提供保护。
  • 简化内存管理，允许程序使用比物理内存更大的地址空间。
  • 实现内存共享。

• 提问：CPU取到的地址是什么地址？物理地址还是虚拟地址？

  • 解答: CPU发出的地址通常是 虚拟地址 (Virtual Address)。这个虚拟地址随后会被 内存管理单元 (MMU) 转换为物理地址 (Physical Address)。

  graph LR
      CPU -- Virtual Address --> MMU;
      MMU -- Physical Address --> PhysicalMemory[物理内存];
      MMU -- Page Fault --> OS[操作系统];
      OS -- Data from Disk --> PhysicalMemory;
      PhysicalMemory <--> Disk[磁盘];
  

  mermaid

1.2 虚拟内存管理的目标#

1. 透明性 (Transparency): 运行的程序不应感知到虚拟内存机制的存在。程序员可以像操作一个巨大的连续内存一样编程。
2. 效率 (Efficiency): 地址转换和页面调度应尽可能快，减少性能开销。需要 硬件支持 (如MMU, TLB)。
3. 保护 (Protection): 确保进程之间、进程与操作系统之间相互隔离，互不干扰。

1.3 存储体系 (Memory Hierarchy)#

• 结构: 寄存器 -> Cache -> 内存 (RAM) -> 磁盘 (Disk)
• 操作系统角色: 协调各级存储器的使用。
• 目标: 结合速度快但容量小的存储（如Cache, RAM）和速度慢但容量大的存储（如磁盘），为用户提供一个既“快”又“大”的逻辑内存（虚存）。

1.4 相关术语辨识#

• 虚拟内存 (Virtual Memory):
  • 解释: 将物理内存与磁盘结合使用，为程序提供一个容量远大于物理内存的逻辑存储空间。
  • 关键: 程序引用的地址（虚拟地址）与物理内存地址不同，由系统自动转换。虚存大小受限于计算机寻址能力和可用磁盘空间。
• 虚拟地址空间 (Virtual Address Space):
  • 解释: 分配给一个进程的逻辑地址范围。
• 虚拟地址 (Virtual Address):
  • 解释: 虚拟地址空间中的某个地址。进程通过虚拟地址访问数据，仿佛它就在内存中。
• 虚拟存储技术 (Virtual Memory Technology):
  • 解释: 一种内存管理技术。程序运行时，只将其一部分装入内存，其余部分留在磁盘。当需要访问不在内存中的部分时，操作系统自动将其从磁盘调入内存。

2. 虚拟页式存储管理 (Paged Virtual Memory)#

2.1 基本思想#

• 按需加载: 装载程序时，只装入部分（甚至零个）页面到物理内存。
• 动态调页: 当进程执行需要访问不在内存中的页面时，产生 页错误 (Page Fault)，操作系统负责将所需页面从磁盘动态调入内存。
• 页面换出: 当内存不足时，将内存中暂时不用的页面交换（写回）到磁盘，以腾出空间。
• 实现方式:
  • 请求调页 (Demand Paging): 只有当页面被访问时才调入。（最常用）
  • 预先调页 (Prepaging): 预测进程可能需要的页面并提前调入。
• 本质: 资源转换技术，用CPU时间和磁盘空间换取（看似无限的）物理内存空间。

2.2 核心策略 (Coffman & Denning)#

1. 取页策略 (Fetch Policy): 决定何时将页面从磁盘调入内存。
   • 请求调页: 发生缺页时才调入。
   • 预调页: 预测并提前调入。
2. 放置策略 (Placement Policy): 决定将调入的页面放置在物理内存的哪个 页框 (Page Frame) 中。
   • 解释: 在分页系统中，任何空闲页框都可以存放任何页面，所以此策略相对简单。
3. 置换策略 (Replacement Policy): 当内存没有空闲页框时，决定选择哪个页框中的页面换出到磁盘。

2.3 设计与实现问题#

• 页表表项 (PTE) 的设计。
• 如何处理页表过大的问题（如多级页表）。
• 地址重定位与快表 (TLB)。
• 缺页异常 (Page Fault) 的处理机制。
• 驻留集 (Resident Set) 管理。
• 置换策略 (Replacement Algorithms)。
• 清除策略 (Cleaning Policy)。
• 加载控制 (Load Control)。

3. 硬件支持与核心机制#

3.1 页表表项 (Page Table Entry - PTE) 设计#

• 关键字段:
  • 页框号 (Page Frame Number - PFN): 该虚拟页对应的物理内存块号。
  • 有效位/驻留位 (Valid/Present Bit - P): 标记该页是否在物理内存中 (1=在内存, 0=不在内存/在磁盘)。
  • 访问位/引用位 (Accessed/Referenced Bit - A/R): 标记该页近期是否被访问过 (硬件在访问时设置，OS定期清零)。用于置换算法。
  • 修改位/脏位 (Dirty/Modified Bit - D/M): 标记该页在内存中是否被修改过 (硬件在写入时设置)。如果为1，换出时必须写回磁盘。
  • 保护位 (Protection Bits - R/W/X): 控制对该页的访问权限（读/写/执行）。
• i386 PDE/PTE 示例: (展示了具体位域)
  • P (Present), A (Accessed), D (Dirty), R/W (Read/Write), U/S (User/Supervisor), PWT (Page Write Through), PCD (Page Cache Disable), PS (Page Size - for large pages).

3.2 处理页表过大的问题#

• 问题:
  • 32位地址空间 (4KB页面, 4B PTE): 页表本身占用内存 2^20 个 PTE * 4B = 4MB = 2^22 = 1024 个 4KB 页面 的空间。
  • 若用户拥有 2G = 2^31 = 2^19 个 4KB 页面 的物理空间，索引这块内存的**有效 (有效位 P=1)**的页表就占 512 页 (2^19 * 4B / 4KB = 512)。
  • 64位地址空间: 页表大小会变得极其巨大 (理论上 2^52 * 8B，不可行)。
• 解决方案:
  1. 多级页表 (Multi-Level Page Tables):
     • 思想: 将巨大的线性页表变成树形结构。外层页表（页目录）的条目指向内层页表。只有被用到的内层页表才需要分配内存。
     • 二级页表示例: 虚拟地址分为 页目录偏移 | 页表偏移 | 页内偏移。CR3寄存器指向页目录基址 -> 查页目录得页表基址 -> 查页表得页框号 -> 拼接页内偏移得物理地址。
     • Core i7 示例 (四级页表): 48位虚拟地址，分为 9 | 9 | 9 | 9 | 12 位，对应四级页表的索引和页内偏移。
     • 优点: 节省空间，只有实际使用的页表部分才需载入内存。虽然理论上总页表项数量不变，但实际上大多数进程只使用地址空间的一小部分。
     • 空间节省示例:
       • 在32位系统中（4GB地址空间），使用4KB页面，线性页表需要1M个页表项（32位虚拟地址空间都需要对应的页表项）。
       • 假设一个进程只使用了4MB的连续内存（位于0x80000000-0x80400000），在二级页表中：
         • 需要1个完整的页目录（1024项，4KB）
         • 只需要1个二级页表（1024项，4KB，对应使用的4MB区域）
         • 其余1023个二级页表（对应未使用的地址空间）根本不需要创建
       • 总计只需8KB内存，而不是线性页表的4MB，节省了约99.8%的空间
     • 缺点: 每次地址翻译需要多次内存访问（可通过TLB缓解）。
  2. 反转页表 (Inverted Page Table):
     • 思想: 不再为每个进程维护一个页表，而是为整个物理内存建立一个全局页表。页表项 i 对应物理页框 i。
     • 内容: 每个页表项记录 (进程ID, 虚拟页号)，表示哪个进程的哪个虚拟页映射到了这个物理页框。
     • 地址转换: 给定 (进程ID, 虚拟页号)，需要搜索整个反转页表找到匹配项，得到其索引（即物理页框号）。
     • 优化: 使用哈希表 (Hash Table) 加速查找。将 (进程ID, 虚拟页号) 哈希到一个索引，指向反转页表中的一个桶（可能需要链表解决冲突）。
     • 优点: 页表大小与物理内存大小成正比，与虚拟地址空间大小和进程数量无关。
     • 缺点: 查找可能较慢（即使有哈希），实现共享比较困难。
     • 应用: PowerPC, UltraSPARC, IA-64 等。

3.3 内存管理单元 (MMU)#

• 定义: CPU中的硬件单元，负责将虚拟地址转换为物理地址。
• 过程: 接收CPU发出的虚拟地址，查询页表（优先查TLB），生成物理地址或触发缺页异常。

3.4 地址转换 (Address Translation)#

• 硬件机制:
  1. CPU发出虚拟地址。
  2. MMU 从虚拟地址中提取 虚拟页号 (VPN) 和 页内偏移 (Offset)。
  3. MMU 使用 VPN（可能结合多级页表结构）查找页表（先查TLB）。
  4. 检查 PTE:
     • Case 1: PTE 有效 (Valid/Present bit = 1) 且权限允许:
       • 从 PTE 中获取 页框号 (PFN)。
       • 将 PFN 与页内偏移拼接，形成 物理地址。
       • 访问内存。
       • 硬件根据访问类型（读/写）可能设置 访问位 (A) 或 修改位 (D)。
     • Case 2: PTE 无效 (Valid/Present bit = 0) 或权限不足:
       • MMU 产生 页错误 (Page Fault) 异常，将控制权交给操作系统。
• 页错误处理 (OS): (详见 3.6)

3.5 快表 (Translation Look-aside Buffer - TLB)#

• 问题: 多级页表导致每次地址翻译需要多次内存访问，显著降低性能。
• 原理: 利用 程序访问的局部性原理 (Locality of Reference)。最近访问过的页面很可能再次被访问。
• 什么是TLB:
  • 一种高速的、容量小的 相联存储器 (Associative Memory)。
  • 特点：按 内容 并行查找，速度极快。
  • 存储内容：缓存近期使用过的 虚拟页号 (VPN) 到 页框号 (PFN) 的映射 (即部分活跃的页表项)。
• 工作流程:
  1. MMU 收到虚拟地址后，首先并行查找 TLB。
  2. TLB Hit (命中): 如果在 TLB 中找到匹配的 VPN，直接获取 PFN，快速完成地址转换。跳过页表查找。
  3. TLB Miss (未命中):
     • MMU 需要访问内存中的页表进行查找。
     • 找到 PFN 后，将 (VPN -> PFN) 的映射关系装入 TLB (可能需要替换掉 TLB 中的一个旧条目，使用LRU等策略)。
     • 完成地址转换。
• TLB 刷新问题:
  • 问题: 进程切换时，原进程的 TLB 条目对新进程无效，需要刷新 TLB，导致新进程初期 TLB Miss 增多，性能下降。
  • 解决:
    • PCID (Process Context Identifier) / ASID (Address Space Identifier): 给 TLB 条目打上进程标识符。切换进程时，只需加载新进程的 PCID/ASID，TLB 中带有不同 ID 的条目不会被匹配，无需完全刷新。
• 关键参数: TLB 的大小、位置（通常集成在MMU或CPU核心内）、替换策略。

3.6 缺页异常 (Page Fault) 处理#

• 触发: 地址转换过程中，MMU 发现所需页面的 PTE 无效 (P=0) 或访问权限不足。
• 本质: 一种硬件中断/异常，将控制权交给操作系统内核的 缺页异常处理程序 (Page Fault Handler)。
• 处理流程 (典型情况 - 页面不在内存):
  1. 保存现场: 保存用户进程的状态（PC, 寄存器等）。
  2. 确定原因: 操作系统分析是真缺页（P=0），还是保护性错误（权限不足）。如果是后者，可能终止进程。
  3. 定位磁盘地址: 如果是真缺页，查找该虚拟页在磁盘（交换空间或文件）上的位置。
  4. 查找空闲页框: 在物理内存中寻找一个空闲的页框。
  5. 处理无空闲页框:
     • 若无空闲页框: 执行 页面置换算法，选择一个牺牲页框 (Victim Frame)。
     • 写回脏页: 如果牺牲页框中的页面是 “脏” 的 (D=1)，则需要将其内容 写回磁盘。
  6. 调入页面: 启动磁盘 I/O 操作，将所需的页面从磁盘读入选定的（空闲或牺牲）页框。
  7. 更新页表: 页面调入完成后，修改该虚拟页对应的 PTE (Page Table Entry，页表项)：设置 P=1，填入 PFN，清除 D 位，可能设置 A 位。
  8. 恢复现场: 恢复用户进程的状态。
  9. 重新执行指令: 重新执行导致缺页异常的指令。此时地址转换可以成功。

3.7 驻留集管理 (Resident Set Management)#

• 驻留集 (Resident Set): 进程当前在物理内存中的页面集合。
• 驻留集大小管理: 决定给每个进程分配多少页框。
  • 固定分配策略 (Fixed Allocation):
    • 在进程创建时确定分配的页框数量。
    • 分配依据可以是:
      • 进程类型（交互式、批处理、应用类型）。
      • 程序员指定的需求。
      • 系统管理员设置的策略。
    • 特点: 简单但缺乏灵活性，无法适应进程工作集大小的动态变化。
  • 可变分配策略 (Variable Allocation):
    • 根据进程的 缺页率 动态评估其局部性表现。
    • 调整机制:
      • 缺页率高 → 增加页框数（扩大驻留集）。
      • 缺页率低 → 减少页框数（缩小驻留集）。
    • 优点: 能够适应程序局部性的变化，提高内存利用率。
    • 缺点: 实现复杂，需要监控缺页率，调整策略可能引入系统开销。
• 系统开销考量:
  • 驻留集管理本身会消耗CPU时间和内存资源。
  • 过于频繁的调整可能导致系统开销超过收益。
  • 需要在响应性和开销之间找到平衡点。

4. 页面置换算法 (Page Replacement Algorithms)#

4.1 置换问题#

• 背景: 当发生缺页异常且没有空闲物理页框时，需要选择一个当前在内存中的页面换出，为新页面腾出空间。
• 目标: 选择一个 最近最不可能被访问 的页面进行置换，以最小化未来的缺页次数。
• 约束: 不能置换被 锁定 (Locked/Pinned) 的页框（如内核代码、I/O 缓冲区等）。
  • 页框锁定: 通过 PTE 中的锁定位或特殊机制，防止 OS 将某些关键页面换出内存，避免 I/O 操作期间页面被换出导致错误，或保证实时任务的响应时间。

4.2 置换范围#

• 局部置换策略 (Local Replacement): 仅在引发缺页的那个进程自己的 驻留集 (Resident Set) 中选择牺牲页。

  • 优点: 进程间的隔离性好。
  • 缺点: 可能无法利用系统中其他进程不活跃的页框。

• 全局置换策略 (Global Replacement): 可以在内存中所有未锁定的页框中选择牺牲页，无论它属于哪个进程。

  • 优点: 更灵活，可能提高系统整体吞吐率。
  • 缺点: 一个行为不良的进程可能挤占其他进程的页框；进程的缺页率受其他进程影响，难以控制。

• 与分配策略的关系:

  • 固定分配通常配合局部置换。
  • 可变分配可以配合局部或全局置换。

4.3 典型置换算法#

1. 最优置换算法 (Optimal - OPT / MIN):

   • 思想: 置换 未来最长时间内不会被访问 的页面。
   • 实现: 无法实现，因为需要预知未来。
   • 作用: 作为性能比较的 基准 (Benchmark)。

2. 先进先出算法 (First-In, First-Out - FIFO):

   • 思想: 置换 在内存中驻留时间最长 的页面。
   • 实现: 维护一个页面进入内存的队列，替换队首页面。
   • 优点: 实现简单。
   • 缺点: 性能较差，可能换出常用页面。存在 Belady 异常。

3. 第二次机会算法 (Second Chance - SCR):

   • 思想: FIFO 的改进。检查队首页面的 访问位 (A/R)。
   • 流程:
     • 检查队首页面 PTE 的 A 位。
     • 如果 A=0，置换该页。
     • 如果 A=1，给它 “第二次机会”：将 A 位清零，并将该页移到队尾，然后检查下一个队首页面。
   • 优点: 比 FIFO 好，避免了立即换出刚被访问过的页面。

4. 时钟算法 (Clock):

   • 思想: Second Chance Replacement (SCR，第二次机会算法) 的高效实现，避免了频繁移动页面。
   • 实现: 将所有物理页框组织成一个 循环链表 (缓冲区)，用一个指针指向下一个要检查的候选页框。
   • 流程:
     • 发生缺页时，从指针当前位置开始扫描。
     • 检查当前页框 PTE 的 A 位。
     • 如果 A=0，选择该页框进行置换，将新页面放入，指针前移。
     • 如果 A=1，将 A 位清零，指针前移，继续检查下一个页框。
   • 优点: 实现相对简单，性能优于 FIFO，接近 LRU。

5. 最近未使用算法 (Not Recently Used - NRU):

   • 思想: 优先淘汰近期 既未被访问 (A=0) 也未被修改 (D=0) 的页面。
   • 实现: 利用 PTE 中的 访问位 (A) 和 修改位 (D) 将页面分为四类：
     • 第 0 类: (A=0, D=0) - 未访问，未修改
     • 第 1 类: (A=0, D=1) - 未访问，已修改
     • 第 2 类: (A=1, D=0) - 已访问，未修改
     • 第 3 类: (A=1, D=1) - 已访问，已修改
   • 流程: OS 定期将所有页面的 A 位清零。发生缺页时，随机 从编号最小的非空类别中选择一个页面进行置换。
   • 优点: 实现简单，性能尚可。

6. NRU 的时钟实现: (一种变体)

   • 扫描 1: 找第一个 (A=0, D=0) 的页框，找到即置换。此过程不清 A 位。
   • 扫描 2 (若扫描 1 失败): 重新扫描，找第一个 (A=0, D=1) 的页框。此过程中，跳过的页框 (A=1) 的 A 位被清零。找到即置换。
   • 扫描 3 (若扫描 2 失败): 此时所有页框 A 位都为 0。重复扫描 1（必然能找到 A=0, D=0 或 A=0, D=1），然后如有必要重复扫描 2。
   • 特点: 优先换出干净页 (D=0)，节省写回磁盘的时间。

7. 最近最少使用算法 (Least Recently Used - LRU):

   • 思想: 置换 过去最长时间未被访问 的页面。基于局部性原理，认为最久未用的页面，近期也最不可能被使用。
   • 实现:
     • 时间戳法: 每个 PTE 记录上次访问时间，置换时间戳最小的。（硬件开销大）
     • 栈/链表法: 维护一个按访问时间排序的页面栈/链表，每次访问将页面移到栈顶/链表头，置换栈底/链表尾的页面。（软件开销大）
   • 优点: 性能非常好，接近 OPT。
   • 缺点: 实现开销大，纯硬件或纯软件实现都困难。

8. 最不经常使用算法 (Not Frequently Used - NFU):

   • 思想: 置换 过去访问次数最少 的页面。LRU 的一种软件近似。
   • 实现: 每个 PTE 关联一个软件计数器，初值为 0。每次时钟中断，检查 A 位，若 A=1，则对应计数器加 1，并将 A 位清零。缺页时置换计数值最小的页面。
   • 缺点: 不能很好地区分早期频繁访问但近期不用的页面和近期才开始访问的页面。

9. 老化算法 (Aging):

   • 思想: 模拟 LRU。改进 NFU，使计数器能反映访问的时间远近。
   • 实现: 每个 PTE 关联一个多位计数器 (e.g., 8-bit)。每次时钟中断：
     1. 将每个计数器 右移 1 位 (模拟时间流逝，旧的访问权重降低)。
     2. 将当前 PTE 的 A 位 加到计数器的 最左边 (最高位)。
     3. 将 A 位清零。
   • 缺页时，置换计数值最小的页面。计数值小的页面表示近期访问较少或很久未访问。
   • 优点: 较好地模拟了 LRU，实现开销适中。
   • 与LRU的区别:
     • 精确度: LRU 精确记录每次访问的时间顺序，而 Aging 只能近似反映访问频率和时间远近。
     • 实现开销: LRU 需要在每次内存访问时更新数据结构，开销大；Aging 只在时钟中断时更新计数器，开销小。
     • 历史长度: LRU 可以无限追溯历史访问记录；Aging 受计数器位数限制（如8位只能记录最近8个时间窗口的访问情况）。
     • 硬件支持: LRU 需要专门硬件支持才能高效实现；Aging 只需要访问位支持，更易于实现。

4.4 算法示例与现象#

• FIFO, LRU, OPT 缺页次数计算:

  • 例子: 页面访问序列 2 3 2 1 5 2 4 5 3 2 5 2，分配 3 个页框。

  • FIFO 算法过程:

    访问页面	2	3	2	1	5	2	4	5	3	2	5	2
    页框1	2	2	2	2	5	5	5	5	3	3	3	3
    页框2	-	3	3	3	3	2	2	2	2	2	5	5
    页框3	-	-	-	1	1	1	4	4	4	4	4	2
    缺页	√	√	×	√	√	√	√	×	√	×	√	√

    总计9次缺页

  • LRU 算法过程:

    访问页面	2	3	2	1	5	2	4	5	3	2	5	2
    页框1	2	2	2	2	2	2	2	2	3	3	3	3
    页框2	-	3	3	3	5	5	5	5	5	5	5	5
    页框3	-	-	-	1	1	1	4	4	4	2	2	2
    缺页	√	√	×	√	√	×	√	×	√	√	×	×

    总计7次缺页

  • OPT 算法过程:

    访问页面	2	3	2	1	5	2	4	5	3	2	5	2
    页框1	2	2	2	2	2	2	4	4	4	2	2	2
    页框2	-	3	3	3	3	3	3	3	3	3	3	3
    页框3	-	-	-	1	5	5	5	5	5	5	5	5
    缺页	√	√	×	√	√	×	√	×	×	√	×	×

    总计6次缺页, 可以发现重点是第五次访问要把 1 换出去, 因为我们知道未来信息 1 不再被用到了

• Belady 异常 (Belady’s Anomaly):

  • 现象: 对于某些置换算法（如 FIFO），增加分配给进程的物理页框数，缺页次数 反而增加 的反常现象。
  • 例子: 序列 1 2 3 4 1 2 5 1 2 3 4 5，FIFO算法。

    • m=3 时，缺页过程:

      访问页面	1	2	3	4	1	2	5	1	2	3	4	5
      页框1	1	1	1	4	4	4	5	5	5	5	5	5
      页框2	-	2	2	2	1	1	1	1	1	3	3	3
      页框3	-	-	3	3	3	2	2	2	2	2	4	4
      缺页	√	√	√	√	√	√	√	×	×	√	√	×

      总计9次缺页

    • m=4 时，缺页过程:

      访问页面	1	2	3	4	1	2	5	1	2	3	4	5
      页框1	1	1	1	1	1	1	5	5	5	5	4	4
      页框2	-	2	2	2	2	2	2	1	1	1	1	5
      页框3	-	-	3	3	3	3	3	3	2	2	2	2
      页框4	-	-	-	4	4	4	4	4	4	3	3	3
      缺页	√	√	√	√	×	×	√	√	√	√	√	√

      总计10次缺页

  • 原因: FIFO 只考虑进来的时间，不考虑进来之后的访问情况。增加页框可能导致一个”坏”的页面（未来会用到）驻留更久，从而在后面挤掉了更有用的页面。
  • LRU 和 OPT 不存在 Belady 异常: 因为它们满足 栈属性 (Stack Property)：即 m 个页框时的内存内容总是 m+1 个页框时内存内容的子集。增加页框只会包含更多有用的页，不会导致缺页增加。

4.5 影响缺页次数的因素#

• 页面置换算法: 好算法 ≈ 少缺页。
• 分配给进程的物理页框数: 太少会导致频繁缺页，过多则浪费内存。存在一个最佳范围。
• 页面尺寸问题:
  • 确定页面大小对于分页的硬件设计非常重要，而对于操作系统是个可选的参数。
  • 要考虑的因素:
    • 内部碎片: 页面越大，内部碎片越多；页面越小，内部碎片越少。
    • 页表长度: 页面越大，页表越小；页面越小，页表越大。
    • 辅存的物理特性: 磁盘传输特性影响最佳页面大小选择。
    • TLB 覆盖范围: 影响地址转换性能。
  • 小页面优缺点:
    • 优点: 减少内部碎片，更适合程序局部性。
    • 缺点: 页表变大，TLB 效率可能降低，磁盘 I/O 效率低。
  • 大页面优缺点:
    • 优点: 页表小，TLB 覆盖范围大，磁盘 I/O 效率高。
    • 缺点: 内部碎片增加，可能不适合小局部性。
  • 最优页面大小: 理论上可以用公式 P = √(2se) 来计算，其中 $s$ 是页表项的大小（表示页表开销），$e$ 是平均程序段大小（表示内部碎片开销）。这个公式平衡了页表大小和内部碎片之间的权衡。
  • 实际实现:
    • Intel 80x86/Pentium: 支持 4KB 或 4MB 页面大小。
    • 现代系统: 通常支持多种页面大小（如 4KB, 2MB, 1GB），为有效使用TLB带来灵活性，但给操作系统带来复杂性。
    • OS 和应用可根据需求灵活选择不同页面大小。
• 程序的编制方法: 访问模式影响局部性。
  • 例子: 只分配了一个 4KB页框，访问按行存储的二维数组 A[1024][1024] (4KB页面)。
    • 按行访问 (方法2): for(i)... for(j)... A[i][j]。空间局部性好，每次访问都在同一页或下一页，缺页少（ 1024 次，每行开始时缺页）。
    • 按列访问 (方法1): for(j)... for(i)... A[i][j]。空间局部性差，每次访问 A[i][j] 和 A[i+1][j] 会跨越多个页面（1024*4 bytes ≈ 1 page），导致大量缺页（1024 * 1024 次）。
• 颠簸/抖动 (Thrashing):
  • 定义: 当系统内存严重不足，分配给进程的页框远小于其活跃页面所需时，进程会不断地发生缺页，大部分时间都用于页面换入换出，而不是真正执行计算。导致系统效率急剧下降。
  • 原因: 并发度过高，或进程所需工作集大于可用内存。
  • 表现: CPU 利用率很低，但磁盘 I/O 非常繁忙。

5. 高级内存管理策略#

5.1 工作集模型 (Working Set Model)#

• 提出者: Denning (1968)
• 基本思想: 基于 程序访问的局部性原理。一个进程在任何时刻都倾向于访问一个相对较小的页面集合，称为 活跃页面 (Active Pages)。如果能将这些活跃页面都保留在内存中，就能显著减少缺页。
• 工作集 (Working Set) W(t, Δ): 在当前时间 t 之前的 时间窗口 Δ 内，进程实际访问过的 虚拟页面 的集合。
  • Δ: 工作集窗口大小，是一个关键参数。
  • 工作集大小 |W(t, Δ)| 随时间动态变化。
• 与驻留集的关系:
  • 驻留集 (Resident Set): 当前时刻，进程 实际 驻留在物理内存中的页面集合。由 OS 分配策略和置换算法决定。
  • 理想状态: 进程的驻留集应包含其当前的工作集 (Resident Set >= Working Set)。
• 工作集策略应用:
  • 置换: 换出不在当前工作集中的页面。
  • 加载控制: 只有当一个进程的工作集能够被完全调入内存时，才激活该进程运行，否则挂起。防止 Thrashing。

5.2 工作集算法 (实现工作集置换)#

• 基本思路: 识别并换出不在当前工作集 (W(t, Δ)) 中的页面。
• 一种实现:
  • PTE 增强: 每个 PTE 增加一个字段，记录该页面的 最后访问时间 (Last Use Time)。
  • 参数: 设置一个时间阈值 T (近似 Δ)。
  • 扫描过程 (类似时钟):
    1. 定期或缺页时扫描页框。
    2. 检查 PTE 的 A 位：
       • 若 A=1: 表示在当前时钟滴答内被访问。记录 当前虚拟时间 到 PTE 的 “最后访问时间” 字段，并将 A 位清零。
       • 若 A=0: 表示在当前滴答内未被访问。计算 页面年龄 (Age) = 当前虚拟时间 - 最后访问时间。
    3. 判断与置换:
       • 如果 Age > T (页面“老”，不在工作集内)：
         • 如果页面是干净的 (D=0)，则该页面是 最佳 牺牲页，直接置换。
         • 如果页面是脏的 (D=1)，先记录下来，继续扫描，希望能找到一个干净的老页面。如果找不到干净的老页面，最后回来置换这个脏的老页面（需要写回磁盘）。
       • 如果 Age ≤ T (页面“年轻”，在工作集内)：保留该页面，继续扫描。
• 讨论:
  • 精确实现工作集算法开销较大（需要记录和比较时间）。
  • 缺页率算法 (Page Fault Frequency - PFF): 一种近似方法。通过监控进程的缺页率来动态调整其驻留集大小。
    • 设置缺页率上限和下限。
    • 缺页率 > 上限: 增加进程的页框数。
    • 缺页率 < 下限: 减少进程的页框数。

5.3 清除策略 (Cleaning Policy)#

• 问题: 当需要空闲页框时，如果选中的牺牲页是 “脏” 的，需要先写回磁盘，增加了缺页处理时间。
• 目标: 保持一定数量的 干净 (Clean) 空闲页框可用。
• 实现: 使用 分页守护进程 (Paging Daemon) (如 kswapd in Linux)。
  • 该进程周期性（或在内存不足时）被唤醒。
  • 检查内存状态，如果空闲页框低于某个阈值。
  • 使用页面置换算法（如 Clock 或 LRU 近似）选择一些页面。
  • 如果选中的页面是脏页，则启动 I/O 将其 提前写回 (Write Back) 磁盘，并将其标记为干净。
  • 这样，未来需要空闲页框时，可以直接使用这些已变干净的页框，或者快速换出它们。
• 双指针时钟 (Two-Handed Clock):
  • 前指针 (Cleaning Hand): 由分页守护进程控制。扫描页框，遇到脏页就启动写回，然后将其标记为干净；遇到干净页则跳过。前指针不断“清洁”页面。
  • 后指针 (Eviction Hand): 由缺页处理程序控制。用于实际选择牺牲页。由于前指针的工作，后指针更有可能遇到干净页面，从而加速缺页处理。

5.4 页缓冲技术 (Page Buffering)#

• 目的: 进一步提高性能，减少因页面换出又立即换回造成的开销。
• 思路:
  • 被置换出的页面 不立即 丢弃或覆盖。
  • 维护两个链表：
    • 空闲页链表 (Free Page List): 存放被置换出的 干净 页面。
    • 修改页链表 (Modified Page List): 存放被置换出的 脏 页面。
  • 这些页面 暂时保留在内存中。
  • 优点:
    • 快速回收 (Soft Fault): 如果进程很快又要访问刚被“置换”到这两个链表中的页面，可以直接将其重新链回进程的驻留集，无需磁盘 I/O。
    • 簇写回 (Cluster Write): 修改页链表中的脏页可以累积起来，成簇地 (in clusters) 写回磁盘，而不是一次只写一页，提高了磁盘 I/O 效率。
• Page Cache (如 OSTEP 23章 提及): 现代 OS 中广泛使用的技术，用于缓存文件数据和匿名页（包括上述缓冲的页面）。
  • 基本概念: 操作系统在物理内存中维护的一个缓存区域，用于存储最近访问的文件数据和元数据。
  • 工作原理:
    • 当进程读取文件时，数据首先从磁盘加载到 page cache，然后再传递给进程。
    • 当进程写入文件时，数据先写入 page cache，标记为”脏”，稍后由后台进程（如 pdflush/flush/kswapd）异步写回磁盘。
    • 后续对相同文件数据的访问可直接从 page cache 获取，避免磁盘 I/O。
  • 管理策略:
    • 使用类似 LRU 的替换算法（如 Linux 的 2Q）决定哪些页面保留在缓存中。
    • 通过 readahead 机制预读文件数据，提高顺序访问性能。
    • 支持 write-back（延迟写）和 write-through（直接写）两种写入策略。
  • 优势:
    • 减少磁盘 I/O: 大幅降低文件操作的延迟，提高系统整体性能。
    • 统一缓存: 在现代系统中，page cache 通常与 buffer cache 统一，形成统一缓存管理。
    • 内存利用: 未使用的物理内存自动用于缓存，提高内存利用率。
  • 2Q 算法: 一种近似 LRU 的页面缓存替换算法，但开销更低且能应对 LRU 不擅长的场景。
    • 基本结构: 维护两个队列:
      • 非活跃队列 (A1): 存放首次访问的页面。
      • 活跃队列 (Am): 存放多次访问的页面。
    • 工作流程:
      • 当页面第一次被访问时，放入非活跃队列 A1 的头部。
      • 当页面在 A1 中再次被访问时，将其从 A1 移除并放入活跃队列 Am 的头部。
      • 当页面在 Am 中被访问时，将其移到 Am 的头部（类似 LRU）。
      • 需要置换页面时，总是从非活跃队列 A1 的尾部选择牺牲页。
      • 定期将活跃队列 Am 尾部的页面移回非活跃队列 A1，以保持整个缓存中约 2/3 的页面在活跃队列中。
    • 优势: 能有效应对扫描型工作负载（如顺序读取大文件）导致的频繁页面互换问题，这类场景下传统 LRU 表现不佳。

5.5 加载控制 (Load Control)#

• 问题: 系统中并发运行的进程过多，总内存需求超过物理内存容量，导致 Thrashing。
• 目标: 控制系统的 并发度 (Multiprogramming Level)，即同时驻留在内存中（活跃）的进程数量。
• 解决方案:
  • 进程挂起/交换 (Process Suspension/Swapping): 当系统负载过高（如通过高缺页率或低 CPU 利用率检测到 Thrashing）时，选择一个或多个进程，将其 所有页面 换出到磁盘（交换区），并将其置于挂起状态。
  • 选择标准: 选择哪些进程挂起？通常选择低优先级进程、长时间阻塞的进程，或者导致最多缺页的进程。
  • 效果: 释放大量内存，降低活跃进程的内存竞争，使剩余进程能够获得足够的工作集空间，恢复系统效率。

6. 内存映射文件 (Memory-Mapped Files)#

6.1 基本思想#

• 允许进程将一个 文件 或文件的一部分直接 映射 到其 虚拟地址空间 的一个区域。
• 映射后，进程可以像访问普通内存（如数组）一样 通过内存读写指令 来访问文件内容，而无需使用 read() / write() 等系统调用。

6.2 工作机制#

• 系统调用: 如 POSIX 的 mmap()。
• 映射建立: mmap() 调用并不立即读取文件内容。它只是在进程的虚拟地址空间中建立一个区域 (vm_area_struct in Linux)，并设置相应的页表项指向 文件 作为后备存储 (Backing Store)。PTE 初始标记为无效。
• 按需调页: 当进程 首次访问 映射区域中的某个地址时，会触发 缺页异常。
• 缺页处理: OS 识别出这是一个映射文件的缺页，计算出该虚拟地址对应文件中的偏移量，然后从 磁盘文件 读取相应的 数据块 (页) 到一个物理页框，并更新 PTE 使其有效。
• 写回:
  • 如果映射是 共享的 (MAP_SHARED)，对内存区域的修改 最终会写回 磁盘上的原始文件（通常在页面换出时、或调用 msync()、或解除映射 munmap() 时）。其他映射同一文件的进程也能看到修改。
  • 如果映射是 私有的 (MAP_PRIVATE)，使用 写时复制 (Copy-on-Write)。首次写入时，会为该进程创建一个私有的页面副本，后续修改只影响此副本，不影响原始文件或其他进程。

一些问题:

• 内核空间共享: 在现代操作系统中，内核空间通常在所有进程间共享
  • 实现方式: 每个进程的页表中，映射到内核空间的部分是相同的，指向同一组物理页框
  • 优势:
    • 减少内存占用：避免为每个进程复制一份内核代码和数据
    • 提高效率：进程切换时无需切换内核部分的地址映射
    • 简化内核访问：系统调用时可以直接访问内核数据结构
  • Linux实现: 通过将所有进程的高地址部分映射到相同的内核物理页面实现
• 减轻页表增长压力的方式:
  • 稀疏地址空间处理:
    • 多级页表 (Multi-level Page Tables): 将页表分为多级，只为实际使用的地址区域分配页表项，避免为整个虚拟地址空间分配连续页表
    • 倒排页表 (Inverted Page Tables): 以物理页框为索引建立表项，每个表项记录映射到该物理页的虚拟页信息，页表大小与物理内存成正比而非虚拟地址空间
• 大页模式 (Huge Pages/Large Pages):
  • 解决的问题:
    • 减少TLB缺失: 使用大页可以增加TLB覆盖范围，单个TLB表项可以映射更大内存区域(如2MB或1GB而非4KB)
    • 减少页表层级: 减少地址转换时的页表遍历层数，降低内存访问延迟
    • 减少页表大小: 相同大小的内存区域需要更少的页表项，节省页表空间
    • 提高内存密集型应用性能: 数据库、科学计算等应用可显著受益
  • 代价:
    • 内部碎片增加: 如果应用只使用大页的一小部分，会造成内存浪费
    • 内存分配挑战: 需要连续的物理内存块，在系统运行一段时间后可能难以满足
    • 页面换出复杂化: 换出一个大页需要更多I/O操作，可能增加延迟
    • 细粒度保护受限: 无法为大页内的不同区域设置不同的访问权限
    • 内存管理复杂性增加: 系统需要同时管理标准页和大页，增加内存管理复杂度

6.3 mmap() 函数 (POSIX 示例)#

void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);

• start: 建议的映射起始虚拟地址 (通常设为 NULL，由内核选择)。
• length: 映射的字节数。
• prot: 内存保护标志 (指定映射区域的访问权限)。
  • PROT_READ: 可读。
  • PROT_WRITE: 可写。
  • PROT_EXEC: 可执行。
  • PROT_NONE: 不可访问。
• flags: 映射类型和选项。
  • MAP_SHARED: 共享映射，修改会写回文件。
  • MAP_PRIVATE: 私有写时复制映射。
  • MAP_ANONYMOUS (或 MAP_ANON): 匿名映射，不关联任何文件，用于分配内存（类似 malloc）。常与 MAP_PRIVATE 结合用于进程的堆、栈、BSS段。
• fd: 要映射的文件描述符。对于匿名映射，此参数忽略（通常设为 -1）。
• offset: 文件内的映射起始偏移量（必须是页面大小的倍数）。

6.4 mmap 与 shm (共享内存) 对比#

• mmap (基于文件):
  • 通信方式: 通过映射 同一个磁盘文件 到不同进程的地址空间实现共享。
  • 持久性: 共享内容与磁盘文件关联，可以是持久的。
  • 使用场景: 共享大文件，IPC，加载动态库，程序加载器。
• shm (System V Shared Memory):
  • 通信方式: 使用 shmget() 创建一个内核管理的 纯内存 共享区域，然后用 shmat() 将其附加到进程地址空间。
  • 持久性: 通常是临时的，与进程生命周期或显式删除 (shmctl with IPC_RMID) 相关，不直接关联磁盘文件。
  • 性能: 可能比基于文件的 mmap 更快，因为它不涉及文件系统开销（除非发生交换）。
  • 大小限制: 受可用物理内存/交换空间限制。

6.5 mmap 相关思考#

• mmap 比物理内存+Swap空间大，是否有问题?
  • 解答: mmap 本身 可以 映射比物理内存+Swap 大得多的文件。mmap 只是建立了虚拟地址到文件内容的 潜在 映射。只有当进程 实际访问 映射区域的页面时，才需要将其调入物理内存。这里需要区分两种情况：
    • 文件映射: 对于映射到文件的页面，文件本身就是这些页面的”后备存储”。当内存不足时，如果这些页面没有被修改过(非脏页)，可以直接丢弃，需要时再从文件重新读取；如果被修改过(脏页)，则需要先写回文件再释放。
    • 匿名映射: 没有关联文件的映射区域(如堆)，必须使用Swap空间作为后备存储。Swap是专门用于存储从内存中换出的页面的磁盘区域。
    因此，文件映射可以超过物理内存+Swap的总大小，因为它使用原始文件作为后备存储。但如果工作集(实际访问的页面总数)超过了物理内存+Swap，系统会发生颠簸(Thrashing)，性能急剧下降，尽管映射本身是合法的。
• 使用 mmap 代替 read/write 进行文件读写的优势?
  • 解答:
    1. 减少数据拷贝: read/write 通常涉及数据在内核缓冲区和用户缓冲区之间的拷贝。mmap 允许进程直接访问内核的页缓存（或直接从磁盘调页），避免了这次拷贝，提高效率，尤其对于大文件或频繁读写。
    2. 简化随机访问: 对于需要频繁在文件中随机定位读写的场景，mmap 将文件视为内存数组，可以通过指针运算直接访问任意位置，代码更简洁，无需管理文件指针和复杂的 lseek 调用。
    3. 内核优化: 内核可以更有效地管理 mmap 区域的页面缓存和预读。

6.6 内存映射文件应用示例#

• 程序加载: 加载可执行文件和动态链接库 (DLLs/SOs) 时，代码段和只读数据段通常通过私有映射 (MAP_PRIVATE) 加载，数据段通过写时复制加载。
• 进程间通信 (IPC): 通过共享映射 (MAP_SHARED) 同一个文件（或匿名映射），实现高效的数据共享。
• 数据库: 像 LMDB (Lightning Memory-Mapped Database) 这样的内存映射数据库，将整个数据库文件映射到内存，利用 OS 的虚拟内存管理进行数据缓存和访问，简化了缓冲管理，提高了 I/O 性能。

7. 虚拟内存管理全貌 (结合进程结构)#

• 进程控制块 (PCB / task_struct in Linux): 包含指向内存描述符 (mm_struct) 的指针。
• 内存描述符 (mm_struct): 描述进程的整个虚拟地址空间，包含指向页表的指针 (如 CR3 指向的页目录物理地址) 和指向虚拟内存区域链表/树 (vm_area_struct list/tree) 的指针。
• 虚拟内存区域 (vm_area_struct - VMA): 描述进程地址空间中一段 连续 的、具有 相同属性 (如权限、映射文件) 的虚拟内存区域。例如，代码段、数据段、堆、栈、每个内存映射文件、每个共享库都对应一个或多个 VMA。
  • 关键字段: 起始地址 (vm_start), 结束地址 (vm_end), 访问权限 (vm_prot), 标志 (vm_flags, 如 VM_READ, VM_WRITE, VM_EXEC, VM_SHARED), 指向映射文件信息的指针 (vm_file) 等。
• 页表 (Page Tables): 将 VMA 内的虚拟页号映射到物理页框号或标记为不在内存。
• 物理内存 (Page Frames): 实际存储数据的内存块。
• 后备存储 (Backing Store): 磁盘上的文件（可执行文件、库、数据文件）或交换空间 (Swap Area)，用于存放不在物理内存中的页面。

交互过程: 访问虚拟地址 -> 查找 VMA -> 查找页表 (TLB first) -> 访问物理内存 / Page Fault -> (缺页处理) -> 访问后备存储。

8. 写时复制 (Copy-on-Write - COW)#

• 目的: 优化资源（特别是内存）的复制过程，推迟实际的物理复制，直到真正需要时才进行。
• 应用场景:
  • fork() 系统调用创建子进程。
  • 私有内存映射 (MAP_PRIVATE)。
• 机制:
  1. 共享初始副本: 当创建副本时（如 fork() 创建子进程），并不立即复制父进程的物理内存页面。而是让子进程的页表项指向与父进程 相同 的物理页框。
  2. 标记为只读: 同时，将这些共享页框在 父子进程的页表项中都标记为只读 (Read-Only)，即使它们原本是可写的。
  3. 写操作触发异常: 如果任何一个进程（父或子）尝试 写入 这些共享的页面，会触发一个 保护性页错误 (Protection Fault)。
  4. 真正复制: 操作系统捕获此异常，识别出是 COW 机制。此时，内核会：
     • 分配一个新的物理页框。
     • 将原始页框的内容 复制 到新页框。
     • 修改 触发写入操作的那个进程 的页表项，使其指向 新复制的页框，并将该页表项的权限 恢复为可写 (Read-Write)。
  5. 恢复执行: 进程继续执行写操作，现在写入的是它自己的私有副本。
• 优点:
  • fork() 效率高: 如果子进程立刻调用 exec() 加载新程序，那么之前的大部分复制就白费了。COW 避免了这种不必要的开销。
  • 节省内存: 只要页面不被修改，父子进程可以一直共享同一物理副本。

9. Windows 虚拟内存管理 (概述)#

(注: 以下内容可能为对 Windows (可能较早版本如 NT/XP/7) 的描述) , 不重要

9.1 Intel x86 虚拟内存机制回顾#

• 保护模式寻址: 使用 段选择符 (Segment Selector) + 偏移量 (Offset) 形成逻辑地址。段选择符指向 段描述符 (Segment Descriptor) (在 GDT/LDT 中)，包含段基址、限长、权限等。逻辑地址 -> 线性地址 (Linear Address)。
• 分页机制: 如果 CR0 寄存器的 PG 位开启，线性地址会被页式机制进一步转换为 物理地址 (Physical Address)。
• 绕过分段: 可以设置段描述符使段基址为 0，限长为 4GB，从而让线性地址等于逻辑地址的偏移量部分，达到“平坦内存模型”的效果。
• 页表结构: x86 支持多级页表 (早期 2 级，x86-64 支持 4 级)。CR3 寄存器指向最高级页表的物理基地址。PTE/PDE 结构包含 PFN, P, A, D, R/W, U/S, PCD, PWT 等位。

9.2 Windows 内存管理器 (Memory Manager)#

• 位置: 位于内核执行体 (Ntoskrnl.exe) 中。
• 主要组成:
  • 执行体系统服务: 提供 API (VirtualAlloc, MapViewOfFile, HeapAlloc 等) 用于虚存分配、回收和管理。
  • 页面错误陷阱处理程序 (MmAccessFault): 处理 MMU 检测到的内存管理异常 (缺页、权限错误)。
  • 后台线程 (关键组件):
    • 工作集管理器 (MmWorkingSetManager): 负责调整进程工作集大小（修整）、老化页面、启动脏页写出等。
    • 进程/栈交换器 (KeSwapProcessOrStack): 负责整个进程或内核线程栈的换入换出 (用于挂起/恢复进程)。
    • 修改页面写出器 (MiModifiedPageWriter): 将“脏”的匿名页面 (来自页文件) 写回到页文件。
    • 映射页面写出器 (MiMappedPageWriter): 将内存映射文件中的“脏”页写回磁盘文件。
    • 零页线程 (MmZeroPageThread): 将空闲页框清零，为按需零页 (Demand-Zero) 提供准备好的页面。

9.3 Windows 地址空间布局 (32-bit 示例)#

• 总览: 4GB 虚拟地址空间。
• 用户空间 (通常 0x00000000 - 0x7FFFFFFF, 2GB):
  • 应用程序代码 (EXE)
  • 动态链接库 (DLL) 代码和数据
  • 进程堆 (Heap)
  • 线程栈 (Stack)
  • 进程环境块 (PEB), 线程环境块 (TEB)
  • 内存映射文件区域
• 系统空间 (通常 0x80000000 - 0xFFFFFFFF, 2GB):
  • 内核代码 (Ntoskrnl.exe), HAL (hal.dll), 内核驱动
  • 页表本身 (自映射区域)
  • 系统缓存 (File Cache)
  • 分页缓冲池 (Paged Pool): 可被换出的内核内存
  • 非分页缓冲池 (Non-Paged Pool): 不能被换出的内核内存 (用于中断处理等)
  • 超空间 (Hyperspace): 临时映射进程页表等
• /3GB 启动选项: 可以修改用户/系统空间划分为 3GB/1GB，让用户进程获得更大地址空间。
• 自映射机制: Windows 将当前进程的 页目录 和 所有页表 映射到系统空间的一个固定虚拟地址范围 (如 0xC0000000 开始)，使得内核可以通过虚拟地址方便地访问任何进程的 PTE/PDE，而无需切换 CR3 寄存器。
  • MiGetPdeAddress(va) 和 MiGetPteAddress(va) 宏利用此机制快速计算给定虚拟地址 va 对应的 PDE 和 PTE 的 虚拟地址。

9.4 Windows 缺页处理#

• 流程:
  1. CPU 访问无效 PTE 地址，触发 0xE 号中断 (Page Fault)。
  2. CPU 将出错的虚拟地址存入 CR2 寄存器。
  3. CPU 跳转到内核的缺页中断处理例程 KiTrap0E。
  4. KiTrap0E 调用核心处理函数 MmAccessFault。
  5. MmAccessFault 读取 CR2，找到对应的 PTE。
  6. 分析 PTE 内容 (即使 P=0，其他位仍有 OS 定义的含义):
     • 页面从未被提交 (Committed): 可能是非法访问。
     • 访问违反权限 (Protection Violation): 如写入只读页。
     • 写时复制 (Copy-on-Write): 执行 COW 操作。
     • 栈扩展 (Stack Expansion): 自动分配并映射新的栈页面。
     • 页面在转换状态 (Transition): 页面正在被 I/O（读入/写出），需等待 I/O 完成。
     • 页面在页文件/映射文件中 (Paged Out): 需要从磁盘调入。
     • 请求零页面 (Demand Zero): 分配一个已清零的物理页框。
  7. 执行相应操作: 分配页框、启动磁盘 I/O、修改 PTE、完成 COW 等。
  8. 返回用户模式，重新执行指令。

9.5 Windows 工作集 (Working Set)#

• 定义: 进程当前驻留在物理内存中的虚拟页面集合 (即驻留集)。
• 类型:
  • 进程工作集: 每个进程私有的。
  • 系统工作集: 内核自身代码和数据（可分页部分）所占用的。
• 管理:
  • 动态调整: 工作集大小是动态变化的，有最小值和最大值限制。
  • 工作集修整 (Trimming): 当系统物理内存紧张时，工作集管理器 会减少某些进程的工作集大小（通常使用 Clock 类似算法移除“最老”的页面），将移除的页面放入 Standby 或 Modified 链表。
  • 自动增长: 进程发生缺页时，如果其工作集大小未达到最大值，且系统有空闲内存，则调入页面会使其工作集增长。

9.6 用户空间内存分配方式#

1. 以页为单位的虚拟内存分配 (VirtualAlloc, VirtualFree):
   • 两阶段:
     • 保留 (Reserve): 在进程虚拟地址空间预留一段范围，不分配物理内存或页文件空间。只是标记地址范围不可用。
     • 提交 (Commit): 为保留的地址空间实际分配物理内存（或页文件支持）。页面首次访问时才会真正调入物理内存（Demand Zero 或从页文件加载）。
   • 虚拟地址描述符 (VAD - Virtual Address Descriptor): 内核为每个进程维护一棵 自平衡二叉树 (VAD Tree)，每个节点描述一段连续的、属性相同的虚拟地址空间（已保留或已提交）。用于快速查找、分配、释放虚拟地址范围。EPROCESS 结构包含指向 VAD 树根的指针。
2. 内存映射文件 (CreateFileMapping, MapViewOfFile):
   • 使用 区域对象 (Section Object) (Win32 API 称之为 File Mapping Object) 实现。
   • CreateFileMapping 创建一个区域对象，可以基于磁盘文件或页文件（用于匿名共享内存）。
   • MapViewOfFile 将区域对象的一部分或全部映射到进程的虚拟地址空间，得到一个 视图 (View)。
   • 通过映射同一区域对象，实现进程间共享内存或文件访问。
3. 内存堆 (Heap) (HeapCreate, HeapAlloc, HeapFree):
   • 用途: 管理 大量、小块 的内存分配。
   • 机制: 进程首先用 VirtualAlloc (通常在进程启动时由系统自动完成，创建默认堆) 分配一大块虚拟内存作为堆区域。然后，堆管理器 (用户模式库或内核函数集) 在这个区域内进一步细分和管理小块内存的分配与释放。
   • 类型: 每个进程有一个 默认进程堆 (GetProcessHeap)。也可以创建额外的 私有堆 (HeapCreate)。

9.7 Windows 物理内存管理#

• 页框号数据库 (PFN Database): 一个 全局数组 (MmPfnDatabase)，数组的每个元素是一个 MMPFN 结构，对应一个物理内存页框。
• MMPFN 结构: 包含该物理页框的所有状态信息，如：
  • 状态 (State): Active, Standby, Modified, Transition, Free, Zeroed, Bad。
  • 链接指针: 用于将处于相同状态的页框链接起来（形成链表）。
  • 指向 PTE 的指针 (如果页面是 Active/Standby/Modified)。
  • 引用计数。
  • 等等。
• 页框状态与链表:
  • Active/Valid: 页面在某个工作集中，PTE有效。
  • Transition: 页面正在进行 I/O。
  • Standby: 页面刚被从工作集移除，内容 干净，PTE 无效但指向此 PFN。可被快速重用 (Soft Fault)。
  • Modified: 页面刚被从工作集移除，内容 脏，PTE 无效但指向此 PFN。重用前需写回磁盘。
  • Free: 页框空闲，内容无效。
  • Zeroed: 页框空闲，且已清零。可立即用于 Demand Zero 页。
  • Bad: 页框硬件损坏，不可用。
  • 链表: 内核维护 FreePageList, ZeroedPageList, StandbyPageList, ModifiedPageList 等链表，通过 MMPFN 中的指针将对应状态的页框链接起来，方便快速查找和管理。
• 状态转换图 (示意): 页面在不同链表和工作集之间根据缺页、写回、清零、置换等操作进行转换。

10. 重点小结#

• 核心概念: 虚拟内存是对物理内存的抽象，提供更大、受保护的地址空间。通过页表和 MMU 实现虚拟到物理地址的转换。
• 关键机制:
  • 分页 (Paging): 将地址空间划分为固定大小的页/页框。
  • 页表 (Page Table): 存储 VPN 到 PFN 的映射及状态位 (P, A, D, Protection)。
  • 多级页表/反转页表: 解决页表过大问题。
  • TLB (快表): 加速地址转换。
  • 缺页异常 (Page Fault): 处理页面不在内存的情况，实现按需调页。
• 重要策略:
  • 置换策略 (Replacement): FIFO, LRU, Clock, Working Set 等，决定牺牲哪个页面。
  • 驻留集管理: 控制进程占用多少物理内存 (Fixed vs. Variable, Working Set)。
  • 清除策略 (Cleaning): 提前写回脏页，保持空闲页框干净。
  • 加载控制: 防止 Thrashing。
• 高级特性:
  • 内存映射文件 (mmap): 高效文件 I/O 和 IPC 机制。
  • 写时复制 (COW): 优化 fork() 和私有映射。
• Windows 特点: VAD 树管理虚拟地址空间，PFN 数据库管理物理页框，多种页面状态链表，工作集模型，多种内存分配 API。