Java虚拟机垃圾收集算法实现

垃圾收集算法实现

垃圾收集算法实现必须考虑运行效率。

对象存活判定算法实现

对象存活判定算法都使用可达性分析算法实现

可达性分析算法实现时有哪些难点

1. GC Roots枚举耗时。
   原因：可作为GC Roots节点主要在全局引用（方法区中常量、类静态属性）和执行上下文（虚拟机栈栈帧中本地变量表）中对象。可能方法区中就有数百M, 遍历所有全局引用和执行上下文，必然会消耗很长时间。
2. 可达性分析导致GC停顿。
   原因：可达性分析需要系统的一致性快照，分析期间，必须暂停所有线程，直到分析完成，以保证分析结果的准确性。这就是GC停顿，也被称为Stop The World。

GC Roots枚举耗时长，又引起长时间的GC停顿，程序性能就太低了，所以需要尽可能减少GC Roots枚举耗时。

如何解决可达性分析耗时问题

空间换时间，使用被称为OopMap的数据结构来存放对象的引用，就不必遍历所有的全局引用和执行上下文，直接检查OopMap中引用即可。

1. 全局引用，即方法区中类静态属性引用和常量引用。在类加载时计算记录引用位置并放入OopMap中。
2. 执行上下文，即虚拟机栈栈帧中本地变量表中引用。在JIT编译时记录引用位置并放入OopMap中。

很多指令都可能引起OopMap内容变化，如果每条指令都改变OopMap，对程序执行效率有很大影响吧，而且也需要更多的额外空间

是的，所以只有在特定的位置，才会去更新OopMap。这些位置被称为安全点。
程序不会在所有地方都可能发生GC,只有在安全点才可能发生GC。先更新OopMap, 然后GC Roots枚举。
安全点的选定不能太少，让GC等待时间很长，也不能太多，影响程序执行效率。

安全点是如何选定的呢

选定标准：是否具有让程序长时间执行的指令。
如：方法调用、循环跳转、异常跳转等。

在多线程下，所有线程是怎么都跑到最近的安全点上再停顿下来呢，毕竟要GC停顿才能进行可达性分析呀

两种方案：

1. 抢先式中断：在GC发生时，所有线程全部中断。如果发现有线程中断的地方不是安全点，就恢复线程，让它跑到安全点上。
   需要对所有线程进行操作，虚拟机不采用。
2. 主动式中断：当GC需要中断线程时，不对线程进行操作，仅仅简单设置一个中断标志。各个线程在跑到安全点时，主动去轮询这个标志，如果中断标志为真时，就自己中断挂起。
   各线程主动配合，虚拟机实现方案。

安全点也要线程跑到安全点才行，如果线程是Sleep或Block状态呢，无法响应jvm中的中断请求呀

是的，这种情况下需要使用安全区域。

安全区域是：在一段代码中，引用关系不会发生变化。在这个区域中任何地方开始GC都是安全的。

1. 线程执行到安全区域
2. 标识自己已经进入了安全区域
3. JVM要发起GC, 过滤标识自己进入安全区域的线程。
4. 线程离开安全区域，检查系统是否完成GC或GC Roots枚举。
5. 完成GC或GC Roots枚举，线程继续执行。
6. 没有完成，线程等待，直到收到可以离开安全区域信号为止。

对象存活判定算法虚拟机实现总结

可达性分析算法实现两大难点

1. GC Roots枚举耗时

• 原因：每次需要遍历方法区和虚拟机栈
• 解决：使用OopMap协助GC Roots枚举
  • 1. 类加载时，计算对象引用位置并存入OopMap中。
  • 2. JIT编译时，计算栈帧中引用位置并存入OopMap中。
  • 问题：很多指令会导致OopMap变化，每条指令都更新OopMap, 影响程序执行效率和需要额外内存空间。
  • 解决：在安全点才会更新OopMap，GC也只会在安全点进行GC停顿。
  • 安全点选定：长时间执行的指令，如：方法调用，循环跳转，异常跳转。
  • 问题：所有线程如何在安全点进行GC停顿。
  • 两种方案：
    • 1. 抢先式中断（非虚拟机实现方案）：GC发生时，中断所有线程，检查线程是否在安全点，不是，恢复线程，跑到最近安全点中断。
    • 2. 主动式中断（虚拟机实现方案）：GC发生时，设置中断标志。所有线程在检查点时轮询中断标志，如果中断标志为真，线程中断挂起。
    • 问题：主动式主断需要线程在安全点去主动轮询，但线程在Sleep或Block状态时无法跑到安全点。
    • 解决：使用安全区域。
      • 安全区域：在一段代码中，引用关系不会发生变化，这段区域任何地方发生GC都是安全的。
      • 问题：线程如何在安全区域进行GC停顿。
      • 1. 线程到安全区域，标识自己已在安全区域。GC发生时，不管标识自己在安全区域的线程。
      • 2. 线程走出安全区域时，检查GC是否完成或GC Roots枚举是否完成。如果完成，则继续执行，如果没有完成，则等待可安全离开安全区域信号。

