第七章 内存管理 (Memory Management)

7.1 主内存基础 (Main Memory Fundamentals)

7.1.1 内存管理概述

内存在计算机系统中的重要性

内存是现代计算机系统操作的核心组件。只有主内存和寄存器是CPU能够直接访问的存储器。程序必须从磁盘装入内存才能执行。

指令执行周期 (Instruction-Execution Cycle)

1. 取指令 (Fetch)：CPU根据程序计数器的值从内存中取出指令
2. 译码 (Decode)：对指令进行译码，可能需要从内存中取操作数
3. 执行 (Execute)：执行指令后，结果可能需要存回内存

内存访问速度层次

• 寄存器访问：一个CPU时钟周期
• 主内存访问：多个CPU时钟周期
• 缓存 (Cache)：位于主内存和CPU寄存器之间，弥补速度差异

7.1.2 地址绑定与地址空间

进程的正常执行过程

1. 磁盘上等待被载入内存执行的进程形成输入队列 (Input Queue)
2. 从输入队列中选择一个进程并载入内存
3. 进程从内存中访问指令和数据
4. 进程终止时，其内存空间被声明为可用

地址表示的不同方式

• 符号地址 (Symbolic Address)：源程序中的地址，如 goto loop1
• 可重定位地址 (Relocatable Address)：编译器生成，如“距模块开始14字节”
• 绝对地址 (Absolute Address)：链接编辑器或装载器生成，如 0x0007 4014

地址绑定的三个阶段

1. 编译时绑定 (Compile Time)

   • 内存位置在编译时已知
   • 生成绝对代码
   • 起始位置改变需要重新编译
   • 例：MS-DOS的.COM格式程序

2. 装载时绑定 (Load Time)

   • 编译时内存位置未知，生成可重定位代码
   • 装载时生成绝对代码
   • 起始位置改变只需重新装载

3. 执行时绑定 (Execution Time)

   • 编译和装载时内存位置都未知
   • 运行时才生成绝对代码
   • 进程执行期间可以在内存段间移动
   • 需要硬件支持地址映射（如基址和限长寄存器）

逻辑地址与物理地址

• 物理地址 (Physical Address)：内存单元看到的地址，直接装入内存地址寄存器
• 逻辑地址 (Logical Address)：CPU生成的地址，也称为虚拟地址 (Virtual Address)

在编译时和装载时地址绑定方案中，逻辑地址和物理地址相同。在执行时地址绑定方案中，逻辑地址和物理地址不同。

内存管理单元 (Memory-Management Unit, MMU)

MMU是将虚拟地址映射到物理地址的硬件设备。在简单的MMU方案中，重定位寄存器的值被加到用户进程生成的每个地址上。

7.1.3 内存保护机制

保护需求

• 保护操作系统免受用户进程访问
• 保护用户进程彼此间免受影响
• 确保每个进程有独立的内存空间
• 确定进程合法地址范围
• 确保进程只能访问合法地址

基址和限长寄存器 (Base and Limit Registers)

• 基址寄存器 (Base Register)：包含最小的合法物理内存地址
• 限长寄存器 (Limit Register)：指定地址范围的大小
• CPU硬件将用户模式下生成的每个地址与这些寄存器进行比较

7.1.4 动态加载与链接

动态加载 (Dynamic Loading)

• 程序和数据是否需要全部在物理内存中才能执行？
• 原理：例程在被调用时才被装载
• 优势：更好的内存空间利用率，未使用的例程永远不被装载
• 适用场景：需要大量代码处理不常发生情况时，如错误处理例程
• 系统支持：操作系统提供库例程帮助程序员实现动态加载

静态链接 vs 动态链接

静态链接 (Static Linking)

• 系统语言库被当作其他目标模块处理
• 由装载器合并到二进制程序映像中
• 每个程序必须在可执行映像中包含语言库的副本
• 浪费磁盘空间和主内存

动态链接 (Dynamic Linking)

• 链接推迟到执行时
• 存根 (Stub)：小段代码，包含在每个库例程引用的映像中
• 存根用于定位相应的内存驻留库例程，或在例程不存在时装载库
• 执行存根时，操作系统检查例程是否在进程内存地址中，用例程地址替换存根并执行
• 优势：库更新时，所有引用它的程序自动使用新版本

7.2 连续内存分配 (Contiguous Memory Allocation)

7.2.1 交换技术 (Swapping)

交换的基本概念

交换是将进程临时从内存换出到后备存储器 (Backing Store)，然后再调回内存继续执行的技术。

交换的应用场景

1. 多道程序环境中的时间片轮转

   • 时间片到期时，内存管理器换出正在运行的进程
   • 将另一个进程换入该内存空间

2. 基于优先级的调度算法中的换入换出 (Roll In, Roll Out)

   • 低优先级进程被换出，高优先级进程被装载和执行
   • 高优先级进程结束后，低优先级进程被换回

后备存储器 (Backing Store)

• 快速磁盘，足够大以容纳所有用户的内存映像副本
• 必须提供对这些内存映像的直接访问

就绪队列 (Ready Queue)

由所有内存映像在后备存储器或内存中且准备运行的进程组成。

交换时间考虑

• 上下文切换时间：换出、换入
• 主要时间：传输时间（假设无寻道时间）
• 总传输时间与交换的内存量直接成比例
• 例：进程大小10MB，磁盘传输速度40MB/s，传输时间 = 10/40 = 0.25秒 = 250ms

7.2.2 连续内存分配类型

内存划分

主内存通常分为两个分区：

1. 常驻操作系统：通常在低地址内存，带有中断向量
2. 用户进程：在高地址内存

固定分区 (Fixed-Sized Contiguous Partition)

基本思想：系统生成时将内存分为若干个固定大小的分区

特点：

• 等大小分区或不等大小分区
• 每个分区恰好包含一个进程
• 多道程序度受分区数量限制

优点：

• 实现简单
• 开销小

缺点：

• 内部碎片（分配的内存可能大于请求的内存）
• 进程数量固定

可变分区 (Dynamic Contiguous Partition)

基本思想：动态创建分区，每个进程载入到与其大小完全相同的分区中

空闲块 (Hole)：可用内存块

• 初始时，所有内存都可用，被视为一个大空闲块
• 进程到达时，从空闲块中分配恰好容纳它的内存，剩余部分形成更小的空闲块

7.2.3 内存分配算法

在连续内存分配方案中，当进程需要载入内存时，操作系统需要从一系列空闲内存块（也称为“洞”）中选择一个合适的块来分配。内存分配算法就是解决如何选择这些空闲块的问题。这些算法旨在优化内存利用率和分配效率。

首次适应 (First-Fit)

• 原理：从空闲块链表的开始处查找，分配第一个足够大的空闲块给进程。
• 搜索策略：搜索可以从空闲块集合的开始处开始（每次都从头开始），也可以从上次首次适应搜索结束的地方开始（循环首次适应）。
• 优点：
  • 简单且实现快速，因为它不需要对整个空闲链表进行排序或完全遍历。
  • 倾向于在内存的低地址部分使用空闲块，从而在高地址部分留下更大的空闲块。
• 缺点：
  • 可能导致内存前部出现许多小的、无法使用的空闲块，增加外部碎片。
  • 较小的空闲块可能会被频繁使用，使得查找下一个足够大的空闲块需要更长的遍历时间。

最佳适应 (Best-Fit)

• 原理：遍历整个空闲块链表，选择大小最接近进程请求的空闲块（即，分配足够大的最小空闲块）。
• 搜索策略：需要搜索整个空闲块列表才能找到最匹配的块，除非列表是按大小排序的。
• 优点：
  • 产生最小的剩余空闲块（外部碎片最小化），因此最有效地利用了内存。
• 缺点：
  • 搜索整个列表的开销较大，分配速度相对较慢。
  • 尽管产生的碎片最小，但这些碎片可能是非常小的空闲块，它们几乎无法被后续的进程使用，形成大量的“微小碎片”。

最坏适应 (Worst-Fit)

• 原理：遍历整个空闲块链表，选择最大的空闲块来分配给进程，希望这样能留下一个较大的剩余空闲块，以供未来更大的进程使用。
• 搜索策略：需要搜索整个空闲块列表才能找到最大的块，除非列表是按大小排序的。
• 优点：
  • 试图保留大的空闲块，理论上可以为大型进程提供更好的机会。
• 缺点：
  • 搜索整个列表的开销较大，分配速度相对较慢。
  • 频繁地将最大的空闲块分割，可能导致大的空闲块迅速耗尽，最终反而无法满足大型进程的需求，并产生中等大小的碎片。

性能比较： 在实际应用中，首次适应 (First-Fit) 和 最佳适应 (Best-Fit) 在分配速度和存储利用率方面通常优于 最坏适应 (Worst-Fit)。

