内存扩展机制与策略

1. 引言：从分段到分页

• 背景: 操作系统需要有效管理内存空间。传统分段 (Segmentation) 方法将空间划分为不同长度分片，但易产生外部碎片 (External Fragmentation)，导致内存利用率下降和分配困难。
• 分页的提出 (Paging): 为解决碎片问题，将虚拟地址空间和物理内存都划分为固定大小的单元。
  • 虚拟地址空间单元：页 (Page)。
  • 物理内存单元：页帧 (Page Frame)。
• 核心优势:
  • 消除外部碎片: 固定大小分配，管理简单。
  • 灵活性: 不依赖特定的地址空间使用模式（如堆栈增长方向）。
• 核心挑战: 如何高效、低开销地实现基于分页的虚拟内存。

2. 分页基础：地址转换与页表

• 地址结构: 虚拟地址分为 虚拟页号 (VPN) 和 页内偏移量 (Offset)。
  • 虚拟地址 = VPN + Offset
  • 页面大小 = 2^(Offset位数)
• 地址转换过程:
  1. CPU生成虚拟地址。
  2. 硬件/OS 提取 VPN 和 Offset。
  3. 使用 VPN 查询 页表 (Page Table)，找到对应的 物理页帧号 (PFN)。
  4. 物理地址 = PFN + Offset (Offset不变)。
  5. 访问物理地址。
• 页表 (Page Table):
  • 作用: 存储 VPN 到 PFN 的映射关系。
  • 存储: 通常是每个进程一个的数据结构，存储在物理内存中。
  • 页表项 (Page Table Entry, PTE): 包含 PFN 及关键控制位：
    • 有效位 (Valid Bit): 映射是否有效（支持稀疏地址空间）。
    • 保护位 (Protection Bits): 读/写/执行权限。
    • 存在位 (Present Bit): 页是否在物理内存中（用于支持交换）。
    • 脏位 (Dirty Bit / Modified Bit): 页是否被修改过（用于优化写回）。
    • 参考位 (Reference Bit / Accessed Bit / Use Bit): 页是否被访问过（用于页面替换）。
• 分页带来的初始问题:
  1. 空间开销: 页表可能非常大 (e.g., 32位/4KB页/4B PTE -> 4MB/进程)。
  2. 时间开销: 每次内存访问都需要额外访问内存中的页表，性能损失严重。

3. 性能优化：地址转换旁路缓冲 (TLB)

• 目的: 加速地址转换，避免每次都访问内存中的页表。
• TLB (Translation Lookaside Buffer): 一个小型的、快速的、通常是全相联的硬件地址转换缓存。存储最近使用的 VPN -> PFN 映射及相关位。
• 工作流程:
  1. 提取 VPN。
  2. 硬件优先查询 TLB。
  3. TLB 命中 (Hit): 快速获取 PFN，计算物理地址，访问内存 (性能接近无虚拟化)。
  4. TLB 未命中 (Miss):
     • 访问内存中的页表获取 PTE。
     • 检查 PTE 有效性、权限、存在位 (Present Bit)。
     • 若页存在于内存 (Present=1) 且有效、权限允许：
       • 将映射加载到 TLB (可能替换旧项)。
       • 重新尝试指令 (此时应 TLB Hit)。
     • 若页不在内存 (Present=0): 触发页错误 (Page Fault) (见第6节)。
     • 若无效或权限不足: 触发相应的异常 (段错误/保护错误)。
• TLB 性能: 依赖程序的局部性 (Locality)：
  • 时间局部性: 近期访问的页可能很快再访。
  • 空间局部性: 访问某地址后可能访问其附近地址 (同页)。
• TLB 管理:
  • 未命中处理:
    • 硬件管理 (CISC如x86): 硬件遍历页表，更新TLB。
    • 软件管理 (RISC如MIPS): 硬件触发异常，OS陷阱处理程序查找页表，用特权指令更新TLB，重试原指令。OS可灵活设计页表结构。
  • 上下文切换:
    • 问题: TLB映射是进程相关的。
    • 方案1: 清空 (Flush): 切换时使所有TLB项无效。简单但开销大。
    • 方案2: 地址空间标识符 (ASID): TLB项中加入ASID区分进程。允许多进程映射共存，减少切换开销。
  • 替换策略: TLB满时选择牺牲项 (LRU, Random)。

