[中文] Operating Systems Notes: 05 - 内存管理概述

1. 重要概念#

1.1 存储体系 (Memory Hierarchy)#

计算机存储器按照速度、容量和成本排列成层次结构。

• 寄存器 (Registers): 最快，容量最小，成本最高，直接由 CPU 访问。
• 高速缓存 (Cache - L1, L2, L3): 速度快，容量较小，成本高，用于缓解 CPU 和主存之间的速度差异。
• 内存 (Main Memory / RAM): 速度、容量和成本居中，是程序运行时代码和数据的主要存储区域。
• 本地磁盘 (Local Disk / Secondary Storage): 速度慢，容量大，成本低，用于持久化存储，如硬盘 (HDD)、固态硬盘 (SSD)。
• 远程磁盘 (Remote Storage): 通过网络访问，速度最慢，容量可以很大。

内存管理主要关注的是主存（内存）的管理。

1.2 地址空间 (Address Space)#

• 定义: 操作系统为每个进程分配的一个独立的逻辑地址范围。进程所能“看到”和访问的地址集合。
• 独立性: 每个进程拥有自己独立的地址空间，一个进程默认不能访问另一个进程的地址空间，这是实现存储保护的基础。
• 管理: 操作系统需要管理地址空间的分配（放置 placement）、回收、分割与合并。

1.3 逻辑地址 vs 物理地址#

• 逻辑地址 (Logical Address):
  • 也称为相对地址 (Relative Address) 或 虚拟地址 (Virtual Address)。
  • 是用户程序（或 CPU 发出）使用的地址。
  • 通常从 0 开始编址，地址是相对于进程自身的地址空间。
  • 编译、汇编后生成的目标代码通常使用逻辑地址。
  • 不能直接用于在物理内存中寻址。
• 物理地址 (Physical Address):
  • 也称为绝对地址 (Absolute Address) 或 实地址 (Real Address)。
  • 是内存存储单元的实际地址，硬件内存总线可以直接访问。

1.4 地址重定位 (Address Relocation)#

• 定义: 将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址的过程。
• 别名: 也常被称为地址转换 (Address Translation)、地址变换 (Address Transformation) 或 地址映射 (Address Mapping)。这些术语基本同义，都指代从逻辑地址到物理地址的转换过程。
• 目的: 保证 CPU 执行指令时能够正确访问到物理内存单元。
• 为什么需要?
  • 多道程序环境下，内存中有多个进程。
  • 程序加载到内存的位置通常在运行时才能确定，无法在编译时预知其物理地址。
• 地址绑定时机 (Binding Time): 指令和数据绑定到内存地址的时间点：
  • 编译时 (Compile Time): 如果编译时就知道程序将驻留在内存的哪个位置，编译器可以直接生成绝对代码。但如果加载位置改变，程序就必须重新编译。很少用。
  • 加载时 (Load Time): 如果编译时不知道加载位置，编译器生成可重定位代码 (Relocatable Code)。加载器 (Loader) 在将程序加载到内存时，根据实际加载的起始地址，一次性地将所有逻辑地址转换为物理地址。这称为静态地址重定位。
  • 运行时 (Run Time): 地址转换延迟到程序运行时才进行。CPU 每次访问内存（取指或访存）时，都会将逻辑地址转换为物理地址。这需要硬件支持（如 MMU），称为动态地址重定位。现代操作系统普遍采用此方式，因为它提供了最大的灵活性（如进程可以在内存中移动）。

静态地址重定位 (Static Relocation)#

• 过程: 在程序被加载进内存时，由加载器一次性完成逻辑地址到物理地址的转换。
• 实现: 通常由软件（加载器）完成。
• 示例:

  // 源代码         // 目标代码 (逻辑地址)        // 装载模块 (磁盘, 逻辑)   // 装载模块 (内存, 物理 @ 1000)
  i = ...;        store 20;                 store 120;               store 1120;
  f();            branch f;                 branch 100;              branch 1100; // 假设 f 在 100
  ...             ...                       ...                      ...
  f: ...          f: ...                    f: ... (在 100)          f: ... (在 1100)
  

  plaintext
• 缺点: 程序加载后不能在内存中移动；不灵活。

动态地址重定位 (Dynamic Relocation)#

• 过程: 在进程执行过程中，每次访问内存地址时进行转换。
• 实现: 需要硬件支持，通常是 内存管理单元 (MMU - Memory Management Unit)。
  • MMU: 一个硬件设备，负责将 CPU 发出的逻辑地址实时转换为物理地址。
  • 实现方式 (简单示例): 使用基址寄存器 (Base Register) 和重定位寄存器 (Relocation Register)。逻辑地址加上重定位寄存器的值得到物理地址。
• 优点: 进程可以在内存中移动（例如，为了内存紧凑）；支持更高级的内存管理技术（如虚拟内存）。

