现代语言中，大多数都实现了垃圾回收功能，不再需要开发者自己来释放无用的内存资源，大大提高了开发效率。

历史

1960 年前后诞生于 MIT 的 Lisp 语言是第一种高度依赖于动态内存分配技术的语言。Lisp 中几乎所有数据都以“表”的形式出现，而“表”所占用的空间则是在堆中动态分配得到的。 Lisp 语言先天就具有的动态内存管理特性要求Lisp 语言的设计者必须解决堆中每一个内存块的自动释放问题，否则，Lisp 程序员就必然被程序中不计其数的 free / delete 语句淹没，这直接导致了垃圾收集技术的诞生和发展。

在学校和工作中，我使用过c/c++这种需要开发者自己来维护内存，时时刻刻需要小心内存泄露的问题，也使用过python、golang、js以及java这种不需要关系内存资源的释放，让自己更加专注于程序的设计和开发，但是也带来了性能的损耗。

垃圾回收GC并不是万能的，如果你接受了它的便利，那么你也需要接受GC带来的性能开销。

内存分配

内存分配大概分为三种：静态分配、局部分配以及动态分配。

1
2
3
4
5
6
7
8
9

静态分配（ Static Allocation ）：
静态变量和全局变量的分配形式。通常，它们无需释放和回收。

自动分配（ Automatic Allocation ）：
在栈中为局部变量分配内存的方法。栈中的内存可以随着代码块退出时的出栈操作被自动释放。

动态分配（ Dynamic Allocation ）：
在堆中动态分配内存空间以存储数据的方式。堆中的内存需要开发者自己来管理，谨慎对待每一个动态分配的对象，避免造成内存泄露。
在软件开发中，如果你懒得释放内存，那么你也需要一台类似的机器人——这其实就是一个由特定算法实现的垃圾收集器。

因此，垃圾回收的目的是回收动态分配的内存。

垃圾回收GC

垃圾回收技术主要包括：引用计数、跟踪式以及分代。

引用计数

引用计数Reference Counting为每个内存对象维护一个引用计数器,

1
2
3
4
5
6
7
8
9
10
11

// 新的引用指向某对象时，该对象引用计数器加1
if add refrence:
    counter +=1

// 对象的引用被销毁时，该对象引用计数器减1
if remove refrence:
   counter -= 1

// 对象的计数器归零时，回收该对象所占用的内存资源
if counter == 0:
   free object

每个计数器只记录了其对应对象的局部信息-被引用的次数，而没有全局的应用信息。

由于只维护局部信息，所以不需要扫描全局对象图就可以识别并释放死对象，但也因为缺乏全局对象图信息，所以无法处理循环引用的状况。

循环引用？

A引用B，B又引用了A，那么A和B引用计数器的值均为1，无法释放该资源。

1
2

A <- B
B <- A

优点 & 缺点

1
2
3
4
5
6
7
8

优点
- 每次创建和销毁都要更新引用计数值，会引起额外的开销
- 计数简单，只需要记录自身被引用次数
- 实时的垃圾回收，不会造成中断

缺点
- 无法处理循环引用
- 多线程对同一对象计数更新产设个竞争

Python使用了引用计数算法，为了解决循环引用的问题还设计了其他GC模块(标记清除和分代收集)。
此外，Python为了解决引用技术的性能问题还引入了内存池机制。

跟踪式

跟踪式垃圾回收是比较常见的垃圾回收技术，主要原则是从程序栈的若干个根对象出发，构造一个可达链，对于那些不可达的内存对象，做回收。

如果一个内存对象有被程序中的至少一个变量引用（直接指向或间接指向），则认为该对象可达，否则认为该对象不可达，可以被垃圾回收。

标记清除

标记清除Mark-Sweep的基本思路是遍历以对象为节点、以引用为边构成的图，把所有可以访问到的对象打上标记，然后清扫一遍内存空间，把所有没标记的对象释放。

具体过程分两步：

