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

字数 2614 2025-11-10 00:03:01

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

在操作系统中，内存分配算法负责管理如何将可用的物理内存分配给需要它的进程。非连续内存分配是现代操作系统（如Linux、Windows）采用的主流方式，它允许一个进程的地址空间被分散地存放在不连续的物理内存块中。这与你之前学过的“连续内存分配”形成对比，后者要求进程的地址空间必须位于一段连续物理内存中。非连续分配的核心优势在于它能更有效地利用内存，并支持大型程序的运行。

核心思想与基础：分页（Paging）

非连续分配最经典和普遍的实现方式是分页。理解分页是理解所有非连续分配算法的基础。

基本概念划分：
- 逻辑地址空间：进程视角的内存。编译器为进程生成从0开始的一段连续的地址空间。
- 物理地址空间：实际硬件RAM的地址空间，由一系列物理内存帧组成。
- 关键思路：将进程的逻辑地址空间分割成一系列大小固定的块，称为页。同时，将物理内存也分割成同样大小的块，称为页框或帧。这样，一个进程的任一“页”可以被加载到物理内存的任一“页框”中。
地址转换机制 - 页表：
- 既然页可以分散存放在任意的页框里，操作系统就需要一个“地图”来记录每个逻辑页到底存放在哪个物理页框里。这个地图就是页表。
- 页表结构：每个进程都有一个独立的页表。页表可以看作一个数组，数组的索引是页号，数组里存放的值是对应的页框号。
- 地址构成：在分页系统中，CPU生成的逻辑地址被硬件自动划分为两部分：
  - 页号：地址的高位部分，用于在页表中查找对应的条目。
  - 页内偏移量：地址的低位部分，表示在该页内部的具体位置。页和页框大小相同，所以偏移量可以直接用于物理地址。
地址转换过程：
当CPU需要访问一个逻辑地址时，会发生以下步骤：
- 步骤1：内存管理单元（MMU）从逻辑地址中提取出页号p和页内偏移量d。
- 步骤2：MMU以页号p作为索引，去查找当前进程的页表。
- 步骤3：从页表的第p个条目中，找到对应的物理页框号f。
- 步骤4：将物理页框号f和原始的页内偏移量d组合起来，形成最终的物理地址。
- 步骤5：使用这个物理地址去访问真正的物理内存。
这个过程确保了即使逻辑页0、1、2分别存放在物理页框5、9、2中（完全不连续），进程也能像使用连续内存一样正常工作。

分页的演进与优化

基本的分页模型存在一个明显问题：页表本身也存储在内存中，每次内存访问实际上需要两次内存访问（一次查页表，一次取数据），这会使性能减半。为了解决这个问题，出现了关键的优化技术。

转换检测缓冲区（TLB）：
- 问题：基本分页的两次内存访问问题。
- 解决方案：在CPU和主存之间增加一个小型且高速的硬件缓存，专门用于存放最近使用过的页表项（页号->页框号的映射）。这个缓存就是TLB。
- 工作流程：
  - CPU给出逻辑地址。
  - MMU先查TLB。如果TLB中有所需页号的映射（称为TLB命中），则直接获得页框号，组合成物理地址，整个过程无需访问内存中的页表，速度极快。
  - 如果TLB中没有（称为TLB未命中），则MMU才不得不去内存中查找页表，找到映射关系后，不仅用其完成地址转换，还会将这个映射关系存入TLB（可能会替换掉一个旧条目），以备下次使用。
- 效果：由于程序具有局部性原理，TLB的命中率通常很高，从而极大地缓解了两次内存访问带来的性能开销。
多级页表：
- 问题：对于32位或64位系统，逻辑地址空间非常大，导致页表本身变得巨大，会占用过多的连续物理内存。例如，32位系统，4KB页大小，页表项4字节，那么一个进程的页表就需要 (2^32 / 2^12) * 4B = 4MB 的连续内存。这还只是一个进程，多个进程将消耗海量内存。
- 解决方案：采用多级页表，将单一的线性大页表变成一棵“页目录树”。
- 工作流程（以二级页表为例）：
  - 逻辑地址被划分为：页目录号 + 页表索引 + 页内偏移。
  - 第一级是页目录，每个条目指向一个二级页表的起始地址。
  - 第二级才是我们之前提到的页表，每个条目指向物理页框号。
  - 核心优势：如果进程的某些地址区间根本未被使用，那么对应的二级页表就无需创建。这大大节省了空间。一级页目录必须常驻内存，但二级页表可以按需调入调出。

