每日算法 — 使用java实现内存池：伙伴系统与碎片合并

引言

内存管理是操作系统和大型应用的核心问题。频繁的malloc/free或new/delete不仅带来系统调用开销，还会产生大量内存碎片。内存池技术通过预先分配大块内存并自行管理，显著提升分配效率。本文用Java实现经典的伙伴系统（Buddy System）内存分配器。

伙伴系统原理

伙伴系统将内存划分为大小为2的幂次的块。当请求大小为k的内存时，系统分配不小于k的最小2^n块。若空闲块过大，则将其对半分割（产生两个”伙伴”），直到大小合适。释放时，检查相邻伙伴是否也空闲，若是则合并为更大的块。

核心规则

• 所有内存块大小为 2^n 字节（如 16, 32, 64, 128…）
• 第 i 级链表管理大小为 2^i 的空闲块
• 块的地址与其伙伴块地址只有第 i 位不同

Java实现

import java.util.*;

/**
 * 内存块：伙伴系统的基本单元
 */
class MemoryBlock {
    int start;          // 起始地址
    int size;           // 块大小（2的幂）
    boolean free;       // 是否空闲
    MemoryBlock buddy;  // 伙伴块引用

    MemoryBlock(int start, int size) {
        this.start = start;
        this.size = size;
        this.free = true;
    }

    int getEnd() { return start + size; }

    boolean isBuddyOf(MemoryBlock other) {
        // 伙伴块判定：起始地址异或 size 等于对方起始地址，且同级
        return this.size == other.size &&
               (this.start ^ other.start) == this.size;
    }
}

/**
 * 伙伴系统内存池
 */
class BuddyAllocator {
    private final int minBlockSize;      // 最小块大小（如 16 字节）
    private final int poolSize;          // 总内存池大小
    private final byte[] memory;         // 实际内存存储
    private final List<LinkedList<MemoryBlock>> freeLists; // 分级空闲链表
    private final Map<Integer, MemoryBlock> blockMap; // 地址到块映射

    public BuddyAllocator(int poolSize, int minBlockSize) {
        // 确保poolSize和minBlockSize都是2的幂
        this.poolSize = Integer.highestOneBit(poolSize);
        this.minBlockSize = Integer.highestOneBit(minBlockSize);
        this.memory = new byte[this.poolSize];

        int levels = log2(this.poolSize) - log2(this.minBlockSize) + 1;
        this.freeLists = new ArrayList<>(levels);
        for (int i = 0; i < levels; i++) {
            freeLists.add(new LinkedList<>());
        }
        this.blockMap = new HashMap<>();

        // 初始化：将整个内存池作为一个大空闲块
        MemoryBlock initial = new MemoryBlock(0, this.poolSize);
        blockMap.put(0, initial);
        freeLists.get(log2(this.poolSize) - log2(this.minBlockSize)).add(initial);
    }

    private int log2(int n) {
        return 31 - Integer.numberOfLeadingZeros(n);
    }

    /**
     * 分配指定大小的内存，返回起始地址（-1表示失败）
     */
    public int allocate(int requestSize) {
        if (requestSize <= 0 || requestSize > poolSize) return -1;

        // 计算需要分配的块大小（不小于请求的最小2的幂）
        int blockSize = minBlockSize;
        while (blockSize < requestSize) blockSize <<= 1;

        int level = log2(blockSize) - log2(minBlockSize);
        int foundLevel = -1;

        // 从当前级别向上查找可用的空闲块
        for (int i = level; i < freeLists.size(); i++) {
            if (!freeLists.get(i).isEmpty()) {
                foundLevel = i;
                break;
            }
        }

        if (foundLevel == -1) return -1; // 内存不足

        // 分裂大块直到目标级别
        MemoryBlock block = freeLists.get(foundLevel).removeFirst();
        block.free = false;

        while (foundLevel > level) {
            block = split(block);
            foundLevel--;
        }

        return block.start;
    }