• 首次适应通常表现良好，因为它查找速度快，并且在大多数情况下能提供合理的内存利用率。其性能介于最佳适应和最坏适应之间，但在实践中往往是最好的折衷方案，因为它避免了最佳适应的搜索开销和最坏适应可能导致的“大空洞”迅速消失问题。
• 最佳适应尽管在理论上最小化了剩余碎片，但在实践中由于需要遍历整个列表来找到“最佳”匹配，其分配时间成本较高，并且可能导致大量微小的、难以利用的碎片。
• 最坏适应由于其分配策略，通常会导致更多的外部碎片，并且由于需要遍历整个列表，其性能最差。它在实践中很少被使用。

综合来看，首次适应算法通常是实际操作系统中连续内存分配最常用的选择，因为它在效率和内存利用率之间取得了良好的平衡。

7.2.4 碎片问题及解决方案

在连续内存分配方案中，尽管我们有各种分配算法来选择空闲块，但一个普遍且难以避免的问题是内存碎片的产生。碎片会降低内存的利用率，甚至可能导致即使总内存充足也无法满足新的内存请求。

外部碎片 (External Fragmentation)

• 定义：外部碎片是指总的空闲内存空间是足够的，但这些空间不连续，分散在内存的各个地方，无法汇集成一个大的连续块来满足较大进程的需求。当进程被载入和移除内存时，它们会留下大小不一的空闲洞，这些洞随着时间的推移变得越来越小且分散。
• 产生原因：
  • 进程动态地进入和离开内存。
  • 内存分配算法未能有效地合并相邻的空闲块。
  • 当一个大空闲块被分割以满足一个较小的请求后，剩余的部分可能不足以容纳其他较大的进程。
• 影响：导致即使系统拥有大量空闲内存，也可能因为没有足够的“连续”空闲空间而无法分配给需要大块连续内存的进程，从而降低内存利用率和系统吞吐量。
• 50%规则 (Fifty-Percent Rule)：对于首次适应 (First-Fit) 算法，有一个经验性的“50%规则”指出，给定N个已分配的内存块，平均约有0.5N个块会因为外部碎片而无法被有效利用。这意味着将近一半的空闲内存可能因为不连续而“丢失”。

内部碎片 (Internal Fragmentation)

• 定义：内部碎片是指分配给进程的内存空间大于进程实际需要使用的内存空间所造成的浪费。这部分多余的内存空间位于已分配块内部，因此其他进程无法使用它。
• 产生原因：
  • 固定分区分配：当分区大小是固定的，如果进程大小小于分区大小，则分区内部会有未使用的空间。
  • 分页：在分页系统中，内存以固定大小的“页”进行分配。如果一个进程的最后一个页没有完全填满，那么该页的剩余部分就会形成内部碎片。平均来说，每个进程的最后一个页会浪费半页的空间。
  • 伙伴系统（Buddy System）：一种内核内存分配策略，它以2的幂次（如4KB、8KB、16KB等）来分配内存。如果请求的内存大小不是2的幂次，系统会分配下一个最近的2的幂次大小的块，导致内部碎片。
• 影响：浪费内存空间，但与外部碎片不同，内部碎片是可用的，只是没有被进程完全利用。

解决方案

1. 紧凑 (Compaction)

   • 原理：紧凑技术旨在解决外部碎片问题。它通过移动内存中已分配的进程，将所有已使用的内存块集中到一端（例如，低地址端），从而将所有小的、不连续的空闲块合并成一个大的、连续的空闲块。
   • 实现条件：只有当内存的重定位（即进程在内存中的物理地址可以动态改变）是动态的（在执行时绑定）时，才可能进行紧凑操作。这意味着需要硬件支持，如基址寄存器和限长寄存器。
   • 成本：执行紧凑操作的成本非常高。它涉及到大量的数据移动，需要暂停正常的进程执行，这会消耗大量的CPU时间和I/O资源，导致系统性能显著下降。因此，紧凑操作通常只在外部碎片问题变得非常严重时才偶尔执行。

2. 分页 (Paging) 和分段 (Segmentation)

   • 根本解决方案：这两种内存管理方案是设计来根本上解决连续内存分配带来的外部碎片问题的。它们通过允许进程的逻辑地址空间与物理地址空间不连续来工作。
   • 分页 (Paging)：将逻辑内存和物理内存都划分为固定大小的块（页和帧），进程的页可以分散地存放在物理内存的任意可用帧中。这消除了外部碎片，但可能引入内部碎片。
   • 分段 (Segmentation)：将程序划分为逻辑单元（段），每个段可以独立地加载到内存的任何位置。段的大小是可变的，这种方式更符合用户的程序结构。分段可以有效地共享和保护内存，但仍然可能面临外部碎片问题，尽管与连续内存分配相比有所改善。

7.3 分页机制 (Paging System)

7.3.1 分页基本概念

分页的优势

分页是一种重要的内存管理方案，允许进程的物理地址空间是非连续的，避免了连续内存分配的缺点。

基本方法

• 帧 (Frame)：将物理内存分为固定大小的块
• 页 (Page)：将逻辑内存分为相同大小的块
• 页的大小等于帧的大小
• 为装载n页大小的程序找到n个空闲帧

地址转换

CPU生成的每个逻辑地址分为两个部分：

• 页号 (Page Number, p)：逻辑地址的高位部分，用于作为页表 (Page Table) 的索引。页表是一个数据结构，存储了逻辑页与物理帧的映射关系。
• 页偏移 (Page Offset, d)：逻辑地址的低位部分，表示页内地址，即该地址在页中的具体位置。这个偏移量在逻辑地址和物理地址中是相同的。

转换过程：

1. 提取页号和页偏移：当CPU生成一个逻辑地址时，硬件（通常是内存管理单元 MMU）会将其分解为页号 p 和页偏移 d。
2. 查询页表：操作系统为每个进程维护一个页表。页号 p 被用作该页表的索引，找到对应页表项。每个页表项包含了该逻辑页在物理内存中对应的帧号 (Frame Number, f)。
3. 构造物理地址：从页表中获取到帧号 f 后，它与原始的页偏移 d 组合起来，形成最终的物理地址。具体而言，物理地址 = 帧号 (f) × 页大小 + 页偏移 (d)。帧号 f 指示了物理内存中该页的起始位置，而页偏移 d 则指定了在该帧内的具体字节位置。

物理地址包含：

• 帧号 (Frame Number, f)：从页表中获得，指示了数据所在的物理内存块（帧）。
• 页偏移 (Page Offset, d)：与逻辑地址中的相同，指示了数据在物理帧内的具体位置。

7.3.2 分页的特点

碎片问题

• 无外部碎片：分页方案的显著优点是它彻底消除了外部碎片。这是因为物理内存被划分为固定大小的帧，任何一个进程的逻辑页都可以被放置在物理内存中的任何一个空闲帧中，无需寻找连续的内存块。操作系统可以维护一个空闲帧列表，当需要为进程分配内存时，只需从列表中取出可用的帧即可。因此，即使内存中存在许多小的空闲块，它们也都是一个完整的帧，可以被任何一个页所使用，不会出现总空间充足但无法分配的问题。

• 有内部碎片：分页方案仍可能存在内部碎片。这是因为进程的逻辑地址空间是按页大小对齐的。如果一个进程的大小不是页大小的整数倍，那么它在内存中占用的最后一个页（帧）将不会被完全填满。虽然单个进程的内部碎片可能不大，但如果系统中存在大量进程，累积的内部碎片也可能占用可观的内存空间。

页大小选择考虑因素

页（帧）的大小是分页系统设计中的一个关键参数，其选择涉及到多种性能和效率的权衡：

1. 内部碎片：页大小越小，平均每个进程的内部碎片就越少，内存利用率理论上更高。因为浪费的部分是页内未使用的空间，小页意味着这部分浪费的绝对值更小。
2. 页表大小：页大小增加时，一个给定大小的逻辑地址空间所需的页数量就会减少，从而导致页表中的条目数量减少。页表条目减少会使得页表本身的大小变小，减少页表所需的内存空间，并且在进行地址转换时，查找页表的开销（如TLB的命中率）可能更高。
3. 磁盘I/O效率：页大小较大时，每次从磁盘（后备存储器）进行页面调入或调出时，传输的数据量更大。这通常意味着磁盘I/O操作的次数减少，从而提高磁盘I/O的效率和吞吐量，因为磁盘寻道时间和旋转延迟等固定开销在传输大数据量时所占比例更小。

权衡：通常需要在这三者之间进行权衡。过小的页会增加页表大小和I/O次数；过大的页会增加内部碎片。现代操作系统通常采用4KB、8KB或16KB等页大小，以在三者之间取得一个平衡点。

物理内存管理

• 通常每个页表项为4字节长。这意味着一个页表项可以存储一个物理帧的基地址，以及一些标志位（如有效/无效位、读/写权限位、修改位等）。
• 如果一个页表项能指向2^32^个物理页帧中的一个（即页表项中用于表示帧号的部分有32位），并且每个帧的大小（也即页大小）为4KB（2^12^字节），那么系统理论上可以寻址的物理内存总量为 2^32^（帧数） × 2^12^（每帧字节数） = 2^44^字节，即16TB的物理内存。分页机制能够支持非常大的物理地址空间。
• 操作系统需要管理物理内存中的所有空闲帧。通常会维护一个空闲帧列表或位图，以便在需要时快速分配帧，并在页被换出时回收帧。

