分页

1. 引言：空间管理的挑战与分页的提出

• 背景: 操作系统管理内存空间时面临挑战。传统方法之一是分段 (Segmentation)，将空间划分为不同长度的分片。
• 分段的问题: 主要问题是外部碎片 (External Fragmentation)，即随着时间推移，内存中产生许多不连续的小块空闲空间，难以分配给需要较大连续空间的新请求。
• 分页的提出: 为解决分段碎片问题，提出第二种方法——分页 (Paging)。其核心思想是将虚拟地址空间和物理内存都划分为固定大小的单元。
  • 虚拟地址空间单元：页 (Page)。
  • 物理内存单元：页帧 (Page Frame)。
• 核心问题: 如何通过分页有效实现虚拟内存，并优化其时间和空间开销？

2. 分页：基本概念与优势

• 基本机制: 将进程的虚拟地址空间分割成固定大小的页，物理内存看作是页帧的阵列。操作系统负责将虚拟页映射到物理页帧。
• 示例: 一个64字节的小地址空间，若页大小为16字节，则有4个虚拟页 (VP 0-3)。若物理内存为128字节，则有8个物理页帧 (PF 0-7)。虚拟页可以映射到物理内存中任意可用的页帧，例如 VP0 -> PF3, VP1 -> PF7, VP2 -> PF5, VP3 -> PF2。
• 优势:
  • 灵活性: 不对地址空间的使用方式做假设（如堆栈增长方向），能高效提供地址空间抽象。
  • 简化的空闲空间管理: 操作系统只需维护一个空闲页帧列表，分配时从中取用即可，避免了外部碎片问题。

3. 地址转换过程

• 虚拟地址结构: 虚拟地址被分为两部分：
  • 虚拟页号 (Virtual Page Number, VPN): 用于标识访问的是哪个虚拟页。
  • 页内偏移量 (Offset): 用于标识在选定页内的具体字节位置。
  • 位数关系: 总虚拟地址位数 = VPN位数 + Offset位数。2^(Offset位数) = 页面大小。
• 转换步骤:
  1. CPU生成虚拟地址。
  2. 硬件/操作系统提取VPN和Offset。
  3. 使用VPN查询页表 (Page Table)，找到对应的物理页帧号 (Page Frame Number, PFN)。
  4. 将PFN替换VPN，与Offset组合，形成最终的物理地址 (Physical Address)。
  5. 访问该物理地址。
• 关键: Offset在转换过程中保持不变。

4. 页表：存储、内容与问题

• 页表 (Page Table):
  • 作用: 存储每个进程的虚拟页到物理页帧的映射关系 (地址转换信息)。
  • 存储: 通常是每个进程一个的数据结构。由于可能非常大，页表本身存储在物理内存中（由操作系统管理，后续会讨论更复杂情况，如存储在内核虚拟内存）。
  • 结构: 最简单的是线性页表 (Linear Page Table)，即一个数组，以VPN作为索引。
• 页表项 (Page Table Entry, PTE): 页表中的每个条目，包含：
  • 物理页帧号 (PFN): 核心映射信息。
  • 有效位 (Valid Bit): 标识该映射是否有效。用于支持稀疏地址空间，无效页无需分配物理帧。
  • 保护位 (Protection Bits): 控制对该页的访问权限（读/写/执行）。访问违反权限会触发异常。
  • 存在位 (Present Bit): 标识该页是在物理内存中还是已被换出到磁盘 (Swap)。
  • 脏位 (Dirty Bit): 标识页面被加载入内存后是否被修改过。
  • 参考位/访问位 (Reference/Accessed Bit): 标识页面是否被访问过，用于页面替换算法。
  • (示例) x86 PTE包含 P, R/W, U/S, PWT, PCD, PAT, G, A, D 位及PFN。
• 分页带来的问题:
  1. 空间开销: 页表可能非常大。例如，32位地址空间、4KB页、4字节PTE，每个进程页表需4MB内存。大量进程会导致巨大的内存开销仅用于页表。
  2. 时间开销: 每次内存访问（取指、加载、存储）都需要额外访问一次内存来读取PTE进行地址转换，导致性能显著下降（可能慢一倍或更多）。

