Java GC基本算法

秒速五厘米 2022-06-10 04:59 76阅读 0赞

# **Java GC基本算法** #

1、JVM内存组成结构

JVM内存结构由堆、栈、本地方法栈、方法区等部分组成，结构图如下所示：

1)堆  
所有通过new创建的对象的内存都在堆中分配，其大小可以通过\-Xmx和\-Xms来控制。堆被划分为新生代和旧生代，新生代又被进一步划分为Eden和Survivor区，Survivor由FromSpace和ToSpace组成，结构图如下所示：  
  
  
新生代。新建的对象都是用新生代分配内存，Eden空间不足的时候，会把存活的对象转移到Survivor中，新生代大小可以由\-Xmn来控制，也可以用\-XX:SurvivorRatio来控制Eden和Survivor的比例。  
旧生代用于存放新生代中经过多次垃圾回收(也即Minor GC)仍然存活的对象  
2)栈  
每个线程执行每个方法的时候都会在栈中申请一个栈帧，每个栈帧包括局部变量区和操作数栈，用于存放此次方法调用过程中的临时变量、参数和中间结果  
3)本地方法栈  
用于支持native方法的执行，存储了每个native方法调用的状态  
4)方法区

存放了要加载的类信息、静态变量、final类型的常量、属性和方法信息。JVM用持久代(或者叫做永久代，PermanetGeneration)来存放方法区，可通过\-XX:PermSize和\-XX:MaxPermSize来指定最小值和最大值。

在过去（自定义类加载器还不是很常见的时候），类大多是”static”的，很少被卸载或收集，因此被称为“永久的(Permanent)”。同时，由于类class是JVM实现的一部分，并不是由应用创建的，所以又被认为是“非堆(non-heap)”内存。  
在JDK8之前的HotSpot JVM，存放这些”永久的”的区域叫做“永久代(permanent generation)”。永久代是一片连续的堆空间，在JVM启动之前通过在命令行设置参数\-XX:MaxPermSize来设定永久代最大可分配的内存空间，默认大小是64M（64位JVM由于指针膨胀，默认是85M）。**永久代的垃圾收集是和老年代(old generation)捆绑在一起的，因此无论谁满了，都会触发永久代和老年代的垃圾收集。不过，一个明显的问题是，当JVM加载的类信息容量超过了参数\-XX：MaxPermSize设定的值时，应用将会报OOM的错误。**

**永久代在JDK8中被完全的移除了。所以永久代的参数\-XX:PermSize和\-XX：MaxPermSize也被移除了。**  
在JDK8中,classe metadata(the virtual machines internal presentation of Java class),被存储在叫做Metaspace的native memory。一些新的flags被加入：  
\-XX:MetaspaceSize，class metadata的初始空间配额，以bytes为单位，达到该值就会触发垃圾收集进行类型卸载，同时GC会对该值进行调整：如果释放了大量的空间，就适当的降低该值；如果释放了很少的空间，那么在不超过MaxMetaspaceSize（如果设置了的话），适当的提高该值。  
\-XX：MaxMetaspaceSize，可以为class metadata分配的最大空间。默认是没有限制的。  
\-XX：MinMetaspaceFreeRatio,在GC之后，最小的Metaspace剩余空间容量的百分比，减少为class metadata分配空间导致的垃圾收集  
\-XX:MaxMetaspaceFreeRatio,在GC之后，最大的Metaspace剩余空间容量的百分比，减少为class metadata释放空间导致的垃圾收集  
默认情况下，class metadata的分配仅受限于可用的native memory总量。可以使用MaxMetaspaceSize来限制可为class metadata分配的最大内存。当class metadata的使用的内存达到MetaspaceSize(32位clientVM默认12Mbytes,32位ServerVM默认是16Mbytes)时就会对死亡的类加载器和类进行垃圾收集。设置MetaspaceSize为一个较高的值可以推迟垃圾收集的发生。

介绍完了JVM内存组成结构，下面我们再来看一下JVM垃圾回收机制。

2、Java GC基本算法

