操作系统中的内存管理：内存分配算法（非连续内存分配）
字数 2673 2025-11-08 20:56:49

操作系统中的内存管理：内存分配算法（非连续内存分配）

在操作系统中，内存分配算法是管理物理内存的关键技术。你已经了解了连续内存分配（如首次适应、最佳适应等），但连续分配容易导致外部碎片。为了解决这个问题，现代操作系统广泛采用了非连续内存分配技术，其中最主要的是分页和分段。本次讲解将聚焦于分页机制中的核心数据结构——页表，并深入探讨其工作原理和优化策略。

1. 基本概念：为什么需要非连续分配？

  • 问题背景：连续内存分配要求一个进程的代码、数据等必须装载在一段连续的内存地址空间中。随着进程的创建和终止，内存中会产生许多小的、不连续的空闲分区（外部碎片）。即使总空闲内存足够，也可能因为找不到一个足够大的连续空间而无法装载新进程。
  • 解决方案：非连续内存分配允许一个进程的代码、数据等被分散地装载到多个不连续的内存区域中。这样，那些小的空闲分区就能被充分利用起来。分页是实现这一目标的主流技术。

2. 分页机制的核心思想

分页机制将物理内存和进程的地址空间都划分成固定大小的、较小的单元。

  • 页框：物理内存被划分为固定大小的块，称为页框。
  • 页面：进程的地址空间（逻辑地址空间）也被划分为同样大小的块，称为页面。
  • 关键点：页面和页框的大小是相等的（例如4KB）。这样，任何一个页面都可以被装载到任何一个可用的页框中。进程的连续逻辑地址，通过页表映射，可以对应到物理内存中不连续的页框上。

3. 地址转换与页表的作用

现在的问题是：给定一个由CPU产生的逻辑地址，如何找到它对应的物理地址？

  • 逻辑地址的构成：在分页系统中，一个逻辑地址被看作由两部分组成：
    1. 页号：高位部分，用于标识该地址属于哪个页面。
    2. 页内偏移量：低位部分，用于标识在该页面内的具体位置。
    • 例如，如果页面大小是4KB（2^12字节），那么逻辑地址的低12位就是偏移量，剩余的高位就是页号。
  • 页表：这是一个为每个进程创建的专用数据结构，存储在内存中。页表的核心功能是建立页号到页框号的映射。
    • 页表项：页表中的每一行称为一个页表项。它至少包含：
      • 有效/存在位：指示该页面当前是否在物理内存中（是否被调入）。
      • 页框号：如果页面在内存中，此项存储该页面所在的物理页框号。
      • 保护位：指示该页的访问权限（读、写、执行）。

4. 地址转换的详细步骤（基本分页）

假设CPU要访问逻辑地址 A。

  1. 分离页号和偏移量：硬件内存管理单元（MMU）根据预设的页面大小，自动将 A 拆分成页号 P 和页内偏移量 d。
  2. 查找页表：MMU以页号 P 作为索引，去查找当前进程的页表。页表的起始地址存储在一个特殊的CPU寄存器——页表基址寄存器中。
  3. 获取页框号：在页表中找到第 P 个页表项，检查其有效位。如果有效，则从中读出物理页框号 f。
  4. 合成物理地址：物理地址由页框号 f 和原来的偏移量 d 拼接而成。因为页面和页框大小相等，所以偏移量 d 在物理页框内是直接适用的。
  5. 内存访问：MMU将合成后的物理地址发送给内存总线，完成实际的内存读写操作。

举例：页面大小4KB，页表项中页框号为5，逻辑地址0x2240。

  • 0x2240的二进制是 0010 0010 0100 0000。取高20位（假设32位系统）为页号，低12位为偏移量。计算得页号P=2，偏移量d=0x240。
  • 查页表第2项，得到页框号f=5。
  • 物理地址 = (页框号5的起始地址) + 0x240 = 5 * 4KB + 0x240 = 0x5000 + 0x240 = 0x5240。

5. 基本分页的性能问题与优化

基本分页有一个严重缺陷：每次内存访问都需要两次内存访问！

  1. 第一次访问内存：读取页表，获取页框号。
  2. 第二次访问内存：访问真正的数据或指令。
    这会使内存访问速度减半，无法接受。

