备战面试日记（2.4） - （JVM.GC算法）

备战面试日记（2.4） - （JVM.GC算法）

本人本科毕业，21届毕业生，一年工作经验，简历专业技能如下，现根据简历，并根据所学知识复习准备面试。

记录日期：2022.1.2

大部分知识点只做大致介绍，具体内容根据推荐博文链接进行详细复习。

文章目录

• • JVM - GC算法
  • • 对象判定是否回收（前置知识点）
    • • 引用计数法
      • 可达性分析算法
      • 再谈引用（见1.3 - JUC）
      • 对象回收前的标记过程
      • 回收方法区
      • • 判定常量是否废弃?
        • 判定类型是否废弃?
        • 为什么要回收方法区？
    • 垃圾回收算法（重点）
    • • 分代收集理论
      • • 为什么要分区？
        • 具体如何分区？
        • 跨代引用的问题？
        • 垃圾回收按区域区分的名称定义（必知）
        • • Partial GC
          • Partial GC - Minor GC / Young GC
          • Partial GC - Major GC / Old GC
          • Partial GC - Mixed GC
          • Full GC
      • 标记-清除算法
      • • 两个阶段
        • 两个缺点
      • 标记-复制算法
      • 标记-整理算法
    • HotSpot的算法细节实现（垃圾收集器前置知识点）
    • • 根节点枚举
      • 安全点
      • • 介绍
        • 安全点一般选在什么时机？
        • 如何让垃圾收集发生时让所有线程都跑到安全点后停顿下来？
        • 为什么主动式中断要轮询标志？
      • 安全区域
      • • 起因
        • 介绍
      • 记忆集与卡表
      • • 给好xdm讲简单点（概括）
      • 写屏障
      • 并发的可达性分析
      • • 起因
        • 三色标记法
        • • 标识产生的问题
          • 标记的解决方案

JVM - GC算法

参考《深入理解JVM虚拟机》第3章 - 垃圾收集器与内存分配策略，这块内容还是看书最详细。

对象判定是否回收（前置知识点） 引用计数法

给对象中添加一个引用计数器，每当有一个地方引用它时，计数器值就加1；当引用失效时，计数器值就减1；任何时刻计数器为0的对象就是不可能再被使用的。

引用计数算法（Reference Counting）的实现简单，判定效率也很高，在大部分情况下它都是一个不错的算法。但是，至少主流的Java虚拟机里面没有选用引用计数算法来管理内存，其中最主要的原因是它很难解决对象之间相互循环引用的问题。

可达性分析算法

通过一系列的称为**“GC Roots”的对象作为起始点**，从这些节点开始向下搜索，搜索所走过的路径称为引用链（Reference Chain），当一个对象到GC Roots没有任何引用链相连（用图论的话来说，就是从GC Roots到这个对象不可达）时，则证明此对象是不可用的。

如图所示（拷于囧辉的文章），对象object 5、object 6、object 7虽然互相有关联，但是它们到GC Roots是不可达的，所以它们将会被判定为是可回收的对象。

在Java语言中，可作为GC Roots的对象包括下面几种：

• 虚拟机栈（栈帧中的本地变量表）中引用的对象。
• 方法区中类静态属性引用的对象。
• 方法区中常量引用的对象。
• 本地方法栈中JNI（即一般说的Native方法）引用的对象。

再谈引用（见1.3 - JUC）

无论是通过引用计数算法判断对象的引用数量，还是通过可达性分析算法判断对象的引用链是否可达，判定对象是否存活都与“引用”有关。

关于强软弱虚四种引用我已经在 1.3-JUC 的Threadlocal引申中讲过了，这里重申一下。

• 强引用：在程序代码之中普遍存在的，类似“Object obj=new Object()”这类的引用，只要强引用还存在，垃圾收集器永远不会回收掉被引用的对象。
• 软引用：用来描述一些还有用但并非必需的对象，使用SoftReference类来实现软引用，在系统将要发生内存溢出异常之前，将会把这些对象列进回收范围之中进行第二次回收。
• 弱引用：用来描述非必需对象的，使用WeakReference类来实现弱引用，被弱引用关联的对象只能生存到下一次垃圾收集发生之前。
• 虚引用：是最弱的一种引用关系，使用PhantomReference类来实现虚引用，一个对象是否有虚引用的存在，完全不会对其生存时间构成影响，也无法通过虚引用来取得一个对象实例。为一个对象设置虚引用关联的唯一目的就是能在这个对象被收集器回收时收到一个系统通知。

对象回收前的标记过程

