GC的三种方式，读ruby之父写的《编程语言的过去、现在和未来》笔记

术语解释：
1.垃圾
所谓垃圾(Garbage),就是需要回收的对象。作为编写程序的人，是可以判断“这个变量已经不需要了”的，但是计算机做不到。因此，如果程序直接或间接的引用一个对象，那么这个对象就被视为“存活”；反之，已经引用不到的对象被视为“死亡”。将这些“死亡”的对象找出来，然后作为垃圾进行回收，这就是GC的本质。
2.根
所谓根（Root），就是判断对象是否可被引用的起始点，至于哪里才是根，不同的语言和编译器都有不同的规定，但基本是将变量和运行栈空间作为根。

主要的GC算法包括：标记清除方式、复制收集方式、引用计数方式。

1.标记清除(Mark and Sweep)是最早开发出的GC算法（1960年）。它的原理非常简单，首先从根开始将可能被引用的对象用递归的方式进行标记，然后将没有标记到的对象作为垃圾进行回收。
初始状态，一个对象可以对其他的对象进行引用。
标记阶段，对象内部有一个Flag标示自己是不是被标记，被标记的对象我们把它涂黑。被标记的对象被视为“存活”对象。标记是从对象树的根部开始的。
清除阶段，在进行垃圾回收时，将从根部开始，将所有对象按顺序扫描一遍，将没有被标记的对象进行回收。
标记清除算法的处理时间，是和存活对象与对象总数的综合相关的。
作为标记清除的变形，还有一种叫做标记压缩(Mark and Compact)的算法，他不是将标记的对象清楚，而是将他们不断压缩。

标记清除算法有一个缺点，就是在分配了大量的对象，并且其中只有一小部分存活的情况下，所消耗的时间会大大超过必要的值，这是因为在清除阶段还需要对大量死亡对象进行扫描。
2.复制收集(Copy and Collection)
复制收集算法试图克服标记算法的缺陷。在这种算法中，会将从根开始被引用的对象复制到另外的空间中，然后，再将复制的对象所能够引用的对象用递归的方式不断复制下去。
将所有没有死亡的对象复制到新的空间中，然后将旧的空间废弃掉，就可以将死亡对象所占用的空间一口气全部释放出来，而没有必要再次扫描每个对象。下次GC的时候，现在的新空间也就变成了将来的旧空间。
根据我的个人经验，Java的GC采用了标记清除和复制收集方式。object-c的GC使用另一种GC：

3.引用计数方式
引用计数(Reference Count)方式是GC算法中最简单也是最容易实现的一种，它和标记清楚方式差不多是在同一时间内发明出来的。
它的基本原理是，在每个对象中保存该对象的引用计数，当引用发生增减时对引用计数进行更新。
引用计数的增减，一般发生在变量赋值、对象内容更新、函数结束(局部变量不再被引用)等时间点。当一个对象的额引用计数变为0时，则说明它将来不会再被引用，因此可以释放对应的内存空间。
1       1         1
A---->B----->D
   \      |       /|
     \    |     /  | 
       \  2  /    | 1
          C      E
假设上图中所有对象中都保存着自己被多个其他对象进行引用的数量（引用计数），每个对象右上角的数字就是引用计数。
当对象的引用发生变化时，引用计数也跟着变化。我们让对象B到对象D的引用失效，于是对象D的引用计数变为0， 于是对象D到C的引用计数为0。由于对象D的引用计数变为0，因此由对象D到对象C和E的引用计数也相应减少。结果，对象E的引用计数也变为0，于是对象E也被释放掉了。

1       1   失效  0
A---->B_____>D
 \       |         /|
   \     |       /  |
     \   |1   /    |0
         C          E
引用计数变为0 的对象被释放，“存活”对象则保留了下来。
1        1
A----->B
   \      |
     \    |
       \  1
          C

