考研笔记

连续分配管理方式

连续分配指为一个进程分配一块地址连续的内存空间。三种方案按灵活性递增：单一连续分配 → 固定分区分配 → 动态分区分配。

这一节的两个重点是：碎片是怎么产生的，以及空闲分区该怎么组织才能找得快。

机制

三种连续分配方案

① 单一连续分配

内存分为系统区和用户区，用户区只放一道用户程序，独占整个用户区。

只适用于单用户单任务的操作系统（如早期的 DOS）。优点是无外部碎片、实现极简；缺点是只能一道程序，且用户区没用完的部分全是浪费。

② 固定分区分配

把用户区预先划分成若干个固定大小的分区，每个分区装一道作业。分区大小可以相等（缺乏灵活性，大作业装不下、小作业浪费）或不等（按常见作业大小划分，灵活些）。

系统需要一张分区说明表，记录每个分区的起始地址、大小、状态（已分配/未分配）。

它是最早的、也是最简单的支持多道程序的方案。 因为分区位置固定不变，可以采用静态重定位，不需要地址变换机构。

缺点是产生内部碎片——作业往往比分区小，剩下的那一块留在分区内谁也用不了。

③ 动态分区分配（可变分区分配）

不预先划分分区，而是在作业装入时，按其实际需要临时划出一块大小刚好的分区。

系统需要用空闲分区表或空闲分区链来记录当前还有哪些空闲块。

两种结构分别长什么样？

  • 空闲分区表：每个空闲分区占一个表项，通常记录分区号、起始地址和分区大小。例如：2 号空闲区｜起址 1000｜大小 500。
  • 空闲分区链：把每个空闲分区本身当作一个链表结点，在分区内保存分区大小以及前驱、后继指针，把所有空闲分区串起来。

分配或回收内存后，都要相应地修改、删除、插入或合并表项（链结点）。两者记录的信息本质相同，区别只是一个用表集中保存，一个用链把空闲区连接起来。

优点是没有内部碎片（分多少给多少）。但用久了会出现新问题：进程不断装入和退出，内存里会散落许多小而分散的空闲块，它们单独都太小放不下新作业，加起来却不小——这就是外部碎片。

解决外部碎片的手段是紧凑（拼接）：把内存中的作业统统往一端挪，把零散的空闲区合并成一大块。

注意紧凑要移动已经装入的作业，因此必须采用动态重定位——移动之后只需修改重定位寄存器即可。这正好解释了为什么可变分区不能用静态重定位。

内部碎片与外部碎片

这一对是本章贯穿始终的概念，务必分清：

  • 内部碎片：已经分配给某进程、但该进程用不上的那部分空间。它在分区内部。
  • 外部碎片：尚未分配给任何进程、但太小以致无法利用的空闲区。它在各分区之间。

判据一句话：这块空间是不是已经归属某个进程了？ 归属了却用不着，是内部；没归属却用不上，是外部。

各方案的碎片情况：

方案内部碎片外部碎片
单一连续分配有无
固定分区分配有无
动态分区分配无有
分页有（最后一页）无
分段无有
段页式有（每段最后一页）无

规律很清晰：按”固定大小的块”分配就有内部碎片，按”实际需要的大小”分配就有外部碎片。 分页按固定的页框分配，所以像固定分区；分段按段的实际长度分配，所以像动态分区。

基于顺序搜索的动态分区分配算法

系统把所有空闲分区串成一条链，分配时从链上找一块合适的。四种找法：

首次适应（First Fit）——空闲分区按地址递增排序，每次从链头开始找，找到第一个够大的就用。

综合性能最好。原因是它倾向于优先使用低地址部分的空间，从而在高地址端保留下大块的连续空闲区。缺点是低地址端会不断被切割出小碎片，而每次查找又都要从头扫过这些碎片。

邻近适应 / 循环首次适应（Next Fit）——与首次适应相同，但每次从上次找到的位置继续往下找，而不是回到链头。

设计动机是避免每次都扫描低地址端那堆小碎片。但它带来一个副作用：空闲区被均匀地消耗，高地址端的大块也会被切碎，反而使大作业更难被满足。综合性能通常不如首次适应。

最佳适应（Best Fit）——空闲分区按容量递增排序，每次找能满足要求的最小分区。

名字叫”最佳”，实际效果并不好：它总是切出尽可能小的剩余部分，于是产生大量难以利用的外部碎片。