1.5 存储保护 (Memory Protection)#

• 目的:
  • 确保每个进程有自己独立的地址空间，防止一个进程访问或修改另一个进程的数据。
  • 防止进程访问其不应访问的内存区域（如操作系统的核心代码）。
  • 防止进程执行不适当的操作（如写入只读代码段）。
• 实现 (基于基址/界限寄存器):
  • 基地址寄存器 (Base Register): 存放进程在物理内存中的起始地址。
  • 界限寄存器 (Limit Register): 存放进程的逻辑地址空间的大小（或最大合法逻辑地址）。
  • 检查过程: CPU 产生的每个逻辑地址 addr 必须满足 0 <= addr < Limit Register。转换后的物理地址 Base Register + addr 也必须在分配给该进程的物理内存范围内 (有时 limit check 可以直接在物理地址上做，Base <= Physical Address < Base + Limit)。
  • 加载: 基址和界限寄存器的值由操作系统通过特权指令 (Privileged Instructions) 加载，用户程序无法修改。
• 其他机制: 页表/段表中的保护位（读/写/执行权限）。

1.6 存储共享 (Memory Sharing)#

允许多个进程安全地共享同一段物理内存区域。例如，共享库（如 C 库）的代码段通常可以在多个进程间共享，只需在物理内存中保留一份副本，节省内存。实现通常依赖于分页或分段机制。

1.7 局部性原理 (Principle of Locality)#

程序在执行过程中的一个普遍倾向：

• 时间局部性 (Temporal Locality): 如果一个内存位置被访问，那么它在不久的将来很可能再次被访问（如循环中的指令、变量）。
• 空间局部性 (Spatial Locality): 如果一个内存位置被访问，那么它附近的内存位置也很可能在不久的将来被访问（如顺序执行的代码、数组元素）。

意义: 存储体系（特别是 Cache）和虚拟内存管理（如页面置换算法）都依赖局部性原理来提高性能。

2. 内存管理的目标与功能#

• 目标: 有效、安全地管理计算机主存资源，提升系统性能和易用性。主要追求：
  • 透明性 (Transparency): 内存管理对用户程序应该是透明的，程序员不需要关心物理内存的细节。
  • 效率 (Efficiency): 最小化内存访问时间，高效利用内存资源（减少浪费），降低管理开销。
  • 保护 (Protection): 确保进程间地址空间隔离，保护操作系统自身。
• 基本功能:
  • 内存分配与回收: 为进程按需分配内存空间，并在进程结束或不再需要时回收。管理空闲内存。
  • 地址映射/转换: 实现逻辑地址到物理地址的转换。
  • 内存保护: 提供机制防止非法内存访问。
  • 内存共享: 支持多个进程共享部分内存区域。
  • 内存扩充: 通过覆盖、交换、虚拟内存等技术，在有限的物理内存上运行更大的程序或更多的进程。

多道程序设计对内存管理提出的挑战:

• 多个进程同时在内存中，需要管理它们各自的空间。
• 需要支持地址重定位（程序加载位置不确定）。
• 需要支持地址保护（进程间隔离）。

3. 进程地址空间#

3.1 地址空间布局 (典型 Linux 布局)#

进程的逻辑地址空间通常划分为几个标准段：

    高地址 0xFFFFFFFF  +-----------------------+
                      | 内核地址空间 (Kernel)    | --> 供操作系统使用，用户模式不可访问
          0xC0000000  +-----------------------+
                      | 用户栈 (Stack)          | --> 函数调用、局部变量 (向下增长)         |
                      | ----------------------- |
                      |                         |
                      | 内存映射区域            | --> 共享库、内存映射文件                  |
                      | (Memory Mapped Region)  |
                      |                         |
                      | ----------------------- |
                      | 堆 (Heap)               | --> 动态内存分配 (malloc, new) (向上增长) |
                      | ----------------------- |
                      | BSS 段 (Uninit. Data)   | --> 未初始化全局/静态变量                 |
                      | ----------------------- |
                      | 数据段 (Data Segment)   | --> 已初始化全局/静态变量                 |
                      | 0x08048000              | -----------------------                   |
                      | 代码段 (Text Segment)   | --> 程序指令 (只读)                       |
    低地址  0x00000000 +-----------------------+

• 加载来源: 代码段、数据段、BSS 段通常从可执行文件中加载。栈和堆是在运行时动态创建和增长的。共享库在运行时动态链接和映射。
• PC (Program Counter): 指向当前执行的指令（在代码段内）。
• SP (Stack Pointer): 指向栈顶。

3.2 XV6 示例 (地址空间)#

XV6 是一个教学用的简单操作系统，其地址空间布局相对简单：

• 地址从低到高依次为：
  • 代码 (text): 程序指令。
  • 数据 (data) & BSS: 初始化和未初始化的全局/静态变量。
  • 栈 (stack): 函数调用栈。
  • 堆 (heap): 动态分配区域。