实现容易是引用计数算法最大的优点。标记清楚和复制收集这些GC机制在实现上都有一定难度；而引用计数方式的话，凡是有些年头的C++程序员（包括我在内），应该都曾经实现过类似的机制，可以说这种算法是相当具有普遍性的。
除此之外，当对象不在被引用的瞬间就会被释放，这也是一个优点。其他的GC机制中，要预测一个对象合适会呗释放是很困难的，而在引用计数方式中则是立即被释放的。而且，由于释放操作是针对每个对象级别执行的，因此和其他算法相比，由于GC而产生的中断时间（Pause time）就比较短，这也是一个优点。
引用计数方式的缺点：
 引用计数最大的缺点，就是无法释放循环引用的对象。
                1
                A
              ^  \
             /      \
         1/          ‘/1
          B-------->C
上图中，A、B、C三个对象没有被其他对象引用，而是相互循环引用，因此他们的引用计数永远不会为0，结果这些对象就永远不会被释放。
引用计数的第二个缺点，就是必须在引用发生增减时对引用计数做出正确的增减，而如果漏掉了某个增减的话，就会引发很难找到原因的内存错误。引用计数忘记了增加的话，会对不恰当的对象进行释放；而引用计数忘记了减少的话，对象会一直残留在内存中，从而导致内存泄露。如果语言编译器本身对引用计数进行管理的话还好，否则，如果是手动管理引用计数的话，那将成为孕育BUG的温床。
最后一个缺点就是，引用计数并不适合并行处理。为了在多线程环境下避免多个线程同时操作引用计数，引用计数的操作必须采用独占的方式来进行，如果引用计数操作频繁发生，每次都要使用加锁等并发控制机制的话，其开销也是不可小觑的。


GC的基本算法，大体上都逃不出上述三种方式以及他们的衍生品。现在，通过对这三种方式进行融合，出现了一些更高级的方式。最有代表的是：分代回收、增量回收和并行回收。

1.分代回收(Generational GC)
由于GC和程序处理的本质是无关的，因此它消耗的时间越短越好。分代回收的目的，正是为了在程序运行期间，将GC所消耗的时间尽量缩短。
分代回收的基本思路，是利用了一般性程序所具备的性质，即大部分对象都会在短时间内成为垃圾，而经过了一定时间依然存活的对象往往用于偶较长的寿命。如果寿命长的对象跟容易存活下来，寿命短的对象则会被很快的废弃，那么到底怎样做才能让GC变得更加高效呢？如果对分配不久，诞生时间较短的“年轻”对象进行重点扫描，应该就可以更有效的回收大部分垃圾。
在分代回收中，对象按照生成的时间进行分代，刚刚生成不久的年轻对象划为新生代(Young generation)，而存活了较长时间的对象则划为老生代(Old generation).根据具体实现方式的不同，可能会划分更多的代。那么根据程序的一般性质（即大部分对象都会在短时间内成为垃圾，而经过了一定时间依然存活的对象往往拥有较长的寿命）,那么只要仅仅扫描新生代对象，就可以回收大部分废弃对象中的一部分。
这种方式称为小回收(Minor GC),参考Java的垃圾回收机制： http://www.blogjava.net/ldwblog/archive/2013/07/24/401919.html
小回收：首先从根开始一次常规扫描，找到“存活”对象。这个步骤常采用标记清楚或者是复制收集算法都可以，不过大多数分代回收都采用了复制收集算法。在扫描过程中，如果遇到属于老生代的对象，则不对该对象继续进行递归扫描。这样一来，需要扫描的对象就大幅减少。
然后，将第一次扫描完后残余下来的对象划分到老生代。具体来说，如果是用复制收集算法，只要将复制目标空间设置为老生代就可以了；而标记清除算法，则大多采用在对象上设置某种标志的方式。

