垃圾收集算法(GarbageCollectionAlgorithm)

清理垃圾算法又叫内存回收算法。

标记清除算法（Mark-Sweep）

标记清除算法是现代垃圾回收算法的思想基础。标记清除算法将垃圾回收分为两个阶段：标记阶段和清除阶段。一种可行的实现是，在标记阶段，首先通过根节点，标记所有从根节点开始的可达对象。因此，未被标记的对象就是未被引用的垃圾对象。然后，在清除阶段，清除所有未被标记的对象。 标记清除算法可能产生的最大的问题是空间碎片。

标记（Mark）垃圾回收的第一步，就是找出活跃的对象。根据 GC Roots 遍历所有的可达对象，这个过程，就叫作标记。
清除（Sweep）清除阶段就是把未被标记的对象回收掉。

复制算法（Copying）

复制算法的核心思想是：将内存空间分为两块，每次只使用其中一块，在垃圾回收时，将正在使用的内存中的存活对象复制到未被使用的内存块中，之后，清除正在使用的内存块中的所有对象，交换两个内存的角色，完成垃圾的回收。如果系统中的垃圾对象比较多，复制算法需要复制的存活的对象数量就会相对较少。因此，在真正需要垃圾回收的时刻，复制算法的效率是很高的。又由于对象是在垃圾回收过程中，统一被复制到新的内存空间中的，因此，可确保回收后的内存空间是没有碎片的。但是，复制算法的代价却是将系统内存折半，因此，单纯的复制算法也难以让人接受。

在Java中新生代串行垃圾回收中，使用了复制算法的思想。将内存区域分为新生代、老年代。新生代分为Eden区、from区、to区3部分。其中from区和to区视为可复制的两块大小相同、地位相等、且可进行角色互换的空间块。from区和to区也称为survivor区。即幸存空间，用于存放未被回收的对象。

在垃圾回收时，Eden区中的存活的对象会被复制到未使用的survivor区中（假设to区），正在使用的survivor区中（假设from区）的年轻对象被复制到to区（大对象，或者老年对象会直接进入老年代，如果to区已满，则对象也会直接进入老年代）。此时，Eden区和from区中的剩余对象就是垃圾对象，可以直接清空，to区则存放此次回收后的存活的对象。这种改进的复制算法，既保证了空间的连续性，有避免了大量内存空间浪费。复制算法比较适合新生代，因为在新生代，垃圾对象通过多于存活对象，复制算法的效果比较好。

标记整理算法（Mark-Compact）

标记整理算法是一种老年代的回收算法。它在标记算法的基础上做了一些优化。和标记清除算法一样，标记压缩算法也首先需要从根节点开始，对所有可达的对象做一次标记。但之后，它并不是简单地清理未标记的对象，而是将所有存活的对象压缩到内存的一端。之后，清理边界外所有的空间。这种算法既避免了碎片的产生，又不需要两块相同的内存空间，因此，性价比比较高。标记-压缩算法的最终效果等同于标记-清除算法执行完成后，在进行一次内存碎片整理，因此也可以把他称为标记-清除-压缩（MarkSweepCompact）算法

分代算法（Generational Collection）

分代算法，将内存区间根据对象的特点分成几块，根据每块内存空间的特点，使用不同的回收算法，以提高垃圾回收的效率。分代收集就是根据对象的存活周期将内存分为新生代和老年代。

为了支持高频率的新生代回收，虚拟机可能使用一种叫作卡表(Card Table)的数据结构。卡表为一个比特位集合，每一个比特位可以用来表示老年代的某一区域中的所有对象是否持有新生代的引用。在垃圾回收时，只需扫描有引用的老年代空间，使用这种方式，可以大大加快新生代回收速度。

新生代对象“朝生夕死”，每次收集都有大量对象（99%）死去，所以可以选择标记-复制算法，只需要付出少量对象的复制成本就可以完成每次垃圾收集
老年代对象生存几率比较高，存活对象比较多，如果选择复制算法需要付出较高的IO成本，而且没用额外的空间可以用于复制，此时选择标记-清除或者标记-整理就比较合理

研究表明大部分对象可以分为两类：

大部分对象的生命周期都很短
其他对象则很可能会存活很长时间

根据对象存活周期的不同将内存划分为几块。对不同周期的对象采取不同的收集算法：

新生代：每次垃圾收集会有大批对象回收，所以采取复制算法
老年代：对象存活率高，采取标记清理或者标记整理算法

① 年轻代（Young Generation）

年轻代使用的垃圾回收算法是复制算法。因为年轻代发生 GC 后，只会有非常少的对象存活，复制这部分对象是非常高效的。但复制算法会造成一定的空间浪费，所以年轻代中间也会分很多区域。

年轻代分为：1个伊甸园空间（Eden ），2个幸存者空间（Survivor ）。当年轻代中的 Eden 区分配满的时候，就会触发年轻代的 GC（Minor GC）。具体过程如下：

在 Eden 区执行了第一次 GC 之后，存活的对象会被移动到其中一个 Survivor 分区（以下简称from）
Eden 区再次 GC，这时会采用复制算法，将 Eden 和 from 区一起清理。存活的对象会被复制到 to 区，然后只需要清空 from 区就可以了

