垃圾收集器与内存分配策略

Java与C++之间有一堵由动态内存分配和垃圾收集技术所围成的高墙，墙外面的人想进去，墙里面的人想出来。

概述

垃圾收集需要考虑三件事情：

哪些内存需要回收？
什么时候回收？
如何回收？

Java内存运行时区域分为五个部分，其中程序计数器、虚拟机栈、本地方法栈3个区域随线程而生，随线程而灭。栈中的栈帧随着方法的进入和退出执行出栈和入栈。这几个区域的内存分配和回收都具备确定性，不需要考虑如何回收。

而堆和方法区这两个区域则有着很显著的不确定性，只有处于运行期间，才能知道程序会创建哪些对象，创建多少个对象，这部分内存的分配和回收是动态的。

对象存活与死亡

可达性分析算法

这个算法的基本思路就是通过一系列称为GC Roots的根对象作为起始节点集，根据引用关系向下搜索。

固定可作为GC Roots的对象包括：

在虚拟机栈中引用的对象，譬如各个线程被调用的方法堆栈中使用到的参数、局部变量和临时变量。
在方法区中类静态属性引用的对象，譬如Java类的引用类型静态变量。
在方法区中常量引用的对象，譬如字符串常量池里的引用。
在本地方法栈中JNI引用的对象
Java虚拟机内部的引用，譬如基本数据类型对应的Class对象，一些常驻的异常对象，系统类加载器等。
所有被同步锁(synchronized关键字)持有的对象。
反映Java虚拟机内部情况的JMXBean，JVMTI中注册的回调

根据垃圾收集器以及当前回收的内存区域不同，还可以有其他对象临时加入，共同构成GC Roots。

譬如分代收集和局部回收，如果只针对堆中某个区域发起垃圾收集时，这个区域的对象可能被位于堆中其他区域的对象所引用，这时候就需要将这些关联区域的对象也一并加入GC Roots。

生存还是死亡

即使不可达对象，也不是直接被回收。要真正宣告对象死亡至少要经历2次标记过程。

如果对象在进行可达性分析后发现没有与GC Roots相连接的引用链，那它将会被第一次标记，随后进行一次筛选，筛选的条件是此对象是否有必要执行finalize()方法。假如对象没有覆盖finalize()方法，或者方法已经被虚拟机调用过，那么JVM将这两种情况都是为“没有必要执行”。

如果对象被判定为有必要执行finalize()方法，那么该对象将会被放置在一个名为F-Queue的队列之中，并在稍后由一条虚拟机自动建立的、低调度优先级的Finalizer线程去执行它们的finalize()方法。

执行finalize()方法不代表一定会等待它运行结束。如果某个对象的finalize()方法执行缓慢，甚至发生死循环，将会导致F-Queue队列中其他对象永久处于等待。

finalize()方法是对象逃脱死亡的最后一次机会。任何一个对象的finalize()方法都只会被系统自动调用一次。稍后收集器将对F-Queue中的对象进行第二次小规模标记，如果对象要在finalize()中成功拯救自己，则只需要重新与引用链上的任何一个对象建立关联即可。

回收方法区

方法区的垃圾回收包含两部分：废弃的常量和不再使用的类。

回收废弃常量与回收堆中的对象类似。

回收废弃的类则需要满足以下三个条件：

该类的所有实例都已经被回收。Java堆内不存在该类及其任何派生子类的实例。
加载该类的类加载器已经被回收。这个条件除非是经过设计的可替换类加载器的场景，如JSP的重加载等，否则很难达成。
该类对应的java.lang.Class对象没有在任何地方被引用。无法在任何地方通过反射访问该类的方法。

垃圾收集算法

分代收集理论

弱分代假说：绝大多数对象都是朝生夕灭
强分代假说：熬过越多次垃圾收集过程的对象就越难以消亡

这两个分代假说共同奠定了收集器的一致的设计原则：收集器应该将Java堆划分出不同的区域，然后将回收对象依据其年龄分配到不同的区域之中存储。

但是新生代中的对象完全有可能被老年代所引用的，所以不得不额外遍历整个老年代中的所有对象。无疑会增加性能负担，所以添加了第三条经验法则：

跨代引用假说：跨代引用相对于同代引用来说仅占极少数。

依据这条假说，不必为了少量的跨代引用去扫描整个老年代，也不必浪费空间专门记录每一个对象是否存在及存在哪些跨代引用，**只需在新生代上建立一个全局的数据结构(记忆集Remembered Set)**，这个结构把老年代划分为若干小块，标识出老年代的哪一块内存会存在跨代引用。此后发生Minor GC时加入GC Roots即可。

标记-清除算法

缺点：

执行效率不稳定。如果大量对象需要回收，则标记和清除过程的执行效率都随对象数量增长而降低。
导致内存空间的碎片化问题。标记、清楚之后会产生大量不连续的内存碎片。

标记-复制算法

缺点：

如果多数对象都是存活的，算法将会产生大量的内存间复制的开销。
可用内存缩小为原来的一半。