7.3.3 页表实现

寄存器实现

• 原理：当页表相对较小（例如，只有 256 项或更少）时，整个页表可以存储在专用的高速硬件寄存器中。这意味着页表的所有映射信息都直接位于 CPU 内部或非常靠近 CPU 的地方。
• 优点：
  • 高效且快速：由于页表在寄存器中，CPU 无需进行额外的内存访问即可完成地址转换。这使得逻辑地址到物理地址的转换速度非常快，通常只需一个 CPU 时钟周期。
• 缺点：
  • 昂贵：硬件寄存器非常昂贵，数量有限，这限制了页表的规模。因此，这种方法只适用于页表非常小，即逻辑地址空间相对较小的系统。
  • 不灵活：如果进程的逻辑地址空间需要扩展，或者有大量进程需要维护各自的页表，寄存器实现会迅速变得不可行。
• 示例：早期的系统如 DEC PDP-11 在其内存管理单元中就采用了这种简单的寄存器实现方式来管理页表。

内存实现

• 原理：对于大多数现代计算机系统，特别是那些支持大逻辑地址空间和多任务处理的系统，页表太大而无法完全存储在寄存器中。因此，页表通常存储在主内存中。
• 页表基址寄存器 (Page-Table Base Register, PTBR)：为了定位内存中的页表，CPU 专门设有一个页表基址寄存器 (PTBR)。PTBR 包含当前运行进程的页表在物理内存中的起始地址。当 CPU 需要进行地址转换时，它会使用 PTBR 中的地址来访问主内存中的页表。
• 优点：
  • 灵活性和可扩展性：页表可以存储在主内存中的任何位置，这使得页表的大小可以动态调整，以适应进程不断变化的逻辑地址空间需求。系统可以支持非常大的逻辑地址空间和大量并发进程。
  • 减少上下文切换时间：在进程上下文切换时，操作系统只需简单地改变 PTBR 的值，使其指向新进程的页表即可。这大大减少了上下文切换所需的开销，因为不需要移动整个页表或进行复杂的硬件重配置。
• 缺点：
  • 性能瓶颈（两次内存访问）：这是内存实现页表最主要的缺点。为了获取一个数据字或一条指令，CPU 需要执行两次内存访问：第一次访问内存是为了通过 PTBR 查找页表，获取对应的物理帧号；第二次访问内存才是为了获取实际的数据或指令。这使得内存访问速度减半，成为系统性能的潜在瓶颈。
  • 为了缓解这种性能损失，现代系统普遍引入了高速缓存，特别是 TLB (Translation Look-aside Buffer)，来加速页表的查询过程。

TLB (Translation Look-aside Buffer)

• 联想寄存器：TLB 是一种特殊的、高速的查找硬件缓存（也称为联想存储器或内容寻址存储器 CAM）。它的设计目的是为了克服页表存储在主内存中时，每次内存访问都需要两次内存访问（一次查页表，一次取数据）所带来的性能瓶颈。
• 特性：TLB 比主内存更快，但容量非常有限，通常只包含少量（例如，64 到 1024 项）最近使用过的页表项。TLB 能够同时并行搜索所有存储的条目。

TLB工作机制： 当 CPU 生成一个逻辑地址时，地址转换过程会首先通过 TLB 进行：

1. TLB 查找（并行搜索）：CPU 将逻辑地址中的页号 p 同时发送给 TLB 和内存管理单元 (MMU) 中的页表查找逻辑。TLB 会并行地查找其所有条目，看是否存在与 p 匹配的页号。
2. TLB 命中 (TLB Hit)：
   • 如果页号 p 在 TLB 中找到（即 TLB 命中），TLB 会立即返回对应的物理帧号 f。MMU 将这个帧号 f 与逻辑地址中的页偏移 d 组合，直接形成物理地址，并发送到主内存进行数据访问。
   • 这是一个非常快速的过程，通常只需一个 CPU 时钟周期或很少的几个周期，因为它避免了对主内存的额外访问。
3. TLB 未命中 (TLB Miss)：
   • 如果页号 p 在 TLB 中未找到（即 TLB 未命中），这意味着 TLB 中没有当前所需的页表项。此时，MMU 必须通过页表基址寄存器 (PTBR) 访问主内存中的完整页表，以获取该逻辑页对应的物理帧号 f。
   • 一旦从主内存的页表中获得了帧号 f，MMU 会将这个页号 p 和对应的帧号 f 作为一个新的条目添加到 TLB 中，以便后续对该页的访问能够快速命中。
   • 如果 TLB 已满，需要某种**置换机制（Replacement Policy）**来选择一个现有的 TLB 条目进行替换（例如，最近最少使用 LRU 算法是常见的选择）。
   • 获取帧号 f 后，MMU 同样将帧号 f 和页偏移 d 组合形成物理地址，并访问主内存。
   • TLB 未命中会带来额外的开销，因为它需要两次内存访问（一次查页表，一次取数据），比 TLB 命中慢得多。

地址空间标识符 (Address-Space Identifiers, ASIDs)

在多任务操作系统中，多个进程会共享 CPU，并且它们的页表可能会频繁地加载到 TLB 中。当发生进程切换时，如果没有特殊机制，TLB 中保存的旧进程的页表项就可能与新进程的页表项冲突，导致地址转换错误。为了解决这个问题，通常有两种方法：

1. TLB 刷新 (TLB Flush)：在每次进程上下文切换时，清空整个 TLB。这种方法简单直接，但会带来性能开销，因为新进程在开始执行时会经历一系列 TLB 未命中，需要重新从内存中加载页表项到 TLB。
2. 地址空间标识符 (ASIDs)：一些TLB在每个TLB项中存储一个额外的字段，即地址空间标识符 (ASID)。ASID 是一个唯一的进程标识符，它与页表项一同存储在 TLB 中。这样，TLB 中的每个条目不仅包含页号 p 和帧号 f，还包含该映射所属的进程的 ASID。

ASID 的工作原理和优势：

• TLB 可以同时包含多个不同进程的项：当 CPU 生成一个逻辑地址并将其页号与 TLB 中的条目进行比较时，它不仅仅比较页号，还会比较当前运行进程的 ASID 与 TLB 条目中存储的 ASID。只有当页号和 ASID 都匹配时，才算作 TLB 命中。这允许 TLB 同时缓存来自不同进程的页表项，而不会混淆。
• 为该进程提供地址空间保护：ASID 确保了一个进程无法通过 TLB 访问属于另一个进程的内存空间，即使它们恰好使用了相同的逻辑页号。这增强了内存隔离和系统安全性。
• 减少上下文切换开销：由于 TLB 可以同时存储多个进程的页表项，当进程切换发生时，如果新进程的页表项已经在 TLB 中（并且其 ASID 匹配），则无需刷新整个 TLB。这大大减少了上下文切换的时间，提高了系统的整体性能。只有当新进程的 ASID 不在 TLB 中，或者 TLB 已满需要为新条目腾出空间时，才会进行部分或全部的 TLB 刷新。
• 如果TLB不支持单独的ASID，那么在每次进程切换时，操作系统必须刷新TLB，以避免使用旧进程的过期映射。这强调了 ASID 对于提高 TLB 效率和上下文切换速度的重要性。

有效访问时间计算 (Effective Access Time, EAT)

在引入 TLB 后，内存访问的平均时间会显著缩短。为了量化这种性能提升，我们使用有效访问时间 (Effective Access Time, EAT) 来衡量。

EAT 的定义：EAT 是指 CPU 访问一个内存地址所需的平均时间。它综合考虑了 TLB 命中和未命中的情况以及对应的访问延迟。

关键参数：

• 内存访问时间 (Memory Access Time, ma)：访问主内存一次所需的时间。通常，它是一个固定值（例如，100 纳秒）。
• TLB 查找时间 (TLB Lookup Time, tlb_lookup)：在 TLB 中查找一个页表项所需的时间。TLB 查找通常非常快，可以忽略不计或计为很小的值。
• 页表查找时间 (Page Table Lookup Time, pt_lookup)：在主内存中查找页表所需的时间。这等同于一次内存访问时间 ma。
• TLB 命中率 (Hit Ratio, alpha)：表示在 TLB 中找到所需页表项的概率。例如，如果 alpha = 0.9，表示 90% 的地址转换请求能在 TLB 中命中。
• TLB 未命中率 (Miss Ratio)：1 - alpha，表示在 TLB 中未能找到所需页表项的概率。

EAT 计算公式：

EAT = alpha × (TLB 查找时间 + 内存访问时间) + (1 - alpha) × (TLB 查找时间 + 页表查找时间 + 内存访问时间)

简化后：

EAT = alpha × (TLB 访问时间 + 内存访问时间) + (1 - alpha) × (TLB 访问时间 + 2 × 内存访问时间)

如果我们假设 TLB 查找时间可以忽略不计（即非常接近0），或者将其包含在第一次内存访问中（如果 TLB 和内存访问并行发生），那么公式可以进一步简化为：

EAT = alpha × (内存访问时间) + (1 - alpha) × (内存访问时间 + 页表查找时间)