• 从根（Root）开始遍历，被根引用了的对象标记为非垃圾对象，非垃圾对象引用的对象同样标记为非垃圾对象，以此递归直到标记完所有对象；
• 再次从根节点开始，对已被标记为垃圾的对象清除释放。

如图，红色代表垃圾对象，黄色代表非垃圾对象，绿色代表未使用空间。

缺点：内存碎片

由于标记清除不需要移动对象的位置，直接回收垃圾对象必然会造成内存碎片。

标记复制

标记复制 Mark-Copy只需要对对象进行一次遍历。

它的基本思想是利用空间换时间，从根开始开始遍历对象，如果对象仍然存在引用，就把它复制到新的内存空间中，一次遍历结束之后，所有存在于新空间的对象就是所有的非垃圾对象，可直接释放掉原有内存空间，不会造成内存碎片。

如图，红色代表垃圾对象，黄色代表非垃圾对象，绿色代表未使用空间。

缺点：浪费内存

标记复制更快速但是需要额外开辟一块用来复制的内存，对垃圾比例较大的情况占优势。

此外，内存空间切换过程中需要暂停程序运行（也就是常说GC停顿）。

标记压缩

标记压缩Mark-Compact是在标记清除算法的基础之上增加对象的移动，从而解决内存碎片的问题。

在压缩阶段，由于要移动可达对象，那么需要考虑移动对象时的顺序，一般分为下面三种：

• 任意顺序 - 即不考虑原先对象的排列顺序，也不考虑对象间的引用关系，随意的移动可达对象，这样可能会有内存访问的局部性问题。

• 线性顺序 - 在重新排列对象时，会考虑对象间的引用关系，比如A对象引用了B对象，那么就会尽可能的将A，B对象排列在一起。

• 滑动顺序 - 顾名思义，就是在重新排列对象时，将对象按照原先堆内存中的排列顺序滑动到堆的一端。

现在大多数的垃圾收集算法都是按照任意顺序或滑动顺序去实现的(由于线性顺序需要考虑对象的引用关系所以实现复杂)。

Two-Finger 算法数据移动过程类似快排，分别用两个指针指向内存的两端，分别向中心移动。如果右侧指针遇到垃圾数据直接回收，否则，移动左侧指针直到遇到可替换垃圾对象，然后替换左右指针的对象。

缺点：移动对象的代价

为了避免内存碎片，移动对象需要遍历整个内存空间，还需要暂停程序更换映射地址空间。

分代回收

分代回收是根据对象的存活周期的不同将内存划分为几块。一般把java堆分为新生代和老年代，这样就可以根据各个年代的特点采用最适当的收集算法。

年轻代垃圾回收

年轻代回收特点：

• 新对象的内存分配都是先在Eden区域中进行的；
• 当Eden区域的空间不足于分配新对象时，就会触发年轻代上的垃圾回收minor gc（minor garbage collection）；
• 每个对象都有一个年龄，代表对象经历过的minor gc的次数；
• 当触发minor gc后，所有存活的对象都会被拷贝到一个新的survivor区域，并且年龄增加1；当对象的年龄足够大，它会从survivor内存区域升级到老年代中。

年老代垃圾回收

当老年代内存区域（图中Tenured）无法容纳新对象时，这时候就会触发老年代的垃圾回收major gc（major garbage collection”）。

垃圾回收算法PS和CMS

常用的垃圾回收算法有Parallel Scavenge(PS) 和Concurrent Mark Sweep(CMS)，它们的不同之处体现在年老代的垃圾回收过程中，而年轻代的垃圾回收过程在这两种垃圾回收器中基本上是一致的。PS在执行垃圾回收时使用了多线程来一起进行垃圾回收，这样可以提高垃圾回收的效率，CMS在进行垃圾回收时，应用程序可以同时运行。

在年轻代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高、没有额外空间对他进行分配担保，就必须使用“标记-整理”算法进行回收。

Parallel Scavenge

PS垃圾回收是由标记清除和标记压缩算法组成。

