边界标记合并技术：内存分配与碎片优化

1. 边界标记合并技术背景

在《深入理解计算机系统》(CSAPP)第9章讨论的动态内存分配器实现中，边界标记(Boundary Tags)是一种关键的数据结构设计。这项技术最早由Knuth在《计算机程序设计艺术》中提出，用于解决内存分配器中的块合并(Coalescing)问题。

现代操作系统课程中常提到的"隐式空闲链表"分配器，正是基于边界标记技术构建的。当程序频繁进行malloc/free操作时，内存中会产生大量内存碎片。边界标记的精妙之处在于，它通过在每个内存块的首尾放置标记信息，使得分配器可以在常数时间内判断相邻块是否空闲，从而决定是否进行合并。

2. 边界标记的数据结构实现

2.1 标记位的具体编码

典型的边界标记实现会在每个内存块的头部和尾部各放置一个标记字(tag word)。这个标记字通常包含两个关键信息：

• 块大小（包括头部和尾部本身占用的空间）
• 当前块的使用状态（已分配/空闲）

在32位系统上，标记字可能这样定义：

c复制typedef struct {
    uint32_t size:31;  // 块大小（低31位）
    uint32_t allocated:1; // 分配状态（最高位）
} boundary_tag;

2.2 内存块的实际布局

考虑一个64字节的空闲块，其内存布局如下：

code复制[头部标记][可用空间][尾部标记]

假设头部标记位于地址0x1000，其内容可能是：

• size = 64 (0x40)
• allocated = 0

那么对应的尾部标记将位于0x103C（0x1000 + 64 - 4），包含与头部完全相同的值。这种对称设计使得分配器可以从任意方向遍历内存块。

3. 合并操作的详细过程

3.1 合并条件判断

当释放一个内存块时，分配器需要检查其物理相邻的前后块是否也是空闲的。通过边界标记，这个过程变得异常简单：

1. 检查前驱块：当前块的头部地址减去4字节（假设标记字占4字节），读取该位置的值即为前驱块的尾部标记
2. 检查后继块：当前块的头部地址加上块大小，读取该位置的值即为后继块的头部标记
3. 如果标记显示相邻块是空闲的，则触发合并

3.2 合并操作的具体步骤

假设我们要释放位于0x20