📚 课程目录第4章分区内存管理（二）

4. 分区内存管理（二）：动态分区原理与三种分配算法

上一章我们聊了固定分区——说白了就是把内存切成几块固定大小的蛋糕。但实际跑起来你会发现，小进程浪费大分区，大进程又塞不进小分区。我早年做嵌入式系统时就吃过这个亏，一个 128KB 的区只放了 30KB 的进程，剩下 98KB 全浪费了。

所以后来大家更爱用动态分区。它不预先切死，进程来多大，就给它切多大一块。听起来很灵活对吧？但灵活背后藏着个麻烦——碎片。怎么切、怎么分配，就成了关键。

4.1 动态分区的基本原理

动态分区的核心思想就一句话：按需分配，用完回收。系统维护一张空闲分区表（或链表），记录当前所有空闲内存块的地址和大小。进程申请内存时，从表中找一块足够大的空闲区，切出一部分给进程，剩下的继续留在表里。

关键数据结构：

空闲分区表：每个条目记录起始地址、大小、状态（空闲/已分配）
空闲分区链表：按地址或大小链接所有空闲块
已分配分区表：记录已分配给进程的分区信息

我习惯用链表实现，因为插入和删除操作更灵活。但要注意，链表节点本身也要占内存，别小看这点开销——我曾经在一个 64KB 的微控制器上跑动态分区，链表节点用了 2KB，结果可用内存少了 3%。

4.2 三种经典分配算法

分配算法的核心问题：空闲块那么多，选哪个给进程？不同的选择策略，直接影响内存利用率和碎片情况。下面这三种是教科书必讲、实战也常用的。

算法	选择策略	优点	缺点
首次适应	从低地址开始，找到第一个够大的块	简单快速，低地址区域利用率高	低地址碎片多，查找可能遍历整个链表
最佳适应	选所有够大的块中，最小的那个	减少大块浪费，碎片最小化	产生大量小碎片，查找慢
最差适应	选所有够大的块中，最大的那个	剩余块仍然较大，减少小碎片	容易消耗大块，大进程可能无法分配

4.2.1 首次适应算法（First Fit）

这是最直观的做法。空闲链表按地址排序，从头开始找，碰到第一个大小≥申请量的块就切。我早期做的一个实时系统用的就是它——实现简单，性能稳定。

// 首次适应算法伪代码
void *first_fit(size_t size) {
    free_block_t *curr = free_list_head;
    while (curr != NULL) {
        if (curr->size >= size) {
            // 切分：分配 curr 的前 size 字节
            split_block(curr, size);
            return curr->start_addr;
        }
        curr = curr->next;
    }
    return NULL; // 没有足够大的空闲块
}

我的经验：首次适应在大多数场景下表现不错。但如果你频繁分配和释放小对象，低地址区域会积累大量小碎片。我建议配合内存紧缩（compaction）使用，定期整理碎片。

4.2.2 最佳适应算法（Best Fit）

最佳适应的想法很美好：不浪费大块，找最接近需求的小块。但实际跑起来，你会发现它产生大量无法使用的微碎片——比如申请 10KB，从 12KB 的块里切，剩下 2KB，这 2KB 以后基本用不上。

我记得有一次优化一个网络协议栈的内存池，用了最佳适应，结果运行 72 小时后内存碎片率高达 40%。后来换成首次适应，碎片率降到 15%。

// 最佳适应算法伪代码
void *best_fit(size_t size) {
    free_block_t *curr = free_list_head;
    free_block_t *best = NULL;
    size_t min_diff = SIZE_MAX;
    
    while (curr != NULL) {
        if (curr->size >= size) {
            size_t diff = curr->size - size;
            if (diff < min_diff) {
                min_diff = diff;
                best = curr;
            }
        }
        curr = curr->next;
    }
    if (best != NULL) {
        split_block(best, size);
        return best->start_addr;
    }
    return NULL;
}

避坑指南：我曾经在一个内存只有 256KB 的 IoT 设备上用了最佳适应，结果系统跑了 3 天就 OOM 了。排查发现，空闲链表里有 50 多个 1~4KB 的小碎片，但最大的连续块只剩 8KB。最佳适应不是不好，而是不适合小内存系统。

4.2.3 最差适应算法（Worst Fit）

最差适应反其道而行之：选最大的块，切完后剩下的部分仍然够大。这样理论上能减少小碎片的产生。但问题也很明显——大块被快速消耗，后续大进程可能找不到合适的块。

// 最差适应算法伪代码
void *worst_fit(size_t size) {
    free_block_t *curr = free_list_head;
    free_block_t *worst = NULL;
    size_t max_size = 0;
    
    while (curr != NULL) {
        if (curr->size >= size && curr->size > max_size) {
            max_size = curr->size;
            worst = curr;
        }
        curr = curr->next;
    }
    if (worst != NULL) {
        split_block(worst, size);
        return worst->start_addr;
    }
    return NULL;
}

嗯，这里要注意：最差适应需要空闲链表按大小排序，否则每次都要遍历。我一般用大小序链表来优化——插入时按大小排序，分配时直接取链表头，复杂度降到 O(1)。

4.3 三种算法的对比与选择

你想想看，这三种算法没有绝对的好坏。我做了这么多年系统，总结了一个简单的选择原则：

首次适应：通用场景，实现简单，性能均衡。推荐默认使用。
最佳适应：内存需求大小比较均匀，且对碎片敏感的场景。但要做好碎片整理。
最差适应：进程大小差异很大，且大块分配不频繁的场景。适合批处理系统。

实战建议：如果你在做通用操作系统，我建议用首次适应 + 空闲链表按地址排序。配合伙伴系统（buddy system）管理小块内存，效果更好。下一章我们会详细讲伙伴系统。

4.4 动态分区的核心问题：碎片与合并

不管用哪种算法，碎片都是绕不开的坎。碎片分两种：

内部碎片：分配出去的内存没用完，比如分配了 10KB，实际只用 7KB，剩下 3KB 浪费在分区内部。
外部碎片：空闲块分散在各处，总和够大，但没有一块连续空间能满足大进程需求。

解决外部碎片的常用手段是内存紧缩——把已分配的分区挪到一起，空出连续的大块空闲区。但紧缩代价很高，需要暂停所有进程、复制内存、更新指针。我一般只在碎片率超过 30% 时才触发紧缩。

4.5 回收与合并

进程释放内存时，要把分区归还给空闲链表。但光归还还不够——如果相邻的空闲块不合并，碎片会越来越多。我见过一个系统，回收时不做合并，运行一周后空闲链表里有 200 多个节点，但最大连续块只有 16KB。

合并策略一般分三种：

无合并：简单释放，不检查相邻块。碎片增长最快。
单向合并：只检查低地址或高地址的相邻块。实现简单，但可能漏掉。
双向合并：同时检查高低地址的相邻块。最彻底，但需要双向链表。

我的习惯：用双向链表管理空闲块，释放时做双向合并。虽然链表操作复杂一点，但能有效控制碎片。另外，我建议在释放时延迟合并——先标记为“待释放”，等碎片率达到阈值再统一合并。这样能减少频繁合并的开销。

4.6 小结

动态分区比固定分区灵活得多，但也带来了碎片管理的挑战。三种分配算法各有优劣：首次适应通用、最佳适应省空间、最差适应保大块。实际项目中，我建议先用首次适应跑起来，再根据碎片情况调整。

嗯，这里要记住：没有银弹。内存管理的优化是一个持续调参的过程，需要结合你的硬件、负载和实时性要求来做取舍。