对来自老生代的引用进行记录：
按照前面的方式，从老生代对象对新生代的引用怎么办呢？如果指扫描新生代区域的话，那么从老生代对新生代的引用就不会被检测到。如果一个年轻的对象只有来自老生代的引用，就会被误认为已经“死亡”了。因此，在分代回收中，会对对象的更新进行监视，将从老生代对新生代的引用，记录在一个叫做记录集（remembered set）的表中。在执行小回收的过程中，这个记录集也作为一个根来对象。
未来让分代回收正确工作，必须使记录集的内容报纸更新。为此，在老生代到新生代的引用产生的瞬间，就必须对该引用进行记录，而负责执行这个操作的子程序，需要被嵌入到所有设计对象更新操作的地方。
这个负责记录引用的子程序是这样工作的：设有两个对象A和B，当对A的内容进行改写并加入对B的引用，如果A属于老生代对象，并且B属于新生代对象，则将该引用添加到记录集中。
这种检查程序需要对所有涉及修改对象内容的地方进行保护，因此被成为写屏障（Writes barrier）.写屏障不仅用于分代回收，同时也用在很多其他的GC算法中。
在运行过程中，老生代对象也会死亡。为了避免老生代区域中的“死亡”对象拜拜占用内存空间，偶尔需要对包括老生代区域在内的全部区域进行一次少秒回收。想这样以全部区域为对象的GC操作被成为完全回收（Full GC）或者大回收(Major GC)。
分代回收的性能会被程序行为、分代数量、大回收触发条件等因素大幅左右。

2.增量回收
在对实时性要求很高的程序中，比起缩短GC的平均中断时间，往往更重视缩短GC的最大中断时间。例如，在机器人的姿势控制程序中，如果因为GC而让控制程序中断了0.1秒，机器人可能就摔倒了。或者车辆控制程序因为GC而延迟相应的花，后果也是不堪设想的。
在这些对实时性要求很高的程序中，必须能够对GC所产生的中断做出预测。例如可以将最多中断10毫秒作为附加条件。

在一般的GC算法中，GC产生的中断时间与对象的数量和状态有关。因此，为了维持程序的实时性，不等到GC全部完成，而是将GC操作细分成多个部分逐一执行。这种方式被成为增量回收(Incremental GC)。
在增量回收中GC过程是渐进的，再回首过程中程序本身会继续运行，对象之间的引用关旭也可能发生变化。如果已经完成扫描和标记的对象被修改，对新的对象产生了引用，这个新的对象就不会被标记，明明是存“存活”的对象却被回收掉了。
为了避免这样的问题，和分代回收一样也采用了写屏障。当已经被标记的对象的引用关系发生变化时，通过写屏障会将新被引用的对象作为扫描的起始点记录下来。
由于增量回收的过程是分布渐进式的，可以将中断时间控制在一定长队之内。另一方面由于终端操作需要消耗一定的时间，GC所消耗的总时间就会相应的增加。

3.并行回收
最近的计算机中，一块芯片上搭载多个CPU核心的多核处理器已经逐渐普及。例如core i7就拥有6核12线程。
在这样的环境中，就需要通过利用多线程来充分发挥CPU的性能。并行回收正是通过最大限度利用CPU的处理能力来进行GC操作的一种方式。
并行回收的基本原理是，在原有的程序运行的同事进行GC操作，这一点和增量回收是相似的。不过，相对于在一个CPU上进行GC任务分割的增量回收来说，并行回收可以利用多CPU的性能，尽可能让这些GC任务并行进行。
由于软件运行和GC操作是同事进行的，因此就会遇到和增量回收同样的问题。为了解决这个问题，并行回收也需要用写屏障来对当前状态信息保持更新。不过，让GC操作完全并行，而一点不影响原有程序运行，是做不到的。因此在GC操作的某些特定阶段，还是需要中断原有程序的运行。

GC大一统理论：美国IBM公司沃森研究中心的David F.Bacon等人认为，任何一种GC算法，都是跟中回收和引用计数回收两种思路的组合。例如，用于改善分代回收和增量回收等跟踪回收算法的新屏障机制，从对引用状态变化进行记录这个角度来看，就是吸收了引用计数回收的思路。