2.1、引用计数（reference counting）  
    原理：此对象有一个引用，则\+1；删除一个引用，则\-1。只用收集计数为0的对象。  
    缺点： （1）无法处理循环引用的问题。如：对象A和B分别有字段b、a，令A.b=B和B.a=A，除此之外这2个对象再无任何引用，那实际上这2个对象已经不可能再被访问，但是引用计数算法却无法回收他们。（2）引用计数的方法需要编译器的配合。编译器需要为此对象生成额外的代码。如赋值函数将此对象赋值给一个引用时，需要增加此对象的引用计数。还有就是，当一个引用变量的生命周期结束时，需要更新此对象的引用计数器。  
引用计数的方法由于存在显著的缺点，实际上并未被JVM所使用。  
2.2、复制（copying）  
    原理：把内存空间划分为2个相等的区域，每次只使用一个区域。垃圾回收时，遍历当前使用区域，把正在使用的对象复制到另外一个区域。  
    优点：不会出现碎片问题。  
    缺点：  
（1）暂停整个应用。  
（2）需要2倍的内存空间。  
2.3、标记\-清扫（Mark-and-sweep）  
    原理：对于“活”的对象，一定可以追溯到其存活在堆栈、静态存储区之中的引用。这个引用链条可能会穿过数个对象层次,算法基于有向图，采用深度优先搜索。  
第一阶段：从GC roots开始遍历所有的引用，对有活的对象进行标记。  
第二阶段：对堆进行遍历，把未标记的对象进行清除。  
优点：解决了循环引用的问题。  
    缺点：  
（1）暂停整个应用；  
（2）会产生内存碎片。  
（3）不管你这个对象是不是可达的，即是不是垃圾，都要在清楚阶段被检查一遍，非常耗时.

sun前期版本就是用这个技术。  
2.4、标记\-压缩（Mark-Compact）  
    第一阶段：同标记\-清扫，标记活的对象，  
第二阶段：这个阶段将所有做了标记的活动对象整理到堆的底部  
    优点：  
（1）避免标记扫描的碎片问题；  
（2）避免停止复制的空间问题。  
2.5、分代（generational collecting）     
原理：基于对象生命周期分析得出的垃圾回收算法。把对象分为年轻代、年老代、持久代，对不同的生命周期使用不同的算法（2-3方法中的一个即4自适应）进行回收。

J2SE1.2以后使用此算法

JVM分别对新生代和旧生代采用不同的垃圾回收机制  
2.5.1、新生代的GC（Minor GC）：  
指发生在新生代的垃圾收集动作，因为 Java 对象大多都具备朝生夕灭的特性，所以 Minor GC 非常频繁，一般回收速度也比较快。  
新生代通常存活时间较短，因此基于Copying算法来进行回收，所谓Copying算法就是扫描出存活的对象，并复制到一块新的完全未使用的空间中，对应于新生代，就是在Eden和FromSpace或ToSpace之间copy。新生代采用空闲指针的方式来控制GC触发，指针保持最后一个分配的对象在新生代区间的位置，当有新的对象要分配内存时，用于检查空间是否足够，不够就触发GC。当连续分配对象时，对象会逐渐从eden到survivor，最后到旧生代，  
2.5.2、旧生代的GC（Major GC  / Full GC）：  
指发生在老年代的 GC。旧生代与新生代不同，对象存活的时间比较长，比较稳定，因此采用标记(Mark)算法来进行回收，所谓标记就是扫描出存活的对象，然后再进行回收未被标记的对象，回收后对用空出的空间要么进行合并，要么标记出来便于下次进行分配，总之就是要减少内存碎片带来的效率损耗。  
MajorGC 的速度一般会比 Minor GC 慢 10倍以上。  
Thinking in java给java gc取了一个罗嗦的称呼：“自适应、分代的、停止\-复制、标记\-扫描”式的垃圾回收器。  
导致Gc的情况：  
1、tenured被写满  
2、perm被写满  
3、System.gc()的显式调用。  
4、上一次GC之后heap的各域分配策略动态变化。

# JVM之GC算法和种类 #