即使在可达性分析算法中不可达的对象，也并非是“非死不可”的，这时候它们暂时处于“缓刑”阶段，要真正宣告一个对象死亡，至少要经历两次标记过程：如果对象在进行可达性分析后发现没有与GC Roots相连接的引用链，那它将会被第一次标记并且进行一次筛选，筛选的条件是此对象是否有必要执行finalize()方法。当对象没有覆盖finalize()方法，或者finalize()方法已经被虚拟机调用过，虚拟机将这两种情况都视为“没有必要执行”。
如果这个对象被判定为有必要执行finalize()方法，那么这个对象将会放置在一个叫做F-Queue的队列之中，并在稍后由一个由虚拟机自动建立的、低优先级的Finalizer线程去执行它。这里所谓的“执行”是指虚拟机会触发这个方法，但并不承诺会等待它运行结束，这样做的原因是，如果一个对象在finalize()方法中执行缓慢，或者发生了死循环（更极端的情况），将很可能会导致F-Queue队列中其他对象永久处于等待，甚至导致整个内存回收系统崩溃。finalize()方法是对象逃脱死亡命运的最后一次机会，稍后GC将对F-Queue中的对象进行第二次小规模的标记，如果对象要在finalize()中成功拯救自己——只要重新与引用链上的任何一个对象建立关联即可，譬如把自己（this关键字）赋值给某个类变量或者对象的成员变量，那在第二次标记时它将被移除出“即将回收”的集合;如果对象这时候还没有逃脱，那基本上它就真的被回收了。

finalize()方法仅作为了解即可，在JDK 9中该方法已经被标记为废弃，并添加新的java.lang.ref.Cleaner，提供了更灵活和有效的方法来释放资源。这也侧面说明了，这个方法的设计是失败的，因此更加不能去使用它，它的运行代价高昂，不确定性大，无法保证各个对象的调用顺序。

回收方法区

方法去垃圾回收的“性价比”通常是比较低的，因为在Java堆中，尤其是在新生代中，对常规应用进行一次垃圾收集通常可以回收70%至99%的内存空间，相比之下，方法去回收囿于苛刻的判定条件，其区域垃圾收集的回收成果往往远低于此。

方法区的垃圾收集主要回收两部分内容：

• 废弃的变量
• 不再使用的类型

判定常量是否废弃?

例如一个字符串“java”曾经进入过常量池中，但是当前系统没有任何一个字符串对象的值是“java”，且虚拟机也没有其他变量引用这个字面量，如果此时发生垃圾回收，而且垃圾收集器判断有必要的情况下，这个“java”常量就会被系统清理出常量池。

常量池中的其他类（接口）、方法、字段的符号引用也类似。

判定类型是否废弃?

需要同时满足三个条件：

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

JVM被允许对满足上面三个条件的无用类进行回收，但是不像对象一样，一失去引用就必然被回收。

关于是否被回收在HotSpot虚拟机中提供了-Xnoclassgc参数控制，还可以使用-verbose:class以及-XX:+TraceClass-Loading、-XX:+TraceClassUnLoading查看类加载和卸载信息。其中-verbose:class以及-XX:+TraceClass-Loading可以在Product版的虚拟机使用，-XX:+TraceClassUnLoading参数需要FastDebug版的虚拟机支持。

为什么要回收方法区？

在大量使用反射、动态代理、CGLib等字节码框架，动态生成JSP以及OSGi这类频繁自定义类加载的场景中，通常都需要Java虚拟机具备类型卸载的能力，以保证不会对方法去造成过大的内存压力。

垃圾回收算法（重点）

目前的主流垃圾回收器都是遵循“分代收集”的理论来设计的。

算法思想总结有三种：标记-清除算法、标记-整理算法、标记-复制算法。

分代收集理论

当前商业虚拟机的垃圾收集器，大多数都遵循“分代收集”（Generational Collection）的理论进行设计，它建立在两个分代假说之上：

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

这两个分代假说共同奠定了多款常用的垃圾收集器的一致的设计原则：收集器应该将Java堆分出不同的区域，然后根据回收对象依据的年龄（年龄即熬过垃圾收集过程的次数）分配到不同的区域存储。

为什么要分区？

通过把他们分区，虚拟机便可以使用较低的频率来回收这个区域，同时兼顾了垃圾收集的时间开销和内存的空间有效利用。

具体如何分区？

分为新生代和老年代，这样就可以根据各个年代的特点采用最适当的收集算法。

在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。

而老年代中因为对象存活率高、没有额外空间对它进行分配担保，就必须使用**“标记—清理”或者“标记—整理”算法**来进行回收。

