4. Buddy内存分配算法

说到显存碎片管理，我第一个想到的就是Buddy算法。这玩意儿在操作系统里已经用了半个多世纪了，但放到GPU显存管理上，依然是个经典方案。说白了，它解决的核心问题就是：如何快速找到一块大小合适的内存，同时尽量减少碎片。

我刚开始接触显存优化时，也想过用更复杂的算法，比如SLAB或者分区伙伴。但后来发现，对于深度学习这种频繁申请释放固定大小张量的场景，Buddy算法其实是最稳的选择。嗯，咱们今天就把它彻底讲透。

4.1 算法原理：二分法的艺术

Buddy算法的核心思想，我总结成一句话：把内存不断对半切，直到切出刚好够用的块。

你想想看，假设我们有一块大小为1GB的连续显存。Buddy算法会把它看作一棵二叉树：

• 根节点：1GB（2^30字节）
• 第一层子节点：两个512MB
• 第二层子节点：四个256MB
• ……一直切到最小粒度，比如4KB

这里有个关键概念叫“阶”（order）。阶就是2的幂次。比如order=0表示最小块（4KB），order=10表示4MB（2^10 * 4KB）。每个内存块的大小都是2^order * 最小块大小。

我在项目中遇到过一个问题：为什么一定要是2的幂？不能是3的幂或者别的？其实原因很简单——只有2的幂才能保证每次对半切后，两块内存的地址是“伙伴”关系。这个伙伴关系是合并的关键，后面会讲。

4.2 伙伴系统的工作流程

Buddy算法的工作流程，说白了就三个动作：申请、切分、合并。我画了一张流程图，你看一眼就明白了。

流程其实不复杂，我拆成三步讲：

4.2.1 申请内存

假设你要申请一块128KB的显存。最小块是4KB，那么128KB对应order=5（2^5 × 4KB = 128KB）。

1. 查空闲链表：先看order=5的空闲链表里有没有空闲块。有就直接拿走。
2. 没有就切分：如果order=5链表空了，就去order=6（256KB）链表里拿一块，切成两个128KB。一个给你用，另一个挂到order=5的空闲链表里。
3. 递归切分：如果order=6也空了，就继续往上找order=7、order=8……直到找到为止。

4.2.2 释放内存

释放时，Buddy算法会做一件很聪明的事——合并伙伴。

什么叫伙伴？就是由同一个大块切分出来的两个大小相等、地址相邻的块。它们有且只有一个特征：两个块的地址异或后，等于块的大小。

释放时，先看伙伴块是否空闲。如果空闲，就把两个块合并成一个256KB的块，然后继续检查上一层的伙伴……这个过程会一直向上递归，直到无法合并为止。

我曾经在调试一个模型时，发现显存占用越来越高，但实际使用的张量并不多。后来一查，就是因为释放时伙伴合并没做好，导致大量碎片。嗯，从那以后我对合并逻辑就特别敏感。

4.3 在显存管理中的应用

Buddy算法在GPU显存管理里，用得最多的就是CUDA的cudaMalloc和cudaFree底层实现。不过NVIDIA做了不少优化，不是纯的Buddy。

我总结了几点实际应用中的经验：

场景	Buddy的优势	需要注意的问题
张量内存分配	分配速度快（O(1)查找）	内部碎片：申请33KB会分配64KB
模型加载	大块连续内存容易分配	模型卸载后合并可能不及时
动态形状张量	频繁申请释放时碎片少	最小块大小设置很关键
多流并发	每个流可以独立维护Buddy	跨流的内存回收需要同步

4.3.1 实际代码示例

下面是一个简化版的Buddy分配器核心逻辑。我剔除了锁和并发处理，只展示核心思想：

#define MIN_BLOCK_SIZE 4096  // 4KB
#define MAX_ORDER 20         // 最大支持 4KB * 2^20 = 4GB

typedef struct buddy_block {
    struct buddy_block *next;
    int order;
    int free;  // 1表示空闲，0表示已分配
} buddy_block_t;

// 空闲链表数组
buddy_block_t *free_lists[MAX_ORDER + 1];

// 分配：从指定order开始查找
buddy_block_t *buddy_alloc(int order) {
    // 1. 先查当前order的空闲链表
    if (free_lists[order] != NULL) {
        buddy_block_t *block = free_lists[order];
        free_lists[order] = block->next;
        block->free = 0;
        return block;
    }
    
    // 2. 当前order没有，去更高order找
    for (int i = order + 1; i <= MAX_ORDER; i++) {
        if (free_lists[i] != NULL) {
            // 切分：把大块切成两块
            buddy_block_t *big_block = free_lists[i];
            free_lists[i] = big_block->next;
            
            // 递归切分到目标order
            while (i > order) {
                i--;
                // 计算伙伴地址：当前地址 + 2^i * MIN_BLOCK_SIZE
                buddy_block_t *buddy = (buddy_block_t *)((char *)big_block + 
                    (1 << i) * MIN_BLOCK_SIZE);
                buddy->order = i;
                buddy->free = 1;
                buddy->next = free_lists[i];
                free_lists[i] = buddy;
            }
            
            big_block->order = order;
            big_block->free = 0;
            return big_block;
        }
    }
    
    return NULL;  // 内存不足
}

// 释放：尝试合并伙伴
void buddy_free(buddy_block_t *block) {
    int order = block->order;
    
    // 尝试向上合并
    while (order < MAX_ORDER) {
        // 计算伙伴地址
        buddy_block_t *buddy = (buddy_block_t *)((char *)block ^ 
            ((1 << order) * MIN_BLOCK_SIZE));
        
        // 检查伙伴是否空闲且order相同
        if (buddy->free && buddy->order == order) {
            // 从空闲链表中移除伙伴
            // ... (链表删除操作)
            
            // 合并：取地址较小的块作为新块
            if (buddy < block) {
                block = buddy;
            }
            block->order = order + 1;
            order++;
        } else {
            break;  // 无法继续合并
        }
    }
    
    // 将合并后的块插入空闲链表
    block->free = 1;
    block->next = free_lists[order];
    free_lists[order] = block;
}

这段代码我刻意简化了，实际工程中还要考虑：

• 并发安全：多线程同时分配释放时，需要加锁或用原子操作
• 内存对齐：返回的地址要对齐到最小块大小
• 元数据存储：block结构体本身也要占内存，通常存在块头部

4.4 优缺点总结

说了这么多，我最后总结一下Buddy算法的优缺点。你心里有个数，就知道什么时候该用它了。

优点：

• 分配和释放都是O(1)或O(log N)时间复杂度，非常快
• 外部碎片很少（因为合并机制）
• 实现简单，代码量少，容易维护

缺点：

• 内部碎片：这是最大的问题。申请33KB会给你64KB，浪费了31KB。对于深度学习这种经常申请奇数大小张量的场景，内部碎片可能达到50%
• 内存膨胀：如果频繁申请释放不同大小的块，空闲链表里会堆积很多小块，导致大块分配失败

好了，Buddy算法就讲到这里。下一节我们会聊SLAB分配器，它专门解决内部碎片的问题。到时候你会看到，两种算法其实可以配合使用，效果更好。

---