在这个过程中，总会有1个 Survivor 分区是空置的。Eden、from、to 的默认比例是 8:1:1，所以只会造成 10% 的空间浪费。这个比例，是由参数 -XX:SurvivorRatio 进行配置的（默认为 8）。

② 老年代（Old/Tenured Generation）

老年代一般使用“标记-清除”、“标记-整理”算法，因为老年代的对象存活率一般是比较高的，空间又比较大，拷贝起来并不划算，还不如采取就地收集的方式。对象进入老年代的途径如下：

提升（Promotion）

如果对象够老，会通过“提升”进入老年代
分配担保

年轻代回收后存活的对象大于10%时，因Survivor空间不够存储，对象就会直接在老年代上分配
大对象直接在老年代分配

超出某个大小的对象将直接在老年代分配
动态对象年龄判定

有的垃圾回收算法，并不要求 age 必须达到 15 才能晋升到老年代，它会使用一些动态的计算方法。

比如，如果幸存区中相同年龄对象大小的和，大于幸存区的一半，大于或等于 age 的对象将会直接进入老年代。

分区算法（Region）

分代算法将按照对象的生命周期长短划分成两部分，分区算法将整个堆空间划分成连续的不同小区间。没法小区间都独立使用，独立回收。这种算法的好处是可以控制一次回收多少个小区间。一般来说，在相同条件下，堆空间越大，一次GC时所需要的时间就越长，从而产生的停顿也越长。为了更好控制GC产生的停顿时间，将一块大的内存区域分割成多个小块，根据目标的停顿时间，每次合理地回收若干个小区间，而不是整个堆空间，从而减少一次GC所产生的停顿。

STW

在垃圾回收时，都会差产生应用程序的停顿，整个程序会被卡死，即”Stop_The_World”，简称:STW 当设置的虚拟机参数不同时，会影响GC发生的时间和频率，进而影响程序的停顿。 Java中Stop-The-World机制简称STW，是在执行垃圾收集算法时，Java应用程序的其他所有线程都被挂起（除了垃圾收集帮助器之外）。Java中一种全局暂停现象，全局停顿，所有Java代码停止，native代码可以执行，但不能与JVM交互；这些现象多半是由于gc引起。

GC时的Stop the World(STW)是大家最大的敌人。但可能很多人还不清楚，除了GC，JVM下还会发生停顿现象。

JVM里有一条特殊的线程－－VM Threads，专门用来执行一些特殊的VM Operation，比如分派GC，thread dump等，这些任务，都需要整个Heap，以及所有线程的状态是静止的，一致的才能进行。所以JVM引入了安全点(Safe Point)的概念，想办法在需要进行VM Operation时，通知所有的线程进入一个静止的安全点。

除了GC，其他触发安全点的VM Operation包括：

JIT相关，比如Code deoptimization, Flushing code cache ；
Class redefinition (e.g. javaagent，AOP代码植入的产生的instrumentation) ；
Biased lock revocation 取消偏向锁；
Various debug operation (e.g. thread dump or deadlock check)；

HotSpot的算法实现

枚举根节点

从可达性分析中从GC Roots节点找引用链这个操作为例，可作为GC Roots的节点主要在全局性的引用（例如常量或类静态属性）与执行上下文（例如栈帧中的本地变量表）中，现在很多应用仅仅方法区就有数百兆，如果要逐个检查这里面的引用，那么必然会消耗很多时间。

另外，可达性分析对执行时间的敏感还体现在GC停顿上，因为这项分析工作必须在一个能确保一致性的快照中进行——这里“一致性”的意思是指在整个分析期间整个执行系统看起来就像被冻结在某个时间点上，不可以出现分析过程中对象引用关系还在不断变化的情况，该点不满足的话分析结果准确性就无法得到保证。这点是导致GC进行时必须停顿所有Java执行线程（Sun将这件事情称为“Stop The World”）的其中一个重要原因，即使是在号称（几乎）不会发生停顿的CMS收集器中，枚举根节点时也是必须要停顿的。

由于目前的主流Java虚拟机使用的都是准确式GC（这个概念在第1章介绍Exact VM对Classic VM的改进时讲过），所以当执行系统停顿下来后，并不需要一个不漏地检查完所有执行上下文和全局的引用位置，虚拟机应当是有办法直接得知哪些地方存放着对象引用。在HotSpot的实现中，是使用一组称为OopMap的数据结构来达到这个目的的，在类加载完成的时候，HotSpot就把对象内什么偏移量上是什么类型的数据计算出来，在JIT编译过程中，也会在特定的位置记录下栈和寄存器中哪些位置是引用。这样，GC在扫描时就可以直接得知这些信息了。下面的代码清单3-3是HotSpot Client VM生成的一段String.hashCode（）方法的本地代码，可以看到在0x026eb7a9处的call指令有OopMap记录，它指明了EBX寄存器和栈中偏移量为16的内存区域中各有一个普通对象指针（Ordinary Object Pointer）的引用，有效范围为从call指令开始直到0x026eb730（指令流的起始位置）+142（OopMap记录的偏移量）=0x026eb7be，即hlt指令为止。

