在《垃圾回收算法之引用计数算法》这篇博客里，我们说到了引用计数算法的缺陷：会造成循环引用的问题。本篇的引用跟踪算法则客服了这种缺陷。

      在引用计数算法中，对于每个引用的对象，我们有一个额外的字段专门计数这个对象被引用的次数，当次数为0时，则视为垃圾。那在引用跟踪算法中，我们如何判断这个对象是垃圾呢？答案是：对象可达图。

一．对象可达图

       它的含义是，首先将所有的对象标记为垃圾并将它们视为根，从根出发，将所有的正在使用的对象串联起来，直至完毕，不被串联的对象即为“不可达”，即被视为垃圾，”可达” 的对象则被认为是有用的，在垃圾回收的过程中幸存下来。      

static void Main(string[] args)
{
   var obj1 = new object();//step1
   DoSomething();//step2
   var obj3 = obj1;//step3  
}//step4

static void DoSomething()
{
   var obj2 = new object();
}

      我们来看下面一段代码，根据可达图的含义来画出对象可达图。从总体来看彼此的调用关系如下：

       我们假设，在运行到step3之后，运行step4之前，进行了一次垃圾回收。

       首先：找出所有的根对象，标志其为”垃圾”，这个是通过将同步块索引的一位设为0来完成的，我们称这个阶段为”标记”阶段。

       在运行到step3后，obj1和obj2和obj3就是这里的3个根，其中根obj2在堆栈中已经被pop出去了，因此堆栈中只有两个根对象obj1和obj3,如图所示：

       因为根obj1均引用了object对象1，所以object对象1的同步块索引的一位被置为1，以标记其不是垃圾，然后检查根obj3的对象引用情况，发现它也引用了object对象1，当它刚要标志其同步索引块的一位时，发现object对象1已经被标记了，则不重新标记它。这样就避免了因循环引用而产生死循环。

      需要注意的是，在标记object对象1时，发现它引用了其他的对象（假设为a），那么对象a也对被标记。

      标记过程会持续，依次检查完所有的根。标记完毕后，堆中的对象要么被标记要么未标记，就会形成一个对象可达图，图中可达的对象不是垃圾，不可达的对象被视为垃圾。知道了哪些是垃圾后，下一步就进入了压缩阶段。

二．压缩阶段

      压缩阶段主要的任务是将幸存的对象压缩成连续的，因为根据应用程序的局部性原理，这样更有利于减少程序集，释放了内存，解决了堆的空间碎片化问题，同时提高了缓存命中率。对于下图而言，我们就是要把acef对象压缩成连续的，其实很简单，我们只需要把c对象挪到a后面，e对象挪到c后面，依此类推，即可使这些内存对象变成连续的。

      在完成这一步后，其实两个问题亟待解决，第一个是c内存压缩后，其在堆中的实际位置变化了，根引用c的位置还是原来的，如果听任下去，将会访问旧的内存地址而造成内存损坏。所以，还要将根中引用c的地址减去在压缩中偏移的字节数，这样就能保证每个根引用的还是原来的c，只不过对象在内存中变换了位置。

      第二个亟待解决的问题是，指向下一个对象在堆中的分配位置NewObjPtr指针也要进行偏移字节数的计算，这样才能保证新对象分配的内存与原有的堆内存是连续的。

      下面是垃圾回收后的托管堆：

       经过垃圾回收过后，内存不可能泄漏了，因为对象可达图中的不可达对象，都会被回收；其次不可能因为访问不可达对象而造成内存损坏，因为现在只能引用可达的对象，不可达的对象是引用不了的。

参考文档

 《CLR via C#》（第4版）

垃圾回收算法之引用跟踪算法