内存管理概念

⭐ 中优先级

真题练习

页式虚拟存储的细节都在组成原理章节，对于本节，重点掌握 动态分区分配算法 以及 几种内存管理方式（页式、段式、段页式）的概念和特点。

内存管理

基础概念

虚拟地址 和 物理地址 空间

虚拟地址（VA, Virtual Address）由指令中的 地址字段 给出，进程看到的都是虚拟地址。物理地址是内存单元在实际内存硬件中的真实位置。

地址翻译

地址翻译指的是在程序执行的过程中 将虚拟地址翻译为物理地址，地址变换由内存管理单元（MMU, Memory Management Unit）在硬件中完成，速度非常快。

内存共享

共享内存（Shared Memory）是多个进程共享的 内存区域。它是最快的 IPC（进程间通信）机制之一，因为进程直接读写内存，无需进入内核态。但是，因为多个进程可以同时访问这些内存，所以可能需要某种 同步机制（如信号量）来防止竞态条件。

内存保护

内存保护是现代操作系统中的一个 核心功能，用于防止一个进程访问另一个进程的 内存空间。这不仅保障了系统的稳定性，而且提高了安全性，因为它可以防止恶意软件损害其他进程或篡改其数据。

可以通过如下机制实现内存保护机制：

分段与分页：
- 分段：内存被划分为不同的段，每个段都有其起始地址和长度。段常常用于表示高级的数据结构，如函数或对象。
- 分页：内存被划分为固定大小的页面，例如 4KB。操作系统为每个进程维护一个页表，来映射其虚拟地址到物理地址。
访问权限：每个段或页面都有与之相关的访问权限。例如，一个页面可能被标记为只读，这意味着任何尝试写入该页面的操作都会引发一个异常。
隔离：由于每个进程都有其独立的地址空间，所以一个进程不能直接访问另一个进程的内存。这为每个进程提供了一种形式的隔离，确保了一个出错的进程不会影响其他进程。

管理方式分类

在现代操作系统中，内存管理方式 大体可以归纳为两类：连续分配 和 离散分配。所谓 连续分配，是指操作系统为进程分配一整段连续的内存区域。这种方式实现简单、开销较小，但灵活性不足。典型的连续分配方式包括三种：单一连续分配、固定分区分配以及动态分区分配。

相比之下，离散分配 方式允许进程占用的内存空间是 不连续的，这使得内存利用率和管理灵活性显著提高。典型的离散分配方式也包含三种：页式、段式、段页式。

后文会具体介绍这几种内存管理方式的细节。

连续分配管理方式

单一连续分配

内存在此方式下分为 系统区 和 用户区，系统区仅供操作系统使用，通常在高地址部分；在用户区内存中，仅有一道用户程序，即整个内存的用户空间都由该程序独占。

这种方式的优点是 简单、无外部碎片，无需进行内存保护，因为内存中永远只有一道程序。缺点是只能用于 单用户、单任务 的操作系统中，存储器的利用率极低。

固定分区分配

固定分区分配是最简单的一种 多道程序存储管理 方式，它将用户内存空间划分为若干 固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该内存，如此循环。

为了方便内存分配，通常将分区按大小排队，并为之建立一张 分区说明表，其中各表项包含每个分区的起始地址、大小和状态。当有用户程序需要装入时，便检索该表，以找到合适的分区基于分配并将其状态设置为“已分配”；未找到合适分区时，则拒绝为给程序分配内存。

动态分区分配

在 固定分区分配 中，内存被预先划分为若干大小固定的区域。这种方式实现简单，但也带来了一个明显问题：分区大小是静态的，而作业大小是动态的。

为了解决固定分区“尺寸僵化、内存利用率低”的问题，操作系统引入了 动态分区分配。

动态分区分配的基本思想是： 不再事先划分固定大小的分区，而是将整个用户内存空间视为一块 连续的可分配区域，在程序装入时才根据其实际需要动态地划分内存。

当进程请求内存时，操作系统从当前的空闲内存中划出一块连续区域分配给该进程；当进程结束或释放内存时，该区域重新成为空闲内存，可供后续进程再次使用。

通过这种 动态、按需分配 的方式，内存从逻辑上被划分为两类区域：

已分配区：正在被内核或进程占用的内存
空闲区：尚未分配、可供后续进程使用的内存

如下图所示，其中 内核内存（kernel memory） 和 进程内存（process memory） 属于已分配区域，其余部分为系统当前的空闲内存。

为了管理这些不断变化的空闲区域，操作系统通常维护一张 空闲分区表（或空闲链表），用于记录每一块空闲内存的：

起始地址
大小

示意如下：

当进程申请内存时，操作系统会遍历 空闲分区表，按照预定的 适应算法（如首次适应、最佳适应等），从中选择一块满足需求的空闲区域，并完成内存分配。

不同适应算法的选择，会直接影响系统中 外部碎片 的产生情况，这一点将在后续章节中详细讨论。

