操作系统中的内存管理：内存分配算法（非连续内存分配）
字数 2380 2025-11-10 11:52:13

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

在操作系统中，内存分配是核心功能之一。你已经了解了连续内存分配，即进程所需的内存空间必须是一段连续的物理地址。然而，连续分配容易导致外部碎片，即使总空闲内存足够，也可能因为分散在不连续的区域而无法满足大进程的需求。非连续内存分配正是为了解决这个问题而提出的。

核心思想
非连续内存分配允许一个进程的内存空间被分散在物理内存的不同位置。这样，操作系统可以利用那些小而分散的内存碎片。实现非连续分配的主要技术是分页和分段。

分页机制详解

分页是最常见、最通用的非连续内存管理方案。

1. 基本概念

  • 页面：将进程的逻辑地址空间划分为一系列大小固定的块，每个块称为一个页面。
  • 页框：将物理内存空间也划分为同样大小固定的块，每个块称为一个页框或物理块。
  • 核心数据结构：页表：操作系统为每个进程维护一个页表。页表的作用是建立进程的页面与物理内存的页框之间的映射关系。可以把它想象成一个“地图”或“通讯录”。

2. 地址转换过程
逻辑地址被分为两部分：

  • 页号：地址的高位部分，用于索引页表。
  • 页内偏移量：地址的低位部分，表示在特定页面/页框内的具体位置。

转换步骤（无快表TLB的最简单情况）：

  1. 提取页号与偏移量：CPU发出一个逻辑地址。内存管理单元（MMU）自动将这个地址拆分成页号（p）和页内偏移量（d）。
  2. 查找页表：MMU使用页号（p）作为索引，去查找当前进程的页表。
  3. 获取页框号：在页表的第p个表项中，存储着该逻辑页面对应的物理页框号（f）。
  4. 合成物理地址：MMU将找到的物理页框号（f）与原始的页内偏移量（d）组合起来，形成最终的物理地址。
  5. 访问内存：这个物理地址被送到内存总线上，从而访问实际的物理内存。

举例说明：
假设页面大小为4KB（2^12字节），逻辑地址是0x2050（十六进制）。

  • 逻辑地址0x2050的二进制是 0010 0000 0101 0000。
  • 页内偏移量d占低12位，即 0000 0101 0000 = 0x050。
  • 剩下的高位是页号p。0x2050除以4KB（0x1000），页号p=2。
  • MMU查找页表的第2项，假设里面记录的页框号f=7。
  • 那么物理地址 = 页框号7的起始地址 + 偏移量0x050 = 7 * 4KB + 0x050 = 0x7000 + 0x50 = 0x7050。

3. 分页的优势与挑战

  • 优势：完全解决了外部碎片问题。任何空闲页框都可以分配给需要的进程。
  • 挑战一：内部碎片：进程的最后一页很可能用不完，会造成页内空间的浪费。平均而言，每个进程会浪费半页的内存。页面越小，内部碎片越小，但页表会越大。
  • 挑战二：页表开销：每个进程都需要一个页表。对于32位系统（4GB地址空间），如果页面大小为4KB，那么一个进程最多可能有2^20个（约100万个）页表项。每个页表项占4字节，一个页表就要占4MB！这本身就是一个巨大的内存开销。

解决页表过大问题：多级页表

多级页表是一种“页表的页表”的思想，旨在减少页表对连续内存的占用。

1. 核心思想
将页表本身也进行分页。建立一个顶级页表（页目录），它的每个表项指向一个二级页表。二级页表的每个表项再指向真正的物理页框。

2. 工作过程（以二级页表为例）
逻辑地址被划分为三部分：一级页号、二级页号、页内偏移量。

  1. MMU用一级页号索引顶级页表，找到对应的二级页表在内存中的位置。
  2. 再用二级页号索引这个二级页表，找到最终的物理页框号。
  3. 将页框号与偏移量组合成物理地址。