4. 空间优化：缩减页表大小

• 目标: 解决线性页表占用过多内存的问题。
• 方法:
  • 4.1 增大页面大小:
    • 优点: 页数减少，PTE减少，页表变小；提高TLB覆盖率。
    • 缺点: 内部碎片 (Internal Fragmentation) 增加。
  • 4.2 混合分页与分段:
    • 原理: 每段一个页表，段寄存器存页表基址和界限。
    • 优点: 节省段间未使用空间的页表项。
    • 缺点: 依赖分段模型；页表大小不一可能引入外部碎片。
  • 4.3 多级页表 (Multi-Level Page Tables):
    • 原理: 将页表本身分页，用页目录 (Page Directory) 指向页表页。无效的页表页无需分配。可扩展至更多级。
    • 优点: 页表大小与实际使用内存成比例，支持稀疏空间；页表页可分散存储。
    • 缺点: TLB Miss时需多次内存访问 (时间换空间)；实现更复杂。
  • 4.4 反向页表 (Inverted Page Tables):
    • 原理: 全局页表，大小与物理内存成正比。表项记录 (PID, VPN) -> PFN。
    • 优点: 极大节省空间。
    • 缺点: 查找需搜索 (通常用哈希)；共享实现复杂。
  • 4.5 页表交换到磁盘:
    • 原理: 将页表放入内核虚拟内存，允许其部分页面被换出。
    • 优点: 能处理超大页表。
    • 缺点: 访问被换出的页表项需先将其换入，增加延迟。

5. 超越物理内存：交换机制 (Swapping)

• 目的: 支持比物理内存更大的虚拟地址空间，运行更多/更大的进程。
• 交换空间 (Swap Space): 在硬盘上开辟的用于存储换出页的区域。
• 存在位 (Present Bit): PTE中的关键位，1表示页在物理内存，0表示页在交换空间（或尚未加载）。
• 页错误 (Page Fault): 访问一个存在位为0的页时发生的事件 (注意：页本身是有效的，只是不在内存中)。
• 页错误处理 (由OS完成):
  1. 硬件检测到 Present=0，触发页错误异常。
  2. OS的页错误处理程序 (Page Fault Handler) 接管。
  3. 查找该页在磁盘上的位置 (通常信息存储在PTE的空闲位)。
  4. 寻找一个空闲物理页帧:
     • 如果有空闲帧，直接使用。
     • 如果内存已满，执行页面替换算法 (见第7节) 选择一个牺牲页帧 (Victim Page)。
     • 如果牺牲页是脏页 (Dirty)，需先将其写回 (Write Back) 到交换空间。
  5. 向磁盘发出读请求，将所需页面读入选定的物理页帧。
  6. 进程在此期间阻塞 (Blocked)，OS可调度其他进程运行。
  7. 磁盘I/O完成。
  8. 更新页表项 (PTE): 设置 Present=1，填入新的 PFN，清除原磁盘地址信息。
  9. 唤醒阻塞的进程。
  10. 重新执行导致页错误的指令 (此时应能正常访问)。

6. 管理内存压力：后台交换与水位线

• 问题: 等到内存完全耗尽再启动替换效率不高。
• 解决方案: 维护少量空闲内存。
  • 高水位线 (High Watermark, HW) 和 低水位线 (Low Watermark, LW)。
  • 当空闲页数量低于 LW 时，后台的交换/页守护进程 (Swap/Page Daemon) 被唤醒。
  • 守护进程运行页面替换算法，不断换出 (Page Out) 页面（优先选择非脏页），直到空闲页数量达到 HW。
  • 守护进程随后休眠。
• 聚集/分组写入 (Clustering/Grouping): 后台守护进程可以将多个脏页一次性写入磁盘，提高I/O效率。

7. 核心策略：页面替换算法

• 目标: 在内存满时，选择踢出哪个页帧，以最小化未来页错误次数 (即最大化缓存命中率)。
• 衡量指标: 平均内存访问时间 (AMAT)
  • AMAT = (PHit * T_Memory) + (PMiss * T_Disk)
  • 由于 T_Disk 远大于 T_Memory，即使很小的 PMiss 也会显著增加 AMAT。
