操作系统内存分配问答集 #2

---

---

问题：解释以下分配算法。

1. 首次适应算法 (First Fit)

2. 最佳适应算法 (Best Fit)

3. 最差适应算法 (Worst Fit)

4. 伙伴系统 (Buddy System)

5. 循环首次适应算法 (Next Fit)

答案

首次适应算法 (First Fit)

首次适应算法是分配第一个足够大的空闲分区或空洞来容纳进程。找到第一个合适的空闲分区后就结束。

优点

速度最快的算法，因为它搜索的次数最少。

缺点

分配后剩余的未用内存区域如果太小就会浪费。因此，无法满足对更大内存的需求。

最佳适应算法 (Best Fit)

最佳适应算法是指分配满足请求进程要求的最小空闲分区。此算法首先搜索整个空闲分区列表，并考虑最小的足够大的空洞。然后尝试找到一个接近实际所需进程大小的空洞。

优点

内存利用率比首次适应算法好得多，因为它首先搜索最小的可用空闲分区。

缺点

它速度较慢，甚至可能导致内存充满微小的无用空洞。

最差适应算法 (Worst Fit)

最差适应算法是指定位最大的可用空闲部分，以便剩余的部分足够大，可以继续使用。它是最佳适应算法的反面。

优点

减少产生小空隙的速率。

缺点

如果稍后出现需要更大内存的进程，则无法容纳它，因为最大的空洞已经被分割并占用。

伙伴系统 (Buddy System)

在伙伴系统中，空闲块的大小是 2 的整数次幂。例如 2、4、8、16 等，直到内存大小。当请求大小为 2k 的空闲块时，将分配来自大小为 2k 的空闲块列表中的一个空闲块。如果大小为 2k 的空闲块不可用，则将下一个更大大小的块 2k+1 分成两半（称为伙伴），以满足请求。

示例

假设总内存大小为 512KB，进程 P1 需要交换 70KB。由于空洞列表只包含 2 的幂次方大小，128KB 就足够大了。最初没有 128KB 的块，也没有 256KB 的块。因此，512KB 块被分成两个 256KB 的伙伴块，其中一个被进一步分成两个 128KB 块，其中一个分配给进程。接下来，P2 需要 35KB。将 35KB 向上舍入到 2 的幂次方，需要 64KB 块。

因此，当 128KB 块被分成两个 64KB 的伙伴块时。同样，进程 P3（130KB）将被调整到整个 256KB 块中。以这种方式满足请求后，当这样的块空闲时，如果它的伙伴块也空闲，则这两个块/伙伴可以重新组合成原来两倍大小的块。

优点

伙伴系统速度更快。当大小为 2k 的块被释放时，会搜索大小为 2k 的空洞以检查是否可以合并，而在其他算法中，必须搜索所有空洞列表。

缺点

它在内存利用率方面往往效率低下。由于所有请求都必须向上舍入到 2 的幂次方，因此 35KB 的进程被分配到 64KB，从而浪费了额外的 29KB，导致内部碎片。伙伴之间可能存在空洞，导致外部碎片。

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

循环首次适应算法是首次适应算法的改进版本。它像首次适应算法一样开始查找空闲分区。下次调用时，它从上次停止的地方开始搜索，而不是从开头开始。