3. 多级页表的优势
它解决了页表需要连续存储的问题。如果进程的某些地址范围根本没有使用，那么对应的二级页表就无需创建，从而节省了大量空间。这是一种典型的“以时间换空间”的策略，因为一次地址转换需要多次访问内存，性能会下降。为了解决这个性能问题，才引入了快表。

分段机制简介

分段提供了另一种非连续分配的视角，它更符合用户的逻辑观点。

1. 基本概念

  • 一个进程的地址空间被划分为若干个段，例如代码段、数据段、堆栈段等。
  • 每个段有逻辑意义，大小不固定。
  • 核心数据结构：段表：每个段在段表中有一项，记录了该段在物理内存中的起始地址和段长（用于越界检查）。

2. 地址转换过程
逻辑地址被分为两部分：

  • 段号：指定是哪个段（如代码段、数据段）。
  • 段内偏移量：指定在该段内的具体位置。

转换步骤：

  1. MMU用段号（s）索引段表。
  2. 检查段内偏移量（d）是否小于段长，若超过则产生越界中断。
  3. 从段表项中取出该段的物理基地址。
  4. 物理地址 = 段基地址 + 段内偏移量。

3. 分页与分段的区别

特性 分页 分段
划分单位 固定的、物理的“页面” 不固定的、逻辑的“段”
对程序员可见性 透明（由操作系统完成） 通常可见（由编译器支持）
地址空间维度 一维线性地址空间 二维地址空间（段号：段内偏移）
碎片问题 内部碎片 外部碎片
主要目的 实现非连续分配，提高内存利用率 满足用户逻辑视图，方便共享和保护

总结

非连续内存分配通过分页和分段技术，有效地解决了连续分配带来的外部碎片问题。其中，分页由于其实现的简单性和高效性，成为了现代操作系统的基石。而为了应对分页带来的页表过大问题，多级页表成为了标准解决方案。分段则从另一个角度（逻辑角度）管理内存，虽然在通用操作系统中很少单独使用，但其思想（按逻辑单元进行内存保护和共享）与分页结合，形成了更强大的段页式内存管理。