• 高地址处有 Trampoline 和 Trapframe 区域，用于用户态和内核态之间的切换，并且在两种模式下都映射。(kernel/memlayout.h 中定义)。

3.3 相关概念解释 (常用于虚拟内存)#

• 活跃页面 (Active Page): 指当前正在被进程频繁访问的页面。
• 工作集 (Working Set): 一个进程在最近一段时间 Δ 内所访问到的页面集合。这是衡量进程当前运行所需内存大小的一个动态指标，反映了程序的局部性。如果一个进程的工作集能完全驻留在内存中，那么它就能高效运行，很少发生缺页中断。
• 常驻集 (Resident Set): 指一个进程当前时刻实际驻留在物理内存中的页面集合。常驻集的大小受操作系统分配策略的影响。理想情况下，常驻集应该包含进程的工作集。

4. 物理内存管理 (空闲空间管理)#

操作系统需要跟踪哪些物理内存是空闲的，哪些已被分配。

4.1 管理数据结构#

• 位图 (Bitmap / Bit Vector):

  • 将物理内存划分为固定大小的分配单元（通常大小等于页框或几倍页框大小）。
  • 位图中的每一位对应一个分配单元。
  • 位的值表示单元状态：0 表示空闲，1 表示已分配（或相反）。
  • 优点: 简单，易于快速找到连续的空闲块。
  • 缺点: 位图本身需要占用内存空间（空间开销与内存总量成正比）。查找指定大小的空闲块可能需要扫描整个位图。

• 空闲区表/链表 (Free List):

  • 维护一个包含所有空闲内存块（区）信息的数据结构。
  • 每个节点/表项记录一个空闲区的起始地址 (Start Address) 和 长度 (Length)。
  • 可以组织成表 (Array) 或链表 (Linked List)。
  • 链表类型:
    • 隐式空闲链表 (Implicit Free List): 空闲块和已分配块都存储在内存中，通过块头部信息（大小、是否空闲）来遍历。分配和回收时需要查找。
    • 显式空闲链表 (Explicit Free List): 只将空闲块链接起来。头部包含指向下一个（有时还有上一个）空闲块的指针。查找空闲块更快，但维护链表指针有开销。
    • 分离空闲链表 (Segregated Free List): 维护多个空闲链表，每个链表负责特定大小范围的空闲块。分配时，根据请求大小直接去对应链表查找。可以加快分配速度，减少碎片。伙伴系统和 SLAB 分配器属于此类。
  • 优点: 空间开销只与空闲块数量有关，不一定与内存总量成正比（对于大块空闲区更有效）。
  • 缺点: 分配和回收时可能需要遍历链表/表，查找合适空闲块。可能会产生外部碎片。

4.2 衡量指标#

• 内存资源利用率: 目标是减少浪费。
  • 内碎片 (Internal Fragmentation): 分配给进程的内存块大于进程实际请求的大小，块内部未被使用的部分。常见于固定分区、页式管理和固定大小分配策略（如伙伴系统分配的块可能大于请求）。
  • 外碎片 (External Fragmentation): 内存中存在足够多的空闲空间总和来满足一个请求，但这些空间不连续，而是散布在已分配块之间的小块。导致无法分配较大的连续内存块。常见于可变分区、段式管理。
• 性能: 分配和回收内存操作的速度，以及这些操作占用的 CPU 时间。

4.3 内存分配算法 (针对空闲区表/链表)#

当需要为进程分配长度为 s 的内存时，如何在空闲区列表中选择一个合适的空闲块？

• 首次适配 (First Fit): 从链表/表的开头开始查找，选择第一个找到的大小 >= s 的空闲块。
  • 优点: 算法简单，速度较快。倾向于在低地址区域留下碎片。
  • 缺点: 可能产生较多的小碎片，且每次查找都从头开始。
• 下次适配 (Next Fit): 从上次分配操作结束的位置开始查找，选择第一个找到的大小 >= s 的空闲块。
  • 优点: 避免了每次都从头查找，空闲块的使用更均匀分布。
  • 缺点: 可能导致大的空闲块很快被分割完。
• 最佳适配 (Best Fit): 遍历整个空闲链表/表，找到大小 >= s 且最小的那个空闲块（即差值 size - s 最小）。
  • 优点: 试图留下最大的可用空闲块，减少大碎片的产生。
  • 缺点: 速度最慢（需要全表扫描），容易产生大量非常小而难以利用的碎片。
• 最差适配 (Worst Fit): 遍历整个空闲链表/表，找到大小 >= s 且最大的那个空闲块。
  • 优点: 试图将剩余部分保持为较大的可用块，避免产生过多小碎片。
  • 缺点: 速度慢（需要全表扫描），可能导致大的空闲块很快被消耗掉，无法满足后续对大内存的需求。