由于页表查找本身就是一次内存访问，所以：

EAT = alpha × ma + (1 - alpha) × (ma + ma)

EAT = alpha × ma + (1 - alpha) × 2 × ma

EAT = (2 - alpha) × ma (此公式仅在TLB查找时间可忽略，且未命中时需要两次内存访问的情况下成立)

其中：

• alpha (命中率)：在 0 到 1 之间，TLB 命中发生的概率。

• ma (内存访问时间)：单次主内存访问所需的时间。

计算示例：

假设内存访问时间 ma = 100 纳秒，TLB 查找时间可以忽略不计。

1. 命中率 = 0.80 (80%)：

   • 这意味着 80% 的时间会在 TLB 中找到，需要 100 ns 进行内存访问。
   • 20% 的时间未命中，需要 100 ns (查页表) + 100 ns (取数据) = 200 ns 进行访问。
   • EAT = 0.80 × 100 ns + 0.20 × 200 ns = 80 ns + 40 ns = 120 ns。
   • 或者使用简化公式：EAT = (2 - 0.80) × 100 ns = 1.20 × 100 ns = 120 ns。

2. 命中率 = 0.98 (98%)：

   • EAT = 0.98 × 100 ns + 0.02 × 200 ns = 98 ns + 4 ns = 102 ns。
   • 或者使用简化公式：EAT = (2 - 0.98) × 100 ns = 1.02 × 100 ns = 102 ns。

结论：从上述示例可以看出，即使 TLB 未命中率很低，它对有效访问时间的影响也很大。因此，设计一个高命中率的 TLB 对于现代操作系统和硬件的性能至关重要，它能够有效地将内存访问的平均时间从两次内存访问降低到接近一次内存访问的时间。

7.3.4 内存保护与共享

内存保护

通过将保护位与每帧关联来实现：

• 读写或只读或只执行
• 非法访问将被捕获到操作系统

有效-无效位 (Valid-Invalid Bit)

附加到页表中的每个项：

• 有效 (Valid)：表示关联页在进程的逻辑地址空间中，是合法页
• 无效 (Invalid)：表示页不在进程的逻辑地址空间中

共享页面

共享代码：

• 只读（可重入）代码的一个副本在进程间共享
• 共享代码必须出现在所有进程逻辑地址空间的相同位置

私有代码和数据：

• 每个进程保持代码和数据的单独副本
• 私有代码和数据的页面可以出现在逻辑地址空间的任何地方

共享示例：在分时环境中，40个用户执行文本编辑器。一个文本编辑器进程包含150KB代码和50KB数据。

• 无共享：(150KB + 50KB)×40 = 8000KB
• 有共享：50KB×40 + 150KB = 2150KB

7.3.3.1 分层页表 (Hierarchical Paging)

对于拥有非常大的逻辑地址空间（例如 32 位或 64 位地址空间）的系统，如果使用传统的单级页表，页表本身将会非常庞大，甚至可能无法完全放入内存中。为了解决这个问题，现代操作系统普遍采用分层页表的结构，也常被称为"页表的页表"或多级页表。

单级页表的挑战：

• 假设一个 32 位逻辑地址空间，页大小为 4KB (2^12^ 字节)。那么逻辑地址空间可以划分为 2^(32-12)^ = 2^20^ = 1,048,576 个页面。
• 如果每个页表项占用 4 字节，那么一个进程的单级页表将需要 2^20^ * 4 字节 = 4MB 的连续内存空间。对于每个进程都拥有这样一个庞大的页表，内存开销是巨大的，并且很难找到连续的 4MB 空间来存储页表。

分层页表的基本原理： 分层页表将一个庞大的单级页表分解成更小、更易于管理的多个子页表，形成一个树状结构。这样，只有当前正在使用的页表部分才需要驻留在内存中，从而节省了内存空间并简化了管理。

以两级页表为例：

• 一个 32 位逻辑地址（假设页大小为 4KB）被分为三个部分：
  • 外部页表索引 (Outer Page Table Index)：最高位，用于索引外部页表。
  • 内部页表索引 (Inner Page Table Index)：中间位，用于索引内部页表。
  • 页偏移 (Page Offset)：最低位，表示页内偏移。
• 外部页表 (Outer Page Table)：包含指向内部页表（或称为二级页表）的指针。只有当外部页表项指向的内部页表是活跃的（即其对应的逻辑地址空间正在被使用）时，该内部页表才需要被加载到内存中。
• 内部页表 (Inner Page Table)：包含指向实际物理帧的指针。这些是用于最终地址转换的页表。

地址转换过程（以两级页表为例）：

1. 从逻辑地址中提取外部页表索引、内部页表索引和页偏移。
2. 第一次内存访问：使用页表基址寄存器 (PTBR) 中存储的外部页表的物理地址，加上外部页表索引，访问主内存中的外部页表，获取指向相关内部页表的物理地址。
3. 第二次内存访问：使用从外部页表获取的内部页表的物理地址，加上内部页表索引，访问主内存中的内部页表，获取最终的物理帧号。
4. 构造物理地址：将获得的物理帧号与页偏移组合，形成最终的物理地址。

分层页表的优势：

• 节省内存空间：页表不再需要是连续的巨大块。只有实际使用的内部页表才需要驻留在内存中。那些未被进程使用的逻辑地址范围（如稀疏地址空间中的空洞）对应的页表部分根本不需要创建或加载到内存，从而显著减少了页表所需的总内存。
• 灵活性：可以根据需要动态地分配和释放页表的部分，更好地适应进程地址空间的动态增长或收缩。
• 支持更大的逻辑地址空间：通过增加页表的层级（例如，三级、四级页表），可以支持远远大于物理内存的逻辑地址空间，这对 64 位系统尤其重要。

分层页表的缺点：

• 地址转换开销增加：每次地址转换都需要进行多次内存访问（层级数 + 1次）。例如，两级页表需要两次内存访问才能找到物理帧号，再加上一次访问实际数据，总共是三次内存访问（如果TLB未命中）。这会降低地址转换的速度。
• 复杂性增加：实现和管理多级页表比单级页表更复杂。

TLB 在多级页表中的作用： TLB 在多级页表中扮演着更重要的角色。由于每次内存访问可能需要多次页表查询，TLB 的高命中率对于缓解这种性能开销至关重要。如果 TLB 能够命中，那么整个多级页表的查询过程就可以被跳过，从而将地址转换时间降低到接近单次内存访问的时间。

7.4 虚拟内存 (Virtual Memory)

7.4.1 虚拟内存概念与优势

传统内存管理的局限性

传统内存管理方法往往要求整个进程在执行前都在内存中。然而，在许多情况下：

• 程序经常有处理异常错误条件的代码
• 数组、列表和表通常分配比实际需要更多的内存
• 程序的某些选项和功能很少使用

虚拟内存的基本思想

虚拟内存管理 (Virtual Memory Management) 是一种技术，使计算机看起来拥有比实际更多的内存。

核心原理：

• 只有部分程序需要在内存中执行
• 逻辑地址空间可以比物理地址空间大得多

虚拟内存的优势

1. 程序不再受物理内存数量限制
2. 更多程序可以同时运行
3. 装载或交换每个用户程序需要更少的I/O，程序启动更快

虚拟地址空间 (Virtual Address Space)

指进程如何存储在内存中的逻辑视图：

• 包括空洞，称为稀疏地址空间 (Sparse Address Spaces)
• 允许更高效的进程创建
• 允许页面共享，加速进程创建
• 允许地址空间被多个进程共享

虚拟内存实现方式

• 请求调页 (Demand Paging)
• 请求分段 (Demand Segmentation)

7.4.2 请求调页 (Demand Paging)

基本概念

请求调页是虚拟内存系统中一种核心的内存管理技术，其主要目标是使得程序可以仅将其需要的部分载入内存，而不是整个程序都必须驻留在内存中。这极大地提高了内存的利用率，并允许运行比物理内存容量更大的程序。

• 核心思想：只在程序执行过程中真正需要一个页面时，才将其从磁盘（后备存储器）加载到物理内存中。当一个程序启动时，通常只有其起始执行所需的少数页面会被加载。随后的页面会在程序执行过程中按需加载。
• 提高内存利用率：通过只加载活跃使用的页面，可以避免将不常用代码（如错误处理例程、很少使用的功能模块）和数据（如大型数组中未被访问的部分）载入内存，从而节省了宝贵的物理内存空间。
• 允许更大的逻辑地址空间：由于无需将整个程序加载到内存，进程的逻辑地址空间可以远远大于可用的物理内存。这使得程序员可以编写更大的程序，而不必担心物理内存的限制。

惰性交换器 (Lazy Swapper)：

• 传统交换器：在传统的内存管理模型中，当操作系统决定要执行一个进程时，会将其整个内存映像（包括所有代码和数据）从磁盘交换到物理内存中，然后才允许其开始执行。
• 惰性调页器 (Lazy Pager)：与传统交换器不同，惰性调页器（或称为请求调页系统）并不会一次性将整个进程加载到内存。相反，它将进程视为一系列逻辑页面，并且仅在进程实际引用到某个页面时（即需要该页面来执行指令或访问数据时），才将该页面从后备存储器（如硬盘上的交换区）加载到物理内存中。这种“按需加载”的策略是请求调页的基石。

