[Linux] 連續記憶體分配策略(Contiguous Memory Allocation)

作業系統的記憶體管理，可以分成採用連續記憶體分配(Contiguous Memory Allocation)和採用分頁(Paging)技術。採用連續記憶體分配，方法簡單且速度快速，但缺點在於容易產生剩餘的記憶體片段(Fragmentation)，記憶體的使用效率並不好，為了解決此現象，因此採用記憶體分頁的方式，來提升記憶體的使用率。

而在連續記憶體分配，有三個最常見的演算法，最先適用(first-fit)、最佳適用(best-fit)和最不適用(worst-fit)。底下舉特考的例子為例：

（102調查局特考_計算機概論）
五、記憶體的配置策略（Storage Placement Strategies）是用以決定進來的程式或資料應置於記憶體的那一區域。其策略包含最不適用（worst-fit）、最佳適用（best-fit）和最先適用（first-fit）等。 

（一）請說明上述三種策略（最不適用、最佳適用和最先適用）在比較之下，各策略的優勢為何？（10分）
（二）若目前記憶體分區（memory partitions）狀況依序為 490 KB，190 KB，290 KB及550 KB，而記憶體空間需求依序為400 KB，220 KB，120 KB及450 KB。請分別描述在最不適用、最佳適用和最先適用三種不同策略下的記憶體配置情形。（10分）

參考答案:
（一）
最不適用：記憶體分配會優先使用最大的分區塊，這樣所剩餘下來的區塊會比較大，也比較有機會提供其他空間需求使用，缺點是記憶體空間使用率較差。
最佳適用：記憶體分配會使用與需求最接近的區塊，這樣使用分配後，所剩餘下來的各可分配記憶體區塊會最小，在記憶體的空間使用率較佳，缺點是所剩餘下來的區塊會比較零碎，而不足讓其他記憶體需求使用。
最先適用：記憶體分配足夠大就使用，優點是簡單、分配速度快速，記憶體使用率也不算太差。

（二）
最不適用
1. 400KB -> 550KB, 剩下 490KB, 190KB, 290KB, 150KB
2. 220KB -> 490KB, 剩下 270KB, 190KB, 290KB, 150KB
3. 120KB -> 290KB, 剩下 270KB, 190KB, 170KB, 150KB
4. 450KB -> must wait

最佳適用
1. 400KB -> 490KB, 剩下 90KB, 190KB, 290KB, 550KB
2. 220KB -> 290KB, 剩下 90KB, 190KB, 70KB, 550KB
3. 120KB -> 190KB, 剩下 90KB, 70KB, 70KB, 550KB
4. 450KB -> 550KB, 剩下 90KB, 70KB, 70KB, 100KB

最先適用
1. 400KB -> 490KB, 剩下 90KB, 190KB, 290KB, 550KB
2. 220KB -> 290KB, 剩下 90KB, 190KB, 70KB, 550KB
3. 120KB -> 190KB, 剩下 90KB, 70KB, 70KB, 550KB
4. 450KB -> 550KB, 剩下 90KB, 70KB, 70KB, 100KB

以上答案僅供參考，有問題歡迎提出來一起來討論！