分配过程: 选定一个空闲块后，如果其大小 Size 远大于请求大小 s，通常会将其分割为两部分：一部分（大小为 s）分配给进程，另一部分（大小为 Size - s）变回一个新的、更小的空闲块。

示例: 假设空闲区为 [15K, 23K], [48K, 20K], [80K, 30K]。进程 P5 请求 5K，进程 P6 请求 13K。

• First Fit: P5 分配到 [15K, 5K]，剩余 [20K, 18K]。P6 分配到 [20K, 13K]，剩余 [33K, 5K]。空闲区变为 [33K, 5K], [48K, 20K], [80K, 30K]。
• Best Fit: P5 分配到 [48K, 5K]，剩余 [53K, 15K]。P6 分配到 [53K, 13K]，剩余 [66K, 2K]。空闲区变为 [15K, 23K], [66K, 2K], [80K, 30K]。
• Worst Fit: P5 分配到 [80K, 5K]，剩余 [85K, 25K]。P6 分配到 [85K, 13K]，剩余 [98K, 12K]。空闲区变为 [15K, 23K], [48K, 20K], [98K, 12K]。

4.4 内存回收 (针对空闲区表/链表)#

当一个进程释放内存块时，需要将其归还给空闲列表。

• 合并 (Coalescing): 为了减少碎片，回收时需要检查该块是否与物理上相邻的空闲块接壤。
  • 上相邻: 与前面的空闲块合并。
  • 下相邻: 与后面的空闲块合并。
  • 上下都相邻: 与前后两个空闲块合并成一个大空闲块。
  • 上下都不相邻: 直接将回收块作为一个新的独立空闲块添加到链表/表中。
• 更新数据结构: 相应地修改空闲区表/链表。

4.5 特定分配策略#

伙伴系统 (Buddy System)#

• 思想: 一种特殊的“分离适配”算法，用于管理大小为 2 的幂次的内存块。Linux 内核底层内存管理曾采用（现在也部分采用）。
• 结构: 将整个可用内存（假设大小为 2^U）看作一个块。维护 U+1 个空闲链表，分别管理大小为 2⁰, 2¹, …, 2^U 的空闲块。
• 分配过程 (请求大小为 s):
  1. 计算满足需求的最小 2 的幂次 k，使得 2^k-1 < s ≤ 2^k。
  2. 查找大小为 2^k 的空闲链表。
  3. 如果找到，分配该块。
  4. 如果没找到，则查找更大的块 (2^k+1)。找到后，将其分裂 (Split) 成两个大小相等的伙伴 (Buddies) (均为 2^k)。一个用于分配，另一个放入 2^k 的空闲链表。
  5. 如果 2^k+1 也没有，继续向上查找并递归分裂，直到找到可分配的块。
• 回收过程 (释放大小为 2^k 的块 B):
  1. 查找块 B 的伙伴 B' (地址可以通过异或运算计算得到)。
  2. 检查伙伴 B' 是否也空闲且大小相同 (2^k)。
  3. 如果是，则将 B 和 B' 合并 (Merge) 成一个更大的块 (2^k+1)，并递归尝试与新块的伙伴合并。
  4. 如果否，则将 B 加入 2^k 的空闲链表。
• 优点: 分裂和合并相对高效（伙伴地址计算快），能较好地控制外部碎片（合并机制）。
• 缺点: 存在内碎片（分配的块大小必须是 2 的幂，可能大于实际需求）。

伙伴系统示例 (1MB 内存):

1. 初始: Free list for 1M: [Block 1M]
2. A 申请 100K: 需要 128K (2⁷)。分裂 1M -> 512K + 512K; 分裂 512K -> 256K + 256K; 分裂 256K -> 128K + 128K。分配一个 128K 给 A。
   • Memory: [A=128K][Free 128K][Free 256K][Free 512K]
   • Free lists: 128K:[1 block], 256K:[1 block], 512K:[1 block]
3. B 申请 240K: 需要 256K (2⁸)。分配链表中的 256K 给 B。
   • Memory: [A=128K][Free 128K][B=256K][Free 512K]
   • Free lists: 128K:[1 block], 512K:[1 block]
4. C 申请 64K: 需要 64K (2⁶)。分裂 128K -> 64K + 64K。分配一个 64K 给 C。
   • Memory: [A=128K][C=64K][Free 64K][B=256K][Free 512K]
   • Free lists: 64K:[1 block], 512K:[1 block]
5. D 申请 256K: 需要 256K (2⁸)。分裂 512K -> 256K + 256K。分配一个 256K 给 D。
   • Memory: [A=128K][C=64K][Free 64K][B=256K][D=256K][Free 256K]
   • Free lists: 64K:[1 block], 256K:[1 block]
