<commit_before>---
title: [JVM虚拟机]垃圾回收算法
date: 2017-08-18 21:22:59
tags:
- java
- jvm
categories:
- java
- jvm
author: 为为
avatar: /images/favicon.png
---

# 引言
  C和C++ 程序员能够直接操作内存，凭自己的需要来决定何时去申请多大内存，何时去释放这块内存。他们甚至可以使用指针，来确定的去操作某块内存地址。作为后来者的JAVA远远不如他们强大，我认识的JAVA程序员可能有半数都从未去关注过内存。在使用JAVA进行业务开发时，我们不需要去关注对象到底存储在内存的哪个位置，也不需要关注这个对象到底占用了多大的内存空间，更不需要特意的为某个对象去释放内存空间。需要我们关注的，只有如何完成产品需求，在规定时间内交付合格的产品给客户。如果你对编程的看法跟上面所述的类似，或者你很认同“完成比完美更重要”这条工程师信条，那么这篇文章就不太适合你来阅读了。  
  内存控制给编程界造成了一个具有魔性的圈，圈内的人想出去，圈外的人想进来。就像C程序员早就受够了内存的申请与释放的折磨，受够了各种内存错误。而很多像你一样的JAVA程序员，立志要写出高性能应用的人，一直在用心地思索怎么才能写出性能更好的多线程应用，当这个追求达到一定层次的时候，你甚至已经开始在乎JAVA垃圾回收所消耗的时间了。由于JAVA自身的限制，我们没办法进入到内存控制的圈内，但我们可以通过设置JVM参数等方式，选择适当的垃圾收集器或设置垃圾回收线程对JAVA的垃圾回收机制进行优化。  
  本文的重点是介绍JVM虚拟机下常用的垃圾回收算法的理论知识，并不介绍具体算法实现代码。在阅读本文之前，希望读者已经掌握了JVM的内存划分设计、对象引用的可达性分析算法与JAVA的四种对象引用级别（Strong Reference/Soft Reference/Weak Reference/Phantom Reference）等相关知识。