解决方案：转换检测缓冲区

  • TLB是什么：TLB是MMU内部的一个小型、高速的硬件缓存，用于缓存最近使用过的页号到页框号的映射。
  • TLB的工作流程（加速的地址转换）：
    1. CPU产生逻辑地址。
    2. MMU首先在TLB中查找该地址的页号 P。
    3. TLB命中：如果在TLB中找到 P，立刻得到页框号 f，合成物理地址。整个过程无需访问内存中的页表，极其快速。
    4. TLB未命中：如果在TLB中没找到 P，则MMU必须执行一次“慢路径”——访问内存中的页表来获取映射。获取到映射后，不仅用于本次地址转换，还会将这条映射关系存入TLB（可能会替换掉旧的条目）。
  • 效果：由于程序具有局部性原理（时间局部性：最近访问的页面很可能再次被访问；空间局部性：访问一个页面，很可能接着访问其相邻页面），TLB的命中率通常非常高（>98%），这使得分页的开销几乎可以忽略。

6. 页表自身过大的问题与多级页表

对于32位系统（地址空间4GB），如果页面大小为4KB，那么一个进程的地址空间最多有 2^32 / 2^12 = 2^20 = 1M 个页面。每个页表项占4字节，那么一个页表就需要 1M * 4B = 4MB 的连续内存空间。为每个进程都维护一个4MB的页表，且要求连续，这本身就成了一个巨大的负担。

解决方案：多级页表

  • 核心思想：将页表本身也进行分页，形成一个树状结构。这相当于对页号的索引过程进行了分级。
  • 以二级页表为例：
    • 将页号 P 进一步拆分为 P1（一级页号）和 P2（二级页号）。
    • 有一个页目录（一级页表），每个目录项指向一个二级页表的起始地址。
    • 地址转换过程：
      1. 用 P1 索引页目录，找到对应的二级页表。
      2. 用 P2 索引该二级页表，找到页表项，获得页框号 f。
      3. 与偏移量 d 合成物理地址。
  • 优势：多级页表不需要将所有二级页表都常驻内存。如果进程的地址空间有很多空洞（例如，只使用了开头和结尾的少量页面），那么只需要为那些实际使用的虚拟内存区域创建并装入二级页表即可，大部分不存在的二级页表根本不用分配，从而极大地节省了内存。

总结

非连续内存分配（特别是分页）通过允许进程占用不连续的物理页框，有效解决了外部碎片问题。其核心是页表这一映射数据结构。为了克服页表带来的性能开销和空间开销，操作系统采用了TLB和多级页表这两大关键优化技术。TLB作为缓存解决了速度问题，多级页表通过“稀疏存储”解决了空间问题，二者共同使得分页机制成为现代操作系统内存管理的基石。