*  [垃圾收集算法][Link 1]
 *  [可达性分析算法][Link 2]
    
     *   *  [强引用StringReference][StringReference]
         *  [软引用SoftReference][SoftReference]
         *  [弱引用WeakReference][WeakReference]
         *  [虚引用PhantomReference][PhantomReference]
     *  [引用计数算法Reference Counting][Reference Counting]
     *  [标记-清除算法Mark-Sweep][-_Mark-Sweep]
     *  [复制算法Copying][Copying]
     *  [标记-整理Mark-Compact][-_Mark-Compact]
     *  [分代收集算法Generational Collection][Generational Collection]
 *  [HotSpot的算法实现][HotSpot]
    
     *  [枚举GC Roots根节点][GC Roots]
     *  [安全点SafePoint][SafePoint]
     *  [安全区域Safe Region][Safe Region]

# 垃圾收集算法 #

这里说说5种GC算法，在说GC算法前，先谈谈判断对象是否活着的可达性分析算法

*  可达性分析算法
 *  引用计数算法
 *  标记-清除算法
 *  标记-整理算法
 *  复制算法
 *  分代收集算法

# 可达性分析算法 #

垃圾回收，首先要判断对象是否还活着.

Java通過可达性分析(Reachability Analysis)来判定对象是否存活

算法基本思路：   
\- 通过一系列称为”GC Roots”的对象作为起点，从这些节点开始向下搜索，搜索走过的路径，叫做引用链(Reference Chain)   
\- 当一个对象到GC Roots没有任何引用链相连，从图论来说，就是从GC Roots到对象不可达，此时判定对象不可用

Java中，可作为GC Roots的對象包括四种

*  VM Stack(栈帧中的本地变量表)中引用的对象
 *  本地方法栈中JNI(即Navtive方法)引用的对象
 *  方法区中类静态属性引用的对象
 *  方法区中常量引用的对象

> 创建–>可达<–>可恢复–>不可达–>垃圾回收

### 强引用StringReference ###

*  创建对象，并把对象赋给一个引用变量，程序通过这个引用变量来操作对象，对象和数组都采用了强引用。
 *  一个对象被一个或以上引用变量引用，则处于可达状态，不会被GC

### 软引用SoftReference ###

*  要用java.lang.ref.SoftReference实现
 *  描述有用但非必需的对象
 *  内存空间足够时，不会被GC；否则，可能会被GC
 *  常用于对内存敏感的程序中
 *  get()获取引用的对象

### 弱引用WeakReference ###

*  java.lang.ref.WeakReference实现
 *  描述非必需对象
 *  不管内存是否足够，都会被GC
 *  get()获取引用的对象

### 虚引用PhantomReference ###

*  java.lang.ref.PhantomRefernce必须和java.lang.ref.RefernceQueue引用队列联合使用
 *  类似于没有引用，和没有引用的效果大致相同
 *  主要用于跟踪对象被垃圾回收的状态
 *  !!! get()无法获取引用的对象
 *  GC后，虚引用会被放入引用队列

即使在可达性分析算法中不可达的对象，也并非是“非死不可”，这时还处于“缓刑”状态，真正标记一个对象的死亡，至少经历两次标记过程

*  对象在可达性分析后，发现没有GC Roots相连接的引用链，此时被第一次标记，且进行一次筛选   
    
    
     *  筛选的条件是：是否有必要执行对象的finalize()方法
     *  对象沒有重写finalze()方法，或者finalize()已经被虚拟机调用过–>没必要执行
 *  如果被判定为“有必要执行”，那么对象会被放到一个叫做F-Queue的队列中，并在稍后由一个JVM自动建立的、低优先级的Finalizer线程去执行finalize()方法.
 *  稍后，GC将对F-Queue中的对象进行第二次小规模的标记. 如果对象没有在finalize()中复活，那基本真的被回收了

## 引用计数算法(Reference Counting) ##

*  老牌的垃圾回收算法
 *  给对象添加一个引用计数器，有一个地方引用它时，计数器+1；引用失效时，-1；计数器为0，对象就是不可能再被使用
 *  客观来说，实现简单，判定效率高
 *  应用如：微软的Component Object Model技术,Python,ActionScript3
 *  但主流Java虚拟机没有用，因为很难解決对象间的循环引用问题
 *  引用和去引用伴随+,-，影响性能

