分割區演算法


作業系統實現了各種演算法,以便找出連結串列中的空洞並將它們分配給進程。

關於每種演算法的解釋如下。

1. 第一擬合演算法

第一擬合演算法(First Fit)演算法掃描連結串列,每當它找到第一個足夠大的孔來儲存進程時,它就會停止掃描並將進程載入到該進程中。 該過程產生兩個分割區。 其中,一個分割區將是一個空洞,而另一個分割區將儲存該進程。

First Fit演算法按照起始索引的遞增順序維護連結串列。這是所有演算法中最簡單的實現方式,與其他演算法相比,它產生更大的空洞。

2. 下一個擬合演算法

Next Fit演算法與First Fit演算法類似,不同之處在於,Next fit從先前分配空洞的節點掃描連結串列。

下一個適合不掃描整個列表,它開始掃描下一個節點的列表。 下一個擬合背後的想法是列表已被掃描一次,因此在列表的其餘部分查詢空洞的可能性更大。

該演算法的實驗表明,下一個擬合併不比第一個擬合更好。 所以這些日子在大多數情況下都沒有被使用。

3. 最佳擬合演算法

最佳擬合演算法試圖找出列表中可能的最小空洞,以適應流程的大小要求。

使用Best Fit有一些缺點。

  1. 由於每次掃描整個列表並試圖找出能夠滿足過程要求的最小空洞,因此速度較慢。

  2. 由於整個尺寸與工藝尺寸之間的差異非常小,所產生的孔將會小到不能用於載入任何工藝,因此它仍然沒有用處。儘管演算法的名稱最適合,但它並不是最好的演算法。

4. 最差擬合演算法

最差匹配演算法每次都掃描整個列表,並試圖找出列表中最大的空洞,以滿足過程的要求。

儘管這個演算法產生了更大的漏洞來載入其他進程,但這並不是更好的方法,因為它比較慢,因為它每次都搜尋整個列表。

5. 快速擬合演算法

快速擬合演算法建議保留常用大小的不同列表。 雖然,實際上這並不是可以暗示的,因為程式需要花費很多時間來建立不同的列表,然後花費空間來載入進程。

第一個擬合演算法是所有演算法中最好的演算法,這是因為

  • 與其他演算法相比,花費的時間更少。
  • 它會產生更大的空洞,以後可以用來載入其他進程。
  • 這是最容易實現的。