操作系统 划分算法

操作系统通过实施不同的算法来寻找链表中的空洞并将它们分配给进程。

以下是每个算法的解释。

1. First Fit算法

First Fit算法扫描链表，每当找到足够大的空洞以容纳一个进程时，它停止扫描并将进程加载到该空洞中。该过程产生两个分区。其中一个分区是一个空洞，而另一个分区存储进程。

First Fit算法根据起始索引的递增顺序维护链表。与其他算法相比，这是最简单实施的算法，并产生更大的空洞。

2. Next Fit算法

Next Fit算法与First Fit算法类似，不同之处在于Next Fit从先前分配空洞的节点开始扫描链表。

Next Fit不扫描整个列表，它从下一个节点开始扫描列表。Next Fit的背后思想是列表已经被扫描过一次，因此在列表剩余部分中找到空洞的概率更大。

对该算法进行的实验显示，Next Fit并不比First Fit更好。因此，在大多数情况下现在不再使用它。

3. Best Fit算法

Best Fit算法试图找出列表中能够容纳进程大小要求的最小空洞。

使用Best Fit有一些缺点。

1. 1. 它较慢，因为它每次扫描整个列表并试图找出能满足进程需求的最小空洞。
2. 由于空洞大小与进程大小之间的差距非常小，产生的空洞将很小，无法用来加载任何进程，因此保持无用。尽管算法的名称是Best Fit，但它并不是所有算法中最好的算法。

4. Worst Fit算法

Worst Fit算法每次扫描整个列表，试图找到列表中能够满足进程需求的最大空洞。

尽管该算法产生较大的空洞以加载其他进程，但由于每次重复搜索整个列表，因此它较慢，这不是更好的方法。

5. Quick Fit算法

Quick Fit算法建议维护不同大小的频繁使用列表。尽管如此，这并不实际可行，因为该过程需要花费很多时间来创建不同的列表，然后扩展空洞以加载进程。

在所有算法中，第一适应算法是 最好的算法 ，因为

1. 它比其他算法时间更短。
2. 它产生更大的空洞，以后可以用来加载其他进程。
3. 它实现最简单。