• 常用策略:
  • 7.1 最优策略 (Optimal / MIN / Belady's):
    • 原理: 替换掉未来最长时间内不会被访问的页。
    • 特性: 理论上达到最低未命中率。
    • 缺点: 需要预知未来，无法实现，仅用作理论比较基准。
  • 7.2 先入先出 (FIFO):
    • 原理: 替换最早进入内存的页。
    • 优点: 实现简单。
    • 缺点: 可能踢出常用页；受 Belady异常 影响（缓存增大，命中率可能反而下降）。
  • 7.3 随机 (Random):
    • 原理: 随机选择一个牺牲页。
    • 优点: 实现简单，不易陷入最差情况。
    • 缺点: 性能不稳定，不利用访问历史。
  • 7.4 最近最少使用 (LRU - Least Recently Used):
    • 原理: 替换最长时间未被访问的页。基于时间局部性原理。
    • 优点: 通常性能较好，能保留常用页。不受Belady异常影响 (具有栈属性)。
    • 缺点: 完美实现开销大，需要在每次内存访问时更新记录。
  • 7.5 近似 LRU (Approximated LRU):
    • 目的: 在较低开销下获得接近 LRU 的效果。
    • 硬件支持: 使用位/参考位 (Use/Reference Bit)，页被访问时硬件置1，OS负责清零。
    • 时钟算法 (Clock Algorithm):
      • 将所有页帧视为循环列表，用一个指针（时钟指针）指向当前检查的页。
      • 替换时检查指针处的页：
        • 若 Use Bit = 0：找到牺牲页，替换之，指针前进。
        • 若 Use Bit = 1：清零 Use Bit (给它第二次机会)，指针前进，继续查找。
      • 优点: 实现相对简单，避免了完全扫描。
  • 7.6 考虑脏页 (Dirty Bit Consideration):
    • 动机: 踢出干净页 (Clean Page) 比踢出脏页 (Dirty Page) 代价小（脏页需写回磁盘）。
    • 实现: 修改替换算法（如时钟算法）优先选择 Use Bit = 0 且 Dirty Bit = 0 的页。若找不到，再考虑 Use Bit = 0 且 Dirty Bit = 1 的页等。
• 工作负载影响: 不同策略在不同访问模式下表现各异。LRU在有局部性时表现好，但在循环顺序访问时可能表现最差。随机策略表现相对稳定。

8. 其他虚拟内存策略与问题

• 8.1 页选择策略 (Page Selection): 何时加载页。
  • 按需分页 (Demand Paging): 访问时才加载 (最常用)。
  • 预取 (Prefetching): 预测并提前加载可能需要的页 (e.g., 加载P时预取P+1)。
• 8.2 写策略 (Write Policy): 何时写回脏页。
  • 聚集/分组写入: 收集多个脏页批量写入，提高磁盘效率。
• 8.3 抖动 (Thrashing):
  • 现象: 内存严重超额分配，系统花费大量时间在换页上，几乎无法执行有效计算。
  • 原因: 活跃进程的工作集（常用页面集合）总和远大于物理内存。
  • 应对:
    • 准入控制 (Admission Control): 暂停部分进程，减少内存压力。
    • 内存不足杀手 (Out-of-Memory Killer): (如某些Linux版本) 强制杀死内存消耗大的进程（简单粗暴）。
    • 最佳方案: 增加物理内存。

9. 总结

• 分页是现代操作系统虚拟内存管理的核心，提供了灵活性并解决了外部碎片。
• TLB 是关键性能优化手段，利用局部性加速地址转换。
• 通过多级页表、反向页表等技术解决了页表空间过大的问题，通常涉及时间与空间的权衡。
• 交换机制 (Swapping) 配合存在位和页错误处理，实现了超越物理内存的虚拟地址空间。
• 页面替换策略 (如近似LRU/Clock) 在内存压力下，通过利用访问历史（Use Bit, Dirty Bit）来决定牺牲页，以最小化昂贵的磁盘I/O。
• 理解这些机制与策略及其相互作用，对于构建高效、稳定的操作系统至关重要。在现代系统中，由于磁盘访问代价极高，避免频繁换页（尤其是避免抖动）是首要目标，有时增加物理内存是最有效的解决方案。