垃圾回收算法总结

垃圾回收算法解决两个问题：识别垃圾和清除垃圾。识别垃圾的思路有两种：引用计数和遍历标记。清除垃圾的方式也有两种：原地回收和复制回收。各路算法按照这两种思路和方式的结合，通过各种方式去缩短GC暂停时间、提供堆使用率、保持程序局部性。

原地回收的算法主要有引用计数算法和标记清除算法。

引用计数算法是引用计数和原地回收的结合。它具有GC最大暂停时间短、可以保持程序局部性的优点，但是存在循环引用对象不能清除、引用计数位频繁更新的缺点。部分标记清除算法对root引用对象转移做了特殊处理，使用标记清除算法来识别垃圾，避免了循环引用对象不被root引用后，不能被清除的问题。Sticky 引用计数法和ZCT引用计数法分别通过忽略计数位溢出，延迟计数位更新的方法减缓了引用计数位频繁更新的问题。

标记清除算法是标记和原地回收的结合。作为一种保守式GC算法，它不需要移动对象，不需要更新引用指针，经常是其他GC算法（如部分标记清除算法，Ungar分代GC算法）的补充手段。标记清除算法存在内存碎片化、不兼容写时复制技术的缺点。通过规整分块大小（BiBOP）可以减缓内存碎片。使用位图记录标记位可以使其兼容写时复制技术。

通过复制活动对象来进行垃圾回收的算法大部分使用了标记来识别垃圾。

标记整理算法是标记和复制算法的结合。它通过将活动对象挪到一起来回收空闲空间，解决了标记清除算法带来的堆内存碎片问题。LISP2算法在移动对象过程中会保持对象顺序，可以保持程序的局部性，但是需要三次遍历堆（分别是计算对象新位置、更新指针、移动对象），导致GC暂停时间过长。Two-Finger算法在对象大小一致的前提下，采用类似于交换排序的方式，将空闲的内存块移动到堆末尾，它将遍历堆的次数从3次降低到2次。表格算法通过对象群和间隙表格，在保持2次遍历的基础上，维持了堆内对象的顺序，而且不要求对象大小一致。

分代GC侧重解决复制带来的GC最大暂停时间过长问题。利用大部分对象生成后会很快被销毁的特点，将堆分成多个区间（代），在不同代之间采用不同的垃圾识别算法，并且保持不同的GC频率。通过减少每次GC扫描的对象来缩短GC暂停时间。Ungar算法将堆分成新生代和老生代，新生代使用复制算法，在老生代采用标记清除算法。同时它通过记录集和写屏障，保证被老生代对象引用的新生代对象不会被回收。列车算法在老生代也采用复制回收算法，它可以减少老生代GC的最大暂停时间，但代价是写屏障会更加繁重。

渐进式GC则是针对标记清除算法的一种改进，它把GC的过程分成扫描root、遍历扫描堆、清除堆内垃圾三个阶段，每个阶段都可以暂停下来，以此到达减少GC最大暂停时间的效果。为了记住对象是否被扫描过，需要使用三色标记法对对象进行标记，并且使用写屏障，在指针更新的时候对标记进行更新。按照写屏障更新标记的时机和对象，可以分成Dijkstra算法、Steele算法、汤浅太一算法。