标记-清除

优质

小牛编辑

130浏览

2023-12-01

标记-清除是主流的追踪式收集算法的一种，和引用计数相比，追踪式收集是一种间接方法，与程序耦合性很低，简单地说，就是程序在需要的时候只管申请内存，使用时也不用像引用计数机制要做实时地维护，直到一定条件（一般是已申请内存空间达到一定阈值），进程暂停执行，由垃圾收集器回收垃圾，然后继续执行，当然如果收集之后还是内存不足，就报错。很多语言的主流实现都使用追踪式收集，比如java，C#等

追踪式收集严格按照垃圾的概念定义，从根集开始，找到所有可达的对象集合，于是全集减去可达集，剩下都是垃圾。标记-清除算法分为三步： 1 初始化所有对象为未标记状态 2 从根集开始，标记所有可达对象 3 遍历所有对象，如果未被标记，则释放后面会看到，实际上是两步，初始化这一步是在第三步处理的

每个对象需要有一个标记位，这个内存占用并不多，因为一个bit位即可，结合语言的对象结构设计，一般是能找到这样一个位的，比方说，对象头用一个int表示对象的类型（类似C++的虚表指针），假定一个程序的类型的数量不会超出int的最大值（32位的int，如果这个范围都超出了，请受我一拜），则符号位可以用来做这个标记

所有新申请的对象，都是未标记状态，其中上述第三步可以这样：

for obj in all_obj   
{   
    if (obj.marked())   
    {   
        obj.unmark();   
    }   
    else   
    {   
        free(obj);   
    }   
}

遍历所有对象的时候，如果被标记了，则修改为未标记状态，如果未标记，则释放。这样一来，保证了每次垃圾回收开始的时候，所有对象都是未标记状态，上述的第一步初始化就可以省了

于是，核心问题就是如何从根集标记所有对象，乍一看这并不难，比方说我们可以采用DFS：

void mark()   
{   
    this.mk = true; //假设用一个bool变量   
    for obj in this.obj_list   
    {   
        if (obj.unmark())   
        {   
            //如果已经标记就不用做了，比如存在环或一个对象被多处引用   
            obj.mark();   
        }   
    }   
}   
for obj in root_set   
{   
    obj.mark();   
}

或者采用BFS

todo_list = root_set   
while (todo_list.size() > 0)   
{   
    new_todo_list = new list;   
    for obj in todo_list   
    {   
        if (obj.unmarked())   
        {   
            obj.mark(); //这里的mark就只是简单设置标记位   
            for item in obj.obj_list   
            {   
                if (item.unmarked())   
                {   
                    new_todo_list.add(item);   
                }   
            }   
        }   
    }   
    todo_list = new_todo_list;   
}

这两种做法都可以，但在垃圾收集中，它们有一个共同的问题，就是如果需要标记的对象很多，消耗空间可能很大，DFS消耗栈空间，BFS消耗每次迭代时列表的空间。如果是一般的问题，内存消耗是应该是，但是在追踪式收集中，垃圾收集器的触发条件一般是在堆空间被消耗得差不多的时候，如果这时候需要一个和对象数量相关的线性空间来进行垃圾收集，就不得不降低垃圾回收触发的堆空间阈值，进一步导致加剧垃圾回收的频率因此，最好的办法是能在常数空间内实现标记过程，可惜的是，这类算法要么很慢，要么很复杂（复杂的算法本身也不会很快）。不过在实际使用中，全文追踪收集的实现已经比较少了，一些新的机制可以缓解这个问题

追踪式收集的优缺点和引用计数相比，大部分都刚好反过来，引用计数的优点，恰好是追踪式收集的缺点，比如：对象生存周期可控性更差，由于收集过程会暂停运行，实时性差，局部性不好等；而反过来，引用计数的很多缺点又恰好是追踪式收集的有点，比如：和程序代码耦合性低，维护方便，程序运行期没有多余消耗，空间浪费少，所有垃圾都能被回收，整体效率高等

具体到标记-清除，从过程可以看到，这个算法的运行时间是和内存中对象数量成正比的（假设内存释放是常数时间），假如对象很多，则可能花不少时间，考虑到实际情况，大部分程序在需要垃圾回收的时候，可达集合往往比较少，据统计，80%~98%的对象在建立之后很快（约几百万条指令）就会销毁，因此，标记阶段的时间相对还比较少，大量时间费在清除阶段，为提高实时性，可以采用延迟清除的手段，即标记完成后，清除阶段分多次进行，因为触发垃圾收集一般是在空闲空间不足的时候，这时候清理出一部分空闲内存就可以让程序继续进行下去这样可能会引入一个问题，即从开始清理到清理完毕，这期间程序会new出新对象，而新对象的状态是unmarked，这时候就需要改进方案来区分，否则可能会错误地清理正在使用的对象，而这段时间成为垃圾的对象不会被立刻回收，这个没有关系，在下次标记的时候就可以正常清理掉了