Appearance
连续分配管理方式
概念
连续分配指为一个程序分配一块"物理地址连续"的内存区域。它是内存管理最早、也最直观的做法：程序整体装进一段连续的内存里，一个进程占一段。
一句话说清它是什么：连续分配就是"给每个程序划一块整地"——下一章 os/21-paging.md 的分页则是"给每个程序发一堆散地"。这一章的全部痛点（碎片）都源自"必须连续"这四个字。
⭐ 内存管理的四个基本功能（贯穿 20~24 五章，先在此交代）：
| 功能 | 含义 | 主要落在哪一章 |
|---|---|---|
| 内存空间的分配与回收 | 谁占哪块、怎么找、怎么还 | 本章 / 21 / 22 |
| 地址转换 | 逻辑地址 → 物理地址 | 21-paging / 22-segment |
| 内存空间的扩充 | 让程序比物理内存大也能跑 | 23-virtual |
| 内存保护 | 越界检查、权限检查 | 21 / 22（界地址、段表长度） |
⚠️ 注意："内存保护"与"地址转换"在这五个功能里是并列的，不要以为只有分页才有保护——连续分配靠"界地址寄存器"，分段靠"段长检查"，分页靠"页表长度检查"，都是保护。
原理
一、单一连续分配
内存被分成两部分：用户区 + 系统区。用户区同一时刻只能装一道程序。
text
0 ┌──────────────┐
│ 操作系统 │ ← 系统区(低地址, 常驻)
├──────────────┤
│ │
│ 用户程序 │ ← 整个用户区都给这一道程序
│ │
└──────────────┘ 上限- 优点：实现最简单，完全不需要地址转换（程序直接跑在物理地址上）。
- 缺点：只能单道；内存浪费严重（程序小于用户区时，剩下的白放着 = 内部碎片）；无保护机制（早期无，后来靠界地址寄存器）。
二、固定分区分配
把用户区预先切成若干"大小固定"的分区，每个分区装一道程序。
text
┌──────┬──────────┬────────────────┬─────────────┐
│ OS │ 分区1 │ 分区2 │ 分区3 │
│ │ 20K │ 60K │ 180K │
└──────┴──────────┴────────────────┴─────────────┘
分区大小划分方式: ① 等大(简单但浪费) ② 不等(按常见作业大小定)- 优点：支持多道（分区各有大小，可实现"多道程序度"）；无外部碎片。
- 缺点：有内部碎片（分区比作业大，剩下的浪费）；分区数固定 → 程序数受限；一个分区分给一道程序，不能共享。
- 数据结构：分区表（每项：起始地址、大小、状态）。
- 分配：找一个足够大的空闲分区给它；不够就排不上队（等待）。
⚠️ 内部碎片与外部碎片的定义必须分清（贯穿本章）：
- 内部碎片（internal）：分配出去的内存块里，进程用不上的那部分——"已分配给进程但没用"。
- 外部碎片（external）：没分配出去、但小到没法满足任何请求的空闲块——"没人要的边角料"。
- 固定分区 → 只有内部碎片；动态分区 → 只有外部碎片（这条对应关系是选择题常客）。
三、动态分区分配
分区在作业装入时"按需建立"，大小正好等于作业大小——不预先划分。
text
装入前: ┌──────┬───────────────────────────┐
│ OS │ 空闲区 (一大块) │
└──────┴───────────────────────────┘
作业 20K 装入后:
┌──────┬────────┬──────────────────┐
│ OS │ 作业A │ 空闲区 │ ← 空闲区被"切走"一块
└──────┴────────┴──────────────────┘- 优点：没有内部碎片（分多大就装多大）。
- 缺点：有外部碎片（回收与装入反复切割，留下许多小空闲块）；需要"分配算法"去找合适的空闲区；需要紧凑。
- 数据结构（两种）：
- 空闲分区表：每项含分区号、始址、大小。
- 空闲分区链：双向链表，每块头部记大小与状态——用"链"就不受"固定表长"限制。
四、动态分区分配算法（四大，本章最常考）
所有算法都在回答同一个问题：一堆大小不一的空闲区，来了一个请求，选哪一个？
| 算法 | 选择规则 | 链的排列 | 优点 | 缺点 |
|---|---|---|---|---|
| 首次适应（First Fit, FF） | 从低地址开始，取第一个够大的 | 按地址递增 | 简单；保留高地址大空闲区 | 低地址反复切割 → 低地址碎片多；每次都从头扫，开销大 |
| 最佳适应（Best Fit, BF） | 取"够用且最小"的那个 | 按容量递增 | 看起来最省 | 留下大量"用不上"的极小碎片 → 外部碎片最多 |
| 最坏适应（Worst Fit, WF） | 取最大的那个 | 按容量递减 | 剩下的块还够大，减少小碎片 | 大块很快被吃光 → 大作业来时装不下 |
| 邻近适应（Next Fit, NF，循环首次适应） | 从"上次分配结束的位置"开始，取第一个够大的 | 按地址递增 | 扫描开销小（不必每次从头） | 高地址大空闲区也容易被切碎 |
⚠️ 三句必记的"反直觉"结论：
- 最佳适应 ≠ 最好——它反而制造最多外部碎片（留下的都是"最紧的边角料"）。"最佳"是指"单次选择最省"，不是"整体最优"。
- 最坏适应 ≠ 最差——它的目的是"切完剩下的块仍足够大"，但代价是大空闲区迅速耗尽。
- 邻近适应 ≠ 首次适应——差别只在"扫描起点"；它的碎片分布更均匀，但会破坏"低地址碎片多、高地址大块完整"这一首次适应的优点。
五、碎片与紧凑
- 外部碎片不可避免（只要反复分配回收），解决手段是"紧凑"（compaction，也叫"拼凑/紧缩"）：
- 做法：把内存中所有进程"搬家"，让它们挨到一起，把碎片挤成一块大的。
- 前提：进程必须能"移动" → 需要动态重定位（重定位寄存器，
os/21-paging.md与计组arch/13-virtual.md讲过）。 - 代价：搬家本身要占用 CPU 时间（拷贝内存）；且搬家时进程必须停下。
- 另一种思路是"允许程序不必连续存放" → 这就是分页/分段（下两章）——从根上消灭外部碎片，代价是引入"内碎片"与"地址转换开销"。
text
紧凑前 紧凑后
┌──┬───┬────┬──┬────┬───┐ ┌──┬───┬────┬─────┬───┐
│OS│ A │空闲│B │空闲│ C │ → │OS│ A │ B │ C │空闲│
└──┴───┴────┴──┴────┴───┘ └──┴───┴────┴─────┴───┘
碎片散落各处 碎片合并到一端示例
例 1：四算法在同一组数据上的对照
初始空闲分区（按地址递增）：
F1 = 120K、F2 = 480K、F3 = 80K、F4 = 300K、F5 = 200K。 请求序列：依次申请100K、260K、90K。
先手推一遍首次适应（FF）：
| 步 | 请求 | 从头扫描 | 选中 | 该分区剩余 |
|---|---|---|---|---|
| 1 | 100K | F1=120 ✔ | F1 | 120 − 100 = 20 |
| 2 | 260K | F1=20 ✘ → F2=480 ✔ | F2 | 480 − 260 = 220 |
| 3 | 90K | F1=20 ✘ → F2=220 ✔ | F2 | 220 − 90 = 130 |
最终空闲：F1=20 F2=130 F3=80 F4=300 F5=200（总空闲 = 20+130+80+300+200 = 730K）。
其余三个算法用下例的脚本一次算清：
# 四个动态分区分配算法在同一组数据上的逐步对照
FREE = [120, 480, 80, 300, 200] # 空闲分区(KB), 按地址递增
REQS = [100, 260, 90] # 请求序列(KB)
def first_fit(free, reqs):
f = free[:]
log = []
for r in reqs:
for k in range(len(f)):
if f[k] >= r:
log.append((r, k + 1, f[k] - r))
f[k] -= r
break
else:
log.append((r, None, 0))
return log, f
def best_fit(free, reqs):
f = free[:]
log = []
for r in reqs:
cand = [(f[k], k) for k in range(len(f)) if f[k] >= r]
if cand:
_, k = min(cand) # 够用且最小
log.append((r, k + 1, f[k] - r))
f[k] -= r
else:
log.append((r, None, 0))
return log, f
def worst_fit(free, reqs):
f = free[:]
log = []
for r in reqs:
cand = [(f[k], k) for k in range(len(f)) if f[k] >= r]
if cand:
_, k = max(cand) # 最大
log.append((r, k + 1, f[k] - r))
f[k] -= r
else:
log.append((r, None, 0))
return log, f
def next_fit(free, reqs):
f = free[:]
log = []
p = 0 # 上次分配结束处的下标
for r in reqs:
for step in range(len(f)):
k = (p + step) % len(f) # 从 p 开始循环扫描
if f[k] >= r:
log.append((r, k + 1, f[k] - r))
f[k] -= r
p = (k + 1) % len(f)
break
else:
log.append((r, None, 0))
return log, f
print('初始空闲分区: ' + ' '.join('F%d=%d' % (i + 1, s) for i, s in enumerate(FREE)) + ' (KB)')
print('请求序列: ' + ', '.join('%dK' % r for r in REQS))
print()
THRESH = min(REQS) # 小于"最小请求"的空闲块, 视为不可用碎片
for name, fn in [('首次适应 FF', first_fit), ('最佳适应 BF', best_fit),
('最坏适应 WF', worst_fit), ('邻近适应 NF', next_fit)]:
log, f = fn(FREE, REQS)
picks = ','.join('F%d' % p if p else '-' for _, p, _ in log)
frag = [s for s in f if s < THRESH]
print(name)
for r, p, rem in log:
print(' 请求 %3dK -> %s, 余 %3dK' % (r, 'F%d' % p if p else '无可用分区', rem))
print(' 选中序列 = %s' % picks)
print(' 最终空闲 = ' + ' '.join('F%d=%d' % (i + 1, s) for i, s in enumerate(f)))
print(' 最大空闲块 = %dK, 不可用碎片(<%dK) = %s, 共 %dK'
% (max(f), THRESH, frag, sum(frag)))
print()
print('总空闲 = %dK, 总请求 = %dK, 四算法都剩 %dK (总空闲量不变, 只是分布不同)'
% (sum(FREE), sum(REQS), sum(FREE) - sum(REQS)))
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
输出对照（真实运行结果）：
初始空闲分区: F1=120 F2=480 F3=80 F4=300 F5=200 (KB)
请求序列: 100K, 260K, 90K
首次适应 FF
请求 100K -> F1, 余 20K
请求 260K -> F2, 余 220K
请求 90K -> F2, 余 130K
选中序列 = F1,F2,F2
最终空闲 = F1=20 F2=130 F3=80 F4=300 F5=200
最大空闲块 = 300K, 不可用碎片(<90K) = [20, 80], 共 100K
最佳适应 BF
请求 100K -> F1, 余 20K
请求 260K -> F4, 余 40K
请求 90K -> F5, 余 110K
选中序列 = F1,F4,F5
最终空闲 = F1=20 F2=480 F3=80 F4=40 F5=110
最大空闲块 = 480K, 不可用碎片(<90K) = [20, 80, 40], 共 140K
最坏适应 WF
请求 100K -> F2, 余 380K
请求 260K -> F2, 余 120K
请求 90K -> F4, 余 210K
选中序列 = F2,F2,F4
最终空闲 = F1=120 F2=120 F3=80 F4=210 F5=200
最大空闲块 = 210K, 不可用碎片(<90K) = [80], 共 80K
邻近适应 NF
请求 100K -> F1, 余 20K
请求 260K -> F2, 余 220K
请求 90K -> F4, 余 210K
选中序列 = F1,F2,F4
最终空闲 = F1=20 F2=220 F3=80 F4=210 F5=200
最大空闲块 = 220K, 不可用碎片(<90K) = [20, 80], 共 100K
总空闲 = 1180K, 总请求 = 450K, 四算法都剩 730K (总空闲量不变, 只是分布不同)四条结论（这张对照表就是本章的核心）：
- 四个算法都从
F1 = 120K起步（第一个请求 100K 只有 F1 最"贴"），但从第二个请求开始分道扬镳：FF/NF 咬住 F2（从低地址/上次位置起扫），BF 跳到 F4（300K 是"够用且最小"的），WF 又回到 F2（480K 最大）。 - BF 的"不可用碎片"最多：
20 + 80 + 40 = 140K，比 WF 的 80K 多 75%——这就是"最佳适应反而最差"的量化证据。 - WF 留下的最大空闲块只有 210K，而 BF 留下了完整的 F2 = 480K——"最坏适应会迅速吃光大块"在这里看得很清楚。
- FF 与 NF 在本题结果只差一个 F2 的余量（130K vs 220K），因为 F3 = 80K 太小，NF 跳过它落到了 F4——NF 的唯一优势是"不必每次从头扫描"，碎片分布更均匀。
例 2：C 实现——首次适应与最佳适应
#include <stdio.h>
#define NP 5 /* 分区数 */
#define NR 3 /* 请求数 */
static int free_sz[NP] = {120, 480, 80, 300, 200}; /* 空闲区(KB), 按地址递增 */
static int req[NR] = {100, 260, 90};
/* 首次适应: 从头找第一个够大的, 返回下标; 找不到返回 -1 */
static int first_fit(int need) {
int k;
for (k = 0; k < NP; k++)
if (free_sz[k] >= need) return k;
return -1;
}
/* 最佳适应: 在所有够大的里挑最小的 */
static int best_fit(int need) {
int k, best = -1;
for (k = 0; k < NP; k++) {
if (free_sz[k] < need) continue;
if (best < 0 || free_sz[k] < free_sz[best]) best = k;
}
return best;
}
/* 用指定算法把请求序列跑一遍, 跑完后把空闲区还原(便于两种算法各跑一次) */
static void run(const char *name, int (*pick)(int)) {
int saved[NP], r, k, i;
for (i = 0; i < NP; i++) saved[i] = free_sz[i];
printf("[%s]\n", name);
for (r = 0; r < NR; r++) {
k = pick(req[r]);
if (k < 0) {
printf(" 请求 %3dK -> 无可用分区, 失败\n", req[r]);
} else {
printf(" 请求 %3dK -> 用 F%d 分区, 余 %3dK\n",
req[r], k + 1, free_sz[k] - req[r]);
free_sz[k] -= req[r];
}
}
printf(" 最终空闲: ");
for (i = 0; i < NP; i++) {
if (i) printf(" ");
printf("F%d=%d", i + 1, free_sz[i]);
}
printf("\n");
for (i = 0; i < NP; i++) free_sz[i] = saved[i]; /* 还原 */
}
int main(void) {
printf("初始空闲分区(按地址递增): F1=120 F2=480 F3=80 F4=300 F5=200 (KB)\n");
run("首次适应 FF", first_fit);
run("最佳适应 BF", best_fit);
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
初始空闲分区(按地址递增): F1=120 F2=480 F3=80 F4=300 F5=200 (KB)
[首次适应 FF]
请求 100K -> 用 F1 分区, 余 20K
请求 260K -> 用 F2 分区, 余 220K
请求 90K -> 用 F2 分区, 余 130K
最终空闲: F1=20 F2=130 F3=80 F4=300 F5=200
[最佳适应 BF]
请求 100K -> 用 F1 分区, 余 20K
请求 260K -> 用 F4 分区, 余 40K
请求 90K -> 用 F5 分区, 余 110K
最终空闲: F1=20 F2=480 F3=80 F4=40 F5=110⚠️ 三点说明：
int (*pick)(int)是函数指针参数——把"选哪个分区"这件事抽出来，run()就与具体算法解耦（这本身就是"模块化"的演示）。若对函数指针不熟，直接把first_fit的函数体复制进run也行。run()首尾各做一次"备份/还原"：不还原的话，第二次调用（BF）看到的就不是初始空闲表了——这是本题最容易写错的地方（和os/16-deadlock.md里"试探分配必须回滚"是同一个纪律）。- 本机无 C 编译器：此段代码逐行人工审查，并用等价的 Python 实现（例 1 脚本里的
first_fit/best_fit）实跑核对过输出——两边结果完全一致。
例 3：固定分区的内部碎片计算
内存 256K，操作系统占 20K，划分为 4 个等长分区。依次装入 30K、40K、50K、20K 四个作业。求每个分区的内部碎片与总利用率。
第一步：分区大小
第二步：逐个算内部碎片
| 分区 | 大小 | 装入作业 | 内部碎片 |
|---|---|---|---|
| 1 | 59K | 30K | 59 − 30 = 29K |
| 2 | 59K | 40K | 59 − 40 = 19K |
| 3 | 59K | 50K | 59 − 50 = 9K |
| 4 | 59K | 20K | 59 − 20 = 39K |
| 合计 | 236K | 140K | 96K |
第三步：利用率
结论：固定分区把近 41% 的内存当碎片浪费掉了（96/236 = 40.68%）——这就是"固定分区只能用于作业大小相近、且对内存浪费不敏感的场景"的原因。
考点
考点
1. 必背结论
- 内存管理四功能：分配与回收、地址转换、空间扩充（虚拟内存）、内存保护。
- 单一连续分配：单道、无地址转换、浪费大；固定分区：多道、只有内部碎片、分区数受限；动态分区：按需切割、只有外部碎片、需要分配算法与紧凑。
- 内部碎片 ⟺ 已分配出去却没用（固定分区）；外部碎片 ⟺ 未分配却小到没人要（动态分区、分页/分段也会有少量）。
- 四算法选择规则：FF 第一个够大的；BF 够用且最小的；WF 最大的；NF 从上次结束处起第一个够大的。
- 链的排列：FF/NF 按地址递增；BF 按容量递增；WF 按容量递减。
- "最佳适应"外部碎片最多；"最坏适应"会迅速吃光大空闲区；"邻近适应"只是换了扫描起点。
- 紧凑（拼凑）的前提是动态重定位，代价是拷贝内存 + 进程必须暂停。
arch/13-virtual.md的动态重定位寄存器给的是基址；连续分配下只需要"界地址寄存器"做越界保护。
2. 高频陷阱
- 把"内部碎片"和"外部碎片"说反：错。内部 = 分给你了但你没用（"里面"的浪费）；外部 = 没分出去但别人用不了（"外面"的零头）。固定分区→内部；动态分区→外部。
- 认为"最佳适应能减少碎片"：错。它留下的是"最紧的边角料"，反而使外部碎片总数最多（例 1 的 140K vs 80K）。
- 认为"最坏适应能把大块留到最后"：错。它每次先吃最大的，大块很快耗尽，后续大请求反而装不下。
- 把"邻近适应"与"首次适应"当成同一个：错。FF 每次从链头扫，NF 从上一次结束处扫——NF 的开销更小、碎片分布更均匀，但失去了"高地址大块被保住"的性质。
BF写成"按地址排列的链里挑最小"：错。BF 的链按容量递增排列，从头往后找第一个 ≥ 请求量的就是最佳（这样才不用全表扫描）。- 说"动态分区没有碎片"：错。动态分区没有内部碎片，但外部碎片一定会有。
- 说"紧凑可以在任何时候做"：错。紧凑要移动进程，必须在能停下并重定位的前提下进行，且开销随时间累计增大。
- 把"分区表"与"分区链"混为一谈：表长度固定、链可动态增减；动态分区用链更合适。
3. 解题模板（"分区分配题"）
① 抄下初始空闲区(注明"按地址递增"), 写下请求序列
② 按题目指定的算法, 逐个请求:
FF/NF: 从头/上次位置起, 找第一个 >= 请求量的
BF : 在所有 >= 请求量的里挑最小的
WF : 在所有 >= 请求量的里挑最大的
记下"选中哪个区、该区余多少"
③ 结尾必答三问: 最终空闲表 / 最大空闲块 / 是否产生外部碎片
④ 若问"能否紧凑": 答"可以, 前提是动态重定位; 代价是拷贝开销与进程暂停"
⑤ 若问利用率: 利用率 = 作业总量 / 分区总量, 内部碎片 = 分区总量 - 作业总量4. 与相邻章节的接口
os/21-paging.md（分页）：分页把"必须连续"这条限制去掉，外部碎片随之消失（代价是页内碎片 + 页表开销）。本章的"外部碎片问题"就是下一章的动机。os/22-segment.md（分段）：分段仍要求"段内连续"，因此外部碎片又回来了——分页消灭它、分段带回来，这个对比是考点。os/23-virtual.md（虚拟内存）："内存空间扩充"这个功能就落在那一章；本章只解决"怎么摆得下"，那一章解决"摆不下怎么办"。os/16-deadlock.md（死锁）："一次申请全部内存"会造成浪费与饥饿；按需分配（分页/请求调页）从设计上避开了"必须预先申请全部内存"。arch/13-virtual.md（虚拟存储器）：那里的"物理页框分配"是硬件视角，本章与 21~24 是操作系统视角——同一件事的上下游两面。
小结
- 内存管理四功能：分配回收、地址转换、空间扩充、内存保护。
- 三种连续分配：单一连续（单道、浪费）→ 固定分区（多道、内部碎片）→ 动态分区（按需、外部碎片）。
- 四算法一句话：FF 第一个够大的（地址递增）、BF 够用且最小的（容量递增）、WF 最大的（容量递减）、NF 从上次位置起第一个够大的。
- 反直觉三结论："最佳适应"外部碎片最多、"最坏适应"迅速吃光大块、"邻近适应"只是换起点。
- 本章锚点数据：初始
120/480/80/300/200，请求100/260/90——FF 选中 F1,F2,F2（余 20/130/80/300/200）、BF 选中 F1,F4,F5（余 20/480/80/40/110）、WF 选中 F2,F2,F4（余 120/120/80/210/200）、NF 选中 F1,F2,F4（余 20/220/80/210/200）；四者总空闲都剩 730K，只是分布不同。 - BF 的不可用碎片 140K > WF 的 80K——"最佳适应反而最差"的量化证据。
- 固定分区锚点：256K 减 OS 20K、分 4 区 → 每区 59K，装 30/40/50/20 → 内部碎片 29/19/9/39 共 96K，利用率 59.32%。
- 紧凑是缓解外部碎片的办法，前提是动态重定位；分页/分段是更彻底的解法。
下一篇：分页存储管理
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。