2. 必须GC停顿

• GC停顿：所有java线程必须暂停，也被称为STW：Stop The World.
• 原因：可达性分析需要在确保一致性的快照中进行，否则引用关系变化，分析的结果就不正确。

垃圾收集器

了解7种垃圾收集器的特点、优缺点、分代、是否支持并发、是否支持多线程、组合和收集流程

垃圾收集器有哪几种, 各有什么特点

1. Serial：新生代收集器，单线程，可以与老年代CMS收集器和Serial Old收集器组合
2. ParNew：新生代收集器，多线程，可以与老年代CMS收集器和Serial Old收集器组合
3. Parallel Scavenge：新生代收集器，多线程，可并行，可以与老年代Serial Old和Parallel Old收集器组合
4. CMS：老年代收集器，多线程，与用户线程并发执行，可以与新生代Serial收集器、ParNew收集器和老年代的Serial Old收集器组合
5. Serial Old：老年代收集器，单线程，可以与新生代三种收集器和老年代CMS收集器组合
6. Parallel Old：老年代收集器，多线程，可并行，可以与新生代Parallel Scavenge收集器组合
7. G1：新生代老年代都适用，多线程，可并行，替代其他所有收集器。

介绍下Serial收集器

Serial收集器是新生代单线程的收集器，在GC时，必须要暂停所有java线程，直到收集结束。

• 优势：在单CPU下收集效率最好，对于运行在Client模式下的虚拟机是很好的选择。
• 缺点：不支持多线程，GC时必须要暂停所有java线程。
• 组合：老年代CMS收集器、Serial Old收集器
• 收集流程：
  1. 新生代空间已满，GC开始，所有java线程在最近的安全点暂停
  2. 单个GC线程执行，新生代使用复制算法
  3. GC结束，所有java线程恢复

介绍下ParNew收集器

ParNew收集器是Serial收集器的多线程版本，支持多线程，其他与Serial基本一致。

• 优势：是唯一和老年代CMS收集器配合使用的新生代多线程收集器
• 缺点：但CPU环境下收集效率并没有Serial收集器好，甚至由于存在线程间的开销，效率更低。
• 组合：老年代CMS收集器、Serial Old收集器
• 收集流程：
  1. 新生代空间已满，GC开始，所有java线程在最近的安全点暂停
  2. 多个GC线程执行，新生代使用复制算法
  3. GC结束，所有java线程恢复

这里的并行和并发分别是什么意思

1. 并行：指多个GC线程同时执行，但java线程是暂停的。
2. 并发：指java线程和GC线程同时执行。

介绍下Parallel Scavenge收集器

Parallel Scavenge收集器是新生代支持多线程的收集器。

与parNew的区别是：Parallel Scavenge收集器目标是达到一个可控制的吞吐量。

• 吞吐量：吞吐量 = 用户代码时间/（用户代码时间+垃圾收集时间），如：虚拟机运行总时间100分钟，垃圾收集1分钟，吞吐量就是99%
• 优势：高交互的程序需要停顿时间很短，而高吞吐量则可以高效率的利用CPU时间，尽快完成程序的运算任务。有自适应调节策略。
• 缺点：无法与老年代的CMS收集器组合。
• 组合：老年代Serial Old、Parallel Old收集器
• 参数设置：
  1. 控制吞吐量
     • -XX:MaxGCPauseMillis ：控制最大GC停顿时间。
       • 说明：设置过小会减少吞吐量和新生代空间，收集频率也会上升。
     • -XX:GCTimeRatio : 设置吞吐量大小。
       • 说明：值范围：0-100，GC时间=1/(1+参数值)
  2. -XX:+UseAdaptiveSizePolicy: 自适应调节开关参数。
     • 说明：开关打开后，不需要手工指定新生代的大小、Eden与Survivor区域的比例、晋升老年代的年龄等细节参数。
     • 虚拟机根据当前系统的运行情况收集性能监控信息，动态调节这些参数以提供最合适的停顿时间或者最大吞吐量。

介绍下Serial Old收集器

Serial Old收集器是Serial收集器的老年代版本，单线程，采用收集-整理算法。

• 优势：可以作为CMS收集器的后备方案，当并发收集发生发生Concurrent Mode Failure时使用Serial Old收集器。
• 缺点：单线程，必须暂停所有java线程
• 组合：新生代三种收集器、老年代CMS收集器后备
• 收集流程：
  1. 老年代空间已满，GC开始，所有java线程在最近的安全点暂停
  2. 单个GC线程执行，老年代使用标记-整理算法
  3. 老年代GC结束，所有java线程恢复