5. 性能问题与TLB (Translation Lookaside Buffer)

• 问题: 每次内存访问都查页表（内存访问）太慢。
• 解决方案: 引入硬件缓存——地址转换旁路缓冲存储器 (TLB)，也称地址转换缓存。
• TLB: 一个小型的、快速的、通常是全相联的硬件缓存，存储最近使用的 VPN -> PFN 映射。
• TLB 工作流程:
  1. CPU生成虚拟地址，提取VPN。
  2. 硬件首先检查TLB中是否存在该VPN的映射。
  3. TLB命中 (Hit):
     • 直接从TLB获取PFN。
     • 结合Offset形成物理地址。
     • 访问内存。 (速度快，接近无虚拟化)
     • (需进行权限检查)
  4. TLB未命中 (Miss):
     • 需要访问内存中的页表获取PTE。 (速度慢，产生额外内存访问)
     • (权限检查、有效性检查)
     • 如果有效且权限允许，将查询到的映射加载到TLB中 (可能替换掉一个旧条目)。
     • 重新尝试导致未命中的指令 (此时应该会TLB命中)。
• 性能关键: TLB的性能依赖于程序的局部性 (Locality)：
  • 时间局部性: 最近访问的页很可能再次访问。
  • 空间局部性: 访问某地址后，很可能访问其附近地址（通常在同一页内）。
  • 高TLB命中率 (Hit Rate) 对性能至关重要。数组顺序访问通常表现良好。

6. TLB 管理

• TLB 未命中处理:
  • 硬件管理 (Hardware-Managed, e.g., CISC如x86): 硬件知道页表结构（通过页表基址寄存器，如CR3），自动遍历页表，找到PTE，更新TLB。
  • 软件管理 (Software-Managed, e.g., RISC如MIPS, SPARC): TLB Miss时，硬件触发一个异常/陷阱。操作系统陷阱处理程序负责查找页表，使用特殊指令更新TLB，然后返回并重试指令。
    • 优点: 操作系统可灵活使用任意页表结构；硬件设计更简单。
    • 挑战: 陷阱处理程序本身不能导致TLB Miss（可放物理内存、预留TLB项）；返回时需重试原指令。
• TLB 内容:
  • 典型条目包含: VPN | PFN | 有效位 | 保护位 | 脏位 | ASID (地址空间标识符) 等。
  • 注意: TLB有效位 != 页表有效位。TLB有效位表示该TLB条目是否为有效缓存映射，而页表有效位表示进程是否合法使用该虚拟页。
• 上下文切换时的TLB处理:
  • 问题: TLB中的映射是进程相关的。切换进程时，旧进程的映射对新进程无效。
  • 方案1: 清空TLB (Flush): 每次切换时，将所有TLB条目设为无效。
    • 优点: 简单、保证正确性。
    • 缺点: 新进程运行时会经历大量初始TLB Miss，性能开销大，尤其在频繁切换时。
  • 方案2: 地址空间标识符 (ASID): 在TLB条目中增加ASID字段，用于区分不同进程的映射。
    • 优点: 允许多个进程的映射共存于TLB，减少切换开销。硬件根据当前运行进程的ASID进行匹配。
    • 实现: 操作系统在切换时需设置当前ASID。ASID位数通常有限（如8位），可能需要处理ASID耗尽问题。
    • 共享页: 不同进程可能将不同的VPN映射到同一个PFN（如共享代码库），ASID可以区分这种情况。
• TLB 替换策略: 当TLB满载需要插入新条目时，选择哪个旧条目被替换。
  • 最近最少使用 (LRU, Least-Recently-Used): 替换最长时间未被使用的条目，利用时间局部性。
  • 随机 (Random): 随机选择一个条目替换，简单且能避免特定访问模式下的最差情况（如循环访问N+1页而TLB大小为N）。

7. 空间问题：缩减页表大小

