动态分区算法

动态分区分配 (Dynamic Partitioning) 概述

背景: 在可变分区存储管理中，内存空间被划分为若干个大小不等的分区。当一个新作业请求内存时，系统需要从空闲分区表或空闲分区链中，按照某种算法选择一个大小合适的空闲分区分配给它。

核心问题: 选择哪个空闲分区？不同的选择策略，会直接影响内存的利用率（即内存碎片问题）和分配效率（即查找开销）。

内存碎片:

• 内部碎片 (Internal Fragmentation): 分配给作业的分区大于作业实际所需，分区内部多余的空间无法被利用。

• 外部碎片 (External Fragmentation): 内存中存在许多不连续的、细小的空闲分区，它们的总和可能很大，但由于不连续，无法满足一个较大作业的内存请求。动态分区算法主要产生外部碎片。

1. 基于顺序搜索的分配算法 (Sequential Search Algorithms)

这类算法的核心思想是，当作业请求内存时，系统按顺序遍历一个记录了所有空闲分区的链表，直到找到一个满足条件的分区为止。

1.1 首次适应算法 (First Fit, FF)

• 算法思想: 从空闲分区链的链首开始查找，将第一个满足大小要求的空闲分区分配给作业。

• 实现: 分配后，如果该分区大于作业请求，剩下的部分仍然作为一个新的空闲分区保留在链中。

• 图示举例:

  • 空闲分区链: [100K, 地址1000] -> [20K, 地址3000] -> [300K, 地址5000]

  • 作业请求: 80K

  • 过程:

    1. 检查第一个分区 100K。100K >= 80K，满足条件。

    2. 分配：从 100K 的分区中划出 80K 给作业。

    3. 更新：原分区变为 20K，空闲分区链更新为 [20K, 地址1000] -> [20K, 地址3000] -> [300K, 地址5000]。

• 优点:

  • 算法简单，开销小。

  • 倾向于保留内存高地址部分的大空闲区，有利于满足后续对大内存的请求。

• 缺点:

  • 随着时间推移，内存低地址部分会被不断切割，产生大量难以利用的小碎片。

  • 每次查找都从头开始，增加了查找开销。

1.2 循环首次适应算法 (Next Fit, NF)

• 算法思想: 它是首次适应算法的变种。不再每次都从链首开始查找，而是从上一次查找结束的位置开始继续向后查找。查找到链尾时，再回到链首。

• 优点:

  • 查找开销相比FF有所降低，不需要每次都从头开始。

  • 空闲分区的分布更加均匀，避免了FF算法中低地址区域碎片集中的问题。

• 缺点:

  • 由于不再优先使用低地址的小分区，导致缺乏大的空闲分区。当有大作业请求时，可能无法满足。

1.3 最佳适应算法 (Best Fit, BF)

• 算法思想: 遍历整个空闲分区链，找到一个与作业请求大小最接近且不小于它的空闲分区进行分配。

• 实现: 为了避免切割后剩下太小的、几乎无法使用的分区，可以规定当剩余部分小于某个阈值时，将整个分区全部分配（产生少量内部碎片以避免外部碎片）。

• 图示举例:

  • 空闲分区链: [100K] -> [90K] -> [300K]

  • 作业请求: 80K

  • 过程:

    1. 遍历整个链表，找到所有满足条件的分区：100K, 90K, 300K。

    2. 比较大小差值：100-80=20, 90-80=10, 300-80=220。

    3. 选择差值最小的，即 90K 的分区进行分配。

• 优点:

  • 能最大限度地保留大分区，提高了满足大作业请求的概率。

• 缺点:

  • 每次都需要扫描整个链表，算法开销大。

  • 非常容易产生大量极小的、难以利用的外部碎片。这是它的致命弱点。

1.4 最坏适应算法 (Worst Fit, WF)

• 算法思想: 与最佳适应相反，它遍历整个空闲分区链，总是挑选一个最大的空闲分区进行分配。

• 逻辑: 寄希望于分配后剩下的空闲区仍然足够大，可以满足其他作业的需求。

• 图示举例:

  • 空闲分区链: [100K] -> [90K] -> [300K]

  • 作业请求: 80K

  • 过程:

    1. 遍历整个链表，找到最大的分区 300K。

    2. 从 300K 的分区中划分 80K 给作业，剩下 220K。

• 优点:

  • 可以减少小碎片的产生。从某种程度上说，它对中小作业更有利。

• 缺点:

  • 同样需要扫描整个链表，开销大。

  • 会迅速消耗掉大的空闲分区，导致后续若有大作业请求，系统将无能为力。

  • 在实践中，性能通常不佳。

2. 基于数据结构的快速查找算法

这类算法通过特殊的数据结构来组织空闲分区，从而避免了线性扫描，提高了查找效率。

2.1 快速适应算法 (Quick Fit) / 分离适配 (Segregated Fit)

• 算法思想: 将空闲分区按其容量大小进行分类，为每一类大小都建立一个单独的空闲分区链表。

• 实现:

  • 系统中有多个空闲分区链表，如一个链表专门存放大小为8K的分区，另一个存放12K的，等等。

  • 当作业请求 size 大小的内存时，系统直接去管理大小为 size (或稍大于 size) 的链表中查找。

  • 如果该链表不为空，直接取下第一块分配即可，查找效率极高 (O(1))。

  • 如果该链表为空，则去更大尺寸的链表中找一个分区，切割后一部分用于分配，另一部分（如果有）插入到对应大小的空闲链表中。

• 优点:

  • 查找效率非常高，分配快速。

  • 不涉及分区的合并和分割（除非在更大链表中切割），实现简单。

• 缺点:

  • 在设计上，如何确定分区的尺寸和类别是个难题。

  • 分区回收时，算法复杂（需要考虑合并问题）。

  • 本质上是以空间换时间，会加剧内存碎片的产生。

2.2 伙伴系统 (Buddy System)

• 算法思想: 一种经典的、介于上述两者之间的方案。它规定所有分区的大小都必须是 2的幂。

• 分配过程:

  1. 假设作业请求 size 大小的内存。系统计算出满足该请求的最小2的幂 2^k (即 2^(k-1) < size <= 2^k)。

  2. 系统检查大小为 2^k 的空闲链表。

  3. 如果链表中有空闲分区，则直接分配。

  4. 如果链表为空，则去查找更大一级的链表，即 2^(k+1)。如果该链表不为空，则取出一个分区，将其对半分裂成两个大小为 2^k 的“伙伴”。一个用于分配，另一个挂入 2^k 的空闲链表。

  5. 如果 2^(k+1) 的链表也为空，则继续向上查找，递归地进行分裂。

• 回收过程:

  1. 当一个大小为 2^k 的分区被释放时，系统会检查其**“伙伴”分区**是否也空闲。

  2. 如果伙伴也空闲，则将两者合并成一个大小为 2^(k+1) 的更大分区。

  3. 合并后的分区，继续尝试与它的伙伴合并，直到无法合并为止。

• 优点:

  • 查找和分裂合并的速度很快，因为伙伴的地址可以通过简单的位运算得出。

  • 能有效地减少外部碎片。

• 缺点:

  • 由于分区大小固定为2的幂，内部碎片问题严重。例如，一个需要33K内存的作业，必须分配一个64K的分区，浪费了31K。

总结与考点分析