首次适应算法最终映像图

A. 首次适应算法是什么

First-fit (FF)是一种用于装箱的在线算法。

它的输入是一个不同大小的项目列表。它的输出是一个包装——将物品分成固定容量的箱子，这样每个箱子中物品的大小之和最多就是容量。理想情况下，我们希望使用尽可能少的 bin，但是最小化 bin 的数量是一个 NP-hard 问题。首次拟合算法使用以下启发式：

它保留一个打开的垃圾箱列表，最初是空的。

当一件物品到达时，它会找到该物品可以放入 的第一个箱子（如果有的话）。

如果找到这样的箱子，则将新物品放入其中。

否则，将打开一个新的箱子并将即将到来的物品放入其中。

优缺点

1、优点

处理速度快。由于处理器将最近的可用内存分区分配给作业，因此执行速度非常快。

2、缺点

浪费大量内存。处理器忽略分配给作业的分区大小与作业大小相比是否非常大。它只是分配内存。结果，浪费了大量内存，许多作业可能无法在内存中获得空间，并且必须等待另一个作业完成。

B. 计算机操作系统：动态分区分配方式的模拟

实验5：动态分区分配方式的模拟

1．实验目的

理解动态分区分配方式中的数据结构和分配算法，深化对动态分区存储管理的理解。

2．实验内容

(1) 利用C语言实现首次适应算法（按地址从小到大排序）和最佳适应算法（按空闲块大小从小到大排序）的动态分区分配和回收过程。使用空闲分区链管理空闲区域，优先使用内存低端空间。

(2) 假设初始内存为640 KB（模拟一个640KB的内存空间，使用malloc()和free()函数操作）。作业请求序列如下：

作业1：申请130 KB

作业2：申请60 KB

作业3：申请100 KB

作业2：释放60 KB

作业4：申请200 KB

作业3：释放100 KB

作业1：释放130 KB

作业5：申请140 KB

作业6：申请60 KB

作业7：申请50 KB

作业6：释放60 KB

分别采用首次适应算法和最佳适应算法进行内存分配与回收，显示每次操作后的空闲分区链情况。

首次适应算法

查找空闲分区链中满足请求的分区，分配内存后保留剩余部分；若无法满足，则分配失败。

最佳适应算法

排序空闲分区链，优先使用与请求大小最接近的分区，分配内存后保留剩余部分；若无法满足，则分配失败。

实验结果

首次适应算法和最佳适应算法操作后的空闲分区链示意图。

疑难小结

通过实验熟悉动态分区分配过程，了解首次适应和最佳适应算法特点。

首次适应算法优点：保留高地址大空闲分区，利于大作业分配；缺点：产生低地址碎片，查找开销增加。

最佳适应算法优点：首次分配接近请求大小，效率高；缺点：可能产生大量难以利用的外部碎片。

主要实现方法

实现动态分区分配时，使用C语言编写分配和回收函数，管理内存分配与释放；通过空闲分区链组织和优化内存使用。

C. 首次适应算法是什么

分区分配算法(Partitioning Placement Algorithm)
最佳适应算法（Best Fit）：
它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。
首次适应算法（First Fit）：
从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。
循环首次适应算法(Next Fit)：
该算法是首次适应算法的变种。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到空闲区的下一个空闲开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得较均匀。