    /**
     * 分裂块为两个伙伴
     */
    private MemoryBlock split(MemoryBlock block) {
        int newSize = block.size / 2;

        // 创建伙伴块
        MemoryBlock buddy = new MemoryBlock(block.start + newSize, newSize);
        blockMap.put(buddy.start, buddy);

        // 更新原块
        block.size = newSize;

        // 原块继续分配，伙伴块放入空闲链表
        int buddyLevel = log2(newSize) - log2(minBlockSize);
        freeLists.get(buddyLevel).add(buddy);

        // 建立双向伙伴引用
        block.buddy = buddy;
        buddy.buddy = block;

        return block;
    }

    /**
     * 释放指定地址的内存
     */
    public void free(int start) {
        MemoryBlock block = blockMap.get(start);
        if (block == null || block.free) return;

        block.free = true;
        int level = log2(block.size) - log2(minBlockSize);

        // 尝试与伙伴合并
        while (block.size < poolSize) {
            MemoryBlock buddy = findBuddy(block);
            if (buddy == null || !buddy.free) break;

            // 移除伙伴的空闲记录
            freeLists.get(level).remove(buddy);

            // 合并：取起始地址较小的一方
            if (buddy.start < block.start) {
                MemoryBlock temp = block;
                block = buddy;
                buddy = temp;
            }

            block.size *= 2;
            block.buddy = null;
            blockMap.remove(buddy.start);

            level++;
        }

        freeLists.get(level).add(block);
    }

    /**
     * 根据地址计算伙伴块
     */
    private MemoryBlock findBuddy(MemoryBlock block) {
        int buddyStart = block.start ^ block.size;
        return blockMap.get(buddyStart);
    }

    /**
     * 打印内存状态
     */
    public void printStatus() {
        System.out.println("=== 内存池状态 ===");
        for (int i = 0; i < freeLists.size(); i++) {
            int size = minBlockSize << i;
            System.out.printf("大小 %4d: %d 个空闲块%n", size, freeLists.get(i).size());
        }
        System.out.println("已分配块数: " + blockMap.values().stream().filter(b -> !b.free).count());
    }

    public int getPoolSize() { return poolSize; }
}

/**
 * 测试入口
 */
public class BuddySystemDemo {
    public static void main(String[] args) {
        // 创建 1024 字节内存池，最小块 16 字节
        BuddyAllocator allocator = new BuddyAllocator(1024, 16);
        allocator.printStatus();

        System.out.println("\n--- 分配 100 字节 ---");
        int p1 = allocator.allocate(100);  // 分配 128 字节块
        System.out.println("分配地址: " + p1);
        allocator.printStatus();

        System.out.println("\n--- 分配 50 字节 ---");
        int p2 = allocator.allocate(50);   // 分配 64 字节块
        System.out.println("分配地址: " + p2);
        allocator.printStatus();

        System.out.println("\n--- 释放 100 字节 ---");
        allocator.free(p1);
        allocator.printStatus();

        System.out.println("\n--- 分配 200 字节 ---");
        int p3 = allocator.allocate(200);  // 分配 256 字节块
        System.out.println("分配地址: " + p3);
        allocator.printStatus();

        System.out.println("\n--- 释放全部 ---");
        allocator.free(p2);
        allocator.free(p3);
        allocator.printStatus();
    }
}

复杂度分析

内部碎片与外部碎片

• 内部碎片：分配的块大于请求大小，浪费空间。伙伴系统中最大浪费接近50%（请求刚好比2^n大1）
• 外部碎片：伙伴系统通过强制合并相邻空闲块，理论上不存在不可合并的外部碎片

总结

伙伴系统以其简洁的分裂-合并机制和O(log n)的分配复杂度，成为Linux内核等系统的经典内存管理方案。理解其原理有助于深入掌握操作系统的内存分配策略。