[数据结构与算法]垃圾回收与算法

stop the world

由并行转变为串行，利用网路延迟的时间，刚好配上，让用户感觉不到世界的停止。解决垃圾线程和用户线程之间的并发问题。

等待所有用户线程进入安全点后并阻塞，做一些全局性操作的行为。当程序运行到这些“安全点”的时候就会暂停所有当前运行的业务线程（Stop The World 所以叫STW），暂停后再找到“GC Roots”进行关系的组建，进而执行标记和清除。在执行垃圾收集算法时，Java应用程序的其他所有线程都被挂起（除了垃圾收集帮助器之外）。Java中一种全局暂停现象，全局停顿，所有Java代码停止，native代码可以执行，但不能与JVM交互；这些现象多半是由于gc引起。

垃圾回收

明确什么是垃圾

垃圾回收的前提是得明确什么是垃圾，得快速定位到垃圾所处的位置，由此引发思考，如何定位垃圾？有以下种方法

1. 引用计数法

   对于某个对象而言，只要程序中持有该对象的引用，则说明此对象不是垃圾，如果一个对象没有任何指针对其引用，则它便是垃圾。

   **弊端：**相互引用的两者，永远不会被回收。引发思考，能不能大部分时间使用应用计数法，到某时刻才使用可达性分析。

2. 可达性分析

   通过GC Root的对象，开始向下寻找，看某对象是否可达。能作为GC Root：类加载器、Thread、虚拟机栈的本地变量，static成员、常量引用、本地方法栈变量等。

   **弊端：**相对于计数法，相对耗时。

3. …

垃圾收集算法

定位垃圾，回收垃圾的方法论，有以下算法

1. 标记-清除(Mark-Sweep)

   **标记：**找出内存中需要回收的对象，并将其标记。此时堆中所有的对象都会被扫描一遍，从而才能确定哪些是需要回收的垃圾，比较耗时。

   **清除：**清除被标记的对象，释放内存空间。

   **缺点：**两个过程都比较耗时，效率不高，会产生大量不连续的内存碎片，空间碎片太多可能会导致以后程序运行过程中需要分配大对象时，无法找到足够大的连续内存，而不得不提前触发另外一次垃圾收集回收动作。

2. 标记-整理(Mark-Compact)

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

3. 复制(Copying)

   将内存划分为两块相等的区域，每次只使用其中一块，空间换时间。

4. …

分代收集算法

Young区

使用复制算法，因为对象生命周期比较短，使用复制算法效率比较高

Old区

使用标记清除或标记整理，生命周期比较长，复制来复制去没必要，不如做个标记再清理。

双指针

Lispa2算法，3根指针，遍历3次，第一次计算需要去的位置，第二次更新引用，第三次挪对象

垃圾收集器

收集算法是内存回收的方法论，那么垃圾收集器就是内存回收的具体实现，也就是落地。

Serial

是最古老最基本的收集器，单线程收集器，在工作期间会STW，适用于内存比较小的嵌入式设备。

优点：拥有很高的单线程收集效率

缺点：收集过程去要暂停所有工作线程

算法：复制算法

适用范围：新生代

应用：Client模式下默认的新生代收集器

设置参数

-XX:+UseSerialGC

ParNew

可理解为Serial收集器的多线程版本，适用于相对时间有要求的场景，比如Web 。

优点：在多线程环境下，比Serial效率高

缺点：收集过程暂停所有用户线程，单CPU时比Serial效率低

算法：复制算法

运行在Server模式下虚拟机首选的新生代收集器

设置参数

# 指定使用CMS后，会默认使用ParNew作为新生代收集器
-XX:+UseConcMarkSweepGC
# 强制指定使用ParNew
-XX:+UseParNewGC
# 指定垃圾收集的线程数量，ParNew默认开启的收集线程与CPU的数量相同
-XX:ParallelGCThreads

Parallel Scavenge

和ParNew类似，但它更关注系统吞吐量。吞吐量越大，则意味着垃圾收集时间越短，用户代码可充分利用CPU资源，尽快完成运算任务，适用于科学计算等弱交互场景。

例如系统共运行100分钟，垃圾收集时间1分钟，则吞吐量=（100-1）/100=99%。