请求调页的硬件支持

1. 页表：每个页表项关联一个有效-无效位

   • v：页面是合法的并在内存中
   • i：页面是非法的或不在内存中

2. 辅助内存：高速磁盘，称为交换空间，保存不在内存中的页面

页错误 (Page Fault)

页错误是请求调页机制中的一个核心事件，也是实现虚拟内存“按需加载”的关键环节。它发生在程序试图访问一个逻辑上合法但当前并未驻留在物理内存中的页面时。

• 定义：当 CPU 生成一个逻辑地址并尝试通过内存管理单元 (MMU) 进行地址转换时，MMU 在查询页表（或 TLB）后，发现对应的页表项中的有效-无效位 (Valid-Invalid Bit) 被设置为 i (无效)。这意味着所需的页面要么是非法的（例如，进程尝试访问超出其分配范围的内存），要么是合法的但当前不在物理内存中。
• 产生原因：
  • 首次访问页面：当进程首次引用某个页面时，该页面尚未被加载到物理内存中，其页表项的有效-无效位最初被设置为 i。
  • 页面被置换到磁盘：如果物理内存不足，之前被加载的页面可能被页面置换算法选中并移到后备存储器（交换空间）中，此时其页表项的有效-无效位会被设置为 i。
  • 非法内存访问：如果进程试图访问一个根本不属于其逻辑地址空间（即操作系统未分配给该进程的区域）的地址，也会触发页错误。在这种情况下，页错误是一种内存保护机制。
• 结果：当 MMU 检测到有效-无效位为 i 时，它会立即生成一个特殊的硬件中断，称为页错误陷阱 (Page Fault Trap)。这个陷阱将控制权从用户进程转移到操作系统内核，由操作系统来处理这个异常情况。

页错误处理步骤

当操作系统接收到一个页错误陷阱时，它会执行一系列复杂的步骤来处理这个事件：

1. 检查引用合法性：操作系统首先会检查导致页错误的逻辑地址是否合法。它会查看进程的内部表（例如，进程控制块 PCB 中的相关信息，如进程的段表或辅助页表），以确定该地址是属于进程的有效逻辑地址空间但页面不在内存中，还是一个非法访问。
   • 无效引用 → 中止：如果地址是非法的（例如，试图访问未分配的内存区域，或者访问权限不匹配，如尝试写入只读页面），操作系统将视为一个致命错误，并中止该进程，可能伴随错误报告。
   • 合法但不在内存中 → 继续第2步：如果地址是合法的，但页面确实不在物理内存中，操作系统则会继续执行调页操作。
2. 定位所需页面：操作系统根据页表项中存储的信息（或者通过其他数据结构，如交换文件表）找到所需页面在后备存储器（通常是硬盘上的交换空间或原始文件系统）中的确切位置。
3. 查找空闲帧：操作系统需要为即将调入的页面在物理内存中找到一个空闲的帧。
   • 如果有空闲帧：操作系统会从维护的空闲帧列表中选择一个可用的物理帧。
   • 如果没有空闲帧：此时物理内存已满。操作系统需要启动页面置换算法 (Page Replacement Algorithm)（如 FIFO、LRU、OPT 等）来选择一个“牺牲帧”——即当前驻留在物理内存中、但可以被置换到后备存储器以腾出空间的页面。如果牺牲帧中的内容被修改过（即“脏页”），则需要先将其写回磁盘（交换空间），然后才能被新页面使用。
4. 页面调入：一旦确定了空闲帧（或牺牲帧），操作系统会发起一个磁盘 I/O 操作，将所需页面从后备存储器读取到选定的物理帧中。
5. 更新页表和帧表：在页面成功加载到物理内存后，操作系统会更新相关的内存管理数据结构：
   • 页表：将该页面的页表项中的有效-无效位设置为 v (有效)，并更新其对应的帧号，指向新加载页面所在的物理帧。
   • 帧表：如果操作系统维护了帧表（用于记录每个物理帧的使用情况），也会相应地更新该帧的状态，标记其为已占用并关联到对应的逻辑页。
   • TLB：如果使用了 TLB，该页的新映射关系（页号和帧号）也会被添加到 TLB 中，以便后续对该页的访问能够快速命中。如果 TLB 已满，可能会涉及 TLB 条目置换。
6. 重新启动引起页错误的指令：一旦页面被成功加载到内存，并且所有相关的页表和数据结构都已更新，操作系统会将控制权返回给用户进程。CPU 会重新执行导致页错误的指令。由于现在所需的页面已在内存中，该指令将能够正常完成执行，进程可以继续运行。

纯请求调页 (Pure Demand Paging)

纯请求调页是一种极致的请求调页策略，其特点是在进程开始执行时，没有任何页面预先被加载到物理内存中。进程的运行完全依赖于页错误机制来按需加载页面。

• 工作方式：当一个程序开始执行时，它的所有逻辑页表项的有效-无效位都初始化为 i (无效)。程序执行的第一个指令必然会导致页错误，操作系统会处理这个错误并加载所需的第一个页面。随后，只有当 CPU 尝试访问一个当前不在内存中的页面时，才会触发页错误，进而将该页面调入内存。
• 优点：
  • 最大化内存利用率：只有进程实际访问的页面才会被加载到物理内存中，这意味着内存中不会有任何未被使用的页面浪费空间。对于那些大部分代码或数据不常被访问的程序（例如，包含大量错误处理代码、不常用功能或大型稀疏数组的程序），这种策略能够极大地节省物理内存。
  • 加速程序启动：由于程序启动时不需要加载整个程序或大量页面，可以显著减少程序的启动时间。因为只有最少量的启动页面需要从磁盘加载。
  • 支持更大的逻辑地址空间：纯请求调页允许进程的逻辑地址空间远远大于可用的物理内存。程序员可以编写非常大的程序，而不用担心系统物理内存的限制，因为只有一小部分会在任何给定时间驻留在内存中。
• 缺点：
  • 初始页错误开销：程序启动时会立即产生一系列的页错误，这些页错误处理会带来一定的开销，包括磁盘I/O和CPU时间。在程序运行的早期阶段，页错误率可能会相对较高。
  • 可能导致频繁的页错误：如果程序的工作集（即在给定时间内频繁访问的页面集合）变化频繁，或者工作集的大小超过了分配给进程的物理帧数，可能会导致频繁的页错误，从而降低系统性能（即抖动现象）。

尽管有初始开销，但纯请求调页在现代操作系统中通常被视为高效的虚拟内存管理方式，因为它与程序的局部性原理高度契合，并能有效利用有限的物理内存资源。

指令重新执行 (Restart Instruction)

在请求调页系统中，页错误可能在程序执行的任何时刻发生，甚至在一条指令执行到一半时。当页错误发生时，操作系统会介入处理，在页面调入内存后，原始的指令需要从头开始重新执行，以确保程序的正确性。这对于原子性操作的指令尤为关键。

• 必要性：

  • 指令的原子性：许多机器指令设计为原子操作，意味着它们要么完全执行成功，要么完全不执行。如果在指令执行过程中（例如，在访问多个操作数时）发生页错误，该指令的执行状态会变得不确定。为了维护指令执行的正确性和原子性，最好的做法是保存进程的完整状态，处理页错误，然后让该指令从头开始重新执行。
  • 状态保存：当页错误陷阱发生时，CPU 和操作系统会保存当前进程的完整上下文，包括程序计数器（PC）、所有通用寄存器的值、条件代码以及任何其他与指令执行相关的状态信息。这些保存的状态使得指令可以在页错误处理完成后，准确地从中断的地方（或从指令的开始）恢复执行。

• 重新执行过程：

  • 页错误处理完成后（即所需页面已成功加载到物理内存中），操作系统会将控制权返回给用户进程。它会通过恢复之前保存的程序计数器，使得 CPU 再次指向导致页错误的指令的起始位置。
  • CPU 再次尝试执行该指令。由于此时所需的页面已在内存中，指令将能够顺利地完成其所有操作，而不会再次触发页错误（除非在指令执行过程中又遇到了新的、不在内存中的页面）。

• 最坏情况示例：考虑一个机器指令，如 *C = *A + *B; （表示将内存地址 A 和 B 的内容相加，结果存入内存地址 C）。这条指令可能涉及到多次内存访问：

  1. 取指令并译码：从内存中读取指令本身。
  2. 取A：访问内存地址 A 以获取其内容。
  3. 取B：访问内存地址 B 以获取其内容。
  4. A和B相加：执行算术运算。
  5. 将和存储在C中：将计算结果写入内存地址 C。

  如果在指令执行到第 5 步（将和存储到 C 中）时，发现地址 C 对应的页面不在内存中，就会发生页错误。此时，操作系统会处理页错误，将 C 所在的页面调入内存。处理完成后，操作系统会让 CPU 重新执行 *C = *A + *B; 这条指令。这意味着 CPU 会重新从第 1 步开始执行，再次读取指令，再次访问 A 和 B，然后再次进行加法运算，最后将结果存入 C。尽管这看起来有些重复，但它确保了指令的原子性和结果的正确性。在实际系统中，硬件和操作系统会协同工作，尽可能高效地处理这种情况。

