垃圾回收GC:.Net自动内存管理上(二)内存算法

浏览数：20 / 时间：2015年06月09日

垃圾回收GC:.Net自动内存管理上(二)内存算法

垃圾回收GC:.Net自动内存管理上(一)内存分配
垃圾回收GC:.Net自动内存管理上(二)内存算法

前言

.Net下的GC完全解决了开发者跟踪内存使用以及控制释放内存的窘态。然而，你或午想要理解GC是怎么工作的。此系列文章中将会解释内存资源是怎么被合理分配及管理的，并包含非常详细的内在算法描述。同时，还将讨论GC的内存清理流程及什么时清理，怎么样强制清理。

内存算法

GC检测用于查看堆中是否有对象不再被程序使用。如果这样的对象存在，这些对象占用的内存就可以被回收利用。（如果堆中没有可用内存空间时，new操作符将会抛出OutOfMemoryException异常）GC是怎样知道一个对象是否还被程序使用呢？你可以想象一下，这不是一个容易回答的问题。

每一个程序都有一组根节点(roots)，它们用于识别定位托管堆中的对象或空(null)对象指向的存储空间。比如，程序中所有全局对象指针或静态对象指针都被看作是程序根节点(roots)的一部分。另外，线程栈中任何局部变量或参数对象指针也被看作程序根节点(roots)的一部分。最后，所有包含托管堆对象指针的CPU寄存器也被看作程序根的一部分。这组激活的根由JIT编译器和CLR维护,并可被GC的算法系统访问。

当GC运行时，它会假设所有堆中的对象都是垃圾。换句话说，它假设程序根节点一开始跟堆中对象没有任何联系。现在，GC开始查看程序根节点并为所有与程序根节点有联系的对象创建一个映射图。比如，GC可能会定位指向堆中任一对象的全局变量。

下图描绘出一个带有几个对象的堆，程序根节点直接指向对象A，C，D，F。所有这些对象就会变成映射图的一部分。当添加对象D时，GC会检测到它还指向对象H，因此对象H也被添加到映射图中。GC会一直这样递归所有相关联的对象。

托管堆((对堆与栈疑惑的可以参考：深入浅出图解C#堆与栈))上分配的对象：

一旦GC完成这部分映射后，GC就会去检查下一个根节点然后再递归相关联的对象，最后完成映射。但有一点不同的是，如果GC在递归相关联对象时发现一个对象之前已经映射过了，GC会停到当前节点不再往下延伸，但是其它节点还会继续。其它节点如果遇到相同情况也会停止，直到所有对象映射完毕。这样的映射方式有两个目的。第一，避免重复映射一个或一组对象大大提升了程序性能。第二，它避免了映射死循环。

当所有根节点都检查并映射过后，GC映射图里将会包含所有程序根节点可达（直接或间接的访问）的对象；如果一个对象没有在这个映射图中，说明程序根节点永远不可能访问到它，那么这个对象就被认为是垃圾。现在GC可以直线的访问堆，查找垃圾对象占用的连续性的内存块。然后GC把非垃圾对象占用的内存空间移动到垃圾对象所占用的内存块上（标准的memcpy操作），并删除所有堆中内存间隙（对象所占用内存块之间的间隙）。当然，这个内存块的移动操作会影响到所有关联的内存指针，因为内存地址发生了变化。因此GC必须修改程序根节点(roots)并确保所有受影响的指针指向对象的新地址。另外，如果任何对象包含一个指向其它对象的指针，GC同时也会负责纠正这些指针。大家还可以参考我的另一篇文章：

深入浅出图解C#堆与栈 C# Heap(ing) VS Stack(ing) 第六节理解垃圾回收GC，提搞程序性能

。下图是执行垃圾回收之后的托管堆：

GC回收之后的托管堆：

在所有垃圾对象被回收后，所有非垃圾对象重新变得紧凑，非垃圾对象指针也会全部被修复，NextObjPtr会被放到最后一个非垃圾对象之后。这时，new操作符又开始偿试创建新对象，程序请求的资源也被成功创建。

你可以看到，GC产生了一次明显的性能消耗，这是使用GC的主要缺点。然而，记住GC仅在堆被占满的情况进行回收，在回收之前，托管堆明显比C语言运行时的堆快很多。GC还提供了一些优化操作可以大大提高垃圾回收的性能。后续文章会讨论GC怎么优化垃圾回收的。

有一些很重要的点要指出来。你不再需要通过写代码去管理程序资源的寿命，文中一开始提到的两种BUG也将不再存在。首先，它不可能再产生资源泄漏，因为任何程序根节点(roots)访问不到的资源（即垃圾）都会被回收。其次，你也不再可能访问一个被释放掉的资源，因为如果资源能够被访问到，它就永远不会被释放。如果资源不能够被访问到，我们也没有理由去访问它。

下面代码展示了资源是怎么样被分配与管理的：

class Application {
    public static int Main(String[] args) {

      //在堆中创建ArrayList对象，myArray现在作为程序根节点
      ArrayList myArray = new ArrayList();

      // 在堆中创建10000个对象
      for (int x = 0; x < 10000; x++) {
         myArray.Add(new Object());    
      }

      // 现在，myArray是一个根（在线程栈里）。
      // 因此，myArray和10000个对象都是可达的
      
      Console.WriteLine(myArray.Length);

      // 在代码中myArray最后一个引用（Console.WriteLine(myArray.Length)）之后, myArray 不再是一个根
      // 不必非要等到此方法返回后，JIT编译器会知道在myArray最后一个引用之后把它标识为非根节点
      

      // 因为myArray不再是根节点，所有10001个对象不再可达
      // 它们会被看作是垃圾
      // 但是它们会一直存在直到GC对它们进行回收
   }
}

如果GC这么出色，为什么C++不使用它呢？原因是GC必须能够识别程序根节点(roots),并且必须能够找到所有对象指针。C++里允许指针进行类型转换，所以不可能确定一个指针指向的是什么。在一般语言运行时CLR中，托管堆总是能够确定对象的确切类型，并可通过元数据metadata信息决定一个对象的成员指向哪些其它对象。