C 語言動態記憶體管理核心機制：空閒鏈表、分配演算法與邊界標記法

核心概念

系統演進狀態

1. 啟動初期：整塊記憶體為一大空閒塊
2. 分配後：低址佔用塊 + 高址空閒塊
3. 釋放後：空閒/佔用塊交錯 → 外部碎片 產生

兩種基本管理策略

策略一：緊湊法

• 持續從高址空閒塊分配
• 空間不足時觸發 記憶體緊湊：移動所有佔用塊合併空閒空間
• 缺點：移動開銷大、需更新所有指標、不支援指標運算的語言難以實作

策略二：空閒鏈表

維護所有空閒塊資訊的鏈結串列，節點對應一空閒塊。

三種鏈表結構

變長請求三大分配演算法

// 共同前提：尋找 size ≥ N 的空閒塊，分割配置 N，剩餘 (M-N) 重新插入鏈表

回收與合併挑戰

單純歸還節點會導致物理相鄰空閒塊分離，需合併相鄰塊獲取更大空間。但空閒鏈表非物理序 → 掃描合併代價高。

邊界標記法

節點結構

typedef struct Block {
    struct Block *llink, *rlink; // 雙向循環鏈表指標
    size_t size;                 // 區塊大小
    struct Block *uplink;        // 指向區塊起始位址
    int tag;                     // 0=空閒, 1=佔用 (頭尾各一)
} Block;

關鍵設計

• 雙向循環鏈表：支援 O(1) 插入/刪除
• uplink 指標：解決區塊大小不固定、無法用位移計算鄰塊位址
• 雙重 tag：頭尾各一，快速判斷物理鄰塊狀態

回收合併邏輯

void free_block(Block *p) {
    // 左鄰塊：位址 = p - sizeof(tag)
    Block *left_tag = (Block*)((char*)p - sizeof(int));
    if (left_tag->tag == 0) { // 左鄰為空閒
        Block *left_block = left_tag->uplink;
        // 合併到左鄰塊
        left_block->size += p->size + 2*sizeof(int);
        left_block->uplink = left_block; // 更新
        // 從鏈表移除 p
        p->llink->rlink = p->rlink;
        p->rlink->llink = p->llink;
        p = left_block; // 更新當前塊指標
    }

    // 右鄰塊：位址 = p + size(p) - sizeof(tag) + sizeof(tag) = p + size(p)
    Block *right_tag = (Block*)((char*)p + p->size - sizeof(int));
    if (right_tag->tag == 0) { // 右鄰為空閒
        Block *right_block = right_tag->uplink;
        // 合併右鄰塊到 p
        p->size += right_block->size + 2*sizeof(int);
        // 修正鏈表
        right_block->llink->rlink = right_block->rlink;
        right_block->rlink->llink = right_block->llink;
        // 更新右塊 uplink
        right_block->uplink = p;
    }

    // 將合併後的 p 重新插入空閒鏈表
    // ...
}

效能優化：下次搜尋指標

維護全域指標 Block *rover 指向上次分配節點的後繼，避免每次從頭掃描，緩解 First Fit 表頭碎片化問題。

總結

• 動態記憶體管理核心在於 空間利用率 與 分配速度 的平衡
• 邊界標記法透過 物理位址標記 解決鏈表非物理序的合併難題
• 現代配置器 會結合多種策略：小物件用固定大小池、大物件用 Best Fit + 邊界標記、巨大物件直接 mmap

參考資源

原文連結：CSDN 部落格