请求调页的性能

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

• 设p为页错误概率（0 ≤ p ≤ 1）
• EAT = (1-p) × (内存访问时间) + p × (页错误时间)
• 如果p = 0，无页错误
• 如果p = 1，每次引用都是错误
• 大多数时候，p非常接近0

7.4.3 写时复制 (Copy-on-Write)

概念

写时复制 (COW) 允许父进程和子进程（或其他共享内存的实体）最初共享内存中的相同页面。这些共享页面被标记为“写时复制”页面。这意味着多个进程可以同时读取这些页面，但如果任一进程尝试写入这些页面时，系统会触发一个机制来创建该页面的私有副本，从而保护原始页面的内容不被修改，同时允许修改发生在私有副本上。

工作机制

1. 进程创建（例如 fork()）：

   • 当一个父进程通过 fork() 系统调用创建一个子进程时，操作系统并不会立即复制父进程的所有内存页面到子进程的新地址空间中。
   • 相反，父子进程会共享所有可写的内存页面，但这些页面会被标记为“只读”或“写时复制”。
   • 此时，物理内存中只有一份这些页面的副本，节省了大量的内存空间和复制时间。

2. 页面修改：

   • 如果父进程或子进程中的任何一个尝试对这些共享的“写时复制”页面进行写入操作，硬件会检测到这次写入，并触发一个写保护错误（类似于页错误）。
   • 操作系统内核会介入处理这个错误。它会为尝试写入的进程创建一个该共享页面的私有副本。这个副本被放置在一个新的物理帧中。
   • 然后，该进程的页表会更新，将其逻辑页映射到这个新的私有物理帧。
   • 一旦副本创建完成，写入操作就会在新创建的私有页面上进行，而不会影响到原始共享页面和其他进程。

优势

• 提供快速进程创建并最小化新页面的数量：这是写时复制最显著的优势。如果 fork() 每次都完整复制父进程的所有内存，那么创建子进程的开销将非常大。COW 避免了不必要的页面复制，特别是当子进程紧接着执行 exec() 系统调用加载新程序时（在这种情况下，子进程的整个地址空间都会被新程序的代码和数据覆盖，之前的复制就完全是浪费）。
• 节省内存空间：只有当页面真正需要被修改时才进行复制，这在多个进程共享大量相同代码和数据（如标准库、只读数据段）的场景下，能够显著减少物理内存的使用量。
• 适用于 exec() 场景：在 Unix-like 系统中，fork() 后通常会紧接着 exec()。在这种模式下，COW 的优势尤为突出，因为子进程在 exec() 之前几乎不需要修改任何页面，从而避免了大量无用的页面复制。

vfork() (作为对比和特殊情况)

• vfork() 是 fork() 的一个变种，它进一步优化了进程创建。
• 原理：vfork() 不会复制父进程的页表，甚至不会使用写时复制。它会暂停父进程，并让子进程直接使用父进程的地址空间。
• 特点：
  • 非常高效：因为没有页面复制，也没有写时复制的开销。
  • 危险：如果子进程在调用 exec() 之前对父进程地址空间中的任何页面进行了修改，那么父进程恢复执行后将看到这些改变。这可能导致父进程的数据损坏或不可预测的行为。
  • 适用场景：vfork() 主要用于子进程创建后立即调用 exec() 的情况，在这种情况下，子进程的地址空间很快就会被替换，因此对父进程内存的潜在修改风险很低。

7.4.4 页面置换算法

页面置换的必要性

当没有空闲帧时会发生什么？

• 假设有40帧，一个10页的进程实际只使用5页，可以运行8个进程而不是4个
• 如果增加多道程序度，会过度分配内存
• 如果运行6个进程，需要60帧，但只有40帧可用

页面置换的选择

1. 终止用户进程
2. 交换出一个进程，释放其所有帧，降低多道程序度
3. 执行页面置换

基本页面置换流程

1. 在磁盘上找到所需页面的位置
2. 找到空闲帧：
   • 如果有空闲帧，使用它
   • 如果没有空闲帧，使用页面置换算法选择牺牲帧
3. 将所需页面读入新空闲的帧，更新页表和帧表
4. 重新启动进程

修改位 (Modify Bit) 的优化

• 每个页面或帧可能有一个硬件相关的修改位（脏位）
• 页面中的任何字或字节被写入时设置修改位
• 如果已修改，页面换出和页面换入
• 如果干净，只需页面换入

主要页面置换算法

1. 先进先出 (FIFO) 算法

原理：先进先出（FIFO）算法是最简单的页面置换算法之一。它基于这样的思想：最早进入内存的页面，当需要置换时，最有可能被淘汰。换句话说，它像一个队列，新页面从队尾进入，最老的页面从队头离开。

实现：通常使用一个 FIFO 队列来管理内存中的页面。每当一个页面被加载到内存时，其页号被添加到队列的尾部。当发生页错误且没有空闲帧时，队列头部的页面（即最先进入内存的页面）被选中作为牺牲页面并被置换出去，然后新的页面进入队列尾部。

特点：

• 易于理解和实现：逻辑简单，管理开销小。
• 性能不总是最优：由于它只考虑页面进入内存的时间，而忽略了页面的实际使用频率。这意味着它可能错误地置换掉那些虽然进入内存早但被频繁使用的重要页面，导致较高的页错误率。
• 可能出现 Belady 异常：这是 FIFO 算法的一个著名缺陷。Belady 异常指的是在某些情况下，为进程分配更多的物理内存帧（即增加内存容量），反而会导致更多的页错误。这是一个反直觉的现象，说明 FIFO 算法在某些工作负载下表现不佳。

示例：假设内存有3个帧，页面引用串为 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。

引用串	帧1	帧2	帧3	页错误
1	1			Yes
2	1	2		Yes
3	1	2	3	Yes
4	4	2	3	Yes (1被淘汰)
1	4	1	3	Yes (2被淘汰)
2	4	1	2	Yes (3被淘汰)
5	5	1	2	Yes (4被淘汰)
1	5	1	2	No
2	5	1	2	No
3	3	1	2	Yes (5被淘汰)
4	3	4	2	Yes (1被淘汰)
5	3	4	5	Yes (2被淘汰)
总页错误数：9次。

2. 最优 (OPT) 算法 (Optimal Page Replacement Algorithm)

原理：最优（OPT）算法是一种理想化的页面置换算法。它的核心思想是：当需要置换页面时，选择在未来最长时间内不会被使用的页面将其淘汰。这样可以最大限度地减少未来的页错误次数。

特点：

• 最低页错误率：这是所有页面置换算法中理论上性能最好的，能够产生最少的页错误。因此，它也常被称为理想算法或最优算法。
• 无 Belady 异常：最优算法不会出现 Belady 异常现象，增加内存帧总能减少或保持页错误数不变。
• 难以实现：因为需要预知未来，即了解程序在未来将访问哪些页面以及何时访问。这在实际操作系统中是不可能实现的。操作系统无法预知程序未来的行为。
• 可用于比较研究：虽然无法实际部署，但 OPT 算法常被用作衡量其他页面置换算法性能的基准。它可以用来评估其他算法的“效率”，即它们距离最优性能有多远。

示例：假设内存有3个帧，页面引用串为 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。

引用串	帧1	帧2	帧3	页错误	淘汰页面（未来最久不用）
1	1			Yes
2	1	2		Yes
3	1	2	3	Yes
4	1	2	4	Yes (3被淘汰，因为它在未来最久不用)	3
1	1	2	4	No
2	1	2	4	No
5	1	2	5	Yes (4被淘汰，因为它在未来最久不用)	4
1	1	2	5	No
2	1	2	5	No
3	1	3	5	Yes (2被淘汰，因为它在未来最久不用)	2
4	1	3	4	Yes (5被淘汰，因为它在未来最久不用)	5
5	1	3	5	Yes (4被淘汰，因为它在未来最久不用)	4
总页错误数：7次。显然，比FIFO算法的9次要少。

3. 最近最少使用 (LRU) 算法 (Least Recently Used Algorithm)

原理：最近最少使用（LRU）算法基于程序的局部性原理，认为最近被使用的页面在未来也很有可能被再次使用。因此，当需要置换页面时，选择在最近一段时间内最久未被使用的页面将其淘汰。它的基本思想是用最近的过去近似最近的将来。

特点：

• 无 Belady 异常：LRU 算法不会出现 Belady 异常现象，分配更多的帧总能获得更少的页错误或保持不变。
• 性能良好：LRU 通常被认为是性能较好的页面置换算法，因为它能够有效地利用程序的局部性，在大多数情况下能提供接近最优算法的性能。
• 实现开销较大：纯 LRU 算法的实现相对复杂，因为它需要精确记录页面被“使用”（访问）的时间或顺序。这需要硬件支持或复杂的软件维护开销。

实现方法：