跨代引用的问题？

分代收集并非只是简单划分内存区域那么容易，它至少存在一个明显的困难：对象不是孤立的，对象之间会存在跨代引用。

问题起因 ： 假设现在进行一次Minor GC，但是有可能老年代的对象引用了新生代的对象，为了找出存活的对象，就必须额外遍历一遍老年代的所有对象保证可达性分析的结果正确性，反之同样，但是遍历对内存回收负担更大。

解决方案 ：在新生代上建立一个全区的数据结构，被称为“记忆集”（Remembered Set），这个结构把老年代分为若干块，标记出老年代的哪一块内存会存在跨代引用。此后当发生Minor GC时，只有包含跨代引用的小块内存里的对象才会被加入到GC Roots进行扫描

垃圾回收按区域区分的名称定义（必知）

因为上面提到了Minor GC，这里把针对其他不同分代产生垃圾收集的名词进行介绍：

Partial GC

部分收集（Partial GC）：指不是完整收集整个Java堆。

Partial GC - Minor GC / Young GC

新生代收集（Minor GC / Young GC）：指新生代的垃圾收集。

Partial GC - Major GC / Old GC

老年代收集（Major GC / Old GC）：指老年代的垃圾收集。

Partial GC - Mixed GC

混合收集（Mixed GC）：指收集整个新生代以及部分老年代的垃圾收集。（G1收集器中）

Full GC

整堆收集（Full GC）：收集整个堆和方法区的垃圾收集。

标记-清除算法

主要记住三个特征：内存不规整、耗时、老年代。

两个阶段

1. 首先标记出所有需要回收的对象。
2. 标记完成后，统一回收掉所有被标记的对象。

当然也可以反过来，标记存活对象，回收未被标记的对象。

两个缺点

1. 效率不稳定，标记和清除这两个过程的执行效率是基于对象数量的增长而降低的
2. 内存碎片多，标记清除后会产生大量不连续的内存碎片，碎片太多会导致后面分配较大的对象时因为找不到连续的内存区域而再触发一次垃圾回收。

标记-复制算法

主要记住两个特征：新生代、浪费一半空间。

它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。

这样使得每次都是对整个半区进行内存回收，内存分配时也就不用考虑内存碎片等复杂情况，只要移动堆顶指针，按顺序分配内存即可，实现简单，运行高效。只是这种算法的代价是将内存缩小为了原来的一半，未免太高了一点。

标记-整理算法

主要记住两个特征：STW、老年代。

标记清除和它的本质差异就是：前者是非移动式，后者是移动式。

标记过程与“标记-清除”算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存。

但是为了移动对象的线程安全，必须全程暂停用户应用程序才能进行。

基于上述的算法，是否移动对象都有弊端，移动则内存回收时更复杂，不移动则内存分配时更复杂。

HotSpot的算法细节实现（垃圾收集器前置知识点）

这部分我会写的比较粗糙，只关注重点问题，因为比较倾向于复习使用，详细内容建议阅读《深入理解JVM虚拟机》第三版的81页 - 89页。

根节点枚举

在HotSpot中，使用一组成为OopMap的数据结构来存放GC Roots的引用。

好处：当类加载完成时，HotSpot就会把对象内什么偏移量上是什么类型的数据计算出来，也会在特定的位置记录下栈和寄存器里哪些位置是引用。这样就可以在收集器扫描时直接获取信息，而不用区方法区等GC Roots开始查找。

OopMap全称就是Ordinary Object Pointer Map，上面记录的key是栈上的本地变量，value是堆上引用。

安全点

主要记住，它主要应用于用户线程运行状态下。

介绍

使用OopMap可以使HotSpot快速完成GC Roots的枚举，但是每一条指令生成对应的OopMap会占用大量存储空间，空间成本会很大。所以采取的方案是，只是在“特定的位置”记录这些信息，这些位置被称为安全点（Safepoint）。

安全点一般选在什么时机？

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

如何让垃圾收集发生时让所有线程都跑到安全点后停顿下来？

这里一般采取抢先式中断（不采用了）、主动式中断两种方案：

• 抢先式中断：抢先式中断不需要线程的执行代码主动去配合，在垃圾收集发生时，系统首先把所有用户线程全部中断，如果发现有用户线程中断的地方不在安全点上，就恢复这条线程执行，让其运行一会再重新中断，直到跑到安全点上。但现在几乎没有虚拟机实现采用抢先式中断来暂停线程响应GC事件。
• 主动式中断：主动式中断的思想是当垃圾收集需要中断线程的时候，不直接对线程 *** 作，而是设置一个标志位，各个线程执行过程时会不停地主动去轮询这个标志，一旦发现中断标志为真时就自己在最近的安全点上主动中断挂起。轮询标志的地方和安全点是重合的，另外还要加上所有创建对象和其他需要在Java堆上分配内存的地方，这是为了检查是否即将要发生垃圾收集，避免没有足够内存分配新对象。

