操作系統實現了各種演算法,以便找出鏈表中的空洞並將它們分配給進程。
關於每種演算法的解釋如下。
1. 第一擬合算法
第一擬合算法(First Fit)演算法掃描鏈表,每當它找到第一個足夠大的孔來存儲進程時,它就會停止掃描並將進程加載到該進程中。 該過程產生兩個分區。 其中,一個分區將是一個空洞,而另一個分區將存儲該進程。
First Fit演算法按照起始索引的遞增順序維護鏈表。這是所有演算法中最簡單的實現方式,與其他演算法相比,它產生更大的空洞。
2. 下一個擬合算法
Next Fit演算法與First Fit演算法類似,不同之處在於,Next fit從先前分配空洞的節點掃描鏈表。
下一個適合不掃描整個列表,它開始掃描下一個節點的列表。 下一個擬合背後的想法是列表已被掃描一次,因此在列表的其餘部分查找空洞的可能性更大。
該演算法的實驗表明,下一個擬合併不比第一個擬合更好。 所以這些日子在大多數情況下都沒有被使用。
3. 最佳擬合算法
最佳擬合算法試圖找出列表中可能的最小空洞,以適應流程的大小要求。
使用Best Fit有一些缺點。
由於每次掃描整個列表並試圖找出能夠滿足過程要求的最小空洞,因此速度較慢。
由於整個尺寸與工藝尺寸之間的差異非常小,所產生的孔將會小到不能用於加載任何工藝,因此它仍然沒有用處。儘管演算法的名稱最適合,但它並不是最好的演算法。
4. 最差擬合算法
最差匹配演算法每次都掃描整個列表,並試圖找出列表中最大的空洞,以滿足過程的要求。
儘管這個演算法產生了更大的漏洞來加載其他進程,但這並不是更好的方法,因為它比較慢,因為它每次都搜索整個列表。
5. 快速擬合算法
快速擬合算法建議保留常用大小的不同列表。 雖然,實際上這並不是可以暗示的,因為程式需要花費很多時間來創建不同的列表,然後花費空間來加載進程。
第一個擬合算法是所有演算法中最好的演算法,這是因為
- 與其他演算法相比,花費的時間更少。
- 它會產生更大的空洞,以後可以用來加載其他進程。
- 這是最容易實現的。