这涉及到如何判定对象是否可达，或者说是否活着，被引用着

## 标记-清除算法(Mark-Sweep) ##

*  最基础的算法，分为“标记”，“清除”两个阶段
 *  这是所有收集算法的基础，后续算法都是基于这种思路，并对其不足进行改进而得到的。
 *  首先，标记出需要回收的对象
 *  接着，标记完成后，统一回收所有标记的对象
 *  主要问题:
    
     *  效率: 标记和清除两个过程的效率都不高
     *  空间碎片: 标记清除后会产生大量不连续的内存碎片，碎片过多会导致大对象无法分配到足够的连续内存，从而不得不提前触发GC，甚至Stop The World

## 复制算法(Copying) ##

*  为解决效率问题，复制算法出现了
 *  将内存分为大小相等的两块，每次只用一块
 *  在一块内存中，当它用完了，就把还或者的对象复制到另外一块大小相等的内存中，连续存储；同时，一次过清理已经使用过的内存空间
 *  相当于每次都回收整个半区，不用考虑碎片问题，只需移动堆顶指针，按顺序分配，实现简单，运行高效
 *  主要问题   
    
    
     *  效率: 在对象存活率较高时，复制操作次数多，效率降低
     *  空间: 內存缩小了一半；需要額外空间做分配担保(老年代)
 *  From Survivor, To Survivor使用的就是复制算法。老年代不使用这种算法

## 标记-整理(Mark-Compact) ##

*  根据老年代的特点，提出了标记-整理/压缩算法
 *  标记阶段与标记-清除算法一样
 *  后续，让存活对象都向一端移动，对齐，直接清理掉端边界以外的内存
 *  老年代使用的算法

## 分代收集算法(Generational Collection) ##

当前的商业虚拟机的垃圾回收都采用 分代收集 算法。根据对象存活周期的不同，将内存划分为几块。

一般将Java堆分为新生代和老年代。

新生代: 每次GC都有大批对象死去，只有少量存活

*  使用复制算法，只需要复制少量存活的对象

老年代：对此存活率高，没有额外空间做分配担保

*  使用 标记-清除,标记-整理两种算法

# HotSpot的算法实现 #

首先，要解决的，是可达性分析，从GC Roots中找对象是否有可达的引用链。

## 枚举GC Roots根节点 ##

可做GC Roots节点的，上文说过，主要有 全局性的引用(包括常量或类静态属性)，执行上下文(栈帧中的本地变量表和JNI引用的对象). 问题是，现在的应用，仅方法区就数百Megabyte，如果逐个检查这里边的引用，必然消耗很多时间

可达性分析必须在一个能确保一致性的内存快照中进行，分析期间，内存系统不能出现变化，否则，会出现分析不正确的情况，例如，前脚这边标记了A对象不可达，此时内存系统还在运行，万一A又被引用了，但A已经被标记为不可达。所以，得有GC停顿,号称几乎不会GC停顿的CMS收集器，在枚举根节点时，也必须停顿

目前主流VM使用准确式GC，所以不需要一个不漏地检查完所有的全局和上下文的引用的位置，虚拟机有办法直接得知哪些地方存放着对象的引用

HotSpot的实现中，使用一组叫做OopMap的数据结构来达到目的。

> (1)类加载完成时，HotSpot就把对象内什么偏移量上是什么类型的数据计算出来。   
> (2)在JIT编译过程中，会在特定的位置记录下栈和寄存器中，哪些位置是引用

这样，GC扫描时，就可以直接得知这些信息了

## 安全点(SafePoint) ##

在OopMap(Ordinary Object Pointer Map)的协助下，HotSpot可以快速准确完成GC Roots枚举。

问题是，引用关系变化，OopMap内容变化的指令非常多，如果为每一条指令生成对应的OopMap,那会需要有大量的空间，GC的空间成本会变得很高

事实上，HotSpot没有为每条指令生成OopMap，前面说了，是在“特定位置”，这个特定位置，就是安全点SafePoint. 程序执行不是所有地方都停顿下来GC，而是到安全点，才停顿。