最坏适应（Worst Fit）——空闲分区按容量递减排序，每次用最大的那块。

想法是切完之后剩下的部分还够大、还能用。但代价是大块空闲区被迅速消耗殆尽，之后大作业就没地方放了。

四者的排序结论：首次适应综合最好，其余三个各有明显缺陷。这个结论有点反直觉（名字最好听的”最佳适应”其实很差），是选择题的常客。

基于索引搜索的动态分区分配算法

疑问点：基于索引搜索的分配算法

动态分区分配中的”基于索引搜索的分配算法”较为抽象，其与顺序搜索的本质区别何在？

两者的本质区别只有一个：要不要遍历。

顺序搜索的问题在于只有一条链。系统里空闲分区一多（大型系统可能有成千上万个），每次分配都要从头扫过去，开销随分区数线性增长。

索引搜索的思路是：别把空闲分区堆在一条链上，按大小分类，为每一类建一个索引项。 分配时先查索引表定位到”该找哪一类”，直接取该类链上的第一块即可，完全不用遍历比较。

这就是”索引”二字的全部含义——用一张按大小分类的表，把”线性查找”换成”直接定位”。

三种具体实现：

① 快速适应算法

按容量大小把空闲分区分成若干类（例如 2KB、4KB、8KB、16KB……），每一类单独拉一条链，再用一张索引表记录每条链的表头指针。

分配时：根据请求大小找到能满足要求的最小那一类，直接取该链的第一块，整块给出去。

  • 优点：查找极快（几乎是 O(1)）；而且因为整块分配、不切割，不产生外部碎片。
  • 缺点：分区回收时要判断和合并伙伴，算法复杂；且由于整块给出，会产生内部碎片（请求 5KB 却给了 8KB）。

② 伙伴系统（见下一小节详述）

③ 哈希算法

以空闲分区的大小为关键字建立哈希表，表项指向对应的空闲分区链。分配时对请求大小做一次哈希运算，直接定位到链表头。

思想与快速适应一致，只是把”查索引表”换成了”算哈希”，进一步加快了定位。

伙伴系统

规则：所有分区的大小都是 2 的幂（ 个页框）。

  • 分配：请求大小为 时，找到满足 的最小 块。若该大小的空闲块不存在，就找更大的块对半劈开，劈出的两半互为伙伴；不断劈，直到得到 大小的块为止。
  • 回收：释放一块时，检查它的伙伴是否也空闲。若是，两者合并成更大的块；合并后继续向上检查能否再合并，直到不能为止。

“伙伴”的严格定义是：大小相同、地址连续，且是由同一个大块一分为二得来的那一对。注意”大小相同且地址相邻”还不够——必须来自同一次划分，所以第 1 块和第 2 块是伙伴，但第 2 块和第 3 块不是。

flowchart TB
    A["<b>1024K</b> 空闲"]:::free
    A -->|"请求 100K，无合适块，对半劈"| B1["512K"]:::free
    A --> B2["512K"]:::free
    B1 -->|"仍太大，再劈"| C1["256K"]:::free
    B1 --> C2["256K"]:::free
    C1 -->|"仍太大，再劈"| D1["<b>128K</b> ← 分配给请求"]:::used
    C1 --> D2["128K 空闲<br/>（D1 的伙伴）"]:::free

    classDef free fill:#dbeafe,stroke:#2563eb,color:#1e3a5f
    classDef used fill:#fee2e2,stroke:#dc2626,color:#7f1d1d

请求 100K 时，最终拿到一个 128K 的块，其中 28K 是内部碎片——这是伙伴系统必然的代价。

伙伴系统与”离散分配”的关系

疑问点：伙伴算法出现在"连续分配"一节，但 Linux 用它管理页框，两者是否矛盾

教材原文：“Linux 系统采用 3.1.2 节介绍的’伙伴算法’对内存中不同长度的连续空闲页框进行统计和记录……”

疑问在于：连续分配与离散分配似乎被混在了一起。

不矛盾。这个困惑源于把两个不同层面的”连续”当成了同一件事。

先把两个视角拆开：

视角一：进程看到的地址空间——这里谈”连续 / 离散”。

分页管理的意义在于：进程的逻辑地址空间可以被拆散，映射到内存中任意位置的、互不相邻的物理页框上。 进程自己感觉地址是连续的，实际存放却是离散的。这就是”离散分配”。

