# 垃圾收集算法
上篇我们聊了如何知道一个对象是否存活，本篇就来看看怎么回收存活的对象吧
# 分代收集理论
分代收集理论，其实是一套经验法则，它建立在两个假说之上：
- 弱分代假说（Weak Generational Hypothesis）：绝大多数对象都是朝生夕死的
- 强分代假说（Strong Generational Hypothesis）：熬过越多次垃圾收集过程的对象就越难以消亡
这两个分代假说呢，引导了常见垃圾收集器的一致的设计原则，那就是收集器应当将Java堆划分成不同的区域，将对象实例根据年龄（即对象熬过垃圾收集的次数）来分配到不同区域存储，使用相对合适的算法来收集它们，也就是如果一块区域里都是朝生夕死的对象，那么就应该采用较高频率，但是时间开销较少的算法来收集它们；如果一块区域里都是可以存活很久的对象，就应该采用较低频率，可能对时间开销容忍比较不敏感的算法来收集这块区域的对象
那么自然就划分出新生代（Young Generation）和老年代（Old Generation）这两块区域了，而相对应的，就可以对这两个区域使用不同的回收类型，如Minor GC，Major GC，Full GC，以及不同的垃圾收集算法，如“标记-复制算法”，“标记-清除算法”和“标记-整理算法”，这些都会在下文中详细说
那么，分代之后，会遇到一个问题，假如对象之间出现了跨代引用，该怎么解决呢。假如说要进行一次对新生代的垃圾收集，发现有对象被老年代对象所引用，就不得不额外去遍历整个老年代所有对象来确保可达性分析结果的正确性。虽然理论可行，但是会为收集工作增加不少负担，为了解决这个问题，就需要对分代收集理论添加第三条经验法则：
- 跨代引用假说（Intergenerational Reference Hypothesis）：跨代引用相对于同代引用来说仅占极少数
其实，这条理论是可以通过前两条理论推断出来的，如果两个对象存在引用关系，那么它们应该是倾向于同生共死的，比如一个新生代对象存在老年代的跨代引用，那么发生垃圾收集时，由于老年代对象难以消亡，它也会同样得以存活，在多次垃圾收集之后，新生代对象也会晋升到老年代，这时，跨代引用也消失了
即便是一定要扫描跨代引用，也可以借助记忆集（Remember Set），它把老年代分成若干小块，来标识出老年代哪块内存存在跨代引用，当发生Minor GC时，只有包含了跨代引用的小块内存里的对象会被加入到GC Roots里进行扫描，这种方式虽然需要在对象改变引用关系时区同步更新维护记忆集，但也比扫描整个老年代要划算得多
# 回收类型
- 部分收集（Partial GC）：指目标不是完整收集整个Java堆的垃圾收集
- 新生代收集（Minor GC/Young GC）：指目标只是新生代的垃圾收集
- 老年代收集（Major GC/Old GC）：指目标只是老年代的垃圾收集，有时会被混淆为指代整堆收集
- 混合收集（Mixed GC）指目标是收集整个新生代以及部分老年代的垃圾收集，目前只有G1收集器有这种行为
- 整堆收集（Full GC）：收集整个Java堆和方法区的垃圾收集
# 标记-清除算法
标记-清除算法是最早也是最基础的垃圾收集算法，后续的收集算法大多是以它为基础，对其做了改进而得到的，正如其名，这个算法分为标记和清除两个步骤
- 标记出所有需要回收的对象
- 标记完成后统一回收掉被标记对象
这个算法主要有两个缺点，第一个是执行效率不太稳定，如果Java堆中包含了大量对象，并且其中大部分都需要被回收，那么标记和清除这两个过程的执行效率都会随着对象数量增长而降低；第二个是这种算法在回收完成后会产生大量内存碎片，导致后续分配大对象的时候，会找不到足够大连续内存空间而不得不触发另一次垃圾收集动作
# 标记-复制算法
那么为了解决标记-清除算法的第一个缺点，有人提出一种称为半区复制（Semispace Copying）的思路，它将可用内存空间划分成大小相等的两块区域，每次只使用其中一块，当一块空间快用完了，它就将存活的对象复制到另外一块上去，再把原先这块区域一次清理出来。当大部分都是可回收的对象时，只需要复制极少数对象即可，不会产生大量内存复制开销，十分契合新生代对象的收集规律，也不会产生内存碎片，其代价就是可用内存缩小成为了原来的一半，产生了空间浪费
空间浪费的问题，其实也在不久后得到了更好的解决方法，IBM公司有一项专门研究对新生代对象的特点做了更量化的诠释，新生代中98%的对象熬不过第一轮垃圾收集，因此无需按照1:1的比例来划分新生代的内存空间
那么更优化的半区复制分代策略就出现了，把新生代分为一块较大的Eden空间和两块较小且相等大小的Survivor空间，HotSpot虚拟机默认Eden和Survivor的大小比例是8:1，即新生代中有90%容量可用，相比原先只有50%可用已经好非常多了，每次垃圾收集只需要将Eden和一块Survivor上存活的对象复制到另一块Survivor上，并清理掉原先的Eden和Survivor的内存空间就可以了
当然了，并不是每次一块Survivor的空间都足以容纳逃过一次垃圾收集的所有对象，这时就需要老年代进行分配担保（Handle Promotion），将一部分对象直接存放近老年代了
# 标记-整理算法
那么针对老年代对象的特点，不想浪费10%内存空间，也不想因为复制算法浪费效率，标记-整理算法的思路，就是让所有存活对象向内存空间的一端移动，然后直接清理掉边界以外的对象
而移动一个存活对象，尤其是老年代这种有大量对象都是存活状态的区域，移动并更新所有引用这些对象的地方，是一项非常重量级的操作，这种操作必须要全程暂停用户线程才能进行，这种停顿被非常形象地描述为“Stop The World”
但如果不对对象进行移动，要解决内存碎片化的问题，就必须要使用更为复杂的内存分配器和内存访问器来解决，比如通过“分区空闲分配链表”来解决内存分配问题（计算机硬盘存储大文件就不要求物理连续的磁盘空间，能够在碎片化的硬盘上存储和访问就是通过硬盘分区表实现的），而内存访问是非常频繁的，如果这里消耗过大，将会极大影响程序的吞吐量
基于以上考虑，老年代的垃圾收集算法就使用了标记-整理算法
# 总结
这次我们简单聊了下几种垃圾收集算法，以及各自的特点，根据特点呢，来使用在不同分代区域的对象垃圾收集上，让垃圾收集工作对应用程序的影响在整体权衡下来都是可以接受的较优解，后续我们会继续探索一些算法细节上的实现，请期待吧~