作業系統記憶體分配問答集 #2

---

---

問題：解釋以下分配演算法。

1. 首次適應演算法 (First Fit)

2. 最佳適應演算法 (Best Fit)

3. 最差適應演算法 (Worst Fit)

4. 夥伴系統 (Buddy System)

5. 迴圈首次適應演算法 (Next Fit)

答案

首次適應演算法 (First Fit)

首次適應演算法是分配第一個足夠大的空閒分割槽或空洞來容納程序。找到第一個合適的空閒分割槽後就結束。

優點

速度最快的演算法，因為它搜尋的次數最少。

缺點

分配後剩餘的未用記憶體區域如果太小就會浪費。因此，無法滿足對更大記憶體的需求。

最佳適應演算法 (Best Fit)

最佳適應演算法是指分配滿足請求程序要求的最小空閒分割槽。此演算法首先搜尋整個空閒分割槽列表，並考慮最小的足夠大的空洞。然後嘗試找到一個接近實際所需程序大小的空洞。

優點

記憶體利用率比首次適應演算法好得多，因為它首先搜尋最小的可用空閒分割槽。

缺點

它速度較慢，甚至可能導致記憶體充滿微小的無用空洞。

最差適應演算法 (Worst Fit)

最差適應演算法是指定位最大的可用空閒部分，以便剩餘的部分足夠大，可以繼續使用。它是最佳適應演算法的反面。

優點

減少產生小空隙的速率。

缺點

如果稍後出現需要更大記憶體的程序，則無法容納它，因為最大的空洞已經被分割並佔用。

夥伴系統 (Buddy System)

在夥伴系統中，空閒塊的大小是 2 的整數次冪。例如 2、4、8、16 等，直到記憶體大小。當請求大小為 2k 的空閒塊時，將分配來自大小為 2k 的空閒塊列表中的一個空閒塊。如果大小為 2k 的空閒塊不可用，則將下一個更大大小的塊 2k+1 分成兩半（稱為夥伴），以滿足請求。

示例

假設總記憶體大小為 512KB，程序 P1 需要交換 70KB。由於空洞列表只包含 2 的冪次方大小，128KB 就足夠大了。最初沒有 128KB 的塊，也沒有 256KB 的塊。因此，512KB 塊被分成兩個 256KB 的夥伴塊，其中一個被進一步分成兩個 128KB 塊，其中一個分配給程序。接下來，P2 需要 35KB。將 35KB 向上舍入到 2 的冪次方，需要 64KB 塊。

因此，當 128KB 塊被分成兩個 64KB 的夥伴塊時。同樣，程序 P3（130KB）將被調整到整個 256KB 塊中。以這種方式滿足請求後，當這樣的塊空閒時，如果它的夥伴塊也空閒，則這兩個塊/夥伴可以重新組合成原來兩倍大小的塊。

優點

夥伴系統速度更快。當大小為 2k 的塊被釋放時，會搜尋大小為 2k 的空洞以檢查是否可以合併，而在其他演算法中，必須搜尋所有空洞列表。

缺點

它在記憶體利用率方面往往效率低下。由於所有請求都必須向上舍入到 2 的冪次方，因此 35KB 的程序被分配到 64KB，從而浪費了額外的 29KB，導致內部碎片。夥伴之間可能存在空洞，導致外部碎片。

迴圈首次適應演算法 (Next Fit)

迴圈首次適應演算法是首次適應演算法的改進版本。它像首次適應演算法一樣開始查詢空閒分割槽。下次呼叫時，它從上次停止的地方開始搜尋，而不是從開頭開始。