介绍下Parallel Old收集器

Parallel Old收集器是老年代支持多线程的收集器，只能与Parallel Scavenge收集器组合，与Parallel Scavenge收集器一样关注吞吐量。

• 收集流程：
  1. 老年代空间已满，GC开始，所有java线程在最近的安全点暂停
  2. 多个GC线程执行，老年代使用标记-整理算法
  3. 老年代GC结束，所有java线程恢复

介绍下CMS收集器

CMS收集器是以获取最短回收停顿时间为目标的收集器，也是第一个低停顿并发收集器。

基于标记-清除算法实现的。

• 收集流程：
  1. 初始标记: 只标记GC Roots能直接关联到的对象，耗时很短，需要暂停所有线程
  2. 并发标记：进行对象可达性分析，可与java线程同时执行，耗时长
  3. 重新标记：修正并发标记期间，因程序继续执行而标记变动的那一部分对象的标记记录，耗时很短，需要暂停所有线程。
  4. 并发清除：清除已死对象内存空间，可与java线程同时执行，耗时长
• 优势：低停顿和支持并发。
• 缺点：
  1. 消耗CPU资源大。
     • 原因：面向并发的程序都会消耗更多CPU资源。
       • 在并发阶段，虽然不会让java线程停顿，但是会因为占用一部分CPU资源而导致应用程序变慢。
       • CMS默认启动的线程数是（CPU数+3）/4。CPU核心超过4时，并发收集线程不少于25%的CPU资源; 小于4时，会消耗一半的CPU资源。
  2. 无法处理浮动垃圾，可能出现Concurrent Mode Failure失败而导致另一次Full GC的产生。
     • 浮动垃圾：由于并发清理阶段java线程也在执行，不断产生的新的垃圾。这部分垃圾在重新标记之后，无法在当前GC中处理，只能等到下一次GC才能清理。
     • 因为浮动垃圾，CMS收集器不能像其他老年代收集器那样，到内存消耗完才触发一次GC, CMS收集器需要在老年代预留足够的空间给浮动垃圾。
     • 如果CMS并发清理期间，预留内存空间无法满足浮动垃圾需要，就会出现一次Concurrent Mode Failure。
     • 这时，虚拟机启用后备方案，使用Serial Old收集器执行一次Full GC，这样停顿时间就很长了。
     • jdk1.5默认设置老年代使用68%空间就触发一次GC，偏保守
     • jdk1.6默认值是92%，有点激进，值太高很容易导致大量的Concurrent Mode Failure，性能降低。
  3. CMS基于标记-清除算法，收集结束会产生大量内存碎片。导致老年代有很多空间，却无法分配大对象，而不得不触发一次Full GC
     • 解决：提供参数：-XX:+UseCMSCompactAtFullCollection, 在CMS进行Full GC时开启内存碎片的合并整理。

介绍下G1收集器

G1收集器特点：

1. 并行和并发
2. 分代收集，不需要其他收集器配合
3. 空间整合
4. 可预测的停顿

分代收集原理：

• 其他收集器收集的范围都是整个新生代或老年代。
• 使用G1收集器，java堆的内存布局与其他收集器不同。
• 整个java堆分为大小相同的独立区域Region，虽然还保留新生代和老年代的概念，但不是物理上的隔离，都是部分不连续Region的集合。
• G1可以采用不同的方式处理新创建的对象，存活了一段时间的对象和熬过多次GC的旧对象。

可预测停顿原理：

• 因为有计划的避免在整个java堆中，进行全区域的垃圾收集
• G1收集器在后台维护一个优先列表，存放各个Region里垃圾的价值大小。价值：回收所获得的空间大小、回收所需的时间。
• 每次根据允许的回收时间，优先回收价值最大的Region。这也是G1名字的由来。
• 这种划分内存空间和优先级的Region回收方式，保证了G1收集器在优先时间内可以获取尽可能高的收集效率。

空间整合原理：

• 从整体上看，G1使用的是标记-整理算法
• 从局部Region上看，G1使用的是复制算法

无论哪一种算法，都不会产生内存碎片。

这种区域划分的思路实现有哪些问题

Region间对象依赖问题。在某个Region中的对象可能被其他任意Region中的对象引用。

在可达性分析中需要扫描整个java堆才能确保准确性，效率太低。

解决方案：空间换时间。

• G1收集器中，Region之间的对象引用使用Remembered Set来避免全堆扫描。
• 每个Region都有与之对应的Remembered Set, 在对引用类型进行写操作时，会中断写操作，检查引用的对象是否处于不同的Region中。
• 如果在不同的Region中，将对象信息存放到被引用对象对应Region的Remembered Set中。
• GC时，在GC Roots枚举中加入Remembered Set的扫描，即可避免全堆扫描也不会有遗漏。