6. 释放 B (256K): 它的伙伴 D=256K 未释放。将 B 加入 256K 链表。
   • Memory: [A=128K][C=64K][Free 64K][Free 256K][D=256K][Free 256K]
   • Free lists: 64K:[1 block], 256K:[2 blocks]
7. 释放 A (128K): 它的伙伴 C=64K+Free 64K 中的 Free 64K 是否是伙伴？需要看具体地址。假设 A 的伙伴是 [C=64K][Free 64K] 中的 Free 64K 之前的那个 128K 块，则 A 不能立即合并。将 A 加入 128K 链表。（原始图示似乎假设 A 的伙伴是 Free 128K，那释放 A 时应该合并成 256K。我们按原始图示逻辑继续）
   • 按图示：释放 A(128K) -> 与其伙伴(Free 128K)合并 -> 256K。
   • Memory: [Free 256K][C=64K][Free 64K][B=256K][D=256K][Free 256K] (B 已经释放) -> [Free 256K][C=64K][Free 64K][Free 256K][D=256K][Free 256K]
   • Free lists: 64K:[1 block], 256K:[3 blocks]
8. E 申请 75K: 需要 128K。从 Free 256K 中分裂 -> 128K+128K。分配一个 128K 给 E。
   • Memory: [E=128K][Free 128K][C=64K][Free 64K][Free 256K][D=256K][Free 256K]
   • Free lists: 64K:[1 block], 128K:[1 block], 256K:[2 blocks]
9. 释放 C (64K): 伙伴是 Free 64K。合并 -> 128K。这个 128K 的伙伴是 E=128K (未释放)。将这个新 128K 加入链表。
   • Memory: [E=128K][Free 128K][Free 128K][Free 256K][D=256K][Free 256K]
   • Free lists: 128K:[2 blocks], 256K:[2 blocks]
10. 释放 E (128K): 伙伴是 Free 128K (来自 C 的合并)。合并 -> 256K。这个 256K 的伙伴是另一个 Free 128K （原始 A 分裂剩下的）？地址决定。按图示，它与另一个 128K 合并成 256K，再与相邻的 Free 256K 合并成 512K。
    • Memory: [Free 512K][Free 256K][D=256K][Free 256K]
    • Free lists: 256K:[2 blocks], 512K:[1 block]
11. 释放 D (256K): 伙伴是 Free 256K。合并 -> 512K。这个 512K 的伙伴是 Free 512K。合并 -> 1M。
    • Memory: [Free 1M]
    • Free lists: 1M:[1 block]

SLAB/SLUB/SLOB 分配器#

• 目的: 高效管理内核中频繁分配和释放的小内存对象（如 inode、task_struct 等）。伙伴系统分配的最小块可能仍太大，导致内碎片。

• 基本思想:

  • 将伙伴系统分配的大块内存（称为 “slab”）进一步细分成多个固定大小的小对象 (object)。
  • 为每种类型的对象维护一个或多个 slab 缓存 (cache)。
  • 分配对象时，从对应的 cache 中快速获取一个空闲对象。
  • 释放对象时，将其放回原 cache，通常无需立即归还给伙伴系统。

• 优点:

  • 减少内碎片（对象大小精确匹配）。
  • 分配和释放速度快（对象通常已初始化，且无需查找）。
  • 利用缓存局部性（对象在 L1/L2 cache 中可能仍然有效）。

• SLAB 分配器 (原始, Jeff Bonwick, Solaris -> Linux):

  • 为每种对象类型维护一个 kmem_cache。
  • 每个 cache 包含多个 slab (通常是 1 或多个物理页)。
  • Slab 内包含对象和元数据。
  • Slab 分为：全满 (full)、部分空闲 (partial)、全空 (empty) 三种链表。分配优先从 partial slab 获取。
  • 问题: 实现相对复杂，元数据管理开销较大，多核环境下锁竞争可能成为瓶颈。

• SLUB 分配器 (改进, Pekka Enberg, Linux 2.6.22+):

  • 目标: 简化设计，提高性能和可伸缩性。是当前 Linux 默认的分配器。
  • 简化: 去除了复杂的 slab 链表管理，主要将 page（物理页）作为 slab 进行管理。元数据存储开销更小。
  • 性能: 减少锁竞争，对 NUMA (Non-Uniform Memory Access) 架构和多核系统优化更好（利用 per-CPU 缓存）。

• SLOB 分配器 (简单):

  • 目标: 极简、紧凑，适用于代码大小和内存开销受限的嵌入式系统。
  • 实现: 使用简单的首次适配算法在小的内存块（slab）内分配。不适合高性能、大内存系统。

• 查看 Slab 信息 (Linux):

  cat /proc/slabinfo
  # 或者使用 slabtop 工具
  slabtop
  

  bash

  (slabinfo 提供详细的 cache 列表，包括对象大小、活动对象数、总对象数、slab 数等信息。)