# 控制最大的垃圾收集停顿时间
-XX:MaxGCPauseMillis
# 直接设置吞吐量的大小
-XX:GCTimeRatio
# 开启这个参数后，就不用手工指定一些细节参数，如：新生代的大小（-Xmn）、Eden与Survivor区的比例（-XX:SurvivorRation）、晋升老年代的对象年龄（-XX:PretenureSizeThreshold）等；JVM会根据当前系统运行情况收集性能监控信息，动态调整这些参数，以提供最合适的停顿时间或最大的吞吐量，这种调节方式称为GC自适应的调节策略（GC Ergonomiscs）
-XX:+UseAdptiveSizePolicy

Serial Old

Serial收集器的老年代版本，适用于内存比较小的嵌入式设备。单线程收集器。算法：标记-整理

Parallel Old

Parallel Scavenge 的老年代版本收集器，使用多线程和标记-整理算法进行垃圾回收，吞吐量优先，适用于科学计算等弱交互场景。

设置参数

-XX:+UseParallelOldGC

CMS

Concurrent Mark Sweep是一款以获取最短回收停顿时间为目的的收集器。适用于相对时间有要求的场景，比如Web 。采用标记-清除算法。

工作过程

1. 初始标记：标记Roots能直接关联到的对象，会Stop The World，但速度很快
2. 并发标记：进行GC Roots Tracing
3. 重新标记：修改并发标记因为用户程序变动的内容，会Stop The World，但速度很快
4. 并发清除：

设置参数

-XX:+UseConcMarkSweepGC

G1

适用于相对时间有要求的场景，比如Web 。

特点

1. 并行与并发
2. 分代收集（但不是物理隔离，而是一个一个大小相等的独立区域Region，不需要连续）
3. 空间整合（标记整理-清除算法，不会导致空间碎片化）
4. 可预测的停顿（比CMS更先进的地方在于能让使用者指定一个长度为M毫秒的时间片段，消耗在垃圾收集上的时间不能超过M毫秒，这就刚好和一个网络延迟匹配上，用户感觉不到程序的卡顿）

工作过程

1. 初始标记：标记GC Roots 能直接关联的对象，并修改TAMS的值，STW
2. 并发标记：从GC Roots进行可达性分析，找出所有存活的对象，与用户线程并发执行
3. 最终标记：修正并发标记阶段因为用户程序变动的数据，STW
4. 筛选回收：对各个Region的回收价值和成本进行排序，根据用户所期望的GC停顿时间指定回收计划

设置参数

# 指定使用G1收集器
-XX:+UseG1GC：
# 当整个Java堆的占用率达到参数值时，开始并发标记阶段；默认为45
-XX:InitiatingHeapOccupancyPercent
# 为G1设置暂停时间目标，默认值为200毫秒
-XX:MaxGCPauseMillis
# 设置每个Region大小，范围1MB到32MB；目标是在最小Java堆时可以拥有约2048个Region
-XX:G1HeapRegionSize

吞吐量和停顿时间

停顿时间越短就越适合需要和用户交互的程序，良好的响应速度能提升用户体验；高吞吐量则可以高效地利用CPU时间，尽快完成程序的运算任务，主要适合在后台运算而不需要太多交互的任务。这两个指标也是评价垃圾回收器好处的标准，其实调优也就是在观察者两个变量。

停顿时间

垃圾收集器 进行 垃圾回收终端应用执行响应的时间

吞吐量

运行用户代码时间 / (运行用户代码时间+垃圾收集时间)

如何选垃圾收集器

官网 ：https://docs.oracle.com/javase/8/docs/technotes/guides/vm/gctuning/collectors.html#sthref28

• 优先调整堆的大小让服务器自己来选择
• 如果内存小于100M，使用串行收集器 如果是单核，并且没有停顿时间要求，使用串行或JVM自己选
• 如果允许停顿时间超过1秒，选择并行或JVM自己选
• 如果响应时间最重要，并且不能超过1秒，使用并发收集器

JVM参数

#（1）串行
-XX：+UseSerialGC
-XX：+UseSerialOldGC
#（2）并行(吞吐量优先)：
-XX：+UseParallelGC
-XX：+UseParallelOldGC
#（3）并发收集器(响应时间优先)
-XX：+UseConcMarkSweepGC
-XX：+UseG1G咕