内存碎片

动态分区分配相比固定分区分配，提高了内存使用率，但是仍然无法避免内存碎片的问题，下图以一个实例说明了在动态分区分配过程中内存碎片产生的过程：

由于各进程所需的内存大小各不相同，在进行内存分配时经常会在已分配的块之间留下 内存碎片。

所谓内存碎片，指的是那些 尺寸过小、无法满足任何进程实际需求 的空闲内存块。因为进程的内存申请往往大于等于某个最小阈值，这些零散且容量不足的碎片就无法被再次利用，导致可用内存实际被浪费。

适应算法

内存空间中的空闲区域可能大小不一，且分布在内存中不同的位置，操作系统使用 空闲块表 来记录这些空闲区域的信息。

当进程申请一块新的内存时，必须从已有的空闲空间中选出一块分配给进程。动态分区的分配策略主要包含四种算法：首次适应（First Fit）、临近适应（Next Fit）、最佳适应（Best Fit）、最坏适应（Worst Fit）。

First Fit （首次适应）：从头遍历空闲块表，找到第一个足够的空闲块 分配给进程。
Next Fit （临近适应）：从上次分配的位置的下一个位置开始查找，找到的第一个足够大的分区分配给进程。如果到了表尾没找到，就从头循环，直到找到或遍历一圈失败。
Best Fit （最佳适应）：遍历整个空闲块表，找到一个 利用率最高 的空闲块给进程。
Worst Fit （最坏适应）：与最佳适应的目标相反，找到一个 利用率最低 的空闲块给进程。

注意

临近适应中的 next 究竟如何理解

“next” 不是指“下一次从上一次分配的那个区块自身开始”，而是指“从上一次分配的那个区块的下一个位置开始查找”。

举个例子，假设有有三个空闲区块 B1, B2, B3，上次是在 B2 分配的，如果采用 next fit 算法，下一次是在 B3 分配（体现 next 的语义），而不是 B2 分配。

适应算法中的利用率计算

假设进程申请的内存大小为 P，空闲块大小为 F，则利用率为：

利用率 = \frac{P}{F}

举个实例例子，假设空闲块序列 [8, 22, 20, 14, 10, 24]，请求大小 P = 16。则四种分配算法会得到不同的结果：

四种适应算法在该例子的对比如下表所示：

算法	查找方式	本例选择结果
First Fit（首次适应）	从空闲块表的头开始，找到第一个 ≥ P 的分区。	`22`（第一个 ≥16 的块）
Next Fit（邻近适应）	从上一次查找结束时的游标位置的下一个空闲块开始顺序查找，找到第一个 ≥ P 的分区；若查到表尾仍未找到，则从表头继续查找一轮。	结果取决于“上一次查找游标”的位置： • 游标在 `8` 处 → 选 `22` • 游标在 `22` 处 → 选 `20` • 游标在 `20` 处 → 选 `24`
Best Fit（最佳适应）	遍历整个空闲块表，找到能容纳 P 且最小的分区（利用率最高）。	`20`（最小的 ≥16 的块，利用率 16/20=80%）
Worst Fit（最坏适应）	遍历整个空闲块表，找到能容纳 P 且最大的分区（利用率最低）。	`24`（最大的 ≥16 的块，利用率 16/24≈66.7%）

内存回收过程

当对 动态内存 进行回收时，需要检查是否可以有相邻 空闲块 合并，如果可以合并的话，合并后需要更新起始地址和大小。

如果没有相邻的空闲块需要合并，直接将释放的内存块作为 独立空闲块 插入空闲块表。

堆内存分配

动态分区分配最初用于操作系统在物理内存中为进程分配连续空间；随着虚拟内存的引入，进程不再需要连续的物理内存，该机制在 OS 层面被分页取代；但其在连续地址空间中按需划分和回收内存的思想，被继承并演化为进程堆内存的分配机制。

早期 OS（无虚拟内存） 动态分区用于在物理内存中为进程分配连续空间。
引入虚拟内存 分页机制消除了进程对连续物理内存的需求，OS 层面的动态分区逐渐退出。
思想下沉到用户态 动态划分、回收连续空间的思想，被用于管理进程的堆内存，形成现代内存分配器。

参考进程内存空间，当一个进程使用操作系统提供的 malloc 接口时，它实际上是在向进程的堆（heap）区域请求一块连续可用的虚拟地址空间，当进程使用 free 接口时，实际上是在堆上释放刚刚申请的动态空间。操作系统或运行时库会负责管理堆空间，其底层机制正是动态分区分配思想的延续。

具体来说，堆内存管理器维护着一个空闲内存块的列表（或类似数据结构），当进程申请内存时，管理器会根据适应算法寻找足够大的空闲块，将其一部分分配给请求，剩余部分可能仍作为空闲块保留。当进程释放内存时，该内存块会被回收并合并相邻的空闲块，以减少碎片。