5. 基本内存管理方案#

不同的策略将进程的逻辑地址空间映射到物理内存。

5.1 单一连续区 (Single Contiguous Allocation)#

• 特点: 内存除操作系统区域外，全部由当前运行的一个用户程序独占。
• 实现: 程序总是加载到同一个内存地址（或通过一个简单的基址寄存器）。
• 优点: 非常简单。
• 缺点: 内存利用率极低，无法支持多道程序设计。适用于非常早期的或简单的嵌入式系统。

5.2 固定分区 (Fixed Partitioning)#

• 特点: 内存被预先划分成若干个大小固定的分区。分区大小可以相同也可以不同。
• 分配: 每个分区装入一个进程。当进程需要内存时，操作系统寻找一个足够大且空闲的分区分配给它。
• 优点: 实现简单，支持了多道程序。
• 缺点:
  • 内碎片: 分配给进程的分区可能大于进程实际需要的大小。
  • 不灵活: 分区大小固定，大进程可能无处容身，小进程占用大分区造成浪费。

5.3 可变分区 (Variable Partitioning / Dynamic Partitioning)#

• 特点: 内存不预先划分。根据进程的实际需求，从空闲内存（洞 Hole） 中动态地分割出一个分区分配给它。

• 分配: 使用 First Fit, Best Fit, Worst Fit 等算法在空闲区列表中查找并分配。

• 优点: 按需分配，没有内碎片，比固定分区灵活。

• 缺点:

  • 外碎片: 随着进程的分配和回收，内存中会产生许多不连续的小空闲区，即使总空闲量足够，也可能无法满足新的较大内存请求。
  • 管理复杂: 需要维护空闲区列表，分配和回收时涉及查找、分割和合并。

• 外碎片解决方案:

  • 紧缩技术 (Compaction / Memory Compaction):
    • 思想: 通过移动内存中的进程，将所有小的空闲区合并成一个或几个大的连续空闲区。
    • 实现: 需要动态重定位支持（因为进程物理地址改变了）。
    • 问题:
      • 开销大: 移动内存内容非常耗时，期间系统性能会下降。
      • 移动时机: 何时进行紧缩？（例如，当分配失败且有足够总空闲空间时，或定时进行）。

5.4 页式管理 (Paging)#

• 核心思想:
  • 逻辑地址空间: 划分为固定大小的块，称为 页 (Page)。
  • 物理内存空间: 划分为与页大小相同的块，称为 页框 (Page Frame) 或物理页面、内存块。
  • 分配: 以页为单位进行。进程需要的页可以加载到任意空闲的页框中。逻辑上相邻的页在物理上不必相邻。
• 逻辑地址结构: 逻辑地址 = 页号 (Page Number) + 页内偏移 (Offset)
  • 例如，32位地址，页面大小 4KB (2¹² B):
    • 高 20位 (31-12) 是页号。
    • 低 12位 (11-0) 是页内偏移。
• 数据结构:
  • 页表 (Page Table): 每个进程都有一个页表。
    • 功能: 记录逻辑页号到物理页框号的映射关系。
    • 页表项 (Page Table Entry - PTE): 至少包含 页框号 (Frame Number)。通常还包含其他控制位：
      • 有效位/驻留位 (Valid/Present Bit): 标记该页是否在物理内存中。
      • 保护位 (Protection Bits): 控制读/写/执行权限。
      • 修改位 (Modified/Dirty Bit): 标记该页加载到内存后是否被修改过。
      • 访问位 (Accessed/Referenced Bit): 标记该页是否被访问过。
    • 存储: 页表本身也存储在内存中。操作系统通过页表基址寄存器 (Page Table Base Register - PTBR) (如 x86 的 CR3 寄存器) 指向当前进程的页表起始地址。
  • 空闲页框列表: 操作系统需要维护一个数据结构（如位图或链表）来跟踪哪些物理页框是空闲的。
• 地址转换过程 (硬件 MMU):
  1. CPU 发出逻辑地址。
  2. MMU 将逻辑地址分解为页号 p 和页内偏移 d。
  3. 使用页号 p 作为索引，访问当前进程的页表 (基址在 PTBR)。
  4. 找到对应的页表项 (PTE)。
  5. 检查 PTE 中的有效位和保护位。如果无效或权限不足，则产生缺页异常 (Page Fault) 或保护异常，陷入操作系统处理。
  6. 如果有效且权限允许，从 PTE 中取出页框号 f。
  7. 将页框号 f 与页内偏移 d 拼接（或 f * PageSize + d）得到最终的物理地址。
  8. 访问物理内存。
• 优点:
  • 无外碎片: 以固定大小的页框为单位分配，总能利用空闲页框。
  • 内存利用率高: 物理内存不必连续。
  • 易于实现共享: 让多个进程的页表项指向同一个物理页框即可共享页面（如共享库代码）。
  • 支持虚拟内存的基础。
