A05 嵌入式自动化脚本的防碎片内存管理器

A05 嵌入式自动化脚本的防碎片内存管理器

项目概述

本项目源自《计算机程序设计艺术》（TAOCP）算法库的知识的系统化工程落地。

算法史故事

1960年，AI先驱McCarthy为LISP发明了标记-清扫垃圾回收，解决了自动内存管理的难题。而Knuth在TAOCP中总结了边界标签技术，在每个内存块的头部和尾部记录大小信息，实现了O(1)时间的相邻空闲内存合并。

课程任务

自动化设备通常需要长时间不间断运行，内存泄漏是致命的。开发一个模拟底层的内存池，底层基于双向链表和边界标签管理空闲块（防碎片）；上层实现一个微型GC引擎，通过DFS遍历模拟的"根集合"进行存活对象标记与自动清扫。

核心要求

• 实现边界标签内存管理（分配/释放/合并相邻空闲块）
• 实现双向链表管理空闲块（按地址排序）
• 实现标记-清扫垃圾回收（从根集合DFS标记存活对象）
• 实现内存碎片整理（可选，移动存活对象合并空闲区）
• 模拟长时间运行场景下的内存分配/释放/GC循环
• 统计内存碎片率、GC触发频率、回收效率

工程哲学：可控可观（Controllability-Observability）

• 可控：对每一字节内存走向有绝对掌控力，不允许不可预知的系统崩溃
• 可观：通过打点、日志和统计，让不可见的算法瓶颈变得清晰可见

工程伦理

理解嵌入式系统中内存泄漏的累积危害，培养对资源受限环境下内存管理的极致追求。

新手破冰指南：C语言视角的四步上手路径

如果把学习编程比作造车：

• 基础数据结构课：教你认识什么是螺丝、齿轮（链表、栈）。
• TAOCP 算法库：是存放着各种高性能标准件的零件库。比如库里的 taocp1_free_storage_list.c（边界标签）是一个顶级变速箱设计图，taocp1_mark_sweep_gc.c（标记-清扫）是一个自动驾驶环境感知模块。它们在库里是孤立的、纯理论的。
• A05 课程设计：是要求你把这两个顶级零件拿出来，通过自己的C语言代码将它们组装集成，打造出一辆能真正在赛道上（长时间不间断运行的嵌入式自动化环境）跑起来的、没有内存泄漏隐患的智能车底盘。

简而言之：算法库是"知识的切片"，而A05项目是"知识的系统化工程落地"。

第一步：建立底层的"绝对可控性"（打破 malloc 黑盒）

你的现状：习惯了调用 malloc 和 free，认为内存是向操作系统"要"来的。

你要做的：自己当操作系统。

在全局定义一个大数组：char memory_pool[10240];。这就是你的全部物理世界。

复习双向链表。但这次，链表的节点不是通过 malloc 创建的，而是直接在 memory_pool 这个数组的不同偏移地址上，用指针强转（Cast）盖上去的结构体。

核心挑战：理解边界标签。你需要在分配出去的每一块内存的"头"和"尾"都放一个包含 size 的结构体。多画内存布局图，搞清楚指针的加减法（指针偏移计算是这里的重灾区）。

第二步：建立对象之间的关系网（图与可达性）

你的现状：学过树和图的概念，但还没真正在复杂场景里用过。

你要做的：理解引用。

定义一个"对象"结构体，里面除了数据，还要有一个指针数组 Object* refs[MAX_REFS];，表示这个对象连接（指向）了哪些其他对象。

这就构成了一个有向图。想象这是智能车控制策略中的节点：A节点（速度控制）依赖B节点（PID参数），如果A还在发挥作用，B就绝对不能被销毁。

第三步：实现状态的"可观性"（DFS与标记）

你的现状：学过栈（Stack）和深度优先搜索（DFS）的皮毛。

你要做的：写出 GC 的前半部分——标记（Mark）。

创建一个数组作为"根集合"（Root Set），也就是所有正在运行的脚本的入口。

写一个基于栈的迭代 DFS。从根集合出发，顺着 refs 指针往下找。找到的对象，就把它的 marked 标志位设为 1。

注意：在嵌入式环境中，尽量不要用递归写 DFS（容易爆栈），用你学过的基础数据结构自己维护一个栈。

第四步：无情清扫与物理合并（闭环）

你要做的：完成 GC 的后半部分——清扫（Sweep）并对接底层。

线性遍历整个 memory_pool 中的每一个对象块。

如果发现它的 marked == 0，说明它是一个游离的"太空垃圾"。

调用你第一步写好的底层 my_free(ptr) 函数。此时，第一步写的边界标签机制会自动发挥作用，把相邻的空闲块以 O(1) 的速度合并起来，防止内存碎片化。

给新手的避坑锦囊

作为只掌握了C语言基础的学生，你最容易在以下几个地方卡壳：

1. 眼见为实（画图是第一生产力）

在写边界标签合并（my_free）时，绝对不要凭空想象。在纸上画出 [Header][Data][Footer] -> [Header][Data][Footer] 的方格图，标出每一个指针指向哪里。一旦合并，哪几个边界标签会被抹除？哪几个会被保留？画清楚了再敲代码。

2. 善用断言（Assert）进行系统自检

为了保证内存的"可控性"，在每个函数的开头和结尾写满 assert。比如：

assert(block->size>0);assert(total_free_memory+total_used_memory==POOL_SIZE);// 质量守恒定律

3. 先跑通"玩具模型"

不要一开始就试图运行一万次的高频读写脚本。先手写三四次分配，制造一个最简单的"A指向B，切断A"的场景，触发一次 GC，用 printf 把此时的内存切片状态原原本本地打印出来（建立系统的可观性），确认回收和合并逻辑100%正确，再进行自动化极限压测。

目录结构

. ├── README.md # 本文件（项目总览） ├── Makefile # GCC编译脚本 ├── .gitignore # Git忽略规则 ├── src/ # 源代码目录 │ ├── main.c # 主程序入口 │ ├── algorithm_a.c # 算法A实现 │ ├── algorithm_b.c # 算法B实现 │ ├── utils.c # 工具函数 │ └── include/ # 头文件目录 │ ├── algorithm_a.h │ ├── algorithm_b.h │ └── utils.h ├── docs/ # 文档目录 │ ├── 01-需求分析.md │ ├── 02-算法史故事.md │ ├── 03-功能框图.png │ ├── 04-详细设计.md │ └── 05-测试报告.md ├── report/ # 课程设计报告 │ └── 设计报告模板.md └── test/ # 测试代码 ├── unit_test.c # 单元测试 └── test_data/ # 测试数据集

快速开始

编译

make# 编译主程序maketest# 编译测试makeclean# 清理

运行

./main ./unit_test

里程碑

Git提交规范

[A-模块] 具体修改内容 示例： [A-边界标签] 实现内存分配与相邻空闲块合并 [A-垃圾回收] 实现DFS标记与清扫逻辑 [A-碎片整理] 实现存活对象移动与空闲区合并 [A-统计] 实现碎片率与GC频率统计

源自《计算机程序设计艺术》的新故事 —— 这本书的作者栏，写着你的名字。