视角二：物理页框本身的分配——这里的”连续”是另一回事。

即使采用了分页，操作系统内核仍然经常需要一批”物理上连续的页框”，典型场景有三类：

  • DMA 传输：外设直接读写内存时不经过 MMU，看到的是物理地址，因此缓冲区必须物理连续
  • 内核数据结构：内核自身的很多结构要求物理连续，以便直接用物理地址访问
  • 大页：一次映射一大片，需要底层物理页框连续

伙伴算法服务的正是视角二。 它的职责是：管理系统中所有的空闲物理页框，并且能够高效地分出一批连续的页框（ 个），以及在释放时把相邻的页框重新合并回大块，避免物理内存被切得七零八落。

所以两句话就能理清：

“离散分配”说的是——进程的逻辑页可以散落到任意物理页框。 “伙伴算法”说的是——物理页框这个资源池本身，要怎么切分和合并才能保证随时拿得出连续的一批。

它们不在一个层面上，因此不冲突。 教材把伙伴算法放在 3.1.2，是因为它在算法形态上属于”连续分配”这一族（它分出去的是一整块连续空间）；而 Linux 用它管理页框，用的也正是这个能力。

补一句：分页解决的是”进程不必占用连续内存”，但它并没有消灭”某些时候就是需要连续物理内存”这个需求。 现代内核里两套机制是并存的——伙伴系统管连续页框块的分配，页表管逻辑到物理的离散映射。

边界

首次适应为什么反而最好

这是最反直觉的一条。四种算法里，名字最谦虚的”首次适应”综合性能最优，名字最好听的”最佳适应”很差。

原因在于它们对”大块空闲区”的保护程度不同：

  • 首次适应总是从低地址开始用，高地址端的大块得以保留，将来大作业还有地方放。
  • 最佳适应每次都精确切割，剩下的零头越来越小，很快积累出大量无法利用的外部碎片。
  • 最坏适应专挑大块下手，大块被最快消耗光。
  • 邻近适应让消耗均匀分布，结果是所有大块都被切碎。

判据：好的分配算法应当尽量少地破坏大块连续空间。

紧凑的前提是动态重定位

紧凑要移动内存中的作业。如果作业用的是静态重定位，地址已经写死在代码里，一移动就全错了。

因此动态分区分配必须配合动态重定位。 这也是”固定分区可以用静态重定位、可变分区不能”的根本原因。

内部碎片 vs 外部碎片：谁能被紧凑消除

紧凑只能消除外部碎片，对内部碎片无能为力。

因为内部碎片已经被算作某个进程的合法领地，操作系统无权也无法把它抠出来——它就在进程的分区里面。而外部碎片属于系统的空闲空间，把作业挪一挪就能拼起来。

快速适应 / 伙伴系统的碎片类型变了

顺序搜索的四种算法（FF/NF/BF/WF）都是按需切割，因此只有外部碎片。

而快速适应和伙伴系统是按预设的档位整块分配（8KB、），因此引入了内部碎片——这与固定分区、分页是同一种成因。

这是索引搜索类算法为了”查得快”付出的代价。

对照速查

方案分区划分内部碎片外部碎片可否静态重定位
单一连续用户区只放一道有无是
固定分区预先划定，大小固定有无是
动态分区装入时按需划出无有否（要紧凑）
顺序搜索算法排序方式每次取主要问题
首次适应 FF地址递增第一个够大的综合最好；低址碎片多
邻近适应 NF地址递增（循环）从上次位置继续大块被均匀切碎
最佳适应 BF容量递增最小的够用块产生大量小碎片
最坏适应 WF容量递减最大的块大块很快耗尽
索引搜索算法组织方式特点
快速适应按容量分类，每类一条链 + 索引表查找极快，整块分配→有内部碎片
伙伴系统块大小均为 ，可劈可合便于分出连续页框块，有内部碎片
哈希算法以容量为键建哈希表定位最快

考点

  • 内部碎片 vs 外部碎片的判据（是否已归属某进程）及各方案的碎片类型
  • 首次适应综合性能最好，最佳适应产生大量小碎片
  • 紧凑只能消除外部碎片，且必须配合动态重定位
  • 索引搜索的本质是”按大小分类建表，免去遍历”
  • 伙伴系统的伙伴定义：大小相同、地址连续、同源于一次划分
  • 伙伴算法管的是物理页框的连续性，与”进程离散分配”不在一个层面

链接

反向链接