1. 计数器 (Counters)：
   • 为每个页表项关联一个时间戳或计数器。每当页面被引用时，将系统时钟的当前值（或一个递增的逻辑计数器值）复制到该页表项的计数器中。
   • 当需要进行页面置换时，遍历所有页表项，选择计数器值最小（即最后一次使用时间最久远）的页面进行淘汰。
   • 缺点：每次内存访问都需要更新时间戳，这会带来较大的开销，需要硬件支持（如高速时钟寄存器），并且在选择牺牲页面时需要扫描所有页表项。
2. 栈 (Stack)：
   • 维护一个页面号的栈（通常使用双向链表实现），栈顶表示最近使用的页面，栈底表示最久未使用的页面。
   • 每当一个页面被引用时，就将该页面的页号从栈中移除，然后将其放置到栈顶。这个操作需要 O(N) 时间（N为页面数）。
   • 当发生页错误且没有空闲帧时，选择栈底的页面（即最久未使用的页面）进行置换。
   • 优点：栈底的页面可以直接获取，避免了扫描。
   • 缺点：每次页面引用都需要在栈中进行查找和移动操作，对性能有一定影响。对于较大的内存，维护这个栈的开销会变得显著。

示例：假设内存有3个帧，页面引用串为 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。

引用串	帧1	帧2	帧3	页错误	淘汰页面（最近最久未使用）
1	1			Yes
2	1	2		Yes
3	1	2	3	Yes
4	4	2	3	Yes (1被淘汰)	1
1	4	1	3	Yes (2被淘汰)	2
2	4	1	2	Yes (3被淘汰)	3
5	5	1	2	Yes (4被淘汰)	4
1	5	1	2	No
2	5	1	2	No
3	5	3	2	Yes (1被淘汰)	1
4	5	3	4	Yes (2被淘汰)	2
5	5	3	4	No
总页错误数：8次。比FIFO好，但比OPT略差。

4. LRU近似算法 (LRU Approximation Algorithms)

由于纯 LRU 算法的实现开销较大（需要硬件支持或复杂的软件维护），现代操作系统通常采用一些近似 LRU 的算法，它们通过较少的硬件支持和更低的开销来达到与 LRU 相似的性能。

引用位 (Reference Bit)：

• 这是大多数 LRU 近似算法的基础。
• 在页表中的每个页表项（或在每个物理帧的数据结构中）关联一个额外的位，称为引用位 (Reference Bit)，初始时所有引用位都被设置为 0。
• 每当硬件（通常是 MMU）访问（读或写）一个页面时，就会自动将该页面对应的引用位设置为 1。

附加引用位算法 (Additional-Reference-Bits Algorithm)：

• 这个算法利用引用位来记录更长时间的使用历史。
• 为内存中的每个页面额外保留一个 8 位字节（或更多位）作为历史记录。这个字节可以看作是页面的“使用历史寄存器”。
• 操作系统会定期（例如，通过定时器中断，每隔 100 毫秒或一个固定的时间周期）执行以下操作：
  1. 将每个页面的当前引用位的值（0 或 1）移入其 8 位历史字节的最高位（最左边）。
  2. 然后将历史字节中已有的位整体向右移动一位。
  3. 丢弃最低位。这个过程就像一个移位寄存器。
• 这样，这 8 位字节就包含了页面在最近 8 个时间段内（例如，最近 800 毫秒）的使用历史。值越接近 11111111（二进制），表示该页面在最近的时间段内被频繁引用；值越接近 00000000，表示该页面越久未被引用。
• 当需要进行页面置换时，选择 8 位历史字节值最小（即引用历史最不活跃）的页面进行淘汰。这种方法简单有效，因为它将复杂的时间顺序比较转化为简单的整数比较。
• 优点：提供比简单引用位更精细的使用历史信息，性能接近 LRU，而开销远小于纯 LRU。它在性能和实现复杂度之间取得了很好的平衡。

二次机会 (Second-Chance) 算法 / 时钟算法 (Clock Algorithm)：

• 二次机会算法是 FIFO 算法的改进版，它利用引用位来避免频繁置换那些刚进入内存但很快又被使用的页面。它通常通过一个循环队列（像时钟的指针一样）来实现，因此也常被称为时钟算法或近似 LRU 算法。
• 实现：
  1. 所有在内存中的页面被组织成一个循环队列（或链表），一个“时钟指针”（或称“扫描指针”）指向队列中的某个页面。
  2. 当需要置换页面时，算法从时钟指针指向的当前页面开始检查：
     • 检查引用位：如果当前页面的引用位为 0（表示最近未被使用过），则该页面被选中作为牺牲页面并被置换。然后，新页面被放入该位置。
     • 如果引用位为 1：如果引用位为 1（表示最近被使用过），则将该引用位清零（设置为 0），并给该页面“第二次机会”，即不立即置换它。然后，时钟指针向前移动到队列中的下一个页面，继续检查。这个过程循环进行，直到找到一个引用位为 0 的页面。
  3. 如果一轮遍历后所有页面的引用位都为 1，那么所有页面的引用位都会被清零，算法会再次从头开始，最终会置换掉第一个被检查到的页面（因为它的引用位在第二轮检查时已经变为 0）。
• 优点：
  • 实现简单，开销小。它避免了纯 LRU 那种复杂的排序或链表维护。
  • 性能优于纯 FIFO，因为它能识别并保留那些被频繁使用的页面。
  • 通常不会出现 Belady 异常（但在某些特定且非常罕见的引用串下，理论上仍可能出现）。
• 缺点：
  • 虽然比 FIFO 好，但性能通常不如纯 LRU 或附加引用位算法。它的精确度不如 LRU。
  • 在最坏情况下，可能需要多次遍历才能找到牺牲页面，导致一些性能开销。

最不常用 (LFU) 算法 (Least Frequently Used Algorithm)

• 原理：最不常用（LFU）算法通过计数来记录每个页面被访问的次数。当需要置换页面时，选择访问次数最少的页面将其淘汰。
• 实现：为每个页表项关联一个计数器。每次页面被引用时，其计数器加1。当需要置换时，扫描所有计数器，选择计数值最小的页面。
• 特点：
  • 优点：能够识别那些长期不被访问的“冷”页面。对于那些访问频率非常稳定的程序，可能表现良好。
  • 缺点：
    • 实现开销大：每次页面访问都需要更新计数器，并且在置换时需要扫描所有计数器，开销较高。
    • 无法反映近期使用情况：一个页面可能在早期被频繁访问过，导致其计数值很高，但之后可能很长时间不再被使用。LFU 无法很好地处理这种情况，因为它不考虑访问的“新旧”程度，只关注总次数。
    • 启动问题：新进入内存的页面，即使很快被频繁使用，其计数器值也可能暂时很低，容易被误淘汰。
  • 通常不如 LRU 及其近似算法：由于其不能很好地反映时间局部性，并且维护开销高，LFU 在实际操作系统中不如 LRU 及其近似算法常用。

7.5 高级内存管理

7.5.1 帧分配策略

最小帧数

必须有足够的帧来保存任何单个指令可能引用的所有不同页面，由体系结构定义：

• PDP-11：2页
• IBM 370的MVC：6页或8页（最坏情况）

最大帧数

由可用物理内存数量定义。

分配方案

固定分配

1. 等分分配：例如，100帧和5个进程，每个进程分配20帧
2. 比例分配：根据进程大小分配
   • 公式：$a_i=(s_i/S)\times m$
   • 其中 $s_i$ 是进程 $i$ 的大小，$S$ 是所有进程大小之和，$m$ 是帧总数

优先级分配

使用基于优先级而不是大小的比例分配方案。

全局置换 vs 局部置换

局部置换 (Local Replacement)：

• 进程只能从自己分配的帧集合中选择置换帧
• 不能增加分配的帧数
• 不受外部环境影响

全局置换 (Global Replacement)：

• 进程可以从所有帧的集合中选择置换帧，即使该帧当前分配给其他进程
• 可以增加分配的帧数
• 更大的系统吞吐量
• 无法控制页错误率
• 受外部环境影响
• 一般来说，全局置换更好

7.5.2 抖动现象与防护

抖动的定义

如果进程花在分页上的时间多于执行时间，该进程就在抖动 (Thrashing)。

抖动的原因

• 如果进程没有足够的页面，它会很快发生页错误
• 必须置换一些页面，但被置换的页面正在使用中，可能立即被调回
• 页错误率非常高，导致抖动

抖动产生的过程

1. CPU利用率低时，操作系统引入新进程增加多道程序度
2. 新进程会从其他进程夺取帧（通过全局置换）
3. 但这些进程也需要那些页面，也会发生错误
4. 进程排队等待分页设备，分页设备忙于页面换入换出
5. CPU利用率下降 → 抖动

防止抖动的方法

1. 局部置换算法

• 如果一个进程开始抖动，它不能从其他进程偷取帧
• 但问题没有完全解决，抖动进程忙于换入换出会增加页错误的平均时间

2. 工作集策略 (Working-Set Strategy)

