OS 基础教程

进程管理

同步

死锁

内存管理

文件管理

original icon
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.knowledgedict.com/tutorial/os-partitioning-algorithms.html

分区算法


操作系统实现了各种算法,以便找出链表中的空洞并将它们分配给进程。

关于每种算法的解释如下。

1. 第一拟合算法

第一拟合算法(First Fit)算法扫描链表,每当它找到第一个足够大的孔来存储进程时,它就会停止扫描并将进程加载到该进程中。 该过程产生两个分区。 其中,一个分区将是一个空洞,而另一个分区将存储该进程。

First Fit算法按照起始索引的递增顺序维护链表。这是所有算法中最简单的实现方式,与其他算法相比,它产生更大的空洞。

2. 下一个拟合算法

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

下一个适合不扫描整个列表,它开始扫描下一个节点的列表。 下一个拟合背后的想法是列表已被扫描一次,因此在列表的其余部分查找空洞的可能性更大。

该算法的实验表明,下一个拟合并不比第一个拟合更好。 所以这些日子在大多数情况下都没有被使用。

3. 最佳拟合算法

最佳拟合算法试图找出列表中可能的最小空洞,以适应流程的大小要求。

使用Best Fit有一些缺点。

  1. 由于每次扫描整个列表并试图找出能够满足过程要求的最小空洞,因此速度较慢。

  2. 由于整个尺寸与工艺尺寸之间的差异非常小,所产生的孔将会小到不能用于加载任何工艺,因此它仍然没有用处。尽管算法的名称最适合,但它并不是最好的算法。

4. 最差拟合算法

最差匹配算法每次都扫描整个列表,并试图找出列表中最大的空洞,以满足过程的要求。

尽管这个算法产生了更大的漏洞来加载其他进程,但这并不是更好的方法,因为它比较慢,因为它每次都搜索整个列表。

5. 快速拟合算法

快速拟合算法建议保留常用大小的不同列表。 虽然,实际上这并不是可以暗示的,因为程序需要花费很多时间来创建不同的列表,然后花费空间来加载进程。

第一个拟合算法是所有算法中最好的算法,这是因为

  • 与其他算法相比,花费的时间更少。
  • 它会产生更大的空洞,以后可以用来加载其他进程。
  • 这是最容易实现的。