Appearance
连续分配（首次/最佳/最坏适应）
2026 大纲 三（一）2 连续分配管理方式。
最朴素的分法：一个进程占一整块，连着放
上一节说内存必须在空间上同时分给多个进程。最朴素的分法就是连着放—— 给每个进程划一整块连续的内存，它从这一头用到那一头。
这个做法有个不小的好处：地址变换极其简单。整块连续意味着逻辑地址和物理地址之间 只差一个固定的偏移，一个重定位寄存器做一次加法就够了，硬件成本几乎为零。
代价则要过一阵子才显出来。进程来来去去，装了又卸、卸了又装，内存就被切得七零八落。 剩下的空闲空间加起来可能还很多，但它们互不相邻，谁也装不下一个稍大的进程。
所以这一节的三种方式其实是同一个矛盾被反复缓解的三个阶段， 而它们缓解到最后仍然缓解不掉的那个东西——外碎片——正是下一节"干脆别连着放"的全部动机。 读的时候盯住两条线：碎片是内的还是外的，以及它是怎么产生的。
交互可视化
一、三种连续分配方式：一条被需求推着走的链
三种方式不是三条并列的路，而是同一个矛盾被反复缓解的三个阶段：单道程序只需把内存分成系统区 + 用户区（单一连续分配，用户区剩下的部分谁也用不了 ⇒ 内碎片）；要跑多道就把用户区事先划成若干固定大小的分区（固定分区分配，进程装进去填不满 ⇒ 仍是内碎片，且分区数固定 ⇒ 多道程序度有上限）；要让分区贴合进程实际大小就不预划分、来一个切一块（动态分区分配，切得刚好 ⇒ 无内碎片，但反复切分与归还会在已分配区之间留下空隙 ⇒ 外碎片）。
| 方式 | 分区何时划定 | 分区大小 | 内碎片 | 外碎片 | 多道程序度上限 |
|---|---|---|---|---|---|
| 单一连续分配 | —— | 整个用户区 | 有 | 无 | 1 |
| 固定分区分配 | 系统启动前预先划定 | 固定（等大或不等大） | 有 | 无 | 分区个数 |
| 动态分区分配 | 进程装入时按需切分 | 随进程而变 | 无 | 有 | 受空闲空间限制 |
固定分区还需要一张分区说明表，每个表项记录分区的起始地址、大小、状态（已分配/未分配），分配时按进程大小检索该表。
不等大小分区是对固定分区的改良：把用户区划成"多个小分区 + 适量中等分区 + 少量大分区"，按程序大小对号入座，能明显压低内碎片。该用等大还是不等大，看作业大小是否集中——同时控制多台同型设备这类场合作业大小一致，等大分区反而更简单实用。
二、动态分区的数据结构
| 结构 | 组织形式 | 每项/每块记什么 | 特点 |
|---|---|---|---|
| 空闲分区表 | 一张顺序表，一个空闲分区占一个表目 | 分区号、分区大小、分区始址 | 结构简单，表长固定，分区数变化大时不方便 |
| 空闲分区链 | 双向链表，链信息直接放在分区自己的头尾 | 头部：状态位、分区大小、前向指针；尾部：后向指针，并重复一遍状态位和分区大小 | 不占额外内存，分区数不受限 |
分区被分配出去后，头尾的前后向指针就失去意义，只有状态位仍要维护。
三、分配：四种策略
四种策略的差别只有一处：面对多个够大的空闲分区时选哪一个。为了让"选"退化成"取第一个满足的"，每种策略都把空闲分区按对应顺序排好。
| 策略 | 选谁 | 空闲分区排列 | 找的时候怎么走 |
|---|---|---|---|
| 首次适应（First Fit） | 第一个够大的 | 按地址递增 | 每次都从链首开始扫 |
| 邻近适应 / 循环首次适应（Next Fit） | 第一个够大的 | 按地址递增（同上） | 从上次分配结束的位置继续往下扫，到链尾则绕回链首 |
| 最佳适应（Best Fit） | 最小的够大分区 | 按大小递增 | 从链首开始扫，第一个够大的必然最小 |
| 最坏适应（Worst Fit） | 最大的分区 | 按大小递减 | 直接取表头 |
| 策略 | 优点 | 缺点 | 代价的来源 |
|---|---|---|---|
| 首次适应 | 综合性能最好；高地址的大空闲区被完整保留 | 低地址不断被切，积累大量小碎片；每次从头扫，查找开销随碎片增多而上升 | 总从低地址开始 |
| 邻近适应 | 空闲分区分布更均匀，查找开销小 | 大的空闲分区也会被均匀地拆掉，最终缺少大分区 | 指针不回头，雨露均沾 |
| 最佳适应 | 大分区被保留下来 | 每次切下的余量都是最小的 → 产生大量极小的不可用碎片 | 每次都追求"最贴合" |
| 最坏适应 | 切完剩下的块仍然较大，不易产生小碎片 | 大分区被迅速消耗，后来的大进程无处安放 | 每次都动最大的那块 |
同一序列下四种策略的碎片演化：每一步扫到哪、切了谁、最终内存是什么形状（想看清"总空闲量相等但可用性不等"是怎么发生的时展开）
某系统采用动态分区分配，当前空闲分区按地址递增依次为 A = 20KB、B = 10KB、C = 120KB、D = 60KB（四块互不相邻，之间隔着已分配区）。依次到达三个进程 P1 = 15KB、P2 = 30KB、P3 = 50KB。邻近适应的起始查找指针初始指向 A。
首次适应（按地址递增扫描）：
| 进程 | 扫描过程 | 命中 | 分配后空闲分区 |
|---|---|---|---|
| P1 = 15 | A(20)✓ | A | A=5 / B=10 / C=120 / D=60 |
| P2 = 30 | A(5)✗ → B(10)✗ → C(120)✓ | C | A=5 / B=10 / C=90 / D=60 |
| P3 = 50 | A(5)✗ → B(10)✗ → C(90)✓ | C | A=5 / B=10 / C=40 / D=60 |
每次都必须从链首重新扫，而不是接着上一次的位置——这正是首次适应与邻近适应唯一的区别，也是它把碎片压在低地址的原因。
邻近适应（按地址递增，但从上次结束处续扫）：
| 进程 | 扫描起点 | 扫描过程 | 命中 | 分配后空闲分区 |
|---|---|---|---|---|
| P1 = 15 | A | A(20)✓ | A | A=5 / B=10 / C=120 / D=60 |
| P2 = 30 | B | B(10)✗ → C(120)✓ | C | A=5 / B=10 / C=90 / D=60 |
| P3 = 50 | D | D(60)✓ | D | A=5 / B=10 / C=90 / D=10 |
指针停在上一次命中的分区之后。P3 从 D 起扫，D 够大就直接命中，根本没有回头看 C——这就是"分布均匀"的机制，也是大分区被逐个拆开的原因。
最佳适应（按大小递增，取第一个够大的）：
| 进程 | 够大的候选 | 命中（最小的那个） | 分配后空闲分区 |
|---|---|---|---|
| P1 = 15 | A(20)、C(120)、D(60) | A(20) | A=5 / B=10 / C=120 / D=60 |
| P2 = 30 | C(120)、D(60) | D(60) | A=5 / B=10 / C=120 / D=30 |
| P3 = 50 | C(120)（D 只剩 30，不够） | C(120) | A=5 / B=10 / C=70 / D=30 |
候选集必须在当前状态上重算——P2 分完后 D 只剩 30KB，已经掉出 P3 的候选集了。手算时最容易错的一步，就是拿初始表去给第二个、第三个进程找分区。
最坏适应（按大小递减，直接取最大的）：
| 进程 | 当前最大分区 | 命中 | 分配后空闲分区 |
|---|---|---|---|
| P1 = 15 | C(120) | C | A=20 / B=10 / C=105 / D=60 |
| P2 = 30 | C(105) | C | A=20 / B=10 / C=75 / D=60 |
| P3 = 50 | C(75) | C | A=20 / B=10 / C=25 / D=60 |
最坏适应连"够不够大"都不用挨个比——最大的都不够，别的更不够。所以它的查找开销恒定，代价是三次全咬在同一块大分区上。
碎片演化对比：四种策略分掉的总量相同（95KB），剩余总空闲量都是 115KB，但空闲空间的形状完全不同：
| 策略 | 最终空闲分区 | 最大可用块 | 新产生的极小碎片（≤10KB） | 若接着来一个 P4 = 65KB |
|---|---|---|---|---|
| 首次适应 | 5 / 10 / 40 / 60 | 60 | 5 | 分配失败 |
| 邻近适应 | 5 / 10 / 90 / 10 | 90 | 5、10 | 成功（用 90 那块） |
| 最佳适应 | 5 / 10 / 70 / 30 | 70 | 5 | 成功（用 70 那块） |
| 最坏适应 | 20 / 10 / 25 / 60 | 60 | 无 | 分配失败 |
三条能从这张表里读出来的结论：总空闲量相等不等于可用性相等（都剩 115KB，能不能装下 65KB 却分成两派）；最坏适应确实没造出小碎片（切下的余量分别是 105、75、25），代价是把唯一的大分区从 120KB 啃到 25KB；这只是一条特定序列上的快照，不能拿来给算法排名。
四、回收：四种邻接情况
分配只是"切一刀"，回收却要判断归还区与前后空闲区是否相邻，并决定怎么合并。只登记不合并，两块相邻的空闲区会被永远当成两块小区看待，内存越回收越碎。
| 情况 | 前邻 | 后邻 | 表项数变化 | 首址取谁 |
|---|---|---|---|---|
| 一 | ✓ | ✗ | 不变 | F1 的首址（不变） |
| 二 | ✗ | ✓ | 不变 | 改为回收区首址 |
| 三 | ✓ | ✓ | −1（取消 F2） | F1 的首址 |
| 四 | ✗ | ✗ | +1（新建） | 回收区首址 |
按"首址变不变、表项数变不变"这两个维度记，四种情况互不重叠。
走一遍四种邻接情况：连续回收四个进程，每次判前后邻接并写出空闲分区表（想看清合并时机与表项数怎么变时展开）
某系统用户区为 0～600KB，采用动态分区分配。当前占用情况为：P1 占 [0, 100)、P2 占 [100, 160)、空闲 [160, 220)、P3 占 [220, 320)、P4 占 [320, 380)、空闲 [380, 460)、P5 占 [460, 560)、P6 占 [560, 600)。初始空闲分区表：[160, 220) 60KB ／ [380, 460) 80KB，共 2 项。现依次回收 P1、P2、P4、P5。
① 回收 P1，回收区 [0, 100)
- 前面：回收区首址为 0，前面没有任何分区 → 不邻接
- 后面：回收区结束于 100，表中最靠前的空闲区起址是 160 ≠ 100 → 不邻接（中间隔着 P2）
⇒ 情况四：新建表项 [0, 100)，按地址插到表首。表项数 2 → 3。
[0, 100) 100KB ／ [160, 220) 60KB ／ [380, 460) 80KB
判"是否邻接"只看地址是否严丝合缝。100 与 160 之间隔着尚未释放的 P2，所以只能单独立项——这也说明回收顺序会影响中间过程。
② 回收 P2，回收区 [100, 160)
- 前面：[0, 100) 结束于 100 = 回收区首址 → 邻接
- 后面：[160, 220) 起址 160 = 100 + 60 → 邻接
⇒ 情况三：三块合一为 [0, 220)，用前一分区的表项和首址 0，大小 = 100 + 60 + 60 = 220KB，取消 [160, 220) 的表项。表项数 3 → 2。
[0, 220) 220KB ／ [380, 460) 80KB
情况三是唯一让表项数减少的情况。刚才被迫单独立项的 [0, 100)，在 P2 归还后立刻被并了回去——合并的时机取决于邻居什么时候释放，与回收算法无关。
③ 回收 P4，回收区 [320, 380)
- 前面：[0, 220) 结束于 220 ≠ 320 → 不邻接（中间是尚未释放的 P3）
- 后面：[380, 460) 起址 380 = 320 + 60 → 邻接
⇒ 情况二：合并为 [320, 460)，大小 = 60 + 80 = 140KB，首址改为回收区首址 320。表项数不变，仍为 2。
[0, 220) 220KB ／ [320, 460) 140KB
这是四种情况里唯一要改首址的一种。若沿用原表项的首址 380，[320, 380) 这 60KB 就凭空消失了。
④ 回收 P5，回收区 [460, 560)
- 前面：[320, 460) 结束于 460 = 回收区首址 → 邻接
- 后面：回收区结束于 560，而 [560, 600) 是仍在占用的 P6 → 不邻接
⇒ 情况一：不新建表项，只把前一分区的大小由 140KB 改为 140 + 100 = 240KB，首址仍是 320。表项数不变，仍为 2。
[0, 220) 220KB ／ [320, 560) 240KB
回收完毕后：内存里只剩 P3 占 [220, 320)、P6 占 [560, 600)，空闲空间被合并成两大块（220KB 与 240KB）。若这四次回收全都只登记不合并，表里会留下 6 个零散表项，最大块只有 100KB——合并这一步，才是回收的实质。
五、紧凑：能救外碎片，但有前提
外碎片已经产生之后还有一条补救路径：紧凑（Compaction，也叫拼接）——把内存中的进程全部往一端搬，使它们互相邻接，原来分散的小空闲区就拼成一整块。
它的硬前提是动态重定位：进程被搬走后物理位置变了，如果地址已在装入时写死（静态重定位），程序立刻就跑不了；只有把地址变换推迟到每次访存、由重定位寄存器完成，紧凑才只需要改一个寄存器的值。"动态可重定位分区分配"这个名字就是这么来的——紧凑和动态重定位是一件事的两面。代价则是搬家本身很贵：大量数据在内存里逐字节挪位，期间被搬的进程无法运行，为维持利用率往往还要频繁紧凑。
真正让紧凑变得不必要的，是下一篇的思路：既然搬来搬去是为了凑出连续空间，那干脆不再要求连续。
六、伙伴算法：把合并的代价压下去
前面四种策略的回收都要扫描空闲结构、判断前后是否邻接，碎片越多扫得越久。 伙伴（Buddy）算法换了个思路：限制块的大小和位置，让"该跟谁合并"变成一次计算而不是一次查找。
做法是内存只按 2 的幂次切块——1 KB、2 KB、4 KB……每一级一条空闲链。 分配时找最小的够用层级，若该级没有空闲块就从上一级劈成两半，其中一半给出去、 另一半挂到本级链上。
关键在回收。一个
- 大小相等（同为
）； - 物理相邻；
- 来自同一个父块——即两者合并后恰好拼成一个对齐的
块。
第三条是最容易被漏掉的。不是任意两个等大又相邻的块都能合：如果它们分属两个不同的父块， 合出来的东西不对齐，下一层就没法继续合。正因为有这条约束， 一个块的伙伴地址可以直接算出来（把块首地址的第
回收时检查伙伴：伙伴空闲就合并成
代价是分配单位被强行凑成 2 的幂，内碎片重新出现了——申请 33 KB 会拿到 64 KB。 这是它和前四种策略最本质的取舍差别：前四种按需切分、没有内碎片但合并要查找； 伙伴算法按幂次切分、合并只需计算但重新引入了内碎片。
考点速记
- 三种连续分配是同一矛盾被反复缓解的三步：单一连续分配（内碎片）→ 固定分区分配（内碎片，多道程序度 = 分区数）→ 动态分区分配（无内碎片、有外碎片）。共同前提是一个进程必须占一整块连续内存。
- 碎片判据：分区大小固定、进程填不满 ⇒ 内碎片（单一连续、固定分区）；分区按需切分、剩下的边角料没人要 ⇒ 外碎片（动态分区）。
- 空闲分区链的尾部重复记状态位与大小，是为了回收时用"回收区首址 − 1"一步读到前一块的尾部——用极少空间换合并时的常数时间。
- 四种分配策略只差"多个够大的分区选哪个"，排序方式是选择规则的推论，不是额外要背的：最佳适应要最小的够大分区 ⇒ 按大小递增排；最坏适应要最大的 ⇒ 按大小递减排、直接取表头。
- 首次适应综合性能最好，但这是大量随机请求下的统计结论——单条请求序列上谁剩的大块更多，结论可能正好相反。
- 衡量碎片严重程度的指标是最大连续空闲块，不是空闲总量。 总量相同、形状不同时，能否装下新进程的结论会相反。
- 回收分四种邻接情况，用"首址变不变、表项数变不变"两个维度区分：只前邻 → 改前一项大小，表项数不变；只后邻 → 改首址为回收区首址并加大小，表项数不变；前后皆邻 → 用前一项首址、大小取三者之和、删掉后一项（−1）；皆不邻 → 新建表项（+1）。⚠️"紧邻"指地址严丝合缝，差一个字节都不算。
- 紧凑能把外碎片拼成大块，前提是动态重定位、代价是大量数据搬移；它动的是进程位置，所以只对外碎片有意义。
- 伙伴算法只合并互为伙伴的块——大小相等、物理相邻、且同属一个父块，三条缺一不可。代价是块按 2 的幂切分，内碎片重新出现。
这一节在真题里被考过的形式：
考法非常集中：四道题里三道是同一种手算题——给一串分配请求，问某种策略下的分配结果或碎片状况。 剩下一道问回收合并的规则。
- 给空闲分区序列和一串请求，问最佳适应算法的分配结果（2010-28、2017-25）。⚠️ 手算时最容易错的一步是拿初始表去给第二、第三个请求找分区——候选集必须在当前状态上重算，前一个请求切完之后有的分区已经掉出候选集了。2017-25 还叠了一次分区合并。
- 问动态分区 + 最佳适应下的外部碎片情况（2019-32）。判据回到速记第六条：看最大连续空闲块，不是把空闲量加起来。最佳适应每次切下的余量都最小，因而积累的是大量极小的、谁也用不了的碎片——总量看着不少，最大块却很小。
- 问回收分区时仅合并大小相等的空闲分区的算法是哪个（2024-27）。答伙伴算法。⚠️ 另三个选项（最佳适应、最坏适应、首次适应）都是分配策略，它们的回收一律"前后相邻就合并"，跟大小无关。这道题实际考的是"分配策略和回收合并规则是两回事"。
复习优先级：必须拿满，且要能手算。 四种策略的手算是本节唯一的技术动作， 练到"每一步都在当前状态上重算候选集"成为习惯即可。回收的四种情况按第七条那两个维度记， 不要死背四段话。伙伴算法目前只考过定义，把"三条伙伴条件 + 重新有内碎片"记住就够。
易错：手算时拿初始空闲分区表给后续请求找分区。每一步都要在当前状态上重算候选集。
易错：拿空闲总量衡量碎片严重程度。指标是最大连续空闲块。
易错：把伙伴算法当成一种分配策略去和最佳适应比。题目问的是回收合并规则——另三个的合并规则都是"相邻就合"。
易错：认为任意两个等大且相邻的空闲块都是伙伴。还必须同属一个父块（合并后恰好对齐成
）。
易错：认为伙伴算法没有内碎片。它按 2 的幂切块，申请 33 KB 会拿到 64 KB。
易错：回收时"只后邻"的情况忘了改首址。合并后的空闲区从回收区开头算起，不改就会把回收区那一段漏在表外。
易错：认为首次适应在任何一条请求序列上都最优。那是大量随机请求下的统计结论。
易错：认为紧凑能消除内碎片。紧凑动的是进程位置，只对外碎片有意义。
教材出处
- 汤小丹《计算机操作系统》4.3.1 单一连续分配、4.3.2 固定分区分配（分区大小相等与不等、分区使用表），p126–p127
- 同上 4.3.3 动态分区分配（空闲分区表与空闲分区链、尾部重复设置状态位和分区大小；分区分配操作），p128
- 同上 4.3.3「回收内存」四种邻接情况与内存回收流程，p129–p130
- 同上 4.3.4 基于顺序搜索的动态分区分配算法（首次适应、循环首次适应、最佳适应、最坏适应及各自代价），p130–p131
- 同上 4.3.6 动态可重定位分区分配（紧凑必须配合动态重定位），p133–p134
- 同上 4.4.2 对换空间的管理（对换区的分配与回收同样分四种情况），p137