标记清除算法是垃圾回收领域最基础的实现方案之一，核心逻辑是识别程序中不再被引用的内存对象，然后自动回收这些对象占用的空间，避免手动释放内存带来的各类问题。该算法主要分为标记和清除两个阶段，在C++中可以通过自定义对象管理结构和内存分配逻辑来实现。
标记清除算法核心原理
标记清除算法的执行流程可以分为两个明确的阶段：
- 标记阶段：从根集（程序中直接可访问的引用集合，比如栈上的指针、全局变量等）出发，遍历所有可达的对象，将这些对象标记为存活状态。
- 清除阶段：遍历所有已分配的内存对象，将未被标记为存活状态的对象回收，释放其占用的内存空间，同时清除存活对象的标记状态，为下一次回收做准备。
C++实现的基础结构设计
要实现简单的标记清除GC，首先需要定义管理对象的基础结构，我们需要为每个分配的对象添加标记位，同时维护已分配对象的集合和根集引用。
对象头结构定义
每个分配的内存块都需要包含标记位和指向下一个对象的指针，方便遍历所有已分配对象：
#include <iostream>
#include <vector>
#include <cstdlib>
// 对象头结构，每个分配的内存块都包含这个头部
struct ObjectHeader {
bool marked; // 标记位，true表示存活
ObjectHeader* next; // 指向下一个已分配对象的头部
// 实际对象数据紧跟在这个头部之后
};
// 简单GC管理器类
class SimpleGC {
private:
ObjectHeader* objectList; // 所有已分配对象的链表头
std::vector<void*> roots; // 根集，存放所有根引用指针
public:
SimpleGC() : objectList(nullptr) {}
// 注册根引用
void addRoot(void* ptr) {
roots.push_back(ptr);
}
// 移除根引用
void removeRoot(void* ptr) {
for (auto it = roots.begin(); it != roots.end(); ++it) {
if (*it == ptr) {
roots.erase(it);
break;
}
}
}
};
内存分配接口实现
分配内存时需要在对象数据前添加ObjectHeader，同时将新对象加入已分配链表：
// 分配指定大小的内存，返回对象数据的起始地址
void* SimpleGC::allocate(size_t size) {
// 分配头部 + 实际数据的总大小
ObjectHeader* header = (ObjectHeader*)malloc(sizeof(ObjectHeader) + size);
if (!header) {
return nullptr;
}
// 初始化头部
header->marked = false;
header->next = objectList;
objectList = header;
// 返回数据部分的起始地址
return (void*)(header + 1);
}
// 获取对象头部，通过数据指针反查头部
ObjectHeader* getObjectHeader(void* dataPtr) {
return ((ObjectHeader*)dataPtr) - 1;
}
标记阶段的实现
标记阶段需要从根集出发，遍历所有可达的对象，这里为了简化实现，假设根集里的指针都是直接指向对象数据的起始地址，遍历时采用深度优先的思路：
// 标记单个对象，递归标记其引用的其他对象（这里简化为仅标记当前对象）
void markObject(ObjectHeader* header) {
if (header->marked) {
return;
}
header->marked = true;
// 实际场景中如果对象包含其他对象引用，需要在这里递归标记
}
// 执行标记阶段
void SimpleGC::mark() {
// 遍历所有根引用
for (void* rootPtr : roots) {
if (rootPtr == nullptr) {
continue;
}
ObjectHeader* header = getObjectHeader(rootPtr);
markObject(header);
}
}
清除阶段的实现
清除阶段遍历所有已分配对象，回收未标记的对象，同时重置存活对象的标记位：
// 执行清除阶段
void SimpleGC::sweep() {
ObjectHeader* prev = nullptr;
ObjectHeader* curr = objectList;
while (curr != nullptr) {
if (!curr->marked) {
// 未标记，回收该对象
ObjectHeader* toFree = curr;
curr = curr->next;
if (prev) {
prev->next = curr;
} else {
objectList = curr;
}
free(toFree);
} else {
// 存活对象，重置标记位
curr->marked = false;
prev = curr;
curr = curr->next;
}
}
}
完整使用示例
下面是一个简单的使用案例，展示GC的分配、根引用管理和回收流程：
int main() {
SimpleGC gc;
// 分配两个对象
int* obj1 = (int*)gc.allocate(sizeof(int));
int* obj2 = (int*)gc.allocate(sizeof(int));
*obj1 = 10;
*obj2 = 20;
// 将obj1加入根集，obj2不加入
gc.addRoot(obj1);
std::cout << "Before GC: obj1=" << *obj1 << ", obj2=" << *obj2 << std::endl;
// 执行垃圾回收
gc.mark();
gc.sweep();
// 回收后obj1存活，obj2被释放
std::cout << "After GC: obj1=" << *obj1 << std::endl;
// 此时访问obj2属于未定义行为，因为其已经被回收
// 清理根引用，释放obj1
gc.removeRoot(obj1);
gc.mark();
gc.sweep();
return 0;
}
实现局限性与优化方向
上述实现是一个极度简化的版本，实际生产级的GC还需要处理很多问题：
- 根集的识别需要结合C++的栈遍历、全局变量遍历，不能手动维护根集。
- 对象之间的引用关系需要自动识别，不能仅标记根对象。
- 需要处理内存碎片问题，标记清除算法容易产生碎片，可结合复制算法或者标记整理算法优化。
- 需要保证线程安全，多线程场景下的内存分配和回收需要加锁或者使用线程本地分配缓存。
这个简单实现主要用于帮助理解标记清除算法的核心逻辑，实际C++开发中如果需要垃圾回收能力，也可以参考这个思路实现符合自己业务场景的轻量GC模块。