安全点选定

所以，安全点的选定，不能太过少，否则GC等待时间太长，产生OOM；也不能太过频繁，否则会增大运行时的负荷。

因此，安全点选择的准则：

*  是否具有让程序长时间执行的特征

具有这个特征的就是指令序列复用，例如方法调用，循环跳转，异常跳转。所以，具有这些功能的指令才会产生SafePoint

让所有线程跑到最近的安全点

另一个问题，发生GC时，如何让所有线程跑到最近的安全点，除了JNI调用的线程。

两种方案

*  抢占式中断(Preemptive Suspension)   
    
    
     *  GC来时，先中断线程，若发现线程不在安全点上，恢复线程，让它跑的安全点
     *  现在，几乎没有VM使用这种方式
 *  主动式中断(Voluntary Suspension)   
    
    
     *  不主动操作线程，GC来时，简单地设个标记，各个线程执行时主动轮询这个标记，发现为真时，自己中断挂起
     *  轮询标记的地方和安全点重合，另外加上创建对象时需要分配内存的地方

## 安全区域(Safe Region) ##

SafePoint只是解决获得CPU执行时间的线程，在不太长的时间内，可以遇到GC的SafePoint的问题。

但没有分配到CPU执行时间的线程，如Sleep,Block状的线程，它们无法响应JVM的中断请求，跑到SafePoint中断挂起，JVM显然也不会等待线程重新获得CPU时间

对这一问题，需要安全区域Safe Region

安全区域

*  一段代码片段中，引用关系不会发生变化
 *  这个区域之中，任意地方开始GC，都是安全的
 *  可以看作SafePoint的扩展

当线程执行到安全区域中的代码时，首先标识自己已经进入Safe Region。那么，这段时间里JVM发起GC时，就不用管标识自己在Safe Region状态的线程了，因为这些线程的引用关系不会发生变化。

线程离开Safe Region时，要检查系统是否已经完成GC Roots枚举或者整个GC过程。如果沒有，就必須等待，直到收到可以安全离开的信号为止；如果完成了，线程继续执行。

[Link 1]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E5%9E%83%E5%9C%BE%E6%94%B6%E9%9B%86%E7%AE%97%E6%B3%95
[Link 2]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E5%8F%AF%E8%BE%BE%E6%80%A7%E5%88%86%E6%9E%90%E7%AE%97%E6%B3%95
[StringReference]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E5%BC%BA%E5%BC%95%E7%94%A8stringreference
[SoftReference]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E8%BD%AF%E5%BC%95%E7%94%A8softreference
[WeakReference]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E5%BC%B1%E5%BC%95%E7%94%A8weakreference
[PhantomReference]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E8%99%9A%E5%BC%95%E7%94%A8phantomreference
[Reference Counting]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E5%BC%95%E7%94%A8%E8%AE%A1%E6%95%B0%E7%AE%97%E6%B3%95reference-counting
[-_Mark-Sweep]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E6%A0%87%E8%AE%B0-%E6%B8%85%E9%99%A4%E7%AE%97%E6%B3%95mark-sweep
[Copying]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E5%A4%8D%E5%88%B6%E7%AE%97%E6%B3%95copying
[-_Mark-Compact]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E6%A0%87%E8%AE%B0-%E6%95%B4%E7%90%86mark-compact
[Generational Collection]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E5%88%86%E4%BB%A3%E6%94%B6%E9%9B%86%E7%AE%97%E6%B3%95generational-collection
[HotSpot]: http://blog.csdn.net/qq_33938256/article/details/52502488#hotspot%E7%9A%84%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0
[GC Roots]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E6%9E%9A%E4%B8%BEgc-roots%E6%A0%B9%E8%8A%82%E7%82%B9
[SafePoint]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E5%AE%89%E5%85%A8%E7%82%B9safepoint
[Safe Region]: http://blog.csdn.net/qq_33938256/article/details/52502488#%E5%AE%89%E5%85%A8%E5%8C%BA%E5%9F%9Fsafe-region