为什么主动式中断要轮询标志？

轮询 *** 作主要是HotSpot使用内存保护陷阱的方式，把轮询 *** 作精简至一条汇编指令。

安全区域

主要记住，它应用于用户线程睡眠或是阻塞。

起因

安全点机制保证了程序执行时，在不太长的时间内就会遇到可进入垃圾收集过程的安全点。但是，当程序不执行即没有分配处理器时间时，典型场景即用户线程处于sleep状态或者blocked状态，这时线程不能走到安全点，虚拟机也不可能持续等待线程重新被激活分配处理器时间。对于这种情况，就必须引入安全区域（Safe Region）来解决。

介绍

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

当用户线程执行到处安全区域里面的代码时，首先会标识自己已经进入了安全区域，这段时间若发生垃圾收集就不会管这些已声明自己在安全区域内的线程了。当线程要离开安全区域时，它要检查虚拟机是否已经完成了根节点枚举（或者垃圾收集过程中其它需要暂停用户线程的阶段），如果完成了，那线程就当作没事发生过，继续执行；否则它就必须一直等待，直到收到可以离开安全区域的信号为止。

记忆集与卡表

注意一点，卡表是记忆集的一种实现。

在前面分代收集理论中提到过记忆集，这是为解决对象跨代引用所带来的问题，垃圾收集器在新生代中建立了名为记忆集（Remembered Set）的数据结构，用以避免把整个老年代加入GC Roots的扫描范围。事实上，并非只有新生代、老年代之间有跨代引用问题，所有涉及部分区域收集行为的垃圾收集器，都存在这个问题。

记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。

这种记录全部含跨代引用对象的实现方案，无论是空间占用还是维护成本都很高，所以其实只要通过记忆集来判断出某一块非收集区域是否存在指向了收集区域的指针就可以了，所以在实现记忆集的时候，可以选用更为粗犷的记忆粒度来节省记忆集的存储和维护成本，下面列举了一些可供选择的记忆精度：

• 字长精度：每个记录精确到一个机器字长，该字包含跨代指针。
• 对象精度：每个记录精确到一个对象，该对象里有字段含有跨代指针。
• 卡精度：每个记录精确到一块内存区域，该区域内有对象含有跨代指针。

其中第三点卡精度指的是用一种称为“卡表”（Card Table）的方式去实现记忆集，这也是目前最常用的一种记忆集的实现形式。它定义了记忆集的记录精度，与堆内存的映射关系等。

卡表最简单的形式可以只是一个字节数组，而HotSpot虚拟机确实也是这样做的。下面这段代码是HotSpot默认的卡表标记逻辑。

CARD_TABLE [this address >> 9] = 0;

字节数组CARD_TABLE的每一个元素都对应着其标识的内存区域中一块特定大小的内存块，这个内存块被称作**“卡页”**（Card Page）。一般来说，卡页大小都是以2的N次幂的字节数，通过上面代码可以看出HotSpot中使用的卡页是2的9次幂，即512字节。如果卡表标识的内存区域的起始地址是0x0000的话，数组CARD_TABLE的第0、1、2号元素分别对应的地址范围是0x00000x01FF、0x02000x03FF、0x400~0x5FF的卡页地址块。

一个卡页的内存中通常包含不止一个对象，只要卡页内有一个（或更多）对象的字段存在着跨代指针，那就将对应卡表的数组元素值标为1，称为这个元素变脏，没有则标识为0。在垃圾收集发生时，只要筛选出卡表中变脏的元素，就能轻易得出哪些卡页内存块中包含跨代指针，把它们加入GC Roots中一并扫描。

给好xdm讲简单点（概括）

记忆集是用来解决跨代引用的。

卡表是记忆集的一种实现。

HotSpot中卡表是一个字节数组，每个元素代表一个内存块，叫做卡页。

如果对应的卡页中有跨代指针，就把对应卡页的值标为1。

垃圾回收时从对应卡页中找出脏元素，加入GC Roots对象进行扫描。

写屏障

在HotSpot虚拟机里是通过写屏障（Write Barrier）技术维护卡表状态的。写屏障可以看做在虚拟机层面对“引用类型子段赋值”这个动作的AOP切面，在引用赋值对象时会产生一个环形通知，供程序执行额外的动作，也就是说赋值的前后都在写屏障的覆盖范畴内。在赋值前的部分写屏障叫做写前屏障（Pre-Write Barrier），在赋值后的则叫做写后屏障（Post-Write Barrier）。

