垃圾回收机制简述
内容基本来源于[浅谈程序语言的垃圾回收机制](https://mp.weixin.qq.com/s?__biz=MzU5NzEwMDQyNA==&mid=2247483808&idx=1&sn=06dcf160978dd022a4e5c5c99ad1b073&chksm=fe59d347c92e5a513f42bb071d97247e384d6a3d94cbcb8f03fb200171aa5aa0af1235e910ca&mpshare=1&scene=22&srcid=0824EHt1if6Nq61TpEDriDvj# rd)看了一遍，再抄一遍以加深记忆、知识备份。
背景
众所周知，c/c++需要程序员手动分配和释放内存，要想处理得好，除了会增加程序员的开发成本之外，其实对程序员自身的内存管理能力也有一定的要求。然而如果处理得不好，极易造成内存泄漏。
目的
一些高级编程语言在设计时，决定将内存的分配和回收这一类工作统一交由语言自实现的“自动处理机”，即我们常说的垃圾回收机制。其目的是为了让程序更稳健（程序员手动管理内存的水平不一，交由自动机处理更有保障）、让程序员更轻松（仅需专注程序逻辑本身）。
实现需要解决的基本问题
垃圾回收机制的实现，需要解决三个基本问题：
what(什么是垃圾)
这里涉及到对垃圾的定义以及垃圾判定算法的实现：
定义：内存中的垃圾，指的是程序将不再使用的对象对应的内存块；
算法的实现：主要有两个，一是引用计数，二是对象可达性分析；
when(什么时候回收垃圾)
垃圾回收的触发时机，主要发生在：内存区域的剩余空间大小，不足以容纳欲创建的对象时。
how(怎么回收垃圾)
内存垃圾的释放很简单，直接调用相应的free api即可。这里强调how，主要是指：在回收内存垃圾时，怎么应对可能产生的内存碎片？
内存碎片，指的是可被分配使用但由于零碎（空间小、分布散）而难以被使用的空闲内存块。当内存碎片过多时，会造成内存的严重浪费。
垃圾回收算法
我们通常所说的垃圾回收算法，是一种广义说法，其主要包含两部分，一是垃圾的判定算法，二才是垃圾的回收算法。前者专注于垃圾的定位和标识，而后者专注于垃圾的释放和内存碎片的处理。
垃圾的判定算法
引用计数(Reference Counting)
对垃圾对象的定义
引用计数判定算法，会给每一个对象设立一个引用计数位，用于统计其他对象对当前对象的引用次数。而引用计数位为0的对象，被视为可回收的垃圾对象。
算法描述
引用计数判定算法，会给每一个对象创建一个引用计数位，初始值为0。当有一个变量引用该对象时，计数位加1；有一个变量解除对其的引用时，计数位减1。当垃圾回收机制被触发时，所有引用计数位值为0的对象，都将被视为垃圾对象而回收。
优点
简单、易理解；
缺点
维护引用计数位的开销较大（需要根据被引用情况的变化而不断更新引用计数位）
对引用成环的垃圾对象（对象循环引用时都不会被释放 ）判定失效：若干个不再被使用的垃圾对象，内部形成了一条引用环，且这个环中的任何对象均不被外部的变量或对象引用。由于环中的任意对象，其引用计数位均不为0，所以即便在垃圾回收机制被触发时，这些垃圾对象也不会被回收，严重情况下，会造成内存泄漏，这个问题就是我们常说的引用计数法的循环引用问题。
不被外部引用的对象环－示图2（需回收但不会被回收）
被外部fooListHead引用的对象环（无需回收）
评价
无法解决循环引用问题，这个也是致命的缺陷，证明了引用计数法没有满足算法的正确性。
应用例子
JavaScript 1.1（实现在Netscape 3）的垃圾回收算法使用了引用计数法；
IE6/7使用引用计数方式对 DOM 对象进行垃圾回收；
对象可达性分析(Reachability Analysis，亦称跟踪算法)
对垃圾对象的定义
对象可达性分析算法，会分别从根对象集合（root set）中的每一个根对象开始，进行遍历搜索。那些不可访问到的对象，将被视为可回收的垃圾对象。
算法描述
a. 每一个对象创建时，会为其添加一个标记位marked, 初始值为false，如下图所示：
b. 当垃圾回收机制被触发时，对象可达性分析算法，会对root set中的每一个根对象（root set可能有多个根对象），使用深度优先搜索遍历算法，进行可达性测试，可以访问到的对象其标记位被标识为为true，如下图所示：
特别地，
Javascript的根对象对应全局对象；
Java的根对象对应：
Local variable and input parameters of the currently executing methods；
Active threads；
Static field of the loaded classes；
JNI references
c. 遍历结束后，可达标记位为false的对象被视为垃圾对象，会被回收机制回收；可达标记位为true的对象，被视为存活对象，其可达标记位重置为false。如下图所示：
优点
能够解决循环引用问题，即能标识出引用成环的垃圾对象为垃圾；
缺点
属于事后判定算法，每次执行，都需要遍历所有对象，开销较大；
执行时会stop-the-world，有一定的中断时间;
评价
相对于引用计数判定算法而言，对象可达性分析算法能够解决循环引用问题，满足了算法的正确性，许多垃圾回收算法对垃圾的判定，也采用对象可达性分析算法。
应用场景
广义上的垃圾回收算法如标记－清除法、标记－压缩法、复制法、分代法中的垃圾判定算法部分，均使用对象可达性分析算法。所以使用了这些垃圾回收算法的场景，均可认为是对象可达性分析算法的应用场景，常见场景的有：
现代Javascript的实现
Java主流的虚拟机
垃圾回收算法
引用计数法（reference counting algorithm)
算法描述
a. 垃圾对象判定过程: [引用计数](# 引用计数(Reference Counting));
b. 垃圾对象回收过程：可以在引用计数位为0时，回收当前垃圾对象。也可以在回收机制被触发时，统一回收引用计数为0的对象。
优点
回收垃圾对象时，操作简单
缺点
没有对内存碎片进行处理，造成内存浪费
空闲内存不连续，增大分配内存的难度，分配内存时需要查找空闲内存列表
评价
总体而言，引用计数法可用性极低。其垃圾判定部分，有循环引用问题；其垃圾回收算法部分，没有进行内存碎片的处理，当程序执行一段时间后（经过多次的对象创建和回收），容易产生零散的内存碎片，进而造成内存的浪费。
标记－清除法（mark-sweep algorithm）
算法描述
a. 垃圾对象判定过程：[对象可达性分析](# 对象可达性分析(Reachability Analysis，亦称跟踪算法))（对应mark阶段）
b. 垃圾对象回收过程：当执行垃圾回收时，标记－清除法，将直接释放marked为false的垃圾对象对应的内存块（对应sweep阶段）。
优点
回收垃圾对象时，操作简单
缺点
没有对内存碎片进行处理，造成内存浪费
空闲内存不连续，增大分配内存的难度，分配内存时需要查找空闲内存列表
评价
总体而言，标记－清除法可用性比引用计数法高，其在垃圾判定部分，能够解决循环引用问题；但其垃圾回收算法部分，和引用计数法一样，亦没有进行内存碎片的处理。总之，标记－清除法还是一个比较朴素的垃圾回收算法，可优化的空间较大。
复制法 （copying algorithm）
算法描述
a. 垃圾对象判定过程：[对象可达性分析](# 对象可达性分析(Reachability Analysis，亦称跟踪算法))
b. 垃圾对象回收过程：
将内存区域一分为二，分为对象区(from-space)和空闲区(to-space)，新创建的对象从对象区获取存储空间；
如果对象区的剩余空间大小不足以容纳新创建的对象，则会触发垃圾回收；
当执行垃圾回收时，会把对象区里的所有存活对象，都复制到空闲区，此时旧的空闲 区变成了新的对象区，旧的对象区变成新的空闲区，角色发生了互换；
复制法回收垃圾过程－图1
复制法回收垃圾过程－图2
实现算法
Cheney’s copying algorithm
优点
杜绝了内存碎片的产生，由于对象的存储空间连续排列，空闲内存也变得连续，所以分配内存时，只需比较一次（判断剩余内存空间是否足以容纳欲新建的对象），使得处理更加简单、高效；
缺点
只有一半的内存空间用于存储对象；
复制操作开销大；
存活对象被移动后，需要找到所有引用了这些存活对象的对象，并更新其引用地址，所以这里包括遍历开销和更新开销；
应用场景
分代法中的新生代
标记－压缩法（mark-compact algorithm）
算法描述
a. 垃圾对象判定过程：[对象可达性分析](# 对象可达性分析(Reachability Analysis，亦称跟踪算法))
b. 垃圾对象回收过程：当执行垃圾回收时，标记－压缩法的垃圾处理机制，会将存活对象按顺序逐一地往内存区域的低地址方向复制，直到所有存活对象的内存块连成一片;
标记－压缩法回收垃圾过程－图1
标记－压缩法回收垃圾过程－图2
优点
杜绝了内存碎片的产生，由于对象的存储空间连续排列，空闲内存也变得连续，所以分配内存时，只需比较一次（判断剩余内存空间是否足以容纳欲新建的对象），使得处理更加简单、高效；
相对于复制法而言，其对内存的利用率更高；
缺点
复制操作开销大；
存活对象被移动后，需要找到所有引用了这些存活对象的对象，并更新其引用地址，所以这里包括遍历开销和更新开销；
实现算法
Table-based compaction
LISP2
应用场景
分代法中的老生代
分代法（generation algorithm）
设计思想
在了解分代法的设计思想（优化思路）时，我们不妨先思考和分析一下，垃圾回收算法的主要开销在哪里？找到了这些主要开销，其实就是找到了优化的切入点。
正如我们之前所说，一个广义的垃圾回收算法，包括两部分，第一部分专注于垃圾的判定，第二部分专注于垃圾的回收和内存碎片的处理。
我们知道，垃圾回收算法很大一部分开销，是源于对内存碎片的处理（通过复制操作来消除内存碎片），所以只要减少了内存碎片的数量，就能减少对内存碎片的处理开销
为了更好地理解这些优化手段，简单思考下如下问题。一、内存碎片是怎样产生的？
在某个内存区域进行频繁的、大小不一的内存分配和释放时，就容易产生内存碎片。随着内存区域容量的增大（跨度增大），内存碎片的产生机率也会增加。
二、怎样可以避免或减少内存碎片的产生？
让内存的分配和释放集中在某个固定、较小的区域，能够降低空闲内存的零散性；
让内存的释放集中在某个固定、较小的区域，能够增加空闲内存的融合概率；
通过降低空闲内存分布的零散性和增加空闲内存的融合概率，就能有效避免内存碎片的产生。
三、怎样才能让内存的分配和释放，集中在某个固定、较小的区域？
lifetime较短的对象，集中在一起（内存频繁的分配和释放集中在这一块）；
lifetime较长的对象，集中在一起；
几乎不会被回收的对象，集中在一起；
四、怎么去评估一个对象lifetime的长短？
a. 从对象的功能来评估
- 程序语言执行的Runtime环境所需的对象，其lifetime往往伴随着程序执行的整个生命周期，这一类的对象，通常可以看成是“永存”的。
b. 利用统计学的知识，从统计结果归纳出的结论来评估
- IBM曾做过统计，98％的内存对象，在创建之后不久就变成了非活动对象；只有2％的对象，会在长时间一直处于活动状态。所以我们可以从这个统计数据得到一个规律：新创建的对象，其大概率是短命对象；创建越久的对象，其大概率是长命对象。
在思考和解答完上述几个问题，不知道你是否会想到一些实现方案？现在我们来看看分代法的设计思路：
a. 创建一个内存区域（新生代），用于集中存储新创建的对象，虽然这个区域内存释放的频数较高，但因为集中的局部存储，空闲内存的零散性降低，空闲内存融合的概率也增大，所以内存碎片的产生机率也会相应越少；
b. 创建一个内存区域（老生代），用于存储创建较久的对象，因为这个区域内存释放的频数较少，所以这个区域不易产生内存碎片；
c. 创建一个内存区域（永久代），用于存储近乎永生的对象如系统运行所需的内置对象，因为在系统的生命周期内，这个区域内存释放的频数几乎为0，所以这个区域很难产生内存碎片；
算法描述
a. 内存区域的划分
分代法对内存区域的划分图
分代算法把内存区域分为三个区域，分别是新生代（Young Genertation）、老生代（Old Generation，亦作Tenured Generation）和永久代（Permanent Generation），其中新生代又可细分为Eden space（伊甸园，上帝把初创的人类置于此，用于存放新创建的对象十分贴切）和Survivor space（等分为两部分，对应复制算法中的from-space和to-space）。
三个区域分别用于存储不同lifetime的对象：
新生代用于存储lifetime较短的对象，如用户程序里的某个函数或方法内的局部对象，为用户程序创建的对象，一开始通常置于此；
老生代用于存储lifetime较长的对象，如用户程序里的单例对象；
永久代用于存储程序运行时，几乎永存的对象，如语言Runtime运行所需的内置对象；
b. 不同内存区域使用的GC算法
|内存区域|GC算法|原因|
|:—:|:—:|:—:|:—:|
|新生代|复制算法|新生代对象的lifetime较短，每次执行完Minor GC后，存活的对象较少，所以需要的内存空间较小、复制移动的次数也较少；复制算法相对于标记－压缩法而言，虽然内存只能使用一半，在存储方面确实是劣势，但每次Minor GC后，存活对象较少，所以使用复制法基本足以存储；但在处理内存碎片方面，小有小的好，复制法from-space的对象更紧凑，算法要扫描的内存空间也越小，最后复制移动也会更快，典型的用空间换时间。|
|老生代|标记－压缩法|需解决内存碎片问题，而标记－清除法无法解决内存碎片问题, 老生代没有其他内存区域为其作空间分配担保，所以应提高内存空间的利用率，而复制法内存只能使用一半,标记－压缩法刚好解决以上两个问题。|
注：关于Minor GC和MaJor GC/Full GC的定义和区别（特指在本文）
新生代执行的垃圾回收，称为Minor GC，通常由Eden spac满时触发（欲新建的对象无法从Eden space获取存储空间）；
老生代执行的垃圾回收，称为Major GC/Full GC，通常由Tunured space满时触发；
Full GC一般会比Minor GC慢10倍以上；
c. 对象晋升
分代法会为每个创建的对象设立一个年龄计数位，初始值为0，对象每被复制移动一次，年龄计数位就会加1。当新生代对象的年龄达到了晋升到老生代的阈值，就可以被复制到老生代。当然，并不是必须资质够老，才可以晋升，还有另外三种特殊的晋升情况。
当新生代Survivor的from-space，某个年龄的对象所占比例大于等于一半，那么大于等于这个年龄的对象可以晋升；
欲创建的对象，其所需内存空间大于等于某个预设值时，直接从老生代获得存储空间（这种对象被称为大对象，如果存储在新生代容易接连Minor GC和Full GC，开销大）；
欲创建的对象，因为无法在新生代获得足够的内存空间，会引起新生代进行一次Minor GC。因为老生代会始终为新生代进行空间分配担保，如果新生代Minor GC执行完毕之后，新生代剩余的内存空间，仍然不足以容纳新创建的对象，那么新生代存活下来的对象，会全部复制到老生代。
d. 空间分配担保机制
空间分配担保机制，按我个人的理解，其目的其实是为了保证新生代始终有空闲的空间用于容纳新建的对象。老生代作为新生代的担保人，如果新生代在执行完Minor GC之后，仍然无法容纳需创建的对象，那么新生代存活的全部对象，都会被复制到老生代，这样新生代就能腾出空闲空间，为后续创建的对象分配内存空间。
e. 老生代担保能力审核
虽然新生代有老生代作担保，但是担保人老生代也会有掉链子的时候（分配担保失败：新生代Minor GC完成后，老生代最大的连续空闲空间不足以容纳要担保的新生代所有的存活对象）, 此时会在老生代引起一次耗时长的Full GC。
因为Full GC开销大，所以为了尽量不执行Full GC，分代法其实在新生代进行Minor GC之前，会对老生代的担保能力进行审核：
a. 如果老生代最大的剩余连续空闲空间大于或等于新生代Minor GC执行前所有对象的空间之和，那么则认为老生代具有足够的担保能力，此时新生代可以放心执行Minor GC操作；
b. 如果小于，即不能确定老生代是否具有足够的担保能力，但如果在大概率上老生代具有担保能力（大概率是指老生代最大的剩余连续空闲区间大于或等于新生代历次晋升对象空间大小的平均值），仍然会冒险（愿意接受老生代担保失败的后果），让新生代先执行一次Minor GC；
c. 如果是小概率具有担保能力，则不会冒险，而是让老生代先执行一次Full GC，以增加其的担保能力。
d. 当然，如果在不能确定老生代是否具有足够的担保能力时，丝毫不想冒老生代担保失败的风险，可以通过配置参数来告诉分代法，只要不能百分百确定老生代具有足够的担保能力，就让老生代执行一次Full GC。（例如Java虚拟机中，提供来一个配置参数HandlePromotionFailure，当设为false时，表示不允许分配担保失败）
优点
减少了内存碎片的产生
更高的内存局部性（具有联系的内存对象存储位置临近的概率大，有助于提高访问速度）
根据不同内存区域存储的对象的lifetime不同，采用不同的垃圾回收算法，性能更加
大部分执行垃圾回收时，耗时短（中断时间也相应短）
缺点
需要记录每个对象的年龄
执行一次Full GC时，开销大，耗时长（中断时间也相应长）
评价
分代算法，和以往的垃圾回收算法不同，它结合了内存对象的生命周期，通过对不同生命周期的内存对象进行分块存储，极大地减少了内存碎片的产生；同时对不同内存区域，采用更合适的回收算法，近一步减少了处理内存碎片的开销。
垃圾回收算法的分类
按垃圾判定算法来划分
使用引用计数的算法有：
- 引用计数法
使用对象可达性分析的算法有：
标记－清除法
标记－压缩法
复制法
分代法
按是否有无进行内存碎片处理来划分
无进行碎片处理的算法有：
引用计数法
标记－清除法
有进行碎片处理的算法有：
标记－压缩法：后处理方式
复制法：杜绝内存碎片
分代法：让内存碎片的更加集中
垃圾回收算法间的横向比较
引用计数法和标记－清除法的区别
二者的垃圾判定算法不一样：前者使用引用计数，无法正确判定引用成环的垃圾对象是应该回收的垃圾，后者使用对象可达性分析（通过对象的可达性来区分对象是否是垃圾），很好解决了循环引用问题。
标记－清除法和标记－压缩法的区别
后者可以看成是前者的改进，标记－压缩法仅比标记－清除法多了一步将存活对象复制到内存区域低地址位的操作，很好地解决了内存碎片问题。
标记－压缩法和复制法的区别
相同点
- 都是通过复制移动的方式，来解决内存碎片问题。
不同点
- 复制法将内存区域一分为二，仅一半用于存储对象。
垃圾收集器（garbage collector）
分类
垃圾收集器是垃圾回收算法在计算机上的实现，是可运行的程序。针对应用场景和硬件设备的不同，垃圾收集器的实现大致可有三类：串行类（serial）、并行类（parallel）和concurrent（并发类）。三者的区别具体如下：
a. 前两者是典型的stop-the-world类型的收集器，在执行垃圾回收时，会暂时其他所有无关线程的执行；
b. 并发类收集器，在执行垃圾回收时，可以和其他的非垃圾回收线程并发执行，保证了在执行垃圾回收时，不会中断用户线程的执行；
c. 串行类和并行类收集器的区别，则在于执行垃圾回收的线程数不一样，前者仅有一条，而后者则可以有多条，可以看成是串行类收集器的多线程版本，随着CPU核数的增加，其收集效果更加明显；
评测指标
对于垃圾收集器的评测，也大致有如下指标：
吞吐量
中断时长
实时和非实时
常见的垃圾收集器
Serial GC
Serial Old GC
ParNew GC
Parallel Scavenge GC
Parallel Old GC
CMS GC
G1 GC