• 缺点:
  • 内碎片: 进程的最后一页通常不会完全占满，导致该页框内产生少量内碎片。
  • 页表开销: 页表本身需要占用内存空间。对于大地址空间和小编页面，页表可能非常大（需要多级页表等技术解决）。
  • 地址转换开销: 每次访存理论上需要两次内存访问（一次查页表，一次访问数据）。实际使用 TLB (Translation Lookaside Buffer)，一种页表项的高速缓存，来加速转换。

5.5 段式管理 (Segmentation)#

• 核心思想:
  • 逻辑地址空间: 按照程序的逻辑结构划分为多个段 (Segment)，如代码段、数据段、栈段等。每个段有自己的名字（通常用段号代替）和长度。段的长度可以不同。
  • 物理内存空间: 仍然是线性地址空间，但分配时按整个段分配。
  • 分配: 以段为单位。每个段需要分配一块连续的物理内存空间，但不同段之间可以不相邻。
• 逻辑地址结构: 逻辑地址 = 段号 (Segment Number) + 段内偏移 (Offset within Segment)
• 数据结构:
  • 段表 (Segment Table): 每个进程一个段表。
    • 功能: 记录逻辑段号到物理内存信息的映射。
    • 段表项 (Segment Table Entry - STE): 通常包含：
      • 段基址 (Segment Base): 该段在物理内存中的起始地址。
      • 段限长 (Segment Limit): 该段的长度。
      • 保护位 (Protection Bits): 如读/写/执行权限。
    • 存储: 段表本身也存储在内存中。操作系统通过段表基址寄存器 (Segment Table Base Register - STBR) 指向当前进程的段表。
  • 物理内存管理: 类似于可变分区管理，需要维护空闲区列表，使用 First Fit 等算法分配连续空间。
• 地址转换过程 (硬件 MMU):
  1. CPU 发出逻辑地址。
  2. MMU 将逻辑地址分解为段号 s 和段内偏移 d。
  3. 使用段号 s 作为索引，访问当前进程的段表 (基址在 STBR)。
  4. 找到对应的段表项 (STE)。
  5. 检查:
     • 段号 s 是否合法（在段表范围内）。
     • 段内偏移 d 是否小于段限长 Limit (0 <= d < Limit)。如果超出，则产生地址越界异常。
     • 访问权限是否允许。如果不允许，则产生保护异常。
  6. 如果检查通过，取出段基址 Base。
  7. 计算物理地址: 物理地址 = 段基址 Base + 段内偏移 d。
  8. 访问物理内存。
• 优点:
  • 符合程序逻辑: 分段是用户可见的，便于程序员组织代码和数据。
  • 易于共享和保护: 可以方便地对整个逻辑段（如代码段）进行共享或设置保护属性。
• 缺点:
  • 外碎片: 段的长度可变，分配和回收类似于可变分区，会产生外碎片。需要紧缩技术。
  • 内存分配复杂: 需要找到足够大的连续空闲块。

5.6 段页式管理 (Segmented Paging)#

• 核心思想: 结合段式和页式的优点。
  • 用户视角 / 逻辑地址空间: 仍然按段划分 (用户可见)。
  • 内存管理 / 物理内存: 按页框划分和分配 (系统底层)。
  • 实现: 每个逻辑段内部再进一步划分为固定大小的页。
• 逻辑地址结构: 逻辑地址 = 段号 s + 段内页号 p + 页内偏移 d (或者看作 段号 s + 段内偏移 offset，其中 offset 再被解释为 页号 p + 页内偏移 d)
• 数据结构:
  • 段表 (Segment Table): 每个进程一个。
    • 段表项: 不再直接指向物理基址，而是指向该段对应的页表的基址，并包含页表的长度（或段的页数）。
  • 页表 (Page Table): 每个段拥有一个页表。
    • 页表项: 记录段内的逻辑页号到物理页框号的映射。
• 地址转换过程 (硬件 MMU):
  1. CPU 发出逻辑地址 (s, offset)。
  2. 用段号 s 查段表，找到对应段的页表基址和段限长。
  3. 检查段内偏移 offset 是否小于段限长。如果超出，则地址越界。
  4. 将段内偏移 offset 分解为段内页号 p 和页内偏移 d。
  5. 使用段内页号 p 作为索引，访问该段的页表（基址来自段表项），找到对应的页表项 (PTE)。
  6. 检查 PTE 的有效位和保护位。
  7. 从 PTE 中取出页框号 f。
  8. 计算物理地址: 物理地址 = 页框号 f * PageSize + 页内偏移 d。
  9. 访问物理内存。
• 优点:
  • 结合了段式的逻辑清晰、易于共享保护和页式的内存利用率高、无外碎片的优点。
