标记-清除算法

算法分为标记和清除两个阶段：首先标记出所有需要回收的对象，在标记完成后统一回收所有被标记的对象。它主要不足有两个：一个是效率问题，标记和清除两个过程的效率都不高，另一个是空间问题，标记清除之后会产生大量不连续的内存碎片，空间碎片太多可能导致以后程序在运行过程中需要分配较大对象时，无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。

标记-清除算法

复制算法

为解决效率问题，它将可用内存分为大小相等的两块，每次只使用其中一块，当这一块内存用完，就将还活着的对象复制到另一块内存上，然后再把已使用过的内存空间一次清理掉。这样每次对整个半区内存进行回收，内存分配时不用考虑内存碎片等复杂问题，只要移动堆顶指针，按顺序分配内存即可，实现简单，运行高效。但是这个算法的代价是内存缩小了一半。

复制算法

现在的商业虚拟机都采用这种收集算法来回收新生代，但不需要按照1：1的比例来分配内存，而是将内存分为一块较大的Eden空间和两块较小的Survivor空间，每次使用Eden和其中一块Survivor，当回收时，将Eden和Survivor中还存活的对象一次性复制到另外一块Survivor空间上，最好清理掉Eden和刚才用过的Survivor空间。

标记-整理算法

复制收集算法在对象存活率较高时就要进行较多的复制操作，效率将会降低，更为关键的是，如果不想浪费50%的空间，就需要额外的空间进行分配担保，以应对被使用的内存中所有对象都100%存活的极端情况，所以老年代一般不能直接选用这种算法。
而“标记-整理”算法，则在标记过程仍然与“标记-清除”一样，但是后续步骤不是直接回收对象进行清理，而是让所有活着的对象想一端移动，然后直接清理掉端边界意外的内存。

标记-整理算法

分代收集算法

只是根据对象存活周期的不同将内存划分为几块。一般是把Java堆分为新生代和老年代，这样就可以根据各个年代的特点采用最合适的算法。在新生代中，每次垃圾收集时都发现大量对象死去，只有少量对象存活，那就选用复制算法；而老年代中因为对象存活率高、没有额外空间对它进行分配担保，就必须采用“标记-清除”或者“标记-整理”算法。

HotSpot的算法实现

枚举根节点

可达性分析中从GC Roots节点开始找引用链，需要逐个检查引用，必然会消耗不少时间；另外可达性分析必须在一个能够确保一致性的快照中进行，必然导致GC进行时必须停顿所有Java执行线程（Stop The World）。
在HotSpot的实现中，使用一组称为OopMap的数据结构来存放对象的引用信息，在类加载额按成的时候，HotSpot就把对象内偏移量等类型数据计算出来，在JIT编译过程中，也会在特定的位置记录下栈和寄存器中哪些位置是引用。这样GC在扫描时就可以直接指导这些信息。

安全点

在OopMap的协助下，HotSpot可以快速确准确的完成GC Roots枚举，但一个很现实的问题随之而来：可能导致引用关系变化，或者说OopMap内容变化的指令很多，如果要为每条指令都生成对应的OopMap，那将会需要大量的额外空间，GC空间成本将会急剧变高。
HotSpot并没有为每条指令都生成OopMap，而是在“特定的位置”记录了这些信息，这些位置被称为安全点（Safepoint），即程序执行时并不会在所有的地方都能停下来做GC，只有到达安全点才能暂停。
对于如何在GC的时候让所有Java线程（不包括JNI调用的线程）都跑到最近的安全点停顿下来，有两种方案可供选择：抢先式中断（Preeminent Suspension）和主动式中断（Voluntary Suspension）。

• 抢先式中断不需要线程的执行代码主动配合，在GC发生时，首先把所有线程全部中断，如果发现线程中断的地方不在安全点上，就恢复线程，让它“跑”到安全点上
• 主动式中断的思想是当GC需要中断线程的时候，不直接对线程操作，仅仅简单的设置一个标志，各个线程执行时主动去轮询这个标志，发现中断标志为真时主动中断挂起。轮询标志的地方和安全点是重和的，另外再加上对象需要分配内存的地方。

安全区域

安全区域是指在一段代码片段中，引用关系不会发生变化。在这个区域中的任意地方开始GC都是安全的，我们可以把Safe Region看做是扩展了的Safepoit。在线程执行到Safe Region中的代码时，首先标识自己进入了Safe Region，当在这段时间里JVM要发起GC时，就不用管标识自己为Safe Region的线程了。当线程离开Safe Region时，它要检查系统是否已经完成了根节点枚举（或者整个GC过程），如果完成了，那线程继续执行，否则他就必须等待直到接收到可以安全离开Safe Region的信号为止。

参考资料

• 深入理解Java虚拟机 JVM高级特性与最佳实践 第2版