新生代的内存布局：新生代分为一块较大的Eden空间和两块较小的Survivor空间。每次分配内存只使用Eden和其中一块Survivor。发生垃圾搜集时，将Eden和Survivor中仍然存活的对象一次性复制到另一块Survivor空间上，然后直接清理。

当一块Survivor空间不足以容纳一次Minor GC之后存活的对象时，就需要依赖老年代进行分配担保(Handle Promotion)。新生代无法容纳的对象会直接进入老年代

标记-整理算法

缺点：

老年代有大量对象存活区域，移动存活对象并更新引用是一种极为负重的操作，且必须全程暂停用户程序才能进行(Stop The World)。

关注吞吐量的Parallel Scavenge收集器是基于标记-整理算法的；关注延迟的CMS收集器是基于标记-清除算法的。

`HotSpot`的算法细节实现

根节点枚举

迄今为止，所有收集器在根节点枚举这一步骤时都是必须暂停用户线程的，所以会面临STW。

HotSpot使用OopMap的数据结构记录对象内什么偏移量上是什么类型的数据计算出来，在即时编译过程中，也会在特定的位置记录下栈里和寄存器里哪些位置是引用。这样收集器在扫描时就能获取，并不需要一个不漏地从GC Roots开始查找。

安全点

HotSpot不会为每条指令都生成OopMap，只是在特定的位置记录这些信息，这个位置被称为安全点。

安全点要求程序必须执行到达安全点后才能够暂停。因此：

安全点的选定不能太少以至于让收集器等待时间过长；
也不能太多以至于过分增大运行时的内存负荷。

安全点位置的选取基本上是以“是否具有让程序长时间执行的特征”为标准进行选定的。“长时间执行”的最明显特征就是指令序列的复用，例如方法调用、循环跳转、异常跳转等。

对于安全点，如何在垃圾收集发生时让所有线程跑到最近的安全点，然后停顿？

抢占式中断：如果发现用户线程中断的地方不在安全点上，就恢复执行，等待一定时间重新中断，直到跑到安全点上。
主动式中断：当垃圾收集需要中断线程时，不直接对线程操作，而是设置一个标志位。各个线程主动轮询标志，一旦发现中断标志为真时就自己在最近的安全点上主动中断挂起。

安全区域

对于在Sleep和Blocked状态的线程，无法让其主动中断。故引入安全区域解决。

安全区域是指能够确保在某一段代码片段之中，引用关系不会发生变化，因此这个区域中任意地方都能开始垃圾收集。安全区域是被扩展的安全点。

当用户线程进入安全区域里面的代码时，会标识自己进入。这样当垃圾回收时就可以直接进行；当离开安全区域时，要检查虚拟机是否完成了根节点枚举(或其他需要暂停用户线程的阶段)，如果完成，则允许离开；否则一直等待。

记忆集与卡表

记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。记录时并不需要了解跨代指针的全部细节，所以选择更为粗犷的记录粒度。

字长精度：每个记录精确到一个机器字长，该字包含跨代指针。
对象精度：每个记录精确到一个对象，该对象里有字段含有跨代指针。
卡精度：每个记录精确到一块内存区域，该区域内有对象含有跨代指针。这种实现被称为卡表。

HotSpot默认的实现为一个字节数组：

1	CARD_TABLE[address >> 9] = 0

字节数组CARD_TABLE每个元素都对应着其标识的内存区域中一块特定大小的内存块(被称为卡页)。一个卡页的内存中包含不止一个对象，只要有一个对象的字段存在跨代指针，就将对应卡表的位置脏位置1。垃圾收集时，筛选出脏位卡页，加入GC Roots一并扫描。

写屏障

使用卡表来缩减GC Roots扫描范围，但没有解决卡表元素如何维护？何时变脏？

何时变脏？有其他分代区域中对象引用了本区域对象时，对应的卡表元素就应该变脏。时间点原则上发生在引用类型字段赋值的那一刻。
如何变脏？经过即时编译后的代码为机器指令流，所以需要在机器码层面把维护卡表的动作放到每一个赋值操作中。

在HotSpot虚拟机中通过写屏障(Write Barrier)维护卡表状态。写屏障可以看作在虚拟机层面对引用类型字段赋值这个动作的AOP切面。如下：

void oop_field_store(oop* field,oop new_value) {
    // 引用字段赋值
    *field = new_value;
    // 写后屏障，完成卡表更新
    post_write_barrier(field,new_value);
}

除了写屏障的开销外，卡表在高并发场景下还面临着**伪共享(False Sharing)**问题。现代CPU的缓存系统中是以缓存行为单位存储的，当多线程修改互相独立的变量时，如果这个变量恰好共享同一个缓存行，就会彼此影响。

一种简单的解决方案是先检查卡表标记，只有当该卡表元素未被标记过时才变脏。

1
2
3

if (CARD_TABLE[address >> 9] != 0) {
    CARD_TABLE[address >> 9] = 0
}

并发的可达性分析

三色标记