一句话
首次适应等算法是为了“大小不一的连续分配”而设计的：块大小不一样，才需要挑选放哪块。分页让每一块都一样大，挑选这件事就不存在了。所以对同一块内存，两者是替代关系；但只要系统里还有“大小可变、又必须连续”的东西，这些算法就还会用上。
这一章只回答一个问题：一块内存怎么分给多个进程。先是连续分配（进程占一整段），碎片越来越麻烦，于是改成把进程切成页随便放，再用页表记住每页放在哪儿。
记住每种算法的排序方式，特点和缺点都能推出来。选择题最常考：哪种算法综合最好、哪种产生最多小碎片。
| 算法 | 空闲分区排序 | 怎么找 | 优点 | 缺点 |
|---|---|---|---|---|
| 首次适应 FF | 地址递增 | 从头找，第一个够大的就用 | 综合性能最好，算法开销小；高地址保留了大块 | 低地址端留下很多小碎片，每次查找都要从它们身上跳过 |
| 邻近适应 NF | 地址递增（循环链表） | 从上次找到的位置往后接着找 | 空闲区分布更均匀，查找开销小 | 高地址的大块也会被切碎，通常比首次适应差 |
| 最佳适应 BF | 容量递增 | 找能放下的最小块 | 大块被保留下来，给大进程用 | 切剩的边角最小，产生最多难以利用的小碎片；回收后要重新排序 |
| 最坏适应 WF | 容量递减 | 永远切最大的那块 | 切剩的部分还比较大，还能用 | 大块很快被用完，大进程来了没地方放；回收后要重新排序 |
内存 100 KB。依次执行：A 30、B 20、C 25、D 15，释放 A、C，再申请 E 8、F 12、G 30（单位 KB）。切换算法，一步步往下点，看最后一步 G 能不能放下。分页模式下页框大小为 5 KB，共 20 个页框。
逻辑地址拆成页号和页内偏移，用页号查页表得到块号，偏移原样不动，拼起来就是物理地址。
页表项里只存块号，不存页号：页号就是下标，由“页表起始地址 + P × 页表项长度”直接算出位置。
首次适应等算法是为了“大小不一的连续分配”而设计的：块大小不一样，才需要挑选放哪块。分页让每一块都一样大，挑选这件事就不存在了。所以对同一块内存，两者是替代关系；但只要系统里还有“大小可变、又必须连续”的东西，这些算法就还会用上。
外部碎片的根源是：剩下的空隙太小，装不下一个必须连续的进程。分页同时拿掉了这两个条件：
代价是换成了内部碎片（每个进程最后一页装不满，平均半页），外加页表占用的空间和查表的时间。
给进程分页框时不用。哪个空闲页框都一样，从空闲页框链表或位示图里拿一个就行，没有“挑哪一块最合适”的问题。
所以首次适应、最佳适应这类算法属于动态分区（和分段），不属于分页。
| 方案 | 内部碎片 | 外部碎片 | 一句话原因 |
|---|---|---|---|
| 单一连续分配 | 有 | 无 | 整个用户区给一道程序，装不满就浪费 |
| 固定分区分配 | 有 | 无 | 分区大小固定，程序装不满分区 |
| 动态分区分配 | 无 | 有 | 按需切，切剩的小空隙放不下别人；可用紧凑解决 |
| 基本分页 | 有（仅最后一页） | 无 | 页框固定大小，最后一页装不满 |
| 基本分段 | 无 | 有 | 段长可变且段内连续，本质是动态分区 |
| 段页式 | 有（每段最后一页） | 无 | 内存按页分配 |