内存管理概念

⭐ 中优先级

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

内存管理

基础概念

虚拟地址 和 物理地址 空间

虚拟地址（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 ，则利用率为：

利用率=F/P

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

Next Fit 根据上次分配的位置

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

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

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

堆内存分配

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

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

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

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

伙伴算法

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

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

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

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

提示

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

伙伴关系

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

离散分配管理方式

页式管理

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

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

注意

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

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

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

段式管理

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

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

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

段概念

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

段表

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

段表与地址翻译逻辑地址 (段地址)段号2段内偏移300用段号查表段表段号基地址限制010004001200060023000800越界检查偏移(300) < 限制(800) ?✓ 通过如果超出则产生段越界错误获取基地址地址计算物理地址 = 基地址 + 偏移3000 + 300 = 3300物理地址3300翻译步骤:1. 从逻辑地址提取段号(2)2. 用段号查段表获得基地址(3000)和限制(800)3. 检查偏移(300)是否小于限制(800)4. 计算物理地址: 3000 + 300 = 3300物理内存段01000-1399段12000-2599段23000-37993300段表实现了逻辑地址到物理地址的映射，同时提供越界保护

地址翻译

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

段页式管理

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

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

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

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