连续内存分配

连续内存分配要求一个进程占用一整段连续的物理内存空间。它是早期存储管理方式的主线，也能帮助理解后续分页、分段为什么要出现。

连续分配要解决三个问题：

问题 含义
如何划分内存 用户区是整体使用、预先分区，还是按进程大小动态分区
如何选择空闲区 多个空闲区都能满足请求时，选哪一个
如何回收空闲区 进程结束后，释放区是否能和相邻空闲区合并

单一连续分配

单一连续分配把内存分为系统区和用户区。系统区通常放在低地址，用于存放操作系统；用户区一次只装入一道用户程序。

特点 说明
优点 实现简单；没有外部碎片
缺点 同一时刻只能运行一个用户程序；用户区可能大量空闲
碎片 分配给进程但没有被用上的部分属于内部碎片

这种方式只适合非常简单的单道程序环境。

固定分区分配

固定分区分配把用户区预先划分成若干固定分区，每个分区装入一道作业。分区大小可以相等，也可以不相等。

方式 特点
分区大小相等 实现简单，但缺乏灵活性
分区大小不等 能适应不同大小的程序，但仍受固定分区限制

固定分区分配需要一张分区说明表，记录每个分区的大小、起始地址和状态。当程序要装入内存时，操作系统查表找到一个空闲且足够大的分区。

固定分区分配没有外部碎片，但容易产生内部碎片：如果一个 6MB 程序被放入 10MB 分区，剩下的 4MB 已经属于该进程所在分区，不能再分给其他进程。

动态分区分配

动态分区分配又称可变分区分配。它不会预先把用户区切成固定分区，而是在进程装入时，根据进程大小动态建立分区。

动态分区分配没有内部碎片，因为分给进程的分区大小正好匹配进程需要；但会产生外部碎片。

内部碎片 vs 外部碎片
碎片 含义
内部碎片 已分配给进程，但进程没有用上的空间
外部碎片 空闲区总量足够，但被切成多个不连续小块，无法满足连续分配请求
即使空闲空间总量足够，但没有一整块连续空间满足请求，就会分配失败。

外部碎片可以通过紧凑解决：移动内存中的进程，把分散的空闲区拼成一整块。但紧凑需要移动进程并更新地址转换信息，代价较高，通常要求动态重定位支持。

空闲分区表与空闲分区链

动态分区分配需要记录空闲区。常见结构有两类：

结构 做法
空闲分区表 每个空闲分区对应一个表项，记录起始地址、大小、状态
空闲分区链 在空闲分区内部保存前向/后向指针，把空闲区串成链表

分配时，从空闲分区表或空闲分区链中找到一块满足大小的空闲区；若空闲区大于请求大小，则切出一部分给进程，剩余部分继续作为空闲区。

回收时，必须检查释放区的相邻位置：

相邻情况 回收操作
前后都不是空闲区 新增一个空闲分区
前面相邻空闲 与前面的空闲区合并
后面相邻空闲 与后面的空闲区合并
前后都相邻空闲 三者合并成一个更大的空闲区

动态分区分配算法

当多个空闲区都能满足请求时，分配算法决定选哪一块。

算法 规则 空闲区组织 主要问题
首次适应 从低地址开始，找第一个足够大的空闲区 按地址递增排列 低地址容易积累小碎片，但综合性能较好
最佳适应 选能满足请求的最小空闲区 按容量递增排列 容易留下很小、难以利用的外部碎片。“最佳”不是最佳。
最坏适应 选最大的空闲区 按容量递减排列 大空闲区容易被快速消耗
邻近适应 从上次查找结束位置继续找 按地址递增的循环结构 可能更快消耗高地址大分区

首次适应

首次适应每次都从低地址开始查找，找到第一个大小满足要求的空闲分区。

它不需要按容量排序，回收后维护成本较低。综合来看，首次适应通常比其他几个简单算法更均衡。

最佳适应

最佳适应优先使用能满足请求的最小空闲分区，希望尽量保留大分区。

它的问题是容易产生大量很小的外部碎片。例如申请 9MB 时使用 10MB 空闲区，会留下 1MB 小碎片，这类碎片之后可能很难再被利用。

最坏适应

最坏适应优先使用最大的空闲分区，希望每次切分后剩余的空间仍然比较大。

它能减少很小碎片的出现，但会不断消耗大分区，不利于后续大进程装入。

邻近适应

邻近适应是首次适应的变体。它不再每次从链头查找，而是从上次查找结束的位置继续向后找，通常用循环链表实现。

它能减少重复扫描低地址小分区的开销，但也会让高地址空闲区更容易被使用，可能导致大空闲区更快被切碎。

基于搜索的分配算法

连续分配还可以通过更适合快速查找的数据结构来管理空闲区。下面三种方法只需掌握基本思想和操作过程。

算法 核心思想 基本操作
快速适应 为常见大小建立多个空闲链表 申请某大小时直接到对应链表取块；释放时放回对应链表
伙伴系统 空闲块大小按 $2^k$ 分级，分裂和合并都找伙伴 申请时向上取整并分裂大块；释放时若伙伴空闲则合并
哈希算法 用哈希表按空闲区大小定位链表 根据申请大小计算哈希值，找到对应或相近大小的空闲链表

快速适应

快速适应为若干常用大小维护单独的空闲分区链表。例如 4KB、8KB、16KB 各有一条链表。申请 8KB 时，不必遍历所有空闲区，直接到 8KB 链表取一个分区。

它的优点是分配速度快；缺点是回收和合并更复杂。如果一个空闲块被分裂或合并，需要维护对应大小链表。

伙伴系统

伙伴系统规定空闲块大小只能是 $2^k$。若申请大小不是 $2^k$，就向上取整到最近的 $2^k$。

申请时，如果没有合适大小的空闲块，就把更大的空闲块不断二分，直到得到所需大小。释放时，如果它的伙伴块也空闲，就合并成更大的块，并继续尝试向上合并。

伙伴系统的优点是分裂和合并规则清晰，查找效率较高；缺点是可能产生内部碎片。例如申请 10KB 必须分配 16KB。

哈希算法

哈希算法用空闲块大小作为关键字，通过哈希函数快速定位某类空闲链表。

申请内存时，根据请求大小计算哈希值，找到对应链表；若该链表没有合适分区，再查找相邻或备用链表。它的目标是减少搜索空闲分区的时间。

小结

管理方式 是否预先分区 碎片特点 适用理解
单一连续分配 用户区整体使用 可能有内部碎片 单道程序
固定分区分配 预先固定分区 内部碎片明显 早期多道程序
动态分区分配 按进程大小动态建立分区 没有内部碎片，但有外部碎片 连续分配的核心模型
基于搜索的算法 取决于具体算法 以提高查找、分裂、合并效率为目标 空闲区管理优化