另一种非连续分配方式：分段（Segmentation）

分页是从物理角度（固定大小）来划分进程地址空间，而分段则是从逻辑角度（可变大小）来划分。

基本思想：
- 一个进程的地址空间被划分为若干个逻辑段，例如：代码段、数据段、堆栈段等。
- 每个段有自己独立的逻辑地址空间，从0开始。
- 逻辑地址表示为：<段号，段内偏移>。
实现机制：
- 系统维护一个段表。每个段表条目记录了：
  - 基地址：该段在物理内存中的起始地址。
  - 段长：该段的长度，用于进行越界检查，提供内存保护。
- 地址转换过程：通过段号找到段表项，获得基地址和段长。检查偏移量是否小于段长，若无越界，则物理地址 = 基地址 + 段内偏移。
分段 vs. 分页：
- 优点：对程序员更“友好”，易于实现共享和保护（可以以“段”为单位设置读写执行权限）。
- 缺点：会产生外部碎片，因为段长可变，在内存中分配和回收后，会留下许多难以利用的小空闲区。

现代操作系统的实践：段页式结合

纯粹的分段由于外部碎片问题已很少单独使用。现代操作系统（如x86架构的Linux/Windows）结合了分段和分页的优点，采用段页式内存管理。

核心思想：先分段，再分页。
实现方式：
- 进程的地址空间仍然被划分为逻辑段（代码、数据等）。
- 但每个段本身不再是连续的一整块内存，而是被进一步划分为固定大小的页。
- 逻辑地址先通过段机制转换为一种中间地址（线性地址），然后再通过页机制将这个线性地址转换为物理地址。
效果：既获得了分段在逻辑管理和保护上的优点，又通过分页消除了外部碎片，并支持了虚拟内存（将页换出到磁盘）。

总结

非连续内存分配，特别是以分页为核心的技术，是现代操作系统内存管理的基石。它通过页表实现逻辑地址到物理地址的映射，通过TLB优化性能，通过多级页表解决大地址空间问题。而段页式结合则是实际应用中集大成的方案。理解这一套机制，是理解虚拟内存、进程隔离、程序加载等高级主题的关键。

