空闲空间管理

可变大小分配带来的碎片问题

当空闲内存被切成许多大小不一的片段后，即使剩余总量足够，也可能找不到一块连续区域来满足新的较大请求。这种外部碎片会让分配失败，尽管系统里其实还有空间。

分割与合并如何维持大块空闲

遇到小于当前空闲块的请求时，分配器把该块切开，把需要的部分交给调用者，剩下的继续留在空闲结构里。释放时则检查左右邻居，若它们也空闲就把几块合成一块更大的连续区域，避免空间被永久切碎。

用头部快速获知已分配块的长度

释放接口只传入指针而不传入长度，因此分配器必须在交给用户的数据前面额外存放一小段头部，里面记下该块真实大小。这样释放时就能立刻知道该回收多少字节并正确更新空闲结构。

常见误区

• 忘记合并相邻空闲块会迅速产生无法使用的碎片
• 头部占用的额外字节会让小对象分配的有效利用率下降

最低标准 C11 · 完整程序 · 下载 .c

#include <stdio.h>
int main(void) {
    printf("Initial heap: free[0-9] used[10-19] free[20-29]\n");
    printf("Free list: addr=0 len=10 -> addr=20 len=10\n");
    printf("Allocate 1 byte from second free chunk:\n");
    printf("Returned pointer: 20\n");
    printf("Updated free list: addr=0 len=10 -> addr=21 len=9\n");
    printf("Free the middle used block (addr=10):\n");
    printf("Without coalescing: addr=10 len=10 -> addr=0 len=10 -> addr=21 len=9\n");
    printf("With coalescing: addr=0 len=30\n");
    return 0;
}

在本地编译

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-17-free-space.c -o example && ./example

预期结果

Initial heap: free[0-9] used[10-19] free[20-29]
Free list: addr=0 len=10 -> addr=20 len=10
Allocate 1 byte from second free chunk:
Returned pointer: 20
Updated free list: addr=0 len=10 -> addr=21 len=9
Free the middle used block (addr=10):
Without coalescing: addr=10 len=10 -> addr=0 len=10 -> addr=21 len=9
With coalescing: addr=0 len=30

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

一个30字节堆当前状态为前10字节空闲、中间10字节已用、后10字节空闲。若释放中间块却不做合并，随后请求15字节会成功吗？说明原因。

继续查证

• OSTEP chapter PDF

标准草案与官方章节会更新；版本标记只说明示例最低要求。