首次適應演算法最終映像圖

A. 首次適應演算法是什麼

First-fit (FF)是一種用於裝箱的在線演算法。

它的輸入是一個不同大小的項目列表。它的輸出是一個包裝——將物品分成固定容量的箱子，這樣每個箱子中物品的大小之和最多就是容量。理想情況下，我們希望使用盡可能少的 bin，但是最小化 bin 的數量是一個 NP-hard 問題。首次擬合演算法使用以下啟發式：

它保留一個打開的垃圾箱列表，最初是空的。

當一件物品到達時，它會找到該物品可以放入 的第一個箱子（如果有的話）。

如果找到這樣的箱子，則將新物品放入其中。

否則，將打開一個新的箱子並將即將到來的物品放入其中。

優缺點

1、優點

處理速度快。由於處理器將最近的可用內存分區分配給作業，因此執行速度非常快。

2、缺點

浪費大量內存。處理器忽略分配給作業的分區大小與作業大小相比是否非常大。它只是分配內存。結果，浪費了大量內存，許多作業可能無法在內存中獲得空間，並且必須等待另一個作業完成。

B. 計算機操作系統：動態分區分配方式的模擬

實驗5：動態分區分配方式的模擬

1．實驗目的

理解動態分區分配方式中的數據結構和分配演算法，深化對動態分區存儲管理的理解。

2．實驗內容

(1) 利用C語言實現首次適應演算法（按地址從小到大排序）和最佳適應演算法（按空閑塊大小從小到大排序）的動態分區分配和回收過程。使用空閑分區鏈管理空閑區域，優先使用內存低端空間。

(2) 假設初始內存為640 KB（模擬一個640KB的內存空間，使用malloc()和free()函數操作）。作業請求序列如下：

作業1：申請130 KB

作業2：申請60 KB

作業3：申請100 KB

作業2：釋放60 KB

作業4：申請200 KB

作業3：釋放100 KB

作業1：釋放130 KB

作業5：申請140 KB

作業6：申請60 KB

作業7：申請50 KB

作業6：釋放60 KB

分別採用首次適應演算法和最佳適應演算法進行內存分配與回收，顯示每次操作後的空閑分區鏈情況。

首次適應演算法

查找空閑分區鏈中滿足請求的分區，分配內存後保留剩餘部分；若無法滿足，則分配失敗。

最佳適應演算法

排序空閑分區鏈，優先使用與請求大小最接近的分區，分配內存後保留剩餘部分；若無法滿足，則分配失敗。

實驗結果

首次適應演算法和最佳適應演算法操作後的空閑分區鏈示意圖。

疑難小結

通過實驗熟悉動態分區分配過程，了解首次適應和最佳適應演算法特點。

首次適應演算法優點：保留高地址大空閑分區，利於大作業分配；缺點：產生低地址碎片，查找開銷增加。

最佳適應演算法優點：首次分配接近請求大小，效率高；缺點：可能產生大量難以利用的外部碎片。

主要實現方法

實現動態分區分配時，使用C語言編寫分配和回收函數，管理內存分配與釋放；通過空閑分區鏈組織和優化內存使用。

C. 首次適應演算法是什麼

分區分配演算法(Partitioning Placement Algorithm)
最佳適應演算法（Best Fit）：
它從全部空閑區中找出能滿足作業要求的、且大小最小的空閑分區，這種方法能使碎片盡量小。為適應此演算法，空閑分區表（空閑區鏈）中的空閑分區要按大小從小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區分配。該演算法保留大的空閑區，但造成許多小的空閑區。
首次適應演算法（First Fit）：
從空閑分區表的第一個表目起查找該表，把最先能夠滿足要求的空閑區分配給作業，這種方法目的在於減少查找時間。為適應這種演算法，空閑分區表（空閑區鏈）中的空閑分區要按地址由低到高進行排序。該演算法優先使用低址部分空閑區，在低址空間造成許多小的空閑區，在高地址空間保留大的空閑區。
循環首次適應演算法(Next Fit)：
該演算法是首次適應演算法的變種。在分配內存空間時，不再每次從表頭（鏈首）開始查找，而是從上次找到空閑區的下一個空閑開始查找，直到找到第一個能滿足要求的的空閑區為止，並從中劃出一塊與請求大小相等的內存空間分配給作業。該演算法能使內存中的空閑區分布得較均勻。