为了防止系统发生“抖动”（Thrashing），即进程把大量时间花在页面的换入换出而不是执行有效工作上，操作系统需要一个机制来确保每个进程都拥有其正常运行所需的足够内存（帧）。“工作集策略”就是其中一种非常有效的方法。

局部性模型 (Locality Model)：

• 基本思想：程序在执行时，并不会随机地访问内存中的任何位置。在某一段时间内，它只会频繁地访问一小部分代码和数据。这种现象被称为局部性原理 (Principle of Locality)。
• 两种局部性：
  • 时间局部性 (Temporal Locality)：如果一个内存位置在某个时间点被访问，那么在不久的将来，它很可能再次被访问。例如，循环中的指令、常用的变量。
  • 空间局部性 (Spatial Locality)：如果一个内存位置被访问，那么它的附近（相邻的内存地址）的内存位置在不久的将来也可能被访问。例如，顺序执行的指令、数组的遍历。
• “局部性”集合：根据局部性原理，程序的执行可以看作是从一个“局部性”区域（或者说一个“活跃集合”）移动到另一个“局部性”区域。一个“局部性”就是指在一段时间内被活跃使用的页面集合。程序可能由多个这样的局部性组成，这些局部性之间可能是重叠的。
• 例子：考虑一个计算矩阵乘法的程序。在程序的不同阶段，它可能会集中访问不同的行或列。当它在处理矩阵A时，访问的页面集中在矩阵A的数据区域；当切换到处理矩阵B时，访问的页面又集中在矩阵B的区域。每个这样的集中访问区域，就可以看作是一个“局部性”。

工作集模型 (Working-Set Model)： 工作集模型是局部性模型在虚拟内存管理中的具体应用。它试图动态地识别并跟踪一个进程当前正在使用的“局部性”集合。

• 工作集窗口 (Working-Set Window, $\mathrm{\Delta }$)：这是一个关键参数，它定义了一个时间窗口，通常以页面引用次数或时间单位（如时钟滴答数）来衡量。例如，如果 $\mathrm{\Delta }=10,000$ 条指令，那么工作集窗口就是最近的 10,000 条指令引用过的页面。
• 工作集 (Working Set, $WS$)：对于一个进程 $P_i$ 来说，在任意时刻 $t$ 的工作集 $W{S}_t(P_i)$ 是指在最近的 $\mathrm{\Delta }$ 时间单位内（或最近 $\mathrm{\Delta }$ 次页面引用中）被该进程访问过的所有页面的集合。
  • 动态性：工作集是动态变化的。如果一个页面在最近的 $\mathrm{\Delta }$ 时间内被访问过，那么它就在工作集中。如果一个页面在最近的 $\mathrm{\Delta }$ 时间内没有被访问，它就会从工作集中“老化”并被移除。
• 为什么重要？：工作集直观地反映了进程在当前时刻的内存需求。如果一个进程的整个工作集都能驻留在物理内存中，那么它的页错误率就会很低，从而能够高效运行。如果工作集中的页面不能全部在内存中，那么该进程就可能发生抖动。

工作集策略实施： 工作集策略的核心思想是：系统应该尽力为每个活跃进程分配足够多的物理帧，以容纳其当前的工作集。

• 核心思想：为了防止抖动，操作系统会定期（或在页错误发生时）计算每个进程的当前工作集，并尝试为其分配足够的物理帧来容纳这些页面。
• 监控总需求：
  • 设 $W{S}_i$ 为进程 $P_i$ 的工作集（即该进程当前实际需要的页数）。
  • $D=\sum W{S}_i$：这是所有当前运行进程的总需求帧数，即所有进程工作集大小的总和。
  • $m$：表示系统中总的可用物理帧数。
• 抖动判断与应对：
  • 如果 $D\le m$：这表示所有活跃进程的工作集总和小于或等于系统可用的物理帧数。在这种情况下，系统有足够的内存来满足所有进程的当前需求，页错误率会较低，系统性能良好。
  • 如果 $D>m$ → 抖动：这意味着所有活跃进程的总内存需求超过了系统可用的物理内存。在这种情况下，页面置换会变得非常频繁，因为进程总是需要那些被置换出去的页面，从而导致高页错误率和系统性能急剧下降，即发生抖动。
• 策略：如果 $D>m$，暂停一些进程：
  • 当操作系统检测到总需求帧数 $D$ 超过可用物理帧数 $m$ 时，它会主动采取措施来降低多道程序度，以缓解抖动。
  • 最常见的策略是暂停（或交换出）一些进程。通过暂停一个或多个进程，这些进程所占用的物理帧就会被释放出来，从而降低了总需求 $D$，使得 $D\le m$ 重新成立。一旦有足够的帧来容纳剩余活跃进程的工作集，系统就能恢复正常运行。
  • 被暂停的进程会在稍后（当内存资源变得充足时）被重新激活并调回内存。

工作集策略的优点：

• 有效防止抖动：通过确保每个活跃进程都拥有其工作集所需的帧，工作集策略能够有效地避免系统进入抖动状态。
• 优化系统吞吐量：通过保持页错误率在一个较低水平，它提高了系统的整体吞吐量。
• 利用局部性原理：它基于对程序行为（局部性）的理解，是一种智能的内存管理方法。

工作集策略的挑战与实现：

• $\mathrm{\Delta }$ 值的选择：选择一个合适的 $\mathrm{\Delta }$ 值非常关键。
  • 如果 $\mathrm{\Delta }$ 太小，工作集可能无法完全包含进程的局部性，导致不必要的页错误。
  • 如果 $\mathrm{\Delta }$ 太大，工作集会包含很多不活跃的页面，导致内存浪费，并且可能过早地判断系统内存不足。
  • 通常通过实验和系统调优来确定一个经验性的 $\mathrm{\Delta }$ 值。
• 实际实现：在实际操作系统中，准确地维护每个页面的上次引用时间（以计算 $\mathrm{\Delta }$ 窗口内的引用）是比较复杂的。通常使用硬件提供的引用位 (Reference Bit) 和定时中断来近似实现。例如，通过定期扫描页表并重置引用位，来模拟页面的“老化”过程。

3. 页错误频率 (Page-Fault Frequency, PFF) 方案

• 建立可接受的页错误率
• 如果实际错误率太低，从进程中移除一帧
• 如果实际错误率太高，为进程分配另一帧
• 如果没有空闲帧，暂停进程

7.5.3 内存映射文件

传统文件访问的问题

每次文件访问都需要系统调用和磁盘访问，使用标准系统调用：open()、read()、write()

内存映射的概念

通过将磁盘块映射到内存中的页面，将文件I/O当作例程内存访问处理：

• 文件最初使用请求调页读取（到内存中）
• 文件的页大小部分从文件系统读取到物理页面
• 对文件的后续读/写被当作普通内存访问处理

内存映射的优势

• 通过内存而不是read()/write()系统调用处理文件I/O，简化文件访问
• 允许多个进程同时映射同一文件，允许共享内存中的页面

7.5.4 内核内存分配

内核内存的特殊性

• 内核内存与用户内存处理方式不同
• 从空闲内存池分配（不同于普通内存）
• 内核请求各种大小的数据结构的内存
• 某些内核内存需要是连续的

内核内存分配策略

1. 伙伴系统 (Buddy System)

原理：

• 从由物理连续页面组成的固定大小段分配内存
• 使用2的幂分配器分配内存
• 以2的幂为单位满足请求（4K、8K、16K...）
• 大小不合适的请求被舍入到下一个最高的2的幂

优点：

• 相邻伙伴的快速合并形成更大的段

缺点：

• 内部碎片

2. 平板分配 (Slab Allocation)

基本概念：

• 平板 (Slab)：一个或多个物理连续的帧
• 缓存 (Cache)：由一个或多个平板组成
• 每个唯一的内核数据结构有单一缓存

工作机制：

• 如果平板装满已使用对象，下一个对象从空平板分配
• 如果没有空平板，分配新平板

优点：

• 无碎片
• 快速内存请求满足

7.6 分段机制 (Segmentation)

7.6.1 分段基本概念

分段的用户视图

分段是支持用户内存视图的内存管理方案。用户程序是段的集合，段是逻辑单元，如：

• 主程序
• 过程、函数、方法、对象
• 局部变量、全局变量
• 公共块
• 栈
• 符号表
• 数组

分段方式

• 由程序员进行
• 由编译器进行

逻辑地址构成

逻辑地址由二元组组成：<段号, 偏移>

7.6.2 段表结构

段表的作用

将二维地址映射到一维物理地址。

段表项内容

每个表项包含：

• 基址 (Base)：段在内存中驻留的起始物理地址
• 限长 (Limit)：段的长度

地址转换过程

1. 段号s用作段表的索引
2. 偏移d必须在0和段限长之间
3. 如果无效，非法内存访问
4. 如果有效，物理地址 = 基址 + d

7.6.3 分段与分页比较

分段的优点

• 符合用户的逻辑视图
• 便于共享和保护
• 段可以动态增长

分段的缺点

• 外部碎片问题
• 段大小不固定，分配复杂

分页的优点

• 无外部碎片
• 分配简单

分页的缺点

• 不符合用户逻辑视图
• 共享和保护较困难