G1收集器流程：

1. 初始标记: 只标记GC Roots能直接关联到的对象，并修改TAMS(Next Top At Mark Start)的值，让下阶段用户程序并发执行时，能在正确可用的Region中创建新对象。耗时短，需要暂停线程。
2. 并发标记：可达性分析，耗时长，与java线程并发执行
3. 最终标记：为了修改在并发标记期，因程序继续执行而导致标记发生改变的那部分标记。
   • 虚拟机将这段时间对象变化记录在Remembered Set Logs中，最终标记阶段需要把Remembered Set Logs中数据合并到Remembered Set中。
   • 需要暂停线程，但多GC线程并行执行。
4. 筛选回收：对各个Region的回收价值和成本进行排序，根据用户期望的GC停顿时间来指定回收计划。可以与java线程并发执行。

7种垃圾收集器总结

1. Serial收集器

• 新生代
• 单线程
• 复制算法
• 组合：老年代的Serial Old，CMS

2. ParNew收集器

• 新生代
• 多线程并行
• 复制算法
• 组合：老年代的Serial Old, CMS

3. Parallel Scavenge收集器

• 新生代
• 多线程并行
• 复制算法
• 目标：可控制的吞吐量
  • 吞吐量：用户线程执行的时间/CPU总时间
  • 参数：
    • 1. 最大GC暂停时间：-XX:MaxGCPauseMillis
    • 2. 吞吐量：-XX:GCTimeRatio
    • 3. 自适应调节：-XX:+UseAdaptiveSizePolicy

4. Serial Old 收集器

• 老年代
• 单线程
• 标记-整理算法
• 可作为CMS收集器的后备处理方案

5. Parallel Old收集器

• 老年代
• 多线程并行
• 标记-整理算法
• 目标：可控制的吞吐量
• 只能与新生代的Parallel Scavenge收集器配合使用

6. CMS收集器

• 老年代
• 多线程并行并发执行
• 标记清除算法
• 优点：低GC停顿，支持并发
• 缺点：
  • 消耗更多CPU资源
  • 无法处理浮动垃圾，可能导致Concurrent Mode Failure，从而产生一次Full GC
  • 使用标记-清除算法，产生大量内存碎片
• 流程：
  1. 初始标记：只标记GC Roots直接关联的对象。耗时短，暂停所有线程。
  2. 并发标记：可达性分析。耗时长，并发执行。
  3. 重新标记：修正并发标记期间因程序继续执行导致的引用变化部分。耗时短，暂停所有线程。
  4. 并发清除：清除所有已死对象内存空间。可并发执行。

7. G1收集器

• 特点：
  • 并发和并行
  • 分代收集，无需其他收集器配合
  • 空间整理
  • 可预测的GC停顿
• 分代收集原理：
  • 内存布局变化：
    • 其他收集器：分为新生代、老年代，新生代分为Eden和Survivor
    • G1收集器：将内存划分为很多大小相同的区域Region, 新生代老年代不存在物理上的区分，都是不连续的Region集合。
    • G1收集器可以使用不同的方式处理新生对象、存活了一段时间的对象和熬过多次GC的旧对象。
• 空间整理原理：
  • 整体上看：使用标记-整理算法，不产生内存碎片
  • 局部Region上看：使用复制算法，也不产生内存碎片
• 可预测的GC停顿
  • 有计划的避免进行整个堆全区域的GC
  • 虚拟机后台维护一张优先表，存放各个Region的回收价值（回收空间大小和回收耗时）
  • 在目标时间下优先回收价值最大的Region，在指定时间下获取尽可能高的回收效率。
• 并发和并行原理：
  • 和CMS收集器类似的收集流程：
    • 初始标记：只标记GC Roots直接关联的对象，并修改TAMS值，让用户线程在下阶段可以在正确可用的Region分配新对象。耗时短，暂停所有线程。
    • 并发标记：可达性分析。耗时长，与用户线程并发执行。
    • 最终标记：修正并发期间因程序继续执行导致的引用变化部分。并发期间标记变化记录在Remembered Set Log中，最终标记时合并到Remembered Set中。耗时短，暂停所有线程。
    • 筛选回收：对各个Region根据回收价值和回收成本进行排序，根据用户期望时间制定回收计划。
• 问题：某个region对象中可能会被任意Region中对象引用，可达性分析时需要全堆扫描
  • 解决：空间换时间
    • 每个region都维护一个Remembered Set，当有引用写操作时，中断写，检查引用对象是否在其他Region中。
    • 如果是，把对象信息放到被引用对象的Region对应的Remembered Set中
    • 在GC时，GC Roots枚举中加入Remembered Set扫描。即可避免全堆扫描也不会有遗漏。

想共同学习jvm的可以加我微信：1832162841，或者进QQ群：982523529