操作系统中的内存管理：内存分配算法（非连续内存分配） 在操作系统中，内存分配算法是管理物理内存的关键技术。你已经了解了连续内存分配（如首次适应、最佳适应等），但连续分配容易导致外部碎片。为了解决这个问题，现代操作系统广泛采用了非连续内存分配技术，其中最主要的是 分页 和 分段 。本次讲解将聚焦于分页机制中的核心数据结构—— 页表 ，并深入探讨其工作原理和优化策略。 1. 基本概念：为什么需要非连续分配？ 问题背景 ：连续内存分配要求一个进程的代码、数据等必须装载在一段连续的内存地址空间中。随着进程的创建和终止，内存中会产生许多小的、不连续的空闲分区（外部碎片）。即使总空闲内存足够，也可能因为找不到一个足够大的连续空间而无法装载新进程。 解决方案 ：非连续内存分配允许一个进程的代码、数据等被分散地装载到多个不连续的内存区域中。这样，那些小的空闲分区就能被充分利用起来。分页是实现这一目标的主流技术。 2. 分页机制的核心思想 分页机制将物理内存和进程的地址空间都划分成固定大小的、较小的单元。 页框 ：物理内存被划分为固定大小的块，称为 页框 。 页面 ：进程的地址空间（逻辑地址空间）也被划分为同样大小的块，称为 页面 。 关键点 ：页面和页框的大小是相等的（例如4KB）。这样，任何一个页面都可以被装载到任何一个可用的页框中。进程的连续逻辑地址，通过页表映射，可以对应到物理内存中不连续的页框上。 3. 地址转换与页表的作用 现在的问题是：给定一个由CPU产生的逻辑地址，如何找到它对应的物理地址？ 逻辑地址的构成 ：在分页系统中，一个逻辑地址被看作由两部分组成： 页号 ：高位部分，用于标识该地址属于哪个页面。 页内偏移量 ：低位部分，用于标识在该页面内的具体位置。 例如，如果页面大小是4KB（2^12字节），那么逻辑地址的低12位就是偏移量，剩余的高位就是页号。 页表 ：这是一个为每个进程创建的专用数据结构，存储在内存中。页表的核心功能是建立 页号到页框号 的映射。 页表项 ：页表中的每一行称为一个页表项。它至少包含： 有效/存在位 ：指示该页面当前是否在物理内存中（是否被调入）。 页框号 ：如果页面在内存中，此项存储该页面所在的物理页框号。 保护位 ：指示该页的访问权限（读、写、执行）。 4. 地址转换的详细步骤（基本分页） 假设CPU要访问逻辑地址 A 。 分离页号和偏移量 ：硬件内存管理单元（MMU）根据预设的页面大小，自动将 A 拆分成页号 P 和页内偏移量 d 。 查找页表 ：MMU以页号 P 作为索引，去查找当前进程的页表。页表的起始地址存储在一个特殊的CPU寄存器—— 页表基址寄存器 中。 获取页框号 ：在页表中找到第 P 个页表项，检查其有效位。如果有效，则从中读出物理页框号 f 。 合成物理地址 ：物理地址由 页框号 f 和 原来的偏移量 d 拼接而成。因为页面和页框大小相等，所以偏移量 d 在物理页框内是直接适用的。 内存访问 ：MMU将合成后的物理地址发送给内存总线，完成实际的内存读写操作。 举例 ：页面大小4KB，页表项中页框号为5，逻辑地址0x2240。 0x2240的二进制是 0010 0010 0100 0000 。取高20位（假设32位系统）为页号，低12位为偏移量。计算得页号P=2，偏移量d=0x240。 查页表第2项，得到页框号f=5。 物理地址 = (页框号5的起始地址) + 0x240 = 5 * 4KB + 0x240 = 0x5000 + 0x240 = 0x5240。 5. 基本分页的性能问题与优化 基本分页有一个严重缺陷： 每次内存访问都需要两次内存访问 ！ 第一次访问内存：读取页表，获取页框号。 第二次访问内存：访问真正的数据或指令。 这会使内存访问速度减半，无法接受。 解决方案：转换检测缓冲区 TLB是什么 ：TLB是MMU内部的一个小型、高速的硬件缓存，用于缓存最近使用过的 页号到页框号 的映射。 TLB的工作流程（加速的地址转换） ： CPU产生逻辑地址。 MMU首先在TLB中查找该地址的页号 P 。 TLB命中 ：如果在TLB中找到 P ，立刻得到页框号 f ，合成物理地址。整个过程 无需访问内存中的页表 ，极其快速。 TLB未命中 ：如果在TLB中没找到 P ，则MMU必须执行一次“慢路径”——访问内存中的页表来获取映射。获取到映射后，不仅用于本次地址转换，还会将这条映射关系存入TLB（可能会替换掉旧的条目）。 效果 ：由于程序具有局部性原理（时间局部性：最近访问的页面很可能再次被访问；空间局部性：访问一个页面，很可能接着访问其相邻页面），TLB的命中率通常非常高（>98%），这使得分页的开销几乎可以忽略。 6. 页表自身过大的问题与多级页表 对于32位系统（地址空间4GB），如果页面大小为4KB，那么一个进程的地址空间最多有 2^32 / 2^12 = 2^20 = 1M 个页面。每个页表项占4字节，那么一个页表就需要 1M * 4B = 4MB 的连续内存空间。为每个进程都维护一个4MB的页表，且要求连续，这本身就成了一个巨大的负担。 解决方案：多级页表 核心思想 ：将页表本身也进行分页，形成一个树状结构。这相当于对页号的索引过程进行了分级。 以二级页表为例 ： 将页号 P 进一步拆分为 P1 （一级页号）和 P2 （二级页号）。 有一个 页目录 （一级页表），每个目录项指向一个 二级页表 的起始地址。 地址转换过程： 用 P1 索引页目录，找到对应的二级页表。 用 P2 索引该二级页表，找到页表项，获得页框号 f 。 与偏移量 d 合成物理地址。 优势 ：多级页表不需要将所有二级页表都常驻内存。如果进程的地址空间有很多空洞（例如，只使用了开头和结尾的少量页面），那么只需要为那些实际使用的虚拟内存区域创建并装入二级页表即可，大部分不存在的二级页表根本不用分配，从而极大地节省了内存。 总结 非连续内存分配（特别是分页）通过允许进程占用不连续的物理页框，有效解决了外部碎片问题。其核心是 页表 这一映射数据结构。为了克服页表带来的性能开销和空间开销，操作系统采用了 TLB 和 多级页表 这两大关键优化技术。TLB作为缓存解决了速度问题，多级页表通过“稀疏存储”解决了空间问题，二者共同使得分页机制成为现代操作系统内存管理的基石。