• 问题: 线性页表占用内存过多。
• 解决方案:
  • 7.1 增大页面大小 (Larger Page Sizes)
    • 原理: 页数减少，PTE数量减少，页表变小。
    • 优点: 简单，减小页表大小，同时能提高TLB覆盖范围（一个TLB项能映射更大内存区域）。
    • 缺点: 内部碎片 (Internal Fragmentation) 增加，即分配的页内可能有大量空间未被使用。
    • 应用: 现代系统支持多种页大小，允许特定应用（如数据库）请求大页面以优化性能和TLB效率，但不作为通用解决方案。
  • 7.2 混合分页与分段 (Hybrid Paging and Segmentation)
    • 原理: 每个逻辑段（代码、堆、栈）有自己的页表。段寄存器的基址指向该段的页表，界限寄存器限制页表大小。
    • 优点: 对于段间有大块未使用空间的稀疏地址空间，可以节省大量页表空间（无需为未使用区域分配PTE）。
    • 缺点: 仍依赖分段模型，灵活性受限；页表本身大小不固定，可能引入外部碎片问题（为页表分配空间时）。
  • 7.3 多级页表 (Multi-Level Page Tables)
    • 原理: 将线性页表本身也进行分页。引入页目录 (Page Directory)，其条目 (PDE) 指向页表的页。如果某页页表对应的所有PTE都无效，则不分配该页表页，对应PDE标记为无效。
    • 结构:
      • 二级页表: 虚拟地址分为 页目录索引 | 页表索引 | 偏移量。先查页目录找到页表页的PFN，再查该页表页找到最终PTE。
      • 多级 (>2): 如果页目录本身也太大（超过一页），可以对页目录再进行分页，形成更多层级。目标是让页表结构的每个组成部分（页目录、页表页）都能装入一个物理页帧。
    • 优点:
      • 空间分配与实际使用的地址空间大小成正比，非常适合稀疏地址空间。
      • 页表页可以分散存储在物理内存中，分配管理更方便。
    • 缺点:
      • TLB Miss时开销增大: 需要多次内存访问（查页目录、查页表页）才能获取PTE。这是典型的时间-空间权衡。
      • 实现更复杂: 硬件或OS处理TLB Miss的逻辑更复杂。
    • TLB的重要性: TLB的存在掩盖了多级查找的成本。只有在TLB Miss时才需要执行完整的、较慢的多级查找。
  • 7.4 反向页表 (Inverted Page Tables)
    • 原理: 页表大小与物理内存大小成正比，而不是与所有进程虚拟地址空间总和成正比。只有一个全局页表，每个条目对应一个物理页帧，记录哪个进程 (PID) 的哪个虚拟页 (VPN) 映射到了该帧。
    • 查找: 需要通过 (PID, VPN) 搜索整个表（通常使用哈希表加速）来找到对应的物理帧。
    • 优点: 极大节省页表空间，尤其在物理内存远小于总虚拟地址空间时。
    • 缺点: 地址转换需要搜索（即使有哈希，也比直接索引慢）；实现共享内存相对复杂。
  • 7.5 页表交换到磁盘 (Swapping Page Tables to Disk)
    • 原理: 将页表本身放置在内核虚拟内存中，允许操作系统在内存压力大时，将部分页表页面换出到磁盘。
    • 优点: 能处理极其巨大的页表，即使物理内存有限。
    • 缺点: 访问一个已被换出的页表项时，会触发缺页中断来加载页表页，进一步增加地址转换延迟。

8. 总结

• 分页是现代操作系统实现虚拟内存的核心机制，它解决了分段的外部碎片问题，提供了灵活性和简单的空闲空间管理。
• 分页引入了两个主要挑战：性能开销（地址转换需额外内存访问）和空间开销（页表可能非常大）。
• TLB 通过缓存地址转换，极大地缓解了性能问题，其效率依赖于程序的局部性。TLB管理（未命中处理、上下文切换、替换策略）是关键。
• 多种技术被用于减小页表空间占用，包括增大页大小、混合分段、多级页表、反向页表以及将页表置于可交换的内核虚拟内存中。这些技术往往涉及时间与空间的权衡以及实现复杂度的增加。
• 理解这些机制及其优缺点对于设计和优化操作系统至关重要。