最差適配記憶體分配演算法模擬：完整實作指南

一、 實驗目的與背景

可變分區記憶體管理是作業系統核心課程中的經典主題。本模擬旨在實作 最差適配演算法，讓學習者理解動態分區分配、回收與碎片整理的完整流程。最差適配策略每次尋找 最大的空閒分區 進行分配，理論上能保留較大的連續空間供大型作業使用，但也容易產生難以利用的微小碎片。

二、 核心資料結構：空閒鏈結串列

相較於靜態的「已分配區表」與「空閒區表」，空閒鏈結串列 更適合動態環境：

• 每個節點記錄：起始位址、大小、下一節點指標。
• 串列依起始位址遞增排序，便於合併相鄰空閒區。
• 動態申請/釋放節點，無需預估最大分區數。

struct FreeBlock {
    size_t start_addr;
    size_t size;
    FreeBlock* next;
};

三、 關鍵演算法流程

1. 最差適配分配

1. 遍歷空閒鏈結串列，找出 size >= request_size 且 size 最大 的節點。
2. 若找到：
   　　a. 若節點大小恰好等於請求大小 → 直接從串列移除該節點。
   　　b. 若節點較大 → 將節點 start_addr 遞增、size 遞減，返回原起始位址。
3. 若未找到 → 觸發碎片整理（見下節）後重試，仍失敗則回報記憶體不足。

2. 記憶體回收與合併

回收時需依歸還區塊的起始位址，插入空閒鏈結串列並檢查前後相鄰區塊：

• 若與前一節點相鄰（prev.start + prev.size == curr.start） → 合併至前一節點。
• 若與下一節點相鄰（curr.start + curr.size == next.start） → 合併至下一節點。
• 若兩側皆相鄰 → 三合一。

3. 碎片整理

將所有已分配區塊向低位址緊湊移動，更新進程的基址暫存器，最後將所有空閒區合併為一個大塊。此操作需暫停所有進程，屬高成本操作，通常在分配失敗時才觸發。

四、 完整程式架構建議

class MemoryManager {
    FreeBlock* free_list_head;
    vector allocated_list; // 記錄已分配區塊：PID, start, size

public:
    bool allocate(int pid, size_t size, size_t& out_addr);
    bool deallocate(int pid);
    void compact();               // 碎片整理
    void print_status() const;    // 列印當前分區圖
};

五、 測試案例設計

六、 參考資源

完整原始碼與詳細註解可參考百度文庫資源：
最差適配記憶體分配模擬實作

結語

透過空閒鏈結串列實作最差適配演算法，能深入體會動態記憶體管理的精髓。建議學習者在掌握基本流程後，嘗試加入「最佳適配」、「首次適配」等策略進行比較分析，並嘗試模擬多執行緒併發分配場景，進一步理解鎖機制與效能權衡。