内存管理概念

内存管理的基本概念

• 逻辑地址 和 物理地址 空间
• 地址变换
• 内存共享

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

• 内存保护

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

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

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

连续分配管理方式

单一连续分配

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

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

固定分区分配

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

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

动态分区分配

动态分区分配的含义就是将内存看成一整块 连续的区域，每次分配的时候直接从其中的空闲区域申请一块内存即可。

申请过的内存可以 释放，成为空闲内存的一部分，释放后的内存可以被其他进程所用。

通过对一段连续的内存进行 动态地分配，内存中的区域可以从逻辑上被划分为 空闲 和 占用 两个部分。下图中的 内核内存（kernel memory）以及 进程内存（process memory）就是被占用的内存。

操作系统可以通过一个 表格 的形式来记录以上空闲内存的大小和起始地址：

当进程申请内存时，操作系统会遍历 空闲块表，根据设定的[#算法]选择出空闲块，然后为进程分配所需的内存空间。

内存碎片

由于每块进程申请的内存大小不同，所以在分配的内存之间可能出现 内存碎片。

内存碎片就是大小比较小的空闲块，无法被其他进程再利用（进程不会申请这么小的空间）。

适应算法

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

当进程申请一块新的内存时，必须从已有的空闲空间中选出一块分配给进程。动态分区的分配策略主要包含四种算法：first fit、next fit、best fit、worst fit。

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

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

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

—

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

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

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

伙伴算法

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

内存分配过程

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

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

内存释放过程

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

伙伴关系

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

页式管理

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

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

段式管理

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

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

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

段定义

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

段表

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

地址转换

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

段页式管理

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

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

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

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