伙伴算法

伙伴算法（Buddy Algorithm）将内存分为大小为 2 的幂次方的块（例如，1KB、2KB、4KB、8KB 等）。当需要分配内存时，算法寻找合适的块；如果没有合适的块，就将更大的块一分为二，直到满足需求。释放内存时，算法尝试将相邻的“伙伴”块合并为更大的块，以减少 内存碎片。

内存分配过程

假设需要分配大小为 $S$ 的内存，算法找到最小的大小为 $2^{n}$ （n 为正整数）块，使得 $2^{n} \geq S$ 。
- 如果有，直接分配该块。
- 如果没有，查找更大一级（ $2^{(n + 1)}$ ）的空闲块，将其一分为二，生成两个 $2^{n}$ 的伙伴块：
  - 一个用于分配。
  - 另一个加入 $2^{n}$ 的空闲链表。
- 如果 $2^{(n + 1)}$ 也没有空闲块，继续向上查找，直到找到合适大小的块或失败。
  分配后更新空闲链表。

下图包含一个使用伙伴算法的 内存分配实例：

内存释放过程

释放一块内存时，检查其“伙伴”块是否也空闲：
- 伙伴块是指与当前块大小相同、地址相邻、且由同一父块分割而来的块。
- 例如，地址为 $A$ 的 $2^{n}$ 块，其伙伴地址为 $A \pm 2^{n}$ （具体取决于地址对齐）。
如果伙伴块空闲，合并为一个 $2^{(n + 1)}$ 的块，并加入更高一级的空闲链表。
重复检查合并，直到无法合并（伙伴不空闲或达到最大块大小）。

提示

联想一下 2048 小游戏，伙伴算法的内存释放过程与之十分类似。

伙伴关系

伙伴块的地址满足特定关系。例如，假设内存起始地址为 0，块大小为 $2^{n}$ ，则地址 $A$ 的伙伴地址为 $A \oplus 2^{n}$ （按位异或）。通过这种关系，算法可以快速定位伙伴块。

离散分配管理方式

页式管理

页式管理的细节详见组成原理中的对应章，这里仅给出基本的思想以与 段式管理 和 段页式管理 进行对比。

页式内存管理的基本思想是将 虚拟内存 和 物理内存 分为若干个大小固定的页面，然后通过页表建立从虚拟页面到物理页面的映射，这样进程就可以离散地使用物理内存中的不同页面。

注意

STBR (segment table base register) 指的是 段表基址寄存器，其中存储的内容是段表在内存中的地址。

PTBR （page table base register）指的是 页表基址寄存器，其中存储的内容是页表在内存中的地址。

通过 表基址寄存器 加上一个偏移，可以访问到表中的某个表项。

段式管理

段式内存管理将程序的不同部分（例如 代码、数据和堆栈）划分为不同的段（segments）。每个段在物理内存中可以不连续，但在逻辑上都被视为连续的。

段式管理的主要优点是它比较简单，有助于提供更好的保护和 共享机制，在 8086 CPU 中使用的内存管理策略就是段式管理。

下文介绍一下段式内存管理中的三个关键概念：段、段表以及 地址转化。

段概念

每个段都有一个明确的角色，例如 代码段、数据段 或 堆栈段。
每个段都有一个 起始地址 和长度。
段内的地址是连续的，但不同段之间的地址可以不连续。

段表

段表是一种数据结构，用于存储每个段的 基地址（在物理内存中的起始地址）和限制（段的长度或末尾地址）。
当一个程序需要访问其内存段时，会使用段号和 段内偏移 作为地址。这个地址被称为 逻辑地址 或 段地址。
逻辑地址通过段表转换为 物理地址。

地址翻译

为了从逻辑地址获取物理地址，首先需要从逻辑地址中提取段号，然后使用段号在段表中查找相应的基地址和限制。
然后，检查逻辑地址中的 偏移量 是否小于该段的限制。如果偏移量超出限制，则产生 段越界错误。
如果偏移量有效，则将偏移量加到段的基地址上，得到 物理地址。

段页式管理

段页式管理（paged segmentation）是一种将 段式内存管理 与 分页式内存管理 相结合的策略。
在段页式管理中，程序首先被划分为逻辑上的段，然后每个段进一步被划分为固定大小的页。
首先，操作系统通过段表对不同的段进行管理。
在每一个段的内部，采用分页的方式将段分为不同的页，实现虚拟页面到物理页面的映射。

在使用段页式内存管理的策略时，虚拟地址可以拆分为三个部分：段号（Segment No）、页号（Page No）、页内偏移（Offset）。

在地址翻译的过程中，首先通过虚拟地址中的段号在段表中找到 页表的起始地址，接下来再通过页号在页表中找到该地址对应的 物理页面号。

它结合了两者的优势，旨在提供 灵活性 和 减少内存碎片。