小偷最优偷窃策略：动态规划解法
2026/7/2 20:05:20
考点频率：★★★★☆（选择题常考，是理解后续页式/段式存储的基础）
难度：⭐⭐
建议：重点掌握两种分区方式的特点、碎片的分类、四种分配算法的优缺点
1️⃣ 什么是分区存储管理？
分区存储管理是最早的多道程序存储管理方式，也是最直观的内存管理方式：将内存划分为若干个连续区域，每个区域装入一道程序。
分区存储的核心问题：每个分区应该多大？分区数量应该是多少？
早期解决这两个问题的思路出现了两种方案——固定分区和动态分区。
2️⃣ 固定分区（Fixed Partitioning）
2.1 原理
操作系统在运行前，将内存划分为若干个大小固定的分区。每个分区可以装入一个程序，分区大小在系统运行期间不能改变。当程序到达时，系统将它分配到能够容纳它的最小分区中。
2.2 分区数量与大小
- 分区数量在系统生成时确定（如分为4个区：8MB、16MB、32MB、64MB）
- 分区大小可以相等，也可以不等（通常不等，以适应不同大小的程序）
2.3 优缺点
| 优点 | 缺点 |
|---|---|
| 实现非常简单，管理开销极小 | 内部碎片：程序比分配到的分区小，分区内剩余空间被浪费，且无法被其他程序利用（例如程序10MB，分区16MB，浪费6MB） |
| 分配速度快（只需查表） | 分区数量固定，多道程序并发度受限 |
| 适用于单道批处理或嵌入式系统 | 程序不能大于最大分区（否则无法运行） |
2.4 内部碎片（Internal Fragmentation）
分配给程序的存储区域中，未被程序使用的那部分空间。它属于某个分区内部，无法被其他程序利用。固定分区是内部碎片的典型来源。
3️⃣ 动态分区（Dynamic Partitioning）
3.1 原理
分区不是预先固定的，而是按程序的实际需求动态创建。程序装入时，系统从空闲内存中分配一个恰好能满足需求的连续区域。
3.2 分配过程
- 程序到达时，系统在空闲区列表中寻找一个足够大的空闲块
- 如果找到，将该空闲块的一部分分配给程序，剩余部分继续作为空闲区
- 程序运行结束后，释放整个分区，与相邻的空闲区合并
3.3 优缺点
| 优点 | 缺点 |
|---|---|
| 没有内部碎片（分区大小完全匹配程序需求） | 外部碎片：经过多次分配和释放后，内存中会出现许多不连续的小空闲块 |
| 内存利用率比固定分区高 | 分配算法比固定分区复杂 |
| 程序大小不受分区大小限制 | 需要定期进行紧缩（Compaction）来整理碎片 |
3.4 外部碎片（External Fragmentation）
内存中散布的、总和可能很大但每个碎片都不够大、无法满足任何程序加载需求的零散空闲块。外部碎片只有通过紧缩（Compaction）将内存中散布的空闲块汇集到一处才能消除，但紧缩需要大量的CPU时间，代价昂贵。
4️⃣ 固定分区 vs 动态分区
| 对比项 | 固定分区 | 动态分区 |
|---|---|---|
| 分区大小 | 固定不变 | 按程序需求动态创建 |
| 分区数量 | 固定 | 动态变化 |
| 内部碎片 | 有 | 无 |
| 外部碎片 | 无 | 有 |
| 内存利用率 | 较低 | 较高 |
| 是否需要紧缩 | 否 | 是（外部碎片积累到一定程度时） |
| 硬件复杂度 | 低 | 较高 |
5️⃣ 动态分区的空闲区分配算法
这是软考中一个相对独立的考点。当系统需要为一个新程序分配空闲区时，可以从空闲区列表中选择一个合适的块，分配算法的好坏直接影响外部碎片的产生速度和内存利用率。
| 算法 | 思路 | 优点 | 缺点 |
|---|---|---|---|
| 首次适应（First Fit） | 从头开始查找，选择第一个能满足要求的空闲区 | 简单、速度较快，大块保留在尾部 | 可能在低地址产生大量碎片 |
| 最佳适应（Best Fit） | 从所有空闲区中，选择与程序需求最接近（即剩余最小）的空闲区 | 尽量保留大块空闲区 | 产生大量极小的碎片（难以利用），查找速度慢 |
| 最坏适应（Worst Fit） | 选择最大的空闲区，分割后剩余的仍然较大 | 碎片相对均匀，不易产生“难以利用的小碎片”，查找速度较快 | 会破坏大块空闲区，可能使大程序无法装入 |
| 循环首次适应（Next Fit） | 从上次查找结束的位置开始查找第一个能满足要求的空闲区 | 分配更均匀，避免低地址被“重点关照”导致碎片集中 | 高地址部分可能很快被消耗掉 |
软考常考：给定空闲区列表和程序大小，要求选择对应的分配结果。
6️⃣ 碎片问题的总结（易混淆点）
| 碎片类型 | 产生场景 | 能否消除 | 消除方法 |
|---|---|---|---|
| 内部碎片 | 固定分区、分页存储（最后一页） | 无法消除，只能减少 | 分区大小合理设置、减小页大小 |
| 外部碎片 | 动态分区、分段存储 | 可以消除 | 紧缩（内存搬移） |
一句话区分：内部碎片是“分区内部没用的空间”，外部碎片是“分区之间散落的零碎空间”。
7️⃣ 经典例题
例题1：下列哪个存储管理方式会产生外部碎片？
A. 固定分区
B. 动态分区
C. 分页存储管理
D. 固定分区 + 分页混合
解析：固定分区产生内部碎片；动态分区产生外部碎片；分页存储管理（后续会讲）无外部碎片。选B。
例题2（计算）：某动态分区系统中，初始空闲区为1024KB。现有进程按以下顺序到达（依次）：P1申请300KB，P2申请200KB，P3申请400KB，P1释放，P4申请150KB。采用首次适应（First Fit）算法，求P1释放后，空闲区的分布。
解析：
- 初始：
[1024] - P1分配300KB：空闲区
[724] - P2分配200KB：空闲区
[524] - P3分配400KB：空闲区
[124] - P1释放300KB：空闲区变为
[300][124]（按地址顺序：300KB空闲块在前，124KB空闲块在后）
答案：空闲区为两个块：300KB 和 124KB（按地址顺序）。
8️⃣ 记忆口诀
固定分区内碎片，动态分区外碎片。
首次适应找首个，最佳适应找最小。
最坏适应找最大，循环适应接着找。
9️⃣ 小测验（评论区对答案）
某动态分区系统采用首次适应算法，空闲区列表按地址顺序为：
[50KB, 120KB, 80KB, 200KB]。现有三个进程依次到达并请求内存：P1请求60KB，P2请求100KB，P3请求70KB。分配完成后，空闲区列表变为（ ）。
A.[50KB, 20KB, 80KB, 100KB]
B.[50KB, 20KB, 10KB, 100KB]
C.[50KB, 20KB, 10KB, 80KB]
D.[50KB, 20KB, 80KB]
🔔本专栏日更2篇，点击头像 → 专栏《软考中级高频考点》订阅，第一时间接收新内容
#软考中级 #软件设计师 #分区存储 #固定分区 #动态分区 #碎片 #操作系统