标记清除算法的一个缺陷就是它会引起内存碎片问题。继而有可能会引发连续的major gc。假设当前存在的内存碎片有10M，但最大的内存碎片只能容纳2M的对象，这个时候如果有一个3M的对象从Survivor区域升级到Tenured区域，那Tenured区域也没有办法存放这个3M的对象。结果就是不断的触发major gc，直到Out of Memory。所以，PS垃圾回收器在清除非可达对象后，还会进行一次compact，来消除内存碎片。

Concurrent Mark Sweep

CMS在进行垃圾收集时，应用程序是可以并行运行的，因此，它减少了垃圾收集时暂停应用程序的时间。
垃圾回收的四个阶段如下，

1
2
3
4
5
6
7
8
9
10
11
12

1. Initial Mark阶段
程序暂停运行`Stop-The-Word`，标记到根对象的第一层孩子节点即停止 ，然后程序恢复运行。由于只标记一层节点，所以暂停时间很短。

2. Concurrent Mark阶段
以Initial Mark阶段标记的节点为根对象，重新开始标记Tenured区域中的可达对象（不需要暂停应用程序，因此称为"Concurrent Mark"）。
由于CMS垃圾回收器和应用程序同时运行，Concurrent Mark阶段它并不保证在Tenured区域的可达对象都被标记了（分配新对象）。

3. Remark阶段
暂停应用程序，确保所有的可达对象都被标记（Concurrent Mark阶段未标记的，`可多线程标记`）。

4. Concurrent Sweep阶段
恢复应用程序的执行，执行sweep来清除所有非可达对象所占用的内存空间。

与PS相比，CS垃圾回收算法可以减少程序暂停的时间。

Garbage First

CMS垃圾收集器虽然减少了暂停应用程序的运行时间，但是由于它没有Compact阶段，它还是存在着内存碎片问题。

于是，为了去除内存碎片问题，同时又保留CMS垃圾收集器低暂停时间的优点，JAVA7发布了一个新的垃圾收集器 - G1垃圾收集器。

G1垃圾收集器和CMS垃圾收集器有几点不同，最大的不同是内存的组织方式变了。

Eden，Survivor和Tenured等内存区域不再是连续的了，而是变成了一个个大小一样的region - 每个region从1M到32M不等。

G1垃圾回收的四个阶段如下，

1
2
3
4
5
6
7
8
9
10
11
12
13

1. Initial Mark阶段
同CMS垃圾收集器的Initial Mark阶段一样，程序暂停运行`Stop-The-Word`，标记到根对象的第一层孩子节点即停止 ，然后程序恢复运行。
由于只标记一层节点。但它不会单独暂停应用程序的执行，而是在G1触发minor gc是发生。

2. Concurrent Mark阶段
同CMS垃圾收集器的Concurrent Mark阶段一样，重新开始标记Tenured区域中的可达对象（不需要暂停应用程序）。
但G1还会回收掉Tenured region中对象的存活率很小或者基本没有对象存活的内存区域（不需要等待clean up阶段，因此成为Garbage First），并计算每个 region的对象存活率以供clean up阶段使用 。

3. Remark阶段 
同CMS垃圾收集器的Remark阶段一样, 但G1采用一种叫做SATB(snapshot-at-the-begining)的算法能够在Remark阶段更快的标记可达对象。

4. Clean up/Copy阶段
与CMS中不同，它有一个Clean up/Copy阶段，在minor gc发生的同时G1会挑选出那些对象存活率低的region进行回收。

由于Initial Mark阶段和Clean up/Copy阶段都是跟minor gc同时发生的，相比于CMS，G1暂停应用程序的时间更少，从而提高了垃圾回收的效率。

G1提供两种GC模式：Young GC与Mixed GC。

Young GC属于G1的新生代回收算法，仅会扫描新生代中的Region进行回收。

Mixed GC属于G1的老年代回收算法，不仅仅会扫描新生代中的Region进行回收，而且会统计出老年代中高收益Region进行回收，因此，Mixed GC并不属于Full GC。