408 高频考点精讲:动态内存管理¶
模块归属:操作系统 · 内存管理
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
1. 考查频次统计¶
- 近十年考查频次:3 次(2017 年第 25 题、2019 年第 32 题、2024 年第 27 题)
- 历年统考总频次:4 次(2010 年第 25 题、2017 年第 25 题、2019 年第 32 题、2024 年第 27 题)
- 出题形式:单项选择题(亦具备与进程调度、动态重定位、基本分页存储管理联合考查综合解答题的命题潜质)
2. 命题特点分析¶
- 空闲分区链动态演化及合并拓扑:重点考查动态分区分配在内存回收阶段的四种边界合并情形(前邻、后邻、前后皆邻、前后均不邻),并结合特定分配算法(如最佳适应算法)在操作完成后对空闲链表的重新排序与状态更新(如 2017 年第 25 题)。
- 分配算法病态行为与碎片成因剖析:深度考查首次适应、循环首次适应(邻近适应)、最佳适应、最坏适应四类经典算法的核心特性对比,尤其是最佳适应算法因局部贪心匹配导致产生大量微小“针头碎片”(难以利用的外部碎片)的本质机理(如 2019 年第 32 题)。
- 特定分配架构的约束准则与算法机制:考查现代操作系统底层常用的伙伴系统(Buddy System)的分区二分分裂、互为伙伴块的充要条件(大小相等、物理地址相邻、来源于同一次分裂)以及递归合并规则(如 2024 年第 27 题)。
3. 近十年考查年份分布表格¶
+----------+------+------+------+------+------+------+------+------+------+------+
| 年份 | 2016 | 2017 | 2018 | 2019 | 2020 | 2021 | 2022 | 2023 | 2024 | 2025 |
+----------+------+------+------+------+------+------+------+------+------+------+
| 考查题号 | -- | #25 | -- | #32 | -- | -- | -- | -- | #27 | -- |
+----------+------+------+------+------+------+------+------+------+------+------+
| 考查分值 | 0 分 | 2 分 | 0 分 | 2 分 | 0 分 | 0 分 | 0 分 | 0 分 | 2 分 | 0 分 |
+----------+------+------+------+------+------+------+------+------+------+------+
二、 具体考察内容¶
1. 核心概念与机制原理¶
1.1 连续分配管理方式演进¶
连续分配指系统为用户程序分配一个连续的物理内存空间。其演进路线如下: - 单一连续分配:内存划分为系统区与用户区,用户区由单道作业独占。无外部碎片,内部碎片严重,不支持多道程序设计。 - 固定分区分配:系统预先将用户空间划分为若干固定大小的分区(各分区大小可均等或不均等),每个分区装入一道作业。采用“分区说明表”维护。不存在外部碎片,但会产生严重的内部碎片。 - 动态分区分配(可变分区分配):在作业装入内存时,根据作业的实际需求动态建立分区。分配的分区大小正好等于作业需求,因而初次分配时不产生内部碎片;但在多道程序反复装入与释放过程中,物理内存会被分割为许多分散的空闲块,产生外部碎片。
1.2 动态分区管理的数据结构¶
- 空闲分区表:每个表项登记分区的序号、起始地址、分区大小及分配状态。
- 空闲分区链:采用双向链表将所有空闲分区连接,节点内部包含起始地址、分区大小、前向指针与后向指针等控制信息。
+-------------------------------------------------------------------------+
| 空闲分区双向链表节点结构 |
+---------------------+-------------------+---------------+---------------+
| 前向指针 (prior) | 后向指针 (next) | 分区起始地址 | 分区长度 Size |
+---------------------+-------------------+---------------+---------------+
1.3 经典动态分区分配算法¶
| 算法名称 | 链表排序策略 | 分配检索流程 | 核心优缺点与碎片特征 |
|---|---|---|---|
| 首次适应算法 (First Fit, FF) | 按物理地址递增排序 | 从链首顺序检索,找到第一个容量满足需求的分区即执行分割 | 综合性能最优。保留高地址大空间;缺点是低地址产生大量小碎片,增加检索开销。 |
| 邻近适应算法 (Next Fit, NF) | 按物理地址递增构成循环链表 | 从上次查找结束的位置继续向后顺序检索 | 分布较为均匀,减少链首检索开销;但使高地址大空闲区过早被分割破坏。 |
| 最佳适应算法 (Best Fit, BF) | 按分区容量递增排序 | 从链首顺序检索,选取第一个满足需求的空闲块(即大小最接近需求的块) | 保留大空闲块;但每次割裂后剩余空间极小,产生大量无法利用的细小外部碎片。 |
| 最坏适应算法 (Worst Fit, WF) | 按分区容量递减排序 | 直接检查链首最大分区;若链首无法满足,则分配失败 | 分割后剩余碎片较大,不易产生微小碎片;但迅速消耗大空闲区,对大作业极不友好。 |
1.4 动态分区回收合并拓扑¶
当进程运行结束释放占用空间时,设回收区物理区间为 \([A_R, A_R + S_R)\),系统需在空闲分区链中探测相邻空闲块并执行合并操作。存在四种拓扑情形:
情形一:回收区与前驱相邻 情形二:回收区与后继相邻
+-----------------------+ +-----------------------+
| 前驱空闲区: [Ap, Sp) | | 回收区: [Ar, Sr) |
+-----------------------+ +-----------------------+
| 回收区: [Ar, Sr) | | 后继空闲区: [As, Ss) |
+-----------------------+ +-----------------------+
合并结果: [Ap, Sp + Sr) 合并结果: [Ar, Sr + Ss)
情形三:回收区同时与前后相邻 情形四:前后均无相邻空闲区
+-----------------------+ +-----------------------+
| 前驱空闲区: [Ap, Sp) | | 独立回收区: [Ar, Sr) |
+-----------------------+ +-----------------------+
| 回收区: [Ar, Sr) | 合并结果: 建立独立空闲节点
+-----------------------+ 空闲分区节点总数增加 1
| 后继空闲区: [As, Ss) |
+-----------------------+
合并结果: [Ap, Sp + Sr + Ss)
空闲分区节点总数减少 1
- 仅与前驱相邻(\(A_P + S_P = A_R\)$ \text{):前驱节点长度修改为} $\(S_P \leftarrow S_P + S_R\)。
- 仅与后继相邻(\(A_R + S_R = A_S\)$ \text{):后继节点起始地址更新为} $\(A_R\)$ \text{,长度更新为} $\(S_R + S_S\)。
- 前后均相邻(\(A_P + S_P = A_R\)$ \text{且} $\(A_R + S_R = A_S\)$ \text{):前驱节点长度扩展为} $\(S_P + S_R + S_S\);后继节点从双向链表中解挂释放,系统中空闲分区总数减少 1。
- 前后均不相邻:新建空闲分区节点,按照当前算法排序准则插入双向链表中,系统中空闲分区总数增加 1。
[!IMPORTANT] 算法链表重新维护要求:若采用最佳适应算法(按容量升序)或最坏适应算法(按容量降序),分区合并改变了分区大小,该节点在链表中的偏序位置被打破,系统必须将该节点从原位置移出,重新插入排序后的正确位置。
1.5 碎片机理与紧凑技术¶
- 内部碎片:已分配给进程的存储空间中未被使用的多余部分(如分页存储中的最后一页、固定分区中作业未用满的部分)。
- 外部碎片:内存中处于未分配状态但由于容量过小、空间分散而无法满足任何进程请求的零散空间。
- 紧凑技术(Compaction / 拼接):将内存中所有分散的占用区向一端搬移,将零散的外部碎片合并为连续的大空闲分区。
- 前提条件:系统必须支持动态运行时装入与重定位(硬件具备重定位寄存器与界地址寄存器),以便在内存物理搬移后动态修正基址。
- 代价开销:涉及海量内存数据拷贝,消耗极高 CPU 与总线周期,必须控制紧凑触发时机。
1.6 伙伴系统(Buddy System)机制¶
伙伴系统是一种兼具连续分配与可控外部碎片的折中分配算法,是 Linux 内核物理页框管理(alloc_pages)的核心基石。
- 规格设定:整个可用内存空间大小为 \(2^U\)$ \text{。所有可分配分区的尺寸均为 2 的整数次幂,即} $\(2^k\)(\(L \le k \le U\))。
- 数据结构:系统维护一个由链表头组成的数组 free_area[k],每个表头挂接大小为 \(2^k\) 的空闲块双向链表。
- 分配逻辑:
1. 设作业请求空间为 \(s\)$ \text{,计算阶数} $\(k\)$ \text{使得} $\(2^{k-1} < s \le 2^k\)。
2. 若 free_area[k] 存在空闲块,直接分配;
3. 若 free_area[k] 为空,沿索引递增方向寻找最小可用的高阶块 \(2^i\)(\(i > k\)$ \text{),将该块从中间对半分裂为两个大小为} $\(2^{i-1}\) 的伙伴块(Buddy);
4. 将其中一个分裂块挂入 free_area[i-1],另一个继续向下分裂,直至生成大小为 \(2^k\) 的块并分配给请求者。
- 回收合并准则:
- 回收大小为 \(2^k\) 的块时,系统探测其互为伙伴的对应块。
- 伙伴块判定的充要条件:
1. 尺寸严格相等,同为 \(2^k\);
2. 物理地址连续相邻,且二者由同一个大小为 \(2^{k+1}\) 的父块二分产生;
3. 伙伴块处于未分配空闲状态。
- 若满足上述条件,两块合并为大小为 \(2^{k+1}\)$ \text{的大块,并继续向上递归探测新伙伴,直至伙伴已被占用或达到系统上限阶数} $\(U\)。
2. 核心定理推导与数学算法模型¶
2.1 伙伴系统物理地址判定与位运算模型¶
设内存从物理地址 0 开始编址,某大小为 \(2^k\)$ \text{字节的分区,其起始物理地址为} $\(A\)$ \text{。根据伙伴系统的几何对齐约束,} $\(A\) 必然满足: $\(A \pmod{2^k} = 0\)$
伙伴地址映射定理¶
起始地址为 \(A\)$ \text{、大小为} $\(2^k\)$ \text{的分区的唯一伙伴块起始地址} $\(\text{Buddy}_k(A)\) 满足: $\(\text{Buddy}_k(A) = A \oplus 2^k\)$ 其中 \(\oplus\) 表示按位异或运算(Bitwise XOR)。
严格推导: 在二进制空间中,若大小为 \(2^{k+1}\)$ \text{的父块起始地址为} $\(P\)(\(P\)$ \text{的低} $\(k+1\) 位全为 0),其裂解出的两个子块分别为左伙伴与右伙伴: - 左伙伴起始地址为 \(P\)$ \text{(低} $\(k\)$ \text{位为 0,第} $\(k\) 位为 0); - 右伙伴起始地址为 \(P + 2^k\)$ \text{(低} $\(k\)$ \text{位为 0,第} $\(k\) 位为 1)。
因此,左伙伴与右伙伴的物理地址仅在二进制的第 \(k\) 位(从第 0 位起算)相异: - 若给定左伙伴地址 \(A = P\)$ \text{,则} $\(A \oplus 2^k = P + 2^k\),即右伙伴地址; - 若给定右伙伴地址 \(A = P + 2^k\)$ \text{,则} $\(A \oplus 2^k = (P + 2^k) \oplus 2^k = P\),即左伙伴地址。
合并基址位与模型¶
两伙伴块合并生成大小为 \(2^{k+1}\)$ \text{的新块,其起始地址} $\(A_{\text{merged}}\) 必为两者地址的最小值,通过位与运算可直接提取: $\(A_{\text{merged}} = \min(A, \text{Buddy}_k(A)) = A \ \& \ \sim(2^k)\)$
2.2 紧凑技术的时间复杂度与总线传输模型¶
设物理内存大小为 \(M\)$ \text{,当前系统内分散存在} $\(n\)$ \text{个已分配作业,各自分配长度为} $\(L_i\)(\(1 \le i \le n\)$ \text{),已占用总空间为} $\(S_{\text{used}} = \sum_{i=1}^n L_i\)$ \text{。系统空闲内存总量(外部碎片总和)为} $\(S_{\text{free}} = M - S_{\text{used}}\)。 设内存总线传输带宽为 \(B\)$ \text{(字节/秒),内存访问周期为} $\(T_{\text{cycle}}\)。若采用移动搬移紧凑策略: 1. 需拷贝的有效数据总量:\(D_{\text{copy}} \le S_{\text{used}}\)。 2. 总线物理读写搬移时间: $\(T_{\text{compaction}} = \frac{2 \times D_{\text{copy}}}{B}\)$ (因子 2 源于每个字节必须经历“读取源地址”与“写回目的地址”双重总线操作)。 3. 系统开销:紧凑期间必须关闭用户态访问并锁定内存总线,导致明显的停顿(Stop-the-World),因此仅当大作业无法载入且外部碎片总和满足分配需求时方可触发。
3. 核心对比辨析¶
3.1 四大经典动态分区算法特性对比¶
| 评判维度 | 首次适应算法 (FF) | 邻近适应算法 (NF) | 最佳适应算法 (BF) | 最坏适应算法 (WF) |
|---|---|---|---|---|
| 空闲链表拓扑 | 地址由低到高递增排列 | 地址递增排列构成循环链表 | 分区容量由小到大递增排列 | 分区容量由大到小递减排列 |
| 检索起点 | 恒从链表首节点起算 | 从上次分配结束节点起算 | 恒从链表首节点起算 | 恒检查首节点(最大块) |
| 分配耗时 | 快速(低地址命中) | 极快(循环遍历) | 较慢(顺序扫描直至满足) | 极快(仅检查链首 \(O(1)\)) |
| 外部碎片形态 | 低地址产生细小碎片 | 碎片在整块内存均匀散布 | 产生极多极小的针头碎片 | 分割后的余块依然较大 |
| 大分区保护能力 | 优秀(高地址长期保留大块) | 恶劣(过早破坏高地址大块) | 良好(优先压榨微小分区) | 极差(首选最大块进行分割) |
| 回收合并维护代价 | 仅需 \(O(n)\)$ \text{地址顺序插入 | 仅需} $\(O(n)\) 地址顺序插入 | 合并后需重新执行容量排序 | 合并后需重新执行容量排序 |
3.2 内部碎片与外部碎片本质辨析¶
| 对比维度 | 内部碎片 (Internal Fragmentation) | 外部碎片 (External Fragmentation) |
|---|---|---|
| 概念定义 | 分配给进程的分区内部未被利用的存储空间 | 分散在各已分配分区之间的无法被利用的空闲空间 |
| 物理位置 | 位于已分配分区内部 | 位于已分配分区外部(属于系统空闲区) |
| 产生诱因 | 存储分配的离散分配粒度限制(如页大小、固定分区规格) | 动态分区分配的反复分配与释放所引起的空间割裂 |
| 典型管理方案 | 固定分区分配、基本分页存储管理、伙伴系统 | 动态分区连续分配方式(FF、BF、WF、NF) |
| 解决/消除途径 | 减小分配粒度(如缩小页框尺寸) | 采用紧凑(拼接)技术或转向离散存储管理(分页) |
3.3 伙伴系统对比传统动态分区分配¶
| 架构维度 | 传统动态分区分配 (Dynamic Partitioning) | 伙伴系统 (Buddy System) |
|---|---|---|
| 分配粒度 | 任意字节/字对齐尺寸(完全连续按需分配) | 严格限定为 \(2^k\) 字节(以 2 的幂次方对齐) |
| 管理数据结构 | 单一空闲分区表或单一双向链表 | 多级空闲链表数组(free_area[]) |
| 合并限制 | 只要物理地址连续,任意大小均可合并 | 必须满足:大小相等、物理相邻、源自同父 |
| 碎片特征 | 无内部碎片,产生大量外部碎片 | 产生可控的内部碎片(平均每块不超过 50%),消除宏观外部碎片 |
| 时间复杂度 | 检索与遍历为 \(O(n)\)$ \text{ | 检索、裂解与伙伴合并均为} $\(O(1) \sim O(\log_2 M)\) |
三、 近十年真题精讲(2016~2025)¶
【真题 1】2017 年 408 第 25 题 · 最佳适应算法空闲链动态更新与分区合并¶
题目:
某计算机按字节编址,其动态分区内存管理采用最佳适应算法,每次分配和回收内存后都对空闲分区链重新排序。当前空闲分区信息如下表所示。
| 分区起始地址 | 20K | 500K | 1000K | 200K |
|---|---|---|---|---|
| 分区大小 | 40KB | 80KB | 100KB | 200KB |
回收起始地址为 60K、大小为 140KB 的分区后,系统中空闲分区的数量、空闲分区链第一个分区的起始地址和大小分别是( )。
A. 3、20K、380KB
B. 3、500K、80KB
C. 4、20K、180KB
D. 4、500K、80KB
【解析】¶
- 知识定位:动态分区存储管理的最佳适应算法(Best Fit)及分区回收合并拓扑。
- 待回收分区参数分析:
- 回收分区起始地址 \(A_R = 60\text{K}\);
- 回收分区大小 \(S_R = 140\text{KB}\);
- 回收分区覆盖物理区间:\([60\text{K}, 60\text{K} + 140\text{KB}) = [60\text{K}, 200\text{K})\)。
- 邻接状态探测与拓扑合并:
- 检查表中已有的 4 个空闲分区:
- 分区 1:\([20\text{K}, 20\text{K} + 40\text{KB}) = [20\text{K}, 60\text{K})\)$ \text{。其结束地址为} $\(60\text{K}\)$ \text{,恰与回收区起始地址} $\(A_R = 60\text{K}\) 紧密前邻。
- 分区 4:\([200\text{K}, 200\text{K} + 200\text{KB}) = [200\text{K}, 400\text{K})\)$ \text{。其起始地址为} $\(200\text{K}\),恰与回收区结束地址紧密后邻。
- 分区 2:\([500\text{K}, 580\text{K})\),不相邻。
- 分区 3:\([1000\text{K}, 1100\text{K})\),不相邻。
- 属于情形三(前后皆邻接):分区 1、待回收区、分区 4 三者物理上完全相连,合并为一个连续的大空闲分区。
- 合并后新分区的起始地址为原分区 1 的起始地址:\(20\text{K}\)。
- 合并后新分区的大小为:\(40\text{KB} + 140\text{KB} + 200\text{KB} = 380\text{KB}\)。
- 空闲分区数量与链表状态计算:
- 原系统共有 4 个空闲分区,分区 1 与分区 4 与回收区合并为 1 个新分区,分区 2 和分区 3 保持不变。
- 系统剩余空闲分区总数:\(4 - 2 + 1 = 3\) 个。
- 当前系统中存在的 3 个空闲分区属性:
- 分区 A:起始地址 \(500\text{K}\)$ \text{,大小} $\(80\text{KB}\);
- 分区 B:起始地址 \(1000\text{K}\)$ \text{,大小} $\(100\text{KB}\);
- 分区 C:起始地址 \(20\text{K}\)$ \text{,大小} $\(380\text{KB}\)。
- 最佳适应算法的重排序规则:
- 题干明确说明“采用最佳适应算法,每次分配和回收内存后都对空闲分区链重新排序”。
- 最佳适应算法的空闲分区链必须按容量升序(由小到大)排列:
- 链表第 1 个节点:起始地址 \(500\text{K}\)$ \text{,大小} $\(80\text{KB}\);
- 链表第 2 个节点:起始地址 \(1000\text{K}\)$ \text{,大小} $\(100\text{KB}\);
- 链表第 3 个节点:起始地址 \(20\text{K}\)$ \text{,大小} $\(380\text{KB}\)。
- 因此,链表第一个分区的起始地址为 \(500\text{K}\)$ \text{,大小为} $\(80\text{KB}\)。
- 干扰项逐项剖析:
- 选项 A(3、20K、380KB):误将合并后产生的新大分区直接置于链首,忽略了最佳适应算法按容量由小到大重排序的规则(此为最坏适应算法的链首特征)。
- 选项 C(4、20K、180KB):仅与前驱分区 1 合并(\(40+140=180\text{KB}\)),遗漏了与后继分区 4 的合并,导致数量与大小均错。
- 选项 D(4、500K、80KB):空闲链首位置排序正确,但空闲分区数量统计错误(未将前后双邻接合并为 1 个分区)。
正确答案:B
【真题 2】2019 年 408 第 32 题 · 动态分区分配算法与碎片特征分析¶
题目:
在下列动态分区分配算法中,最容易产生内存碎片的是( )。
A. 首次适应算法
B. 最坏适应算法
C. 最佳适应算法
D. 循环首次适应算法
【解析】¶
- 知识定位:动态分区分配算法的碎片产生机理对比。
- 核心原理剖析:
- 动态分区分配中的“内存碎片”特指外部碎片(由于分配后切割剩余的空间过小,无法满足后续任何作业的需求)。
- 最佳适应算法 (Best Fit):
- 算法追求局部最佳匹配,每次都遍历空闲链,选取与作业请求尺寸最接近且满足条件的空闲块进行切割。
- 绝大多数情况下,空闲块大小与作业请求大小不会完全绝对相等,相减后切割出的“剩余空闲块”往往极小(如作业需 100KB,选取了 101KB 的块,剩余 1KB)。
- 这种极小的剩余碎片散布在内存各处,既不能容纳新作业,又占据链表节点,成为难以利用的针头外部碎片。随着系统不断运行,这些微小碎片急剧增加,因此最佳适应算法最容易产生大量碎片。
- 首次适应算法 (First Fit):
- 只要能容纳即分配,低地址切割后可能留有碎片,但碎片集中在低地址端,高地址端仍保持大片未被切割的连续大分区,综合碎片表现优于最佳适应。
- 循环首次适应算法 (Next Fit):
- 碎片较均匀地散布于整个内存,大分区被过早割裂,但微小碎片产生率依然显著低于最佳适应算法。
- 最坏适应算法 (Worst Fit):
- 每次专门选取当前最大的空闲分区进行切割。
- 切割后剩余的空闲块依然相当大,通常可以继续容纳后续的新进程,因此最不容易产生极细碎的微小外部碎片(其主要缺陷是迅速破坏大分区,而非产生细碎碎片)。
- 干扰项辨析:
- 选项 A 错误:首次适应算法综合性能优异,高地址大分区保留好。
- 选项 B 错误:最坏适应算法剩余块较大,最不容易产生微小碎片。
- 选项 D 错误:循环首次适应算法主要缺陷是缺乏大空闲区,微小碎片程度不及最佳适应。
正确答案:C
【真题 3】2024 年 408 第 27 题 · 伙伴系统分区回收合并约束¶
题目:
回收分区时,仅合并大小相等的空闲分区的算法是( )。
A. 伙伴算法
B. 最佳适应算法
C. 最坏适应算法
D. 首次适应算法
【解析】¶
- 知识定位:内存连续分配管理中的伙伴系统(Buddy System)回收合并机制。
- 各选项算法合并机制对比:
- 伙伴算法(Buddy System):
- 系统的分区规范严格约束为 2 的整数次幂(即 \(2^k\) 字节)。
- 内存回收时,执行合并操作必须满足严格的“伙伴判定准则”:两块大小必须完全相等(同为 \(2^k\)$ \text{)、物理地址连续相邻、且互为二分分裂产生的伙伴。若相邻的空闲块大小不相等(例如相邻空闲块阶数为} $\(k+1\)),则系统绝对不允许将二者直接合并。因此,伙伴算法在回收分区时,仅合并大小相等的空闲分区。
- 最佳适应算法 (Best Fit) / 最坏适应算法 (Worst Fit) / 首次适应算法 (First Fit):
- 属于传统动态连续分区分配算法。
- 其分区大小是连续任意的(按字节或字对齐),不设 2 的幂次方限制。
- 在回收内存时,合并的唯一充要条件是物理地址连续相邻(前邻或后邻)。无论相邻空闲分区的大小是 40KB、80KB 还是 200KB,只要起始与结束物理地址紧密相接,必须立即合并为一个连续分区(如 2017 年第 25 题中 40KB、140KB、200KB 三个不同大小的分区完全合并)。绝非“仅合并大小相等的分区”。
- 选项辨析与排除:
- 选项 A 正确:符合伙伴系统的伙伴互等定义。
- 选项 B、C、D 错误:传统动态分区算法在物理相邻时合并,对相邻分区的大小无任何相等性要求。
正确答案:A
四、 综合考法拓展¶
1. 动态重定位与紧凑开销的系统级考查¶
在 408 综合大题中,动态分区分配常与处理器执行机制、动态重定位寄存器及内存总线性能进行跨模块综合考查。
1.1 硬件重定位机制协同¶
- 进程在动态分区中装入时,其指令与数据中的地址均为相对逻辑地址(从 0 开始编址)。
- CPU 内部设置基址寄存器(重定位寄存器)与限长寄存器(界地址寄存器): $$ \text{物理地址} = \text{逻辑地址} + \text{基址寄存器内容} $$ 其中须满足 $$ \text{0 \le \text{逻辑地址} < \text{限长寄存器内容}} $$,否则触发越界中断。
- 紧凑操作的系统行为:当执行紧凑技术将作业由区间 \([A_1, A_1 + L)\)$ \text{搬迁至区间} $\([A_2, A_2 + L)\)$ \text{后,操作系统只需直接修改该进程在进程控制块(PCB)及运行现场恢复时装入基址寄存器的值(从} $\(A_1\)$ \text{变更为} $\(A_2\)),进程代码段中包含的相对地址完全无需改变。
1.2 紧凑性能开销定量分析模型¶
假设某系统发生外部碎片无法容纳新进程,触发内存紧凑: - 设待移动进程集合为 \(\mathcal{P} = \{P_1, P_2, \dots, P_m\}\)$ \text{,大小分别为} $\(S_1, S_2, \dots, S_m\); - 系统时钟频率为 \(f\)$ \text{,内存总线宽度为} $\(W\)$ \text{位(每次总线事务传输} $\(W/8\)$ \text{字节),单次内存读/写操作均需} $\(C_{\text{cycle}}\) 个总线时钟周期; - 移动进程所需耗费的总时间为: $\(T = \sum_{i=1}^m \frac{S_i}{W/8} \times 2 \times \frac{C_{\text{cycle}}}{f}\)$ 此类设问是考查计算机组成原理(总线带宽、访存周期)及操作系统(内存分配、紧凑开销)的经典跨学科交汇点。
2. 动态内存管理与进程生命周期的协同分析¶
[创建进程申请空间] ---> 遍历空闲链表检索可用分区
|
+-------------------+-------------------+
| (分配成功) | (分配失败)
v v
切割空闲分区并修改链表 检查外部碎片总和是否满足要求
初始化 PCB (登记基址与限长) |
进程进入 就绪队列 (Ready) +-------------+-------------+
| (总和满足) | (总和亦不满足)
v v
触发内存紧凑 进程进入 阻塞队列
更新各进程基址寄存器 等待其他进程释放内存
- 进程创建时:向操作系统发出内存分配请求,操作系统根据预设算法(FF/BF/WF/NF)检索空闲链表。若找不到足够大的连续分区,但在未分配空间总和充足时,操作系统将调度紧凑程序;若总空闲容量不足,进程创建受阻,置为等待状态。
- 进程终止时:操作系统回收其所占物理分区,触发四种相邻合并探测,更新空闲链拓扑;随后唤醒因内存不足而阻塞的进程,重新进行分区检索。
3. 从连续分配到现代离散存储管理的演进逻辑¶
理解动态内存管理的局限性,是透彻掌握虚拟存储管理的前提:
连续动态分区分配 伙伴系统 (Buddy System) 分页离散存储管理 (Paging)
+-----------------------+ +-----------------------+ +-----------------------+
| 存在严重外部碎片 | 演进至 | 空间按 2^k 阶梯化 | 演进至 | 空间以固定页框离散化 |
| 需代价高昂的紧凑技术 | --------> | 外部碎片可控且合并快速| --------> | 完全消除外部碎片 |
| 要求物理连续性 | | 产生一定内部碎片 | | 仅保留末页微小内部碎片|
+-----------------------+ +-----------------------+ +-----------------------+
- Linux 现代架构的分层融合策略:
- 现代 OS 并未彻底抛弃连续管理思想。以 Linux 为例,底层物理页框(4KB)的管理依然采用伙伴系统,以应对直接内存访问(DMA)或高速缓存对大块物理连续地址的刚性需求;
- 在伙伴系统之上,针对内核小对象采用 SLAB 分配器(按对象缓存分配,消除伙伴系统的内部碎片);
- 在用户进程地址空间,全面采用多级分页与虚拟内存映射,彻底消除了用户空间的外部碎片。
五、 考点速记清单¶
1. 核心要点速记¶
- 首次适应 (FF):低地址排,顺序找,首个满足即切割;高地址大块留得好,低地址碎片多。
- 邻近适应 (NF):环形链,接上次,转圈找;碎片散得匀,大块死得快。
- 最佳适应 (BF):小到大,找最贴;微小针头碎片多,链表排序开销大。
- 最坏适应 (WF):大到小,挑最大;割完余块还能用,大作业来没处塞。
- 伙伴系统:块大小恒为 \(2^k\),大小相等、地址连续、同父二分、空闲可用方可合并。
2. 核心公式汇总¶
- 伙伴起始地址计算: $\(\text{Buddy}_k(A) = A \oplus 2^k\)$
- 伙伴合并基地址计算: $\(A_{\text{merged}} = A \ \& \ \sim(2^k)\)$
- 前后邻接合并区间: $\([A_P, S_P) \cup [A_R, S_R) \cup [A_S, S_S) \longrightarrow [A_P, S_P + S_R + S_S)\)$
3. 易错陷阱提示¶
- [!WARNING] 陷阱一:忽略算法对空闲链表的重排序 在回收分区并执行合并后,若系统使用的是最佳适应算法或最坏适应算法,合并后的新分区其容量发生变化,必须重新按容量大小调整在链表中的顺序。切忌直接将合并结果插入原位置或链首。
- [!WARNING] 陷阱二:混淆伙伴系统与传统算法的合并准则 传统连续分配(FF、BF、WF)只要物理地址相邻即可合并,与分区大小是否相等无关;而伙伴算法必须大小相等且属于同一父块分裂产生的法定伙伴才能合并。
- [!WARNING] 陷阱三:紧凑技术的硬件依赖 紧凑技术的根本前提是系统具有动态重定位能力(即在执行期由硬件自动加上重定位寄存器的基地址)。若系统仅支持静态重定位,则一旦装入内存物理地址便不可变更,无法实施紧凑。