# 垃圾回收算法
## 标记-清除算法（Mark-Sweep）
  > 首先标记出所有需要回收的对象，在标记完成后统一回收所有被标记的对象。

  标记-清除算法的工作过程如图1所示。  
  ![](https://weiwei02.coding.me/images/java/jvm/垃圾回收标记-清除.png)  
  图1 标记-清除算法示意图  

  * 优点： 算法简单清晰，其它垃圾收集算法都是据此算法的思想并对其不足改进而得到的。  
  * 缺点： 1.效率低，标记和清除需要遍历内存，效率极低。2.回收内存之后产生大量的内存碎片，当内存碎片过多时，应用需要给大对象分配内存时无法分配连续内存。

## 复制算法（Copying）
  > 将内存按容量划分为完全等大小的两块，每次只使用其中一块内存。当这一块内存用完后，将还活着的对象全部复制到另一块上面，然后把这一块上已使用的内存空间全部清理掉。其示意图如图二所示。  

  ![](https://weiwei02.coding.me/images/java/jvm/垃圾回收复制.png)  
  图2 复制算法示意图

  * 优点： 实现简单，运行高效。每次都是对整个半区进行内存回收，内存分配时无需考虑内存碎片等复杂情况。  
  * 缺点： 浪费内存空间。在最坏的情况下，这种垃圾回收算法可能浪费了一半的内存空间。  

  在JAVA应用中，90%之上的对象的生存时间都极短，所以JVM把内存分为一块较大的Eden空间和两块较小的Survivor空间，每次只使用Eden和其中一块Survior空间。当需要进行垃圾回收时，将Eden和Survivor中还处于可达状态的对象一次性的复制到另一块Survivor空间中，最后清空Eden和刚刚使用的Survivor空间。当Survivor空间不够用时，还会将长时间存活的对象转存的老年代中。在HotSpot虚拟机中，默认的Eden和Survivor空间的比例是8:1，这样可以做到只浪费10%的内存。  

## 标记-整理算法（Mark-Compact）
  > 标记-整理算法的标记过程与标记-清除算法的标记过程类似，但在标记完成后并不是直接对可回收的对象进行清理，而是让所有正在存活的对象都向前端移动，然后直接清理掉边界以外的内存。其示意图见图3.  

  ![](https://weiwei02.coding.me/images/java/jvm/垃圾回收标记-整理.png)  
  图3 标记-整理算法示意图  

  * 优点： 节省内存空间，提升内存运用率，且不会产生内存碎片。  
  * 缺点： 性能低。  

## 分代收集算法（Generational Collection）
  > 根据对象的存活时间把内存分为新生代和老年代，根据个代对象的存活特点，每个代采用不同的垃圾回收算法。  

  分代收集就是根据不同代的特性，使用最合适的垃圾回收算法进行垃圾回收。如新生代中，每次垃圾收集都会有大量的对象死去，只有极小部分对象存活，所以更适合复制算法。老年代中对象存活率高，且没有额外的内存空间为它进行分配担保，所以更适合用标记-清除或标记-整理算法。

# HotSpot算法实现
## 枚举根节点（GC Roots）
  在垃圾回收时，我们要想办法找出哪些对象是存活的，一般会选取一些被称为GC Root的对象,从这些对象开始枚举。在进行GC Root枚举时要求所有对象停下来，也就是JVM所称的“Stop the world”。所有的算法实现都会将虚拟机停下来的，否则分析结果的准确性将无法保证。  
  由于HotSpot采用准确式GC，该技术主要功能就是让虚拟机可以准确的知道内存中某个位置的数据类型是什么，比如某个内存位置到底是一个整型的变量，还是对某个对象的 reference。这样在进行 GC Roots 枚举时，只需要枚举 reference 类型的即可。在能够准确地确定 Java 堆和方法区等 reference 准确位置之后，HotSpot 就能极大地缩短 GC Roots 枚举时间，所以当执行系统停顿下来之后，虚拟机不需要遍历所有的根节点和上下文去确定GC Roots，而是存在着一个OopMap的数据结构来达到这个目的。  
  在类加载完成的时候，虚拟机就会把什么类的什么偏移上是什么类型的数据计算出来。在JIT编译的时候也会在特定位置记下在寄存器和栈中哪些位置是引用，GC在扫描时就可直接得到信息。

##  安全点(Safepoint)

  Safepoint：会导致 OopMap 内容变化的指令非常多，如果为每一条指令都生成对应的 OopMap，那么将需要大量的额外空间，这样对导致 GC 成本很高，所以 HotSpot 只在 “特定位置” 记录这些信息，这些位置被称为 安全点(Safepoint)。并非程序在任意时刻都可以停顿下来进行 GC，而只有程序到达 安全点(Safepoint) 以后才可以停顿下来进行 GC；所以安全点既不能太少，以至于 GC 过程等待程序到达安全点的时间过长，也不能太多，以至于 GC 过程带来的成本过高。

  由于在 GC 过程中必须保证程序已执行，那么也就是说 必须等待所有线程都到达安全点上方可进行 GC。一般来说有两种解决方案可以选择：

  * 抢先式中断：不需要线程的执行代码去主动配合，当发生 GC 时，先强制中断所有线程，然后如果发现某些线程未处于安全点，那么将其唤醒，直至其到达安全点再次将其中断；这样一直等待所有线程都在安全点后开始 GC。现在几乎没有虚拟机使用这种方式。  

  * 主动式中断：不强制中断线程，只是简单地设置一个中断标记，各个线程在执行时轮询这个标记，一旦发现标记被改变(出现中断标记)时，那么将运行到安全点后自己中断挂起；目前所有商用虚拟机全部采用主动式中断。

# 安全区(Safe Region)

  安全点机制仅仅是保证了程序执行时不需要太长时间就可以进入一个安全点进行 GC 动作，但是当特殊情况时，比如线程休眠、线程阻塞等状态的情况下，显然 JVM 不可能一直等待被阻塞或休眠的线程正常唤醒执行，此时就引入了安全区的概念。  
  安全区(Safe Region)：安全区域是指在一段代码区域内，对象引用关系等不会发生变化，在此区域内任意位置开始 GC 都是安全的。线程运行到Safe Region中的代码时，首先标记自己进入了安全区，然后在这段区域内，如果线程发生了阻塞、休眠等操作，JVM 发起 GC 时将忽略这些处于安全区的线程。当线程再次被唤醒时，首先他会检查是否完成了 GC Roots枚举(或这个GC过程)，然后选择是否继续执行，否则将继续等待 GC 的完成。

## 引用

  本文是对class文件的学习笔记，笔记的内容并非是原创，而是大量参考其它资料。在写作本文的过程中引用了以下资料，为为在此深深谢过以下资料的作者。
  1. 《The Java® Virtual Machine Specification · Java SE 8 Edition》
  2. 《深入理解Java虚拟机：JVM高级特性与最佳实践/周志明著.——2版.——北京：机械工业出版社，2013.6》
  3. 《Java Platform, Standard Edition HotSpot Virtual Machine Garbage Collection Tuning Guide》

    非原创声明
      >本文并非我的原创文章，而是我学习jvm时的笔记。文中的材料与数据大部分来自于其它资料，详细请查看本文的引用章节。

## 关于

    本项目和文档中所用的内容仅供学习和研究之用，转载或引用时请指明出处。如果你对文档有疑问或问题，请在项目中给我留言或发email到 <EMAIL>  
    我的[github](https://github.com/weiwei02/): https://github.com/weiwei02/  
    我相信技术能够改变世界。<commit_msg>定版垃圾收集算法<commit_after>---
title: JVM虚拟机-垃圾回收算法
date: 2017-08-18 21:22:59
tags:
- java
- jvm
categories:
- java
- jvm
author: 为为
avatar: /images/favicon.png
---

# 引言
  C和C++ 程序员能够直接操作内存，凭自己的需要来决定何时去申请多大内存，何时去释放这块内存。他们甚至可以使用指针，来确定的去操作某块内存地址。作为后来者的JAVA远远不如他们强大，我认识的JAVA程序员可能有半数都从未去关注过内存。在使用JAVA进行业务开发时，我们不需要去关注对象到底存储在内存的哪个位置，也不需要关注这个对象到底占用了多大的内存空间，更不需要特意的为某个对象去释放内存空间。需要我们关注的，只有如何完成产品需求，在规定时间内交付合格的产品给客户。如果你对编程的看法跟上面所述的类似，或者你很认同“完成比完美更重要”这条工程师信条，那么这篇文章就不太适合你来阅读了。  

  内存控制给编程界造成了一个具有魔性的圈，圈内的人想出去，圈外的人想进来。就像C程序员早就受够了内存的申请与释放的折磨，受够了各种内存错误。而很多像你一样的JAVA程序员，立志要写出高性能应用的人，一直在用心地思索怎么才能写出性能更好的多线程应用，当这个追求达到一定层次的时候，你甚至已经开始在乎JAVA垃圾回收所消耗的时间了。由于JAVA自身的限制，我们没办法进入到内存控制的圈内，但我们可以通过设置JVM参数等方式，选择适当的垃圾收集器或设置垃圾回收线程对JAVA的垃圾回收机制进行优化。  

# 概述
  本文的重点是介绍JVM虚拟机下常用的垃圾回收算法的理论知识，并不介绍具体算法实现代码。在阅读本文之前，希望读者已经掌握了JVM的内存划分设计、对象引用的可达性分析算法与JAVA的四种对象引用级别（Strong Reference/Soft Reference/Weak Reference/Phantom Reference）等相关知识。在本文之后，我还会再去整理一些关于垃圾收集器等方面的知识。文中所涉及的代码或理论都已在JDK8中进行验证。

# 垃圾回收算法
## 标记-清除算法（Mark-Sweep）
  > 首先标记出所有需要回收的对象，在标记完成后统一回收所有被标记的对象。

  标记-清除算法的工作过程如图1所示。  
  ![](https://weiwei02.coding.me/images/java/jvm/垃圾回收标记-清除.png)  
  图1 标记-清除算法示意图  

  * 优点： 算法简单清晰，其它垃圾收集算法都是据此算法的思想并对其不足改进而得到的。  
  * 缺点： 1.效率低，标记和清除需要遍历内存，效率极低。2.回收内存之后产生大量的内存碎片，当内存碎片过多时，应用需要给大对象分配内存时无法分配连续内存。

## 复制算法（Copying）
  > 将内存按容量划分为完全等大小的两块，每次只使用其中一块内存。当这一块内存用完后，将还活着的对象全部复制到另一块上面，然后把这一块上已使用的内存空间全部清理掉。其示意图如图二所示。  

  ![](https://weiwei02.coding.me/images/java/jvm/垃圾回收复制.png)  
  图2 复制算法示意图

  * 优点： 实现简单，运行高效。每次都是对整个半区进行内存回收，内存分配时无需考虑内存碎片等复杂情况。  
  * 缺点： 浪费内存空间。在最坏的情况下，这种垃圾回收算法可能浪费了一半的内存空间。  

  在JAVA应用中，90%之上的对象的生存时间都极短，所以JVM把内存分为一块较大的Eden空间和两块较小的Survivor空间，每次只使用Eden和其中一块Survior空间。当需要进行垃圾回收时，将Eden和Survivor中还处于可达状态的对象一次性的复制到另一块Survivor空间中，最后清空Eden和刚刚使用的Survivor空间。当Survivor空间不够用时，还会将长时间存活的对象转存的老年代中。在HotSpot虚拟机中，默认的Eden和Survivor空间的比例是8:1，这样可以做到只浪费10%的内存。  

## 标记-整理算法（Mark-Compact）
  > 标记-整理算法的标记过程与标记-清除算法的标记过程类似，但在标记完成后并不是直接对可回收的对象进行清理，而是让所有正在存活的对象都向前端移动，然后直接清理掉边界以外的内存。其示意图见图3.  

  ![](https://weiwei02.coding.me/images/java/jvm/垃圾回收标记-整理.png)  
  图3 标记-整理算法示意图  

  * 优点： 节省内存空间，提升内存运用率，且不会产生内存碎片。  
  * 缺点： 性能低。  

## 分代收集算法（Generational Collection）
  > 根据对象的存活时间把内存分为新生代和老年代，根据个代对象的存活特点，每个代采用不同的垃圾回收算法。  

  分代收集就是根据不同代的特性，使用最合适的垃圾回收算法进行垃圾回收。如新生代中，每次垃圾收集都会有大量的对象死去，只有极小部分对象存活，所以更适合复制算法。老年代中对象存活率高，且没有额外的内存空间为它进行分配担保，所以更适合用标记-清除或标记-整理算法。

# HotSpot算法实现
## 枚举根节点（GC Roots）
  在垃圾回收时，我们要想办法找出哪些对象是存活的，一般会选取一些被称为GC Root的对象,从这些对象开始枚举。在进行GC Root枚举时要求所有对象停下来，也就是JVM所称的“Stop the world”。所有的算法实现都会将虚拟机停下来的，否则分析结果的准确性将无法保证。  

  由于HotSpot采用准确式GC，该技术主要功能就是让虚拟机可以准确的知道内存中某个位置的数据类型是什么，比如某个内存位置到底是一个整型的变量，还是对某个对象的 reference。这样在进行 GC Roots 枚举时，只需要枚举 reference 类型的即可。在能够准确地确定 Java 堆和方法区等 reference 准确位置之后，HotSpot 就能极大地缩短 GC Roots 枚举时间，所以当执行系统停顿下来之后，虚拟机不需要遍历所有的根节点和上下文去确定GC Roots，而是存在着一个OopMap的数据结构来达到这个目的。  

  在类加载完成的时候，虚拟机就会把什么类的什么偏移上是什么类型的数据计算出来。在JIT编译的时候也会在特定位置记下在寄存器和栈中哪些位置是引用，GC在扫描时就可直接得到信息。

##  安全点(Safepoint)

  Safepoint：会导致 OopMap 内容变化的指令非常多，如果为每一条指令都生成对应的 OopMap，那么将需要大量的额外空间，这样对导致 GC 成本很高，所以 HotSpot 只在 “特定位置” 记录这些信息，这些位置被称为 安全点(Safepoint)。并非程序在任意时刻都可以停顿下来进行 GC，而只有程序到达 安全点(Safepoint) 以后才可以停顿下来进行 GC；所以安全点既不能太少，以至于 GC 过程等待程序到达安全点的时间过长，也不能太多，以至于 GC 过程带来的成本过高。

  由于在 GC 过程中必须保证程序已执行，那么也就是说 必须等待所有线程都到达安全点上方可进行 GC。一般来说有两种解决方案可以选择：

  * 抢先式中断：不需要线程的执行代码去主动配合，当发生 GC 时，先强制中断所有线程，然后如果发现某些线程未处于安全点，那么将其唤醒，直至其到达安全点再次将其中断；这样一直等待所有线程都在安全点后开始 GC。现在几乎没有虚拟机使用这种方式。  

  * 主动式中断：不强制中断线程，只是简单地设置一个中断标记，各个线程在执行时轮询这个标记，一旦发现标记被改变(出现中断标记)时，那么将运行到安全点后自己中断挂起；目前所有商用虚拟机全部采用主动式中断。

# 安全区(Safe Region)

  安全点机制仅仅是保证了程序执行时不需要太长时间就可以进入一个安全点进行 GC 动作，但是当特殊情况时，比如线程休眠、线程阻塞等状态的情况下，显然 JVM 不可能一直等待被阻塞或休眠的线程正常唤醒执行，此时就引入了安全区的概念。  

  安全区(Safe Region)：安全区域是指在一段代码区域内，对象引用关系等不会发生变化，在此区域内任意位置开始 GC 都是安全的。线程运行到Safe Region中的代码时，首先标记自己进入了安全区，然后在这段区域内，如果线程发生了阻塞、休眠等操作，JVM 发起 GC 时将忽略这些处于安全区的线程。当线程再次被唤醒时，首先他会检查是否完成了 GC Roots枚举(或这个GC过程)，然后选择是否继续执行，否则将继续等待 GC 的完成。

## 引用

  本文是对class文件的学习笔记，笔记的内容并非是原创，而是大量参考其它资料。在写作本文的过程中引用了以下资料，为为在此深深谢过以下资料的作者。
  1. 《The Java® Virtual Machine Specification · Java SE 8 Edition》
  2. 《深入理解Java虚拟机：JVM高级特性与最佳实践/周志明著.——2版.——北京：机械工业出版社，2013.6》
  3. 《Java Platform, Standard Edition HotSpot Virtual Machine Garbage Collection Tuning Guide》

    非原创声明
      >本文并非我的原创文章，而是我学习jvm时的笔记。文中的材料与数据大部分来自于其它资料，详细请查看本文的引用章节。

## 关于

  本项目和文档中所用的内容仅供学习和研究之用，转载或引用时请指明出处。如果你对文档有疑问或问题，请在项目中给我留言或发email到 <EMAIL>  
  我的[github](https://github.com/weiwei02/): https://github.com/weiwei02/  
  我相信技术能够改变世界。
{'fraction_non_alphanumeric': 0.09071949947862357, 'fraction_numerical': 0.011006835824354072, 'mean_word_length': 8.797956867196367, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 15, 'https://': 10, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3195728', 'n_tokens_mistral': 7364, 'n_tokens_neox': 8309, 'n_words': 336}