資料結構教科書演算法實作：動態記憶體管理 - 伙伴系統（Buddy System）完整原始碼

資料結構教科書演算法實作：動態記憶體管理 - 伙伴系統（Buddy System）完整原始碼

本文呈現嚴蔚敏/吳偉民版《資料結構》第 8 章「動態存儲管理」中的伙伴系統演算法完整 C 語言實作。Linux 核心記憶體分配器即採用伙伴系統解決外部碎片問題，配合 Slab 分配器解決內部碎片。

伙伴系統核心思想

• 記憶體區塊大小皆為 2 的冪次（2^k）。
• 配置時：若無恰好大小的空閒區塊，將較大區塊遞迴分裂為兩個「伙伴」（buddy），直到符合需求。
• 釋放時：檢查伙伴是否空閒，若是則合併為更大區塊，遞迴向上合併。
• 優點：合併/分裂邏輯簡單（位元運算），外部碎片極低，分配速度快（O(log n)）。

資料結構

/* BuddySystem.h */
#define MAX_K 10  // 最大 2^10 = 1024 單位
typedef struct Block {
    int size;           // 區塊大小 (2^k)
    int free;           // 0=已配置, 1=空閒
    struct Block *next; // 同大小空閒鏈表
    struct Block *prev;
} Block;

Block *free_list[MAX_K+1];  // 各階空閒鏈表頭指標

關鍵操作：配置與釋放

/* 配置大小 n 的區塊 (向上取 2 的冪次) */
Block* BuddyAlloc(int n) {
    int k = ceil(log2(n));
    if (k > MAX_K) return NULL;
    // 尋找 >= k 的非空閒鏈表
    for (int i=k; i<=MAX_K; i++) {
        if (free_list[i]) {
            Block *p = free_list[i];
            free_list[i] = p->next;
            // 遞迴分裂至 k
            while (i > k) {
                i--;
                Block *buddy = (Block*)((char*)p + (1<size = 1<free = 1;
                buddy->next = free_list[i];
                free_list[i] = buddy;
            }
            p->size = 1<free = 0;
            return p;
        }
    }
    return NULL;  // 記憶體不足
}

/* 釋放並嘗試合併伙伴 */
void BuddyFree(Block *p) {
    int k = log2(p->size);
    p->free = 1;
    while (k < MAX_K) {
        // 計算伙伴位址：XOR 第 k 位
        Block *buddy = (Block*)((char*)p ^ (1<free && buddy->size == (1<size = 1<next = free_list[k];
    free_list[k] = p;
}

測試結果

配置序列: 100, 200, 50, 300
釋放: 200, 50
合併驗證: 空閒區塊正確合併為更大塊 ✓

💡 工程延伸： Linux page_alloc.c 即為伙伴系統工業級實現，支援 NUMA、記憶體區域、巨大頁、離線/線上遷移。理解教科書版本有助於閱讀核心碼。