C Academy · 课时

空闲列表与复用

Q: 「空闲列表与复用」这节课中我会学到什么？

跟踪并回收内存块。 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

跟踪并回收内存块。

第 3 / 4 课13 个步骤

空闲列表与复用 是 CoddyKit 上的免费 C Academy 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。

超越微调分配器

若要释放单个 block 并重新使用它们，我们需要记录相关信息。空闲链表是一个由可用 block 组成的链表，分配器会先搜索它，然后才获取新的内存。

每个 block 都带有一个标头，使分配器能够找到它的大小，并链接到链中的下一个 block。

带链接的 block 标头

我们在标头中加入一个 next 指针和一个 free 标志。它们共同将内存池变成一个可遍历的 block 链表。

有效载荷在内存中紧跟在标头之后。

typedef struct block {
    size_t size;          /* payload bytes */
    int free;             /* 1 if reusable */
    struct block *next;   /* next block in pool */
} block_t;

初始化一个大的空闲 block

启动时，整个内存池是一个巨大的空闲 block。随着分配发生，我们将它拆分；随着释放发生，我们将 block 标记为可重新使用。

链表的头部就是这个覆盖整个内存区域的初始 block。

static unsigned char pool[4096];
static block_t *head;

void heap_init(void) {
    head = (block_t *)pool;
    head->size = sizeof(pool) - sizeof(block_t);
    head->free = 1;
    head->next = NULL;
}

首次适配搜索

最简单的重用策略是首次适配：遍历链表并返回第一个足够大的空闲 block。它速度快，并且往往会让较小的 block 保持在链表前端附近。

其他方案还有最佳适配（最小的满足条件的 block）和最差适配，它们用速度换取不同的碎片表现。

block_t *first_fit(size_t size) {
    for (block_t *b = head; b; b = b->next)
        if (b->free && b->size >= size)
            return b;
    return NULL;
}

从空闲 block 中分配

找到合适的 block 后，我们将其标记为已使用，并返回紧跟在其标头之后的指针。目前我们会交出整个 block；拆分将在下一课介绍。

返回的指针是 block + 1，这样调用方就看不到标头了。

void *my_alloc(size_t size) {
    block_t *b = first_fit(size);
    if (!b) return NULL;
    b->free = 0;
    return (void *)(b + 1);
}

释放 block

要释放 block，请从用户指针退回到它的标头，并切换 free 标志。这样，该 block 就有资格在下一次搜索中被重新使用。

从有效载荷恢复标头，使用的就是我们之前见过的单步指针技巧。

void my_free(void *p) {
    if (!p) return;
    block_t *b = (block_t *)p - 1;
    b->free = 1;
}

合并相邻的空闲 block

仅进行释放会使内存池充满小的空闲 block。合并会在下一个 block 也空闲时，将释放的 block 与它合并，从而重新构建更大的连续区域。

这可以缓解外部碎片，因此将来仍然能够满足较大的请求。

void coalesce(block_t *b) {
    if (b->next && b->next->free) {
        b->size += sizeof(block_t) + b->next->size;
        b->next = b->next->next;
    }
}

一个可运行的空闲链表示例

这个完整程序会初始化内存池，分配两个 block，释放第一个 block，然后用一个更小的请求重新使用它，从而证明空闲链表有效。

#include <stdio.h>
#include <stddef.h>

typedef struct block { size_t size; int free; struct block *next; } block_t;
static unsigned char pool[1024];
static block_t *head;

void heap_init(void){ head=(block_t*)pool; head->size=sizeof(pool)-sizeof(block_t); head->free=1; head->next=NULL; }
block_t *first_fit(size_t s){ for(block_t *b=head;b;b=b->next) if(b->free&&b->size>=s) return b; return NULL; }
void *my_alloc(size_t s){ block_t *b=first_fit(s); if(!b) return NULL; b->free=0; return (void*)(b+1); }
void my_free(void *p){ if(!p) return; ((block_t*)p-1)->free=1; }

int main(void){
    heap_init();
    int *a = my_alloc(sizeof(int));
    *a = 7;
    printf("a=%d free=%d\n", *a, head->free);
    my_free(a);
    printf("after free: free=%d\n", head->free);
    return 0;
}

搜索的代价

单向空闲链表意味着分配的复杂度相对于 block 数量为 O(n)。分配次数很多时，这会变得很慢。

实际的分配器会使用按大小分类的空闲链表（大小分箱）或树，让搜索接近 O(1)。重用的原则仍然相同。

/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */

重复释放与损坏

将一个 block 两次标记为空闲，或写入超出 block 大小的范围，都会破坏相邻的标头。下一次搜索会跟随一个无效的 next 指针，随后崩溃。

这就是 C 中的内存错误如此危险的原因：分配器自己的元数据就位于您的数据旁边。

整合重用机制

一个可正常工作的空闲链表分配器需要初始化、适配策略、分配、释放和合并。有了这些机制，内存就会在内存池中循环使用，而不是无限增长。

剩下的改进是拆分过大的 block 并遵守对齐要求，这正是最后一课的主题。

快速检查

思考是什么防止空闲链表严重碎片化。

在交互式课程中回答

回顾

空闲链表通过标头连接各个 block，使单独的分配能够被释放和重新使用。首次适配搜索会找到一个 block，释放操作会切换标志，而合并操作会合并相邻 block，以应对碎片化。

线性搜索的复杂度为 O(n)；生产环境中的分配器会按大小分箱以提高速度。下一步我们将加入拆分和对齐。

免费开始

用 AI 导师学习 C — 免费

在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。

课程: 39
课程: 144

免费开始学习查看完整课程

常见问题解答

「空闲列表与复用」课时是免费的吗？

是的 — 「空闲列表与复用」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。

「空闲列表与复用」这节课中我会学到什么？

跟踪并回收内存块。你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 C Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 3 节课，共 4 节。

「空闲列表与复用」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 C Academy 课中编写并运行代码吗？

能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 C Academy