您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

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

編輯：關於C語言

一、動態記憶體管理核心問題

系統如何滿足任意大小分配請求、如何回收重用、如何減少碎片。核心資料結構：空閒塊 (Free Block) 與 佔用塊 (Allocated Block)。

二、空閒鏈表三種組織形式

1. 等大塊鏈表 (Fixed-size Blocks)

所有請求大小相同 (如物件池)。
初始化：將堆劃分為等大塊，串成鏈表。
分配：取頭節點 O(1)。
回收：插回頭部 O(1)。
零外部碎片，但有內部碎片。

2. 多規格鏈表 (Multiple Size Classes)

請求大小屬於有限規格集合 (如 16, 32, 64, 128... bytes)。
每個規格維護一條鏈表。
分配：找最小滿足規格的鏈表取頭；若該鏈表空，向上規格分割。
回收：歸還對應規格鏈表，嘗試合併相鄰同規格塊 (Buddy System 思想)。

3. 通用大小鏈表 (General Variable-size)

請求大小任意，塊大小動態分割/合併。
單一鏈表串聯所有空閒塊，節點含 size、next。
三大分配演算法：

三、三大分配演算法

演算法	策略	資料結構	優點	缺點
首次適配	掃描鏈表，第一個滿足 size 的塊	無序鏈表	實作簡單、分配快	產生大量微小碎片集中在鏈表頭，後續掃描慢
最佳適配	掃描全表，找最接近 size 的塊	按 size 升序鏈表	殘留塊最大、減少碎片	需全表掃描/有序插入慢、留下大量難用的微小塊
最差適配	使用最大的塊	按 size 降序鏈表	保留大塊應對大請求	同最佳適配，碎片化嚴重

四、邊界標記法：高效合併相鄰空閒塊

核心思想：在每個塊 (空閒/佔用) 的頭部與尾部各存一個標記，記錄塊大小與狀態。使得給定任一塊地址，可 O(1) 找到物理相鄰的前後塊並判斷是否空閒。

塊結構

// 空閒塊 (雙向循環鏈表節點)
struct FreeBlock {
    size_t size;           // 塊總大小 (含頭尾標記)
    struct FreeBlock *prev, *next; // 鏈表指標
    // 頭部標記 (隱含在 size/prev 前)
};

// 佔用塊
struct UsedBlock {
    size_t size;           // 塊大小
    // 無 prev/next
    // 頭部標記
    // 資料區...
    // 尾部標記 (size | 1)  // 低位標記狀態
};

// 統一標記結構 (位於塊頭/尾)
struct Tag {
    size_t size;  // 低位 bit0: 0=空閒, 1=佔用
    // 空閒塊額外有 prev/next 指標緊接在後
};

合併邏輯 (釋放時)

void free_block(void *ptr) {
    Tag *head = (Tag*)ptr - 1;           // 塊頭標記
    size_t size = head->size & ~1;       // 清除狀態位
    Tag *tail = (Tag*)((char*)ptr + size - sizeof(Tag)); // 塊尾標記
    
    // 1. 檢查前塊 (物理相鄰)
    Tag *prev_tail = (Tag*)((char*)head - sizeof(Tag));
    if ((prev_tail->size & 1) == 0) {    // 前塊空閒
        // 從空閒鏈表移除前塊
        FreeBlock *prev = (FreeBlock*)((char*)prev_tail - prev_tail->size + sizeof(Tag) + 1);
        unlink_free(prev);
        // 合併：擴大前塊 size
        prev->size += size;
        head = (Tag*)prev;               // 更新 head 指向合併後塊頭
        size = prev->size;
        tail = (Tag*)((char*)head + size - sizeof(Tag));
    }
    
    // 2. 檢查後塊
    Tag *next_head = (Tag*)((char*)tail + sizeof(Tag));
    if ((next_head->size & 1) == 0) {    // 後塊空閒
        FreeBlock *next = (FreeBlock*)(next_head + 1);
        unlink_free(next);
        size += next->size;
        // head 不動，只更新 size
    }
    
    // 3. 更新頭尾標記狀態為空閒 (bit0=0)
    head->size = size;
    tail = (Tag*)((char*)head + size - sizeof(Tag));
    tail->size = size;
    
    // 4. 插入空閒鏈表 (可用地址序或大小序)
    insert_free((FreeBlock*)(head + 1));
}

五、現代分配器演進

dlmalloc (Doug Lea)：分離空閒鏈表 (size classes) + 邊界標記 + wilderness chunk (顶部野塊) + mmap 大塊直接映射。Glibc malloc 基礎。
ptmalloc：dlmalloc 多執行緒版，每執行緒 arena 減少鎖爭用。
jemalloc：Facebook，多 arena、per-CPU cache、分代、巨大頁支援、統計分析豐富。
tcmalloc：Google，Thread-local cache、Central free list、Page heap、極快小物件分配。
mimalloc：Microsoft，頁面級管理、免鎖、安全、效能優異。