• 缺点:
  • 系统开销大: 需要维护段表和多个页表，增加了内存占用。
  • 地址转换更复杂: 需要多次内存访问（查段表 -> 查页表 -> 访问数据）。同样需要 TLB 来加速。

6. 内存 “扩充” 技术#

在物理内存不足时，让系统能运行更大程序或更多进程的技术。

6.1 覆盖技术 (Overlaying)#

• 目的: 在物理内存小于程序总大小的情况下运行程序。
• 思想: 程序的不同模块（覆盖段）按照它们的调用关系在同一块内存区域中相互替换。只有当前需要的模块和常驻模块保留在内存中。
• 实现:
  • 程序员负责: 需要程序员手动划分程序模块，并指定它们之间的覆盖结构 (Overlay Structure)。
  • 操作系统提供加载覆盖模块的机制。
• 示例: 程序 A 调用 B 或 C；B 调用 D 或 E；C 调用 F。
  • 常驻区: A (8K)
  • 覆盖区 0: B (8K) 或 C (10K) -> 需要 10K
  • 覆盖区 1: D (12K) 或 E (4K) (当B在内存时) 或 F (10K) (当C在内存时) -> 需要 12K
  • 总需内存 = 常驻区 + Max(覆盖区0) + Max(覆盖区1) = 8K + 10K + 12K = 30K (远小于原始总和 54K)。
• 优点: 能够在小内存上运行大程序。
• 缺点:
  • 对用户不透明: 增加了程序员的负担，编程复杂。
  • 执行时间增加: 需要从外存动态加载覆盖模块，属于“时间换空间”。
• 应用: 主要用于早期内存极其有限的操作系统。

6.2 交换技术 (Swapping)#

• 目的: 提高内存利用率和系统吞吐量，允许运行的进程总大小超过物理内存。
• 思想: 将暂时不运行的进程完整地从内存移动到外存（交换区 Swap Space），称为换出 (Swap Out / Roll Out)。当需要再次运行时，再从外存将其换回 (Swap In / Roll In) 到内存中。
• 实现:
  • Swapper (交换程序): 操作系统中负责执行交换操作的模块。
  • 交换区 (Swap Space): 通常是磁盘上一块连续或特殊管理的区域，用于快速读写整个进程映像。
• 关键问题与讨论:
  • 交换内容: 进程的哪些部分需要交换？通常是进程的整个用户地址空间（代码、数据、堆、栈等运行时状态）。
  • 交换位置: 被换出的进程保存在磁盘的交换区。
  • 交换时机:
    • 内存空间不足时触发换出。
    • 进程长时间阻塞或优先级低时可能被换出。
    • 与调度器结合，选择合适的进程换入换出。
  • 换出进程选择: 考虑进程状态（不应换出等待 I/O 的进程）、优先级、在内存驻留时间等因素。
  • 换入位置: 换回内存时不一定回到原来的物理地址。需要动态地址重定位支持。
  • 进程空间增长: 如果进程在内存中时其地址空间增长（如堆或栈扩展），分配可能需要更多内存。如果此时内存不足，可能需要换出其他进程。如果进程在交换区时需要增长，则处理更复杂，通常不允许或有预留机制。
• 优点: 提高了内存利用率，支持运行比物理内存更大的进程集合。
• 缺点:
  • 开销大: 整个进程映像的磁盘 I/O 非常耗时。
  • 可能导致抖动 (Thrashing): 如果内存严重不足，系统可能花费大量时间在换入换出进程上，而实际执行用户代码的时间很少。
• 应用: 曾用于分时系统，现代系统中的虚拟内存可以看作是更精细化的交换技术（以页为单位）。

6.3 虚拟内存技术 (Virtual Memory)#

（本讲义中提及，但未详细展开，通常是后续章节内容） 结合了请求调页 (Demand Paging) 或请求分段 (Demand Segmentation) 与交换技术的思想。允许程序只加载部分页面/段到内存即可运行，其余部分在需要时才从磁盘加载。这是现代操作系统普遍采用的核心内存管理技术。

7. 重点小结#

• 基本概念: 存储体系、逻辑地址/物理地址、地址重定位（静态/动态）、地址保护、共享、局部性。
• 物理内存管理:
  • 数据结构：位示图、空闲区表/链表（隐式/显式/分离）。
  • 分配算法：首次/下次/最佳/最差适配。
  • 回收与合并。
  • 碎片问题：内碎片、外碎片。
  • 特定策略：伙伴系统、SLAB/SLUB/SLOB 分配器。
• 内存管理方案:
  • 单一连续区、固定分区、可变分区（+紧缩）、页式、段式、段页式。
  • 每种方案的特点、优缺点、地址转换机制、相关数据结构（页表/段表）。
• 内存扩充技术: 覆盖技术、交换技术（虚拟内存是更高级形式）。