垃圾回收器
GC（Garbage Collection)：JAVA/.NET中的垃圾回收器。Java是由C++发展来的。它摈弃了C++中一些繁琐容易出错的东西。其中有一条就是这个GC。而C#又借鉴了JAVA。
垃圾回收的原因
从计算机组成的角度来讲，所有的程序都是要驻留在内存中运行的。而内存是一个限制因素(大小)。除此之外，托管堆也有大小限制。因为地址空间和存储的限制因素，托管堆要通过垃圾回收机制，来维持它的正常运作，保证对象的分配，尽可能不造成“内存溢出”。
大白话原理：我们定义变量会申请内存空间来存放变量的值，而内存的容量是有限的，当一个变量值没有用了（称为垃圾），就应该将其占用的内存给回收掉。变量名是访问到变量的唯一方式，所以当一个变量值没有任何关联的变量名时，我们就无法访问到该变量了，该变量就是一个垃圾，会被程序的垃圾回收机制自动回收。
垃圾（Garbage）就是程序需要回收的对象，如果一个对象不在被直接或间接地引用，那么这个对象就成为了「垃圾」，它占用的内存需要及时地释放，否则就会引起「内存泄露」。有些语言需要程序员来手动释放内存（回收垃圾），有些语言有垃圾回收机制（GC）。本文就来讨论GC实现的三种基本方式。
其实这三种方式也可以大体归为两类：跟踪回收，引用计数。美国IBM的沃森研究中心David F.Bacon等人发布的「垃圾回收统一理论」一文阐述了一个理论：任何垃圾回收的思路，无非以上两种的组合，其中一种的改善和进步，必然伴随着另一种的改善和进步。
垃圾回收的基本原理
算法思路都是一致的：把所有对象组成一个集合，或可以理解为树状结构，从树根开始找，只要可以找到的都是活动对象，如果找不到，这个对象就被回收了
垃圾回收算法
跟踪回收
跟踪回收的方式独立于程序，定期运行来检查垃圾，需要较长时间的中断。
标记—清除算法（Mark-Sweep）
标记—清除算法是最基础的收集算法，它分为“标记”(mark)和“清除”(sweep)两个阶段：首先标记出所需回收的对象，在标记完成后统一回收掉所有被标记的对象，它的标记过程其实就是前面的可达性分析算法中判定垃圾对象的标记过程。
阶段1: Mark-Sweep 标记清除阶段，先假设heap中所有对象都可以回收，然后找出不能回收的对象，给这些对象打上标记，最后heap中没有打标记的对象都是可以被回收的；
阶段2: Compact 压缩阶段，对象回收之后heap内存空间变得不连续，在heap中移动这些对象，使他们重新从heap基地址开始连续排列（节省内存资源）。
Heap内存经过回收、压缩之后，可以继续采用前面的heap内存分配方法， 即仅用一个指针记录heap分配的起始地址就可以。主要处理步骤：将线程挂起→确定roots→创建reachable objects graph→对象回收→heap压缩→指针修复。可以这样理解roots：heap中对象的引用关系错综复杂（交叉引用、循环引用），形成复杂的 graph，roots是CLR在heap之外可以找到的各种入口点。
GC搜索roots的地方包括全局对象、静态变量、局部对象、函数调用参数、当前CPU寄存器中的对象指针（还有finalization queue）等。主要可以归为2种类型：已经初始化了的静态变量、线程仍在使用的对象（stack+CPU register）指针修复是因为compact过程移动了heap对象，对象地址发生变化，需要修复所有引用指针，包括stack、CPU register中的指针以及heap中其他对象的引用指针。
回收前状态
回收后状态
该算法有如下缺点：
- 标记和清除过程的效率都不高
- 标记清除后会产生大量不连续的内存碎片，空间碎片太多可能会导致，当程序在以后的运行过程中需要分配较大对象时无法找到足够的连续内存而不得不触发另一次垃圾收集动作
复制算法（Copy）
复制算法是针对标记—清除算法的缺点，在其基础上进行改进而得到的，它将可用内存按容量分为大小相等的两块，每次只使用其中的一块，当这一块的内存用完了，就将还存活着的对象复制到另外一块内存上面，然后再把已使用过的内存空间一次清理掉。复制算法有如下优点：
- 每次只对一块内存进行回收，运行高效
- 只需移动栈顶指针，按顺序分配内存即可，实现简单
- 内存回收时不用考虑内存碎片的出现
它的缺点是：可一次性分配的最大内存缩小了一半
复制算法的执行情况如下图所示：
回收前状态
回收后状态
现在的商业虚拟机都采用这种收集算法来回收新生代，新生代中的对象98%都是“朝生夕死”的，所以并不需要按照1:1的比例来划分内存空间，而是将内存分为一块比较大的Eden空间和两块较小的Survivor空间，每次使用Eden和其中一块Survivor。当回收时，将Eden和Survivor中还存活着的对象一次性地复制到另外一块Survivor空间上，最后清理掉Eden和刚才用过的Survivor空间。HotSpot虚拟机默认Eden和Survivor的大小比例是8:1，也就是说，每次新生代中可用内存空间为整个新生代容量的90%（80%+10%），只有10%的空间会被浪费。
当然，98%的对象可回收只是一般场景下的数据，我们没有办法保证每次回收都只有不多于10%的对象存活，当Survivor空间不够用时，需要依赖于老年代进行分配担保，所以大对象直接进入老年代。
标记—整理算法（Mark-Compact）
复制算法比较适合于新生代，在老年代中，对象存活率比较高，如果执行较多的复制操作，效率将会变低，所以老年代一般会选用其他算法，如标记—整理算法。该算法标记的过程与标记—清除算法中的标记过程一样，但对标记后出的垃圾对象的处理情况有所不同，它不是直接对可回收对象进行清理，而是让所有的对象都向一端移动，然后直接清理掉端边界以外的内存。标记—整理算法的回收情况如下所示：
回收前状态
回收后状态
引用计数
引用计数是指，针对每一个对象，保存一个对该对象的引用计数，该对象的引用增加，则相应的引用计数增加。如果对象的引用计数为零，则回收该对象。
优点：引用计数最大的优点就是容易实现，C++程序员应该都实现过类似的机制。二是成本小，基本上引用计数为0的时候垃圾会被立即回收，而其他方法难以预测对象的生命周期，垃圾存在的时间都会比这个方法高。另，这种垃圾回收方式产生的中断时间最短。
缺点：最著名的缺点就是如果对象中存在循环引用，就无法被回收。例如，下面三个对象互相引用，但是不存在从根（Root）指向的引用，所以已经是垃圾了。但是引用计数不为0.
还有一个缺点就是，引用计数不适合在并行中使用，多个线程同时操作引用计数，会引起数值不一样的问题从而导致内存错误。所以引用计数必须采用独占方式，如果引用操作频繁，那么加锁等并发控制机制的开销是相当大的。
Perl和Python采用了这种GC机制。
它们的衍生算法
分代收集
基于引用计数的回收机制，每次回收内存，需要把所有的对象的引用计数都遍历一遍，这是非常耗费时间的，于是引入分代回收提高回收效率，采用‘空间换取时间的策略’。
当前商业虚拟机的垃圾收集都采用分代收集，它根据对象的存活周期的不同将内存划分为几块，一般是把Java堆分为新生代和老年代。
新定义的变量值，会放在新生代中，假设每隔1分钟扫描一次，如果发现变量值依然存活，那该变量值的等级会提高，当权重大于3（假设为3），会放到青春代中，每隔5分钟扫描一次，继续存活下去，权重继续增高，当权重大于10（假设为10），会被放到老年代中，次时每隔10分钟扫描一次，以此类推。等级越高，被垃圾回收扫描的频率越低。
回收：依然是引用计数作为回收依据
- 在新生代中，每次垃圾收集时都会发现有大量对象死去，只有少量存活，因此可选用复制算法来完成收集
- 老年代中因为对象存活率高、没有额外空间对它进行分配担保，就必须使用标记—清除算法或标记—整理算法来进行回收
| GC算法 | 优点 | 缺点 | 存活对象移动 | 内存碎片 | 适用场景 |
|---|---|---|---|---|---|
| 引用计数 | 实现简单 | 不能处理循环引用 | |||
| 标记清除 | 不需要额外空间 | 两次扫描，耗时严重 | N | Y | 老年代 |
| 复制 | 没有标记和清除 | 需要额外空间 | Y | N | 新生代 |
| 标记整理 | 没有内存碎片 | 需要移动对象的成本 | Y | N | 老年代 |
增量算法 (Incremental Collecting)
上面的算法缩短了「GC平均中断时间」，但是在对实时性要求很高的程序中，对「GC最高中断时间」的要求更高。比如，自动驾驶软件，如果某次GC中断了0.1s，那么损失可能是致命的。
增量回收就是将GC分成几部分来执行。设置「GC最多中断10ms」这样的条件限制来使GC的终端时间视作可预测的。
但是，在两段的GC程序之间，引用关系可能发生了变化。所以，这种GC算法也要写屏障，来记录引用关系的变化。虽然这种方式控制了中断最高时间，但是由于中断次数增加，GC总时间是增加的。
增量算法的基本思想是，如果一次性将所有的垃圾进行处理，需要造成系统长时间的停顿，那么就可以让垃圾收集线程和应用程序线程交替执行。每次垃圾收集线程只收集一小片区域的内存空间，接着切换到应用程序线程。依次反复，直到垃圾收集完成。
使用这种方式，由于在垃圾回收过程中，间断性地还执行了应用程序代码，所以能减少系统的停顿时间。但是，因为线程切换和上下文转换的消耗，会使得垃圾回收的总体成本上升，造成系统吞吐量的下降。
并行回收
基本原理是，在程序运行的同时进行GC工作，最大化CPU的性能。但是这种方式也要面对增量回收的问题，所以也要进行写屏障操作。
然而这种方式也并未做到完全不暂停原程序的运行，在某些特定的GC阶段还是要暂停原程序。多核化迅速发展的今天，这种算法也在不断优化。不间断原程序实现并行回收这个领域是相当值得期待的。