分區演算法

操作系統實現了各種演算法,以便找出鏈表中的空洞並將它們分配給進程。

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

1. 第一擬合算法

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

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

2. 下一個擬合算法

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

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

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

3. 最佳擬合算法

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

使用Best Fit有一些缺點。

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

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

4. 最差擬合算法

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

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

5. 快速擬合算法

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

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

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

上一篇: 鏈表動態分區 下一篇: 分頁技術