操作系统中的内存管理：内存分配算法（非连续内存分配）在操作系统中，内存分配算法负责管理如何将可用的物理内存分配给需要它的进程。非连续内存分配是现代操作系统（如Linux、Windows）采用的主流方式，它允许一个进程的地址空间被分散地存放在不连续的物理内存块中。这与你之前学过的“连续内存分配”形成对比，后者要求进程的地址空间必须位于一段连续物理内存中。非连续分配的核心优势在于它能更有效地利用内存，并支持大型程序的运行。核心思想与基础：分页（Paging）非连续分配最经典和普遍的实现方式是分页。理解分页是理解所有非连续分配算法的基础。基本概念划分：逻辑地址空间：进程视角的内存。编译器为进程生成从0开始的一段连续的地址空间。物理地址空间：实际硬件RAM的地址空间，由一系列物理内存帧组成。关键思路：将进程的逻辑地址空间分割成一系列大小固定的块，称为页。同时，将物理内存也分割成同样大小的块，称为页框或帧。这样，一个进程的任一“页”可以被加载到物理内存的任一“页框”中。地址转换机制 - 页表：既然页可以分散存放在任意的页框里，操作系统就需要一个“地图”来记录每个逻辑页到底存放在哪个物理页框里。这个地图就是页表。页表结构：每个进程都有一个独立的页表。页表可以看作一个数组，数组的索引是页号，数组里存放的值是对应的页框号。地址构成：在分页系统中，CPU生成的逻辑地址被硬件自动划分为两部分：页号：地址的高位部分，用于在页表中查找对应的条目。页内偏移量：地址的低位部分，表示在该页内部的具体位置。页和页框大小相同，所以偏移量可以直接用于物理地址。地址转换过程：当CPU需要访问一个逻辑地址时，会发生以下步骤：步骤1 ：内存管理单元（MMU）从逻辑地址中提取出页号 p 和页内偏移量 d 。步骤2 ：MMU以页号 p 作为索引，去查找当前进程的页表。步骤3 ：从页表的第 p 个条目中，找到对应的物理页框号 f 。步骤4 ：将物理页框号 f 和原始的页内偏移量 d 组合起来，形成最终的物理地址。步骤5 ：使用这个物理地址去访问真正的物理内存。这个过程确保了即使逻辑页 0 、 1 、 2 分别存放在物理页框 5 、 9 、 2 中（完全不连续），进程也能像使用连续内存一样正常工作。分页的演进与优化基本的分页模型存在一个明显问题：页表本身也存储在内存中，每次内存访问实际上需要两次内存访问（一次查页表，一次取数据），这会使性能减半。为了解决这个问题，出现了关键的优化技术。转换检测缓冲区（TLB）：问题：基本分页的两次内存访问问题。解决方案：在CPU和主存之间增加一个小型且高速的硬件缓存，专门用于存放最近使用过的页表项（页号->页框号的映射）。这个缓存就是TLB。工作流程： CPU给出逻辑地址。 MMU先查TLB。如果TLB中有所需页号的映射（称为TLB命中），则直接获得页框号，组合成物理地址，整个过程无需访问内存中的页表，速度极快。如果TLB中没有（称为TLB未命中），则MMU才不得不去内存中查找页表，找到映射关系后，不仅用其完成地址转换，还会将这个映射关系存入TLB（可能会替换掉一个旧条目），以备下次使用。效果：由于程序具有局部性原理，TLB的命中率通常很高，从而极大地缓解了两次内存访问带来的性能开销。多级页表：问题：对于32位或64位系统，逻辑地址空间非常大，导致页表本身变得巨大，会占用过多的连续物理内存。例如，32位系统，4KB页大小，页表项4字节，那么一个进程的页表就需要 (2^32 / 2^12) * 4B = 4MB 的连续内存。这还只是一个进程，多个进程将消耗海量内存。解决方案：采用多级页表，将单一的线性大页表变成一棵“页目录树”。工作流程（以二级页表为例）：逻辑地址被划分为：页目录号 + 页表索引 + 页内偏移。第一级是页目录，每个条目指向一个二级页表的起始地址。第二级才是我们之前提到的页表，每个条目指向物理页框号。核心优势：如果进程的某些地址区间根本未被使用，那么对应的二级页表就无需创建。这大大节省了空间。一级页目录必须常驻内存，但二级页表可以按需调入调出。另一种非连续分配方式：分段（Segmentation）分页是从物理角度（固定大小）来划分进程地址空间，而分段则是从逻辑角度（可变大小）来划分。基本思想：一个进程的地址空间被划分为若干个逻辑段，例如：代码段、数据段、堆栈段等。每个段有自己独立的逻辑地址空间，从0开始。逻辑地址表示为： <段号，段内偏移> 。实现机制：系统维护一个段表。每个段表条目记录了：基地址：该段在物理内存中的起始地址。段长：该段的长度，用于进行越界检查，提供内存保护。地址转换过程：通过段号找到段表项，获得基地址和段长。检查偏移量是否小于段长，若无越界，则物理地址 = 基地址 + 段内偏移。分段 vs. 分页：优点：对程序员更“友好”，易于实现共享和保护（可以以“段”为单位设置读写执行权限）。缺点：会产生外部碎片，因为段长可变，在内存中分配和回收后，会留下许多难以利用的小空闲区。现代操作系统的实践：段页式结合纯粹的分段由于外部碎片问题已很少单独使用。现代操作系统（如x86架构的Linux/Windows）结合了分段和分页的优点，采用段页式内存管理。核心思想：先分段，再分页。实现方式：进程的地址空间仍然被划分为逻辑段（代码、数据等）。但每个段本身不再是连续的一整块内存，而是被进一步划分为固定大小的页。逻辑地址先通过段机制转换为一种中间地址（线性地址），然后再通过页机制将这个线性地址转换为物理地址。效果：既获得了分段在逻辑管理和保护上的优点，又通过分页消除了外部碎片，并支持了虚拟内存（将页换出到磁盘）。总结非连续内存分配，特别是以分页为核心的技术，是现代操作系统内存管理的基石。它通过页表实现逻辑地址到物理地址的映射，通过 TLB 优化性能，通过多级页表解决大地址空间问题。而段页式结合则是实际应用中集大成的方案。理解这一套机制，是理解虚拟内存、进程隔离、程序加载等高级主题的关键。