应用写屏障后，虚拟机就会为所有赋值 *** 作生成相应的指令，一旦收集器在写屏障中增加了更新卡表 *** 作，无论更新的是不是老年代对新生代对象的引用，每次只要对引用进行更新，就会产生额外的开销，不过这个开销与Minor GC时扫描整个老年代的代价相比还是低很多的。

除了写屏障的开销外，卡表在高并发场景下还面临着“伪共享”（False Sharing）问题。伪共享是处理并发底层细节时一种经常需要考虑的问题，现代中央处理器的缓存系统中是以缓存行（Cache Line）为单位存储的，当多线程修改相互独立的变量时，如果这些变量恰好共享同一个缓存行，就会彼此影响（写回、无效化或者同步）而导致性能降低，这就是伪共享问题。

为了避免伪共享问题，一种简单的解决方案是不采用无条件的写屏障，而是先检查卡表标记，只有当该卡表元素未被标记过时才将其标记为脏，即将卡表更新的逻辑变为以下代码所示：

if (CARD_TABLE [this address >> 9] != 0)
    CARD_TABLE [this address >> 9] = 0;

在JDK7之后，HotSpot虚拟机增加了一个新的参数：-XX:+UseCondCardMark，用来决定是否开启卡表更新的条件判断。开启会增加一次额外判断的开销，但能避免伪共享问题，两者各有性能损耗，是否打开要根据应用实际运行情况来进行测试权益。

AOP为Aspect Oriented Programming的缩写，意为面向切面编程，通过预编译方式和运行期动态代理实现程序功能的统一的一种技术，这里可以顺便学习一下Spring AOP。

并发的可达性分析 起因

当前主流语言的垃圾收集器都是以可达性分析算法来判定对象是否存活的，可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析，这意味着必须全程冻结用户线程的运行。在根节点枚举这个步骤中，由于GC Roots相比整个Java堆中的全部对象毕竟来说还是极少数，且在各种优化技巧的加持下，它带来的停顿已经是非常短暂且相对固定的了。

三色标记法

若想解决或者降低用户线程的停顿，就要先搞清楚为什么必须在一个能保障一致性的快照上才能进行对象图的遍历？为了能解释清楚这个问题，我们引入了三色标记（Tri-color-Marking）作为工具来辅助推导，把遍历对象图过程中遇到的对象，按照“是否访问过”这个条件标记成以下三种颜色：

• 白色：**表示对象尚未被垃圾收集器访问过。**显然在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在可达性分析结束的阶段，仍然是白色的对象，即代表不可达。
• 黑色：表示对象已被垃圾收集器访问过，且这个对象的所有引用都已被扫描过。黑色的对象代表已经扫描过，它是安全存活的，如果有其它对象引用指向了黑色对象，无需重新扫描一遍。黑色对象不可能直接（不经过灰色对象）指向某个白色对象。
• 灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。

标识产生的问题

若用户线程与收集器是并发工作的，收集器在对象图上标记颜色，同时用户线程在修改引用关系——即修改对象图的结构，这样可能出现两种后果，一种是把原本消亡的对象错误标记为存活，这种情况可容忍且可在下次收集清理掉就好；

另一种是把原本存活的对象错误标记为已消亡，程序肯定会因此而发生错误。下图演示了这样的致命错误是如何产生的。

标记的解决方案

wilson于1994年在理论上证明了，当且仅当以下两个条件同时满足时，会产生“对象消失”的问题，即原本应该是黑色的对象被误标为白色：

• 赋值器插入了一条或多条从黑色对象到白色对象的新引用。
• 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。

因此，我们要解决并发扫描时的对象消失问题，只需破坏这两个条件中任意一个即可。由此分别产生了两种解决方案：

• 增量更新（Incremental Update）
• 原始快照（Snapshot At The Beginning, SATB）

增量更新要破坏的是第一个条件，当黑色对象插入到指向新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。可简单理解为黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了。

原始快照要破幻的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次。可简化理解为无论引用关系是否删除与否，都会按照刚开始扫描那一刻的对象图快照来进行搜索。

以上无论是对引用关系的记录还是删除，虚拟机的记录 *** 作都是通过写屏障实现的。

简而言之，增量更新是一次快照，记录新插入的引用；原始快照，是直接使用快照。

CMS是基于增量更新的，G1、Shenandoah是基于原始快照的。