操作系统中的内存管理：内存分配算法（非连续内存分配） 在操作系统中，内存分配是核心功能之一。你已经了解了连续内存分配，即进程所需的内存空间必须是一段连续的物理地址。然而，连续分配容易导致外部碎片，即使总空闲内存足够，也可能因为分散在不连续的区域而无法满足大进程的需求。非连续内存分配正是为了解决这个问题而提出的。 核心思想 非连续内存分配允许一个进程的内存空间被分散在物理内存的不同位置。这样，操作系统可以利用那些小而分散的内存碎片。实现非连续分配的主要技术是 分页 和 分段 。 分页机制详解 分页是最常见、最通用的非连续内存管理方案。 1. 基本概念 页面 ：将进程的 逻辑地址空间 划分为一系列大小固定的块，每个块称为一个页面。 页框 ：将 物理内存空间 也划分为同样大小固定的块，每个块称为一个页框或物理块。 核心数据结构：页表 ：操作系统为每个进程维护一个页表。页表的作用是建立进程的 页面 与物理内存的 页框 之间的映射关系。可以把它想象成一个“地图”或“通讯录”。 2. 地址转换过程 逻辑地址被分为两部分： 页号 ：地址的高位部分，用于索引页表。 页内偏移量 ：地址的低位部分，表示在特定页面/页框内的具体位置。 转换步骤（无快表TLB的最简单情况）： 提取页号与偏移量 ：CPU发出一个逻辑地址。内存管理单元（MMU）自动将这个地址拆分成页号（p）和页内偏移量（d）。 查找页表 ：MMU使用页号（p）作为索引，去查找当前进程的页表。 获取页框号 ：在页表的第p个表项中，存储着该逻辑页面对应的物理页框号（f）。 合成物理地址 ：MMU将找到的物理页框号（f）与原始的页内偏移量（d）组合起来，形成最终的物理地址。 访问内存 ：这个物理地址被送到内存总线上，从而访问实际的物理内存。 举例说明： 假设页面大小为4KB（2^12字节），逻辑地址是0x2050（十六进制）。 逻辑地址0x2050的二进制是 0010 0000 0101 0000 。 页内偏移量d占低12位，即 0000 0101 0000 = 0x050。 剩下的高位是页号p。0x2050除以4KB（0x1000），页号p=2。 MMU查找页表的第2项，假设里面记录的页框号f=7。 那么物理地址 = 页框号7的起始地址 + 偏移量0x050 = 7 * 4KB + 0x050 = 0x7000 + 0x50 = 0x7050。 3. 分页的优势与挑战 优势 ：完全解决了外部碎片问题。任何空闲页框都可以分配给需要的进程。 挑战一：内部碎片 ：进程的最后一页很可能用不完，会造成页内空间的浪费。平均而言，每个进程会浪费半页的内存。页面越小，内部碎片越小，但页表会越大。 挑战二：页表开销 ：每个进程都需要一个页表。对于32位系统（4GB地址空间），如果页面大小为4KB，那么一个进程最多可能有2^20个（约100万个）页表项。每个页表项占4字节，一个页表就要占4MB！这本身就是一个巨大的内存开销。 解决页表过大问题：多级页表 多级页表是一种“页表的页表”的思想，旨在减少页表对连续内存的占用。 1. 核心思想 将页表本身也进行分页。建立一个顶级页表（页目录），它的每个表项指向一个二级页表。二级页表的每个表项再指向真正的物理页框。 2. 工作过程（以二级页表为例） 逻辑地址被划分为三部分： 一级页号 、 二级页号 、 页内偏移量 。 MMU用一级页号索引顶级页表，找到对应的二级页表在内存中的位置。 再用二级页号索引这个二级页表，找到最终的物理页框号。 将页框号与偏移量组合成物理地址。 3. 多级页表的优势 它解决了 页表需要连续存储 的问题。如果进程的某些地址范围根本没有使用，那么对应的二级页表就无需创建，从而节省了大量空间。这是一种典型的“以时间换空间”的策略，因为一次地址转换需要多次访问内存，性能会下降。为了解决这个性能问题，才引入了 快表 。 分段机制简介 分段提供了另一种非连续分配的视角，它更符合用户的逻辑观点。 1. 基本概念 一个进程的地址空间被划分为若干个 段 ，例如代码段、数据段、堆栈段等。 每个段有逻辑意义，大小不固定。 核心数据结构：段表 ：每个段在段表中有一项，记录了该段在物理内存中的 起始地址 和 段长 （用于越界检查）。 2. 地址转换过程 逻辑地址被分为两部分： 段号 ：指定是哪个段（如代码段、数据段）。 段内偏移量 ：指定在该段内的具体位置。 转换步骤： MMU用段号（s）索引段表。 检查段内偏移量（d）是否小于段长，若超过则产生越界中断。 从段表项中取出该段的物理基地址。 物理地址 = 段基地址 + 段内偏移量。 3. 分页与分段的区别 | 特性 | 分页 | 分段 | | :--- | :--- | :--- | | 划分单位 | 固定的、物理的“页面” | 不固定的、逻辑的“段” | | 对程序员可见性 | 透明（由操作系统完成） | 通常可见（由编译器支持） | | 地址空间维度 | 一维线性地址空间 | 二维地址空间（段号：段内偏移） | | 碎片问题 | 内部碎片 | 外部碎片 | | 主要目的 | 实现非连续分配，提高内存利用率 | 满足用户逻辑视图，方便共享和保护 | 总结 非连续内存分配通过分页和分段技术，有效地解决了连续分配带来的外部碎片问题。其中， 分页 由于其实现的简单性和高效性，成为了现代操作系统的基石。而为了应对分页带来的页表过大问题， 多级页表 成为了标准解决方案。 分段 则从另一个角度（逻辑角度）管理内存，虽然在通用操作系统中很少单独使用，但其思想（按逻辑单元进行内存保护和共享）与分页结合，形成了更强大的 段页式内存管理 。