代码清单3-3　String.hashCode（）方法编译后的本地代码

[Verified Entry Point]
0x026eb730：mov%eax，-0x8000（%esp）
…… ；ImplicitNullCheckStub slow case
0x026eb7a9：call 0x026e83e0 ；OopMap{ebx=Oop[16]=Oop off=142} ；*caload ；-java.lang.String：hashCode@48（line 1489）
；{runtime_call}
0x026eb7ae：push$0x83c5c18 ；{external_word}
0x026eb7b3：call 0x026eb7b8
0x026eb7b8：pusha
0x026eb7b9：call 0x0822bec0；{runtime_call}
0x026eb7be：hlt

安全点

在OopMap的协助下，HotSpot可以快速且准确地完成GC Roots枚举，但一个很现实的问题随之而来：可能导致引用关系变化，或者说OopMap内容变化的指令非常多，如果为每一条指令都生成对应的OopMap，那将会需要大量的额外空间，这样GC的空间成本将会变得很高。

实际上，HotSpot也的确没有为每条指令都生成OopMap，前面已经提到，只是在“特定的位置”记录了这些信息，这些位置称为安全点（Safepoint），即程序执行时并非在所有地方都能停顿下来开始GC，只有在到达安全点时才能暂停。Safepoint的选定既不能太少以致于让GC等待时间太长，也不能过于频繁以致于过分增大运行时的负荷。所以，安全点的选定基本上是以程序“是否具有让程序长时间执行的特征”为标准进行选定的——因为每条指令执行的时间都非常短暂，程序不太可能因为指令流长度太长这个原因而过长时间运行，“长时间执行”的最明显特征就是指令序列复用，例如方法调用、循环跳转、异常跳转等，所以具有这些功能的指令才会产生Safepoint。

对于Sefepoint，另一个需要考虑的问题是如何在GC发生时让所有线程（这里不包括执行JNI调用的线程）都“跑”到最近的安全点上再停顿下来。这里有两种方案可供选择：抢先式中断（Preemptive Suspension）和主动式中断（Voluntary Suspension），其中抢先式中断不需要线程的执行代码主动去配合，在GC发生时，首先把所有线程全部中断，如果发现有线程中断的地方不在安全点上，就恢复线程，让它“跑”到安全点上。现在几乎没有虚拟机实现采用抢先式中断来暂停线程从而响应GC事件。

而主动式中断的思想是当GC需要中断线程的时候，不直接对线程操作，仅仅简单地设置一个标志，各个线程执行时主动去轮询这个标志，发现中断标志为真时就自己中断挂起。轮询标志的地方和安全点是重合的，另外再加上创建对象需要分配内存的地方。下面代码清单3-4中的test指令是HotSpot生成的轮询指令，当需要暂停线程时，虚拟机把0x160100的内存页设置为不可读，线程执行到test指令时就会产生一个自陷异常信号，在预先注册的异常处理器中暂停线程实现等待，这样一条汇编指令便完成安全点轮询和触发线程中断。

代码清单3-4　轮询指令

0x01b6d627：call 0x01b2b210；OopMap{[60]=Oop off=460} ；*invokeinterface size ；-Client1：main@113（line 23）
；{virtual_call}
0x01b6d62c：nop ；OopMap{[60]=Oop off=461} ；*if_icmplt ；-Client1：main@118（line 23）
0x01b6d62d：test%eax，0x160100；{poll}
0x01b6d633：mov 0x50（%esp），%esi
0x01b6d637：cmp%eax，%esi

安全区域

使用Safepoint似乎已经完美地解决了如何进入GC的问题，但实际情况却并不一定。Safepoint机制保证了程序执行时，在不太长的时间内就会遇到可进入GC的Safepoint。但是，程序“不执行”的时候呢？所谓的程序不执行就是没有分配CPU时间，典型的例子就是线程处于Sleep状态或者Blocked状态，这时候线程无法响应JVM的中断请求，“走”到安全的地方去中断挂起，JVM也显然不太可能等待线程重新被分配CPU时间。对于这种情况，就需要安全区域（Safe Region）来解决。

安全区域是指在一段代码片段之中，引用关系不会发生变化。在这个区域中的任意地方开始GC都是安全的。我们也可以把Safe Region看做是被扩展了的Safepoint。

在线程执行到Safe Region中的代码时，首先标识自己已经进入了Safe Region，那样，当在这段时间里JVM要发起GC时，就不用管标识自己为Safe Region状态的线程了。在线程要离开Safe Region时，它要检查系统是否已经完成了根节点枚举（或者是整个GC过程），如果完成了，那线程就继续执行，否则它就必须等待直到收到可以安全离开Safe Region的信号为止。

到此，笔者简要地介绍了HotSpot虚拟机如何去发起内存回收的问题，但是虚拟机如何具体地进行内存回收动作仍然未涉及，因为内存回收如何进行是由虚拟机所采用的GC收集器决定的，而通常虚